Tutarlı Hashleme (Consistent Hashing): Hash Halkası, Sanal Düğümler ve Yeniden Dengeleme

Bir önbelleği hash(key) % 10 ile on sunucuya dağıtıyorsunuz. Trafik artıyor, on birinci bir sunucu ekliyorsunuz ve isabet oranı çöküyor: Neredeyse her anahtar artık farklı bir sunucuya düşüyor; önbellek her yerde aynı anda soğuyor ve arkasındaki veritabanı yükün tamamını alıyor. Tutarlı hashleme (consistent hashing) tam olarak bunu önlemek için var.

Bu yazı hash halkasını ve sanal düğümleri bir diyagramla açıklıyor, ne kadar fayda sağladıklarını ölçüyor, kompakt bir uygulama gösteriyor ve gerçek sistemlerde karşılaşacağınız alternatifleri karşılaştırıyor: rendezvous hashleme, jump hash, Maglev ve sabit hash slot'ları.

Modulo hashleme neden bozulur

server = hash(key) % N ile eşleme N'ye bağlıdır. N'yi değiştirdiğinizde bir anahtar ancak hash'i her iki değer için aynı kalanı veriyorsa yerinde kalır; bu da nadirdir. Bir milyon anahtarla yapılan hızlı bir simülasyonda:

İdeal değer 1/11, yani yaklaşık %9,1'dir: Yeni sunucu adil payını almalı, başka hiçbir şey taşınmamalıdır. Halka buna yaklaşır; kalan fark, yeni sunucunun token'larının ortalamadan biraz daha büyük yaylara denk gelmesinden kaynaklanır.

Bir önbellek için fark, isabet oranında kısa bir düşüş ile soğuk başlangıç arasındadır. Shard'lanmış bir veritabanı ya da durum tutan bir grup worker için ise verinin onda birini taşımak ile neredeyse tamamını taşımak arasındaki farktır.

Hash halkası

Karger ve meslektaşlarının 1997'de web önbellekleme için ortaya koyduğu tutarlı hashleme, hem sunucuları hem anahtarları aynı dairesel hash uzayına eşler; örneğin 0'dan 2^64 - 1'e kadar olan tam sayılar, en büyük değer 0'a sarılacak şekilde.

1. Her sunucunun adını halkada bir konuma hash'leyin.
2. Her anahtarı halkada bir konuma hash'leyin.
3. Anahtarın konumundan saat yönünde ilerleyin. Karşılaştığınız ilk sunucu anahtarın sahibidir.

Bir sunucu eklemek onu tek bir konuma yerleştirir ve sunucu yalnızca kendisi ile öncülü arasındaki anahtarları devralır. Diğer her anahtar olduğu yerde kalır. Bir sunucuyu çıkarmak, anahtarlarını saat yönündeki bir sonraki sunucuya devreder. Başka hiçbir şey değişmez.

Sanal düğümler: dengesizliği düzeltmek

Sunucu başına tek konumla sunucular arasındaki yaylar rastgele ve eşitsizdir; bu yüzden bazı sunucular halkanın diğerlerinden çok daha büyük bir kısmına sahip olur. On sunuculu aynı simülasyon bunun ne kadar olduğunu gösteriyor:

Çözüm, her sunucuya cache-a#0, cache-a#1 gibi adları hash'leyerek sanal düğüm ya da token denen çok sayıda konum vermektir. Sanal düğümler iki fayda daha getirir:

• Ağırlıklar. İki kat belleğe sahip bir sunucu iki kat token alır.
• Daha yumuşak arızalar. Bir sunucu öldüğünde çok sayıdaki küçük yayı birçok farklı ardıla gider; böylece yükü, tek bir komşunun yükünü ikiye katlamak yerine kümeye yayılır.

Bedeli, daha büyük bir arama tablosu ve üyelik değiştiğinde taşınacak daha fazla meta veridir. Cassandra bu ödünleşimi pratikte gösterir: 4.0 sürümü varsayılanı 16'ya indirene kadar düğüm başına varsayılan olarak 256 token kullanıyordu; yeni varsayılan, bu 16 token'ı rastgele değil eşit yerleştiren bir token tahsis algoritmasıyla birlikte gelir.

Küçük bir uygulama

Bir halka, sıralı bir token konumları listesi ve bir ikili aramadan ibarettir:

import bisect
import hashlib

def hash64(value: str) -> int:
    # MD5 for spread, not security; any well-mixed hash works
    return int.from_bytes(hashlib.md5(value.encode()).digest()[:8], "big")

class HashRing:
    def __init__(self, servers, vnodes=100):
        self.vnodes = vnodes
        self.points = []   # sorted token positions
        self.owners = {}   # position -> server
        for server in servers:
            self.add(server)

    def add(self, server):
        for i in range(self.vnodes):
            p = hash64(f"{server}#{i}")
            bisect.insort(self.points, p)
            self.owners[p] = server

    def remove(self, server):
        for i in range(self.vnodes):
            p = hash64(f"{server}#{i}")
            self.points.remove(p)
            del self.owners[p]

    def lookup(self, key: str) -> str:
        i = bisect.bisect_right(self.points, hash64(key)) % len(self.points)
        return self.owners[self.points[i]]

Aramalar T token için O(log T) maliyetindedir. Üretim sürümleri ayrıca token çakışmalarını ele alır ve her istemcinin üyelik görünümünü aynı tutar, çünkü farklı sunucu listelerine sahip iki istemci anahtarların nerede durduğu konusunda anlaşamaz.

Halka üzerinde replikasyon

Depolama sistemleri halkayı yönlendirmenin yanı sıra yerleşim için de kullanır. Amazon'un Dynamo makalesi, her anahtarı konumundan saat yönündeki ilk N farklı sunucuda, yani tercih listesinde (preference list) saklar ve listede zaten bulunan bir sunucuya ait ek token'ları atlar. N = 3 ile bir sunucuyu kaybetmek, tuttuğu her şeyin iki kopyasını, halkadaki komşuları olan sunucularda hâlâ bırakır.

Aynı “saat yönünde ilerle ve tekrarları atla” fikri raflara ve bölgelere de genişler: Replikalar farklı arıza alanlarına yayılana kadar token'ları atlayın.

Karşılaşacağınız alternatifler

Jump consistent hash, shard'ların numaralandığı ve yalnızca büyüdüğü shard'lanmış depolamaya uyar. Rendezvous hashleme, arama başına O(N)'nin önemli olmadığı küçük sunucu kümelerine uyar. Hash slot'ları, otomatik yerleşimi açık ve operatör kontrolündeki taşımalarla takas eder; birçok ekip veritabanları için bunu tercih eder.

Sıcak anahtarlar ve sınırlı yükler

Tutarlı hashleme trafiği değil anahtarları dengeler. Ünlü bir kullanıcı ya da viral bir ürün yine tek bir sunucuya düşer. Sınırlı yüklü tutarlı hashleme (consistent hashing with bounded loads), her sunucuyu ortalamanın belirli bir yüzde üzerinde sınırlar ve taşanı saat yönündeki bir sonraki sunucuya gönderir. HAProxy bunu hash-balance-factor ayarıyla uygular. Gerçekten sıcak anahtarlar için yine de o anahtarın replikasyonuna, istek birleştirmeye (request coalescing) ya da önde küçük bir yerel önbelleğe ihtiyacınız vardır.

Operasyonel tuzaklar

• Hash fonksiyonunu ya da token şemasını değiştirmek, tıpkı modulo hashleme gibi her şeyi karıştırır. Bunu bir migrasyon olarak ele alın.
• Üyelik tutarlı olmalıdır. Sunucu listesini bir koordinasyon servisi ya da yük dengeleyicinin yapılandırması gibi tek bir kaynaktan dağıtın ve tek adımda değiştirin.
• Gidip gelen sunucular çalkalanmaya yol açar. Birkaç dakikada bir sağlık kontrolünden kalan bir sunucu anahtarlarını ileri geri taşır. Onu çıkarıp yeniden eklemeden önce histerezis ekleyin.
• Yeni sunucular soğuk başlar. Yeni bir önbellek düğümü payına düşen istekleri hemen alır; arka uç ıskalamaları kaldıramıyorsa onu ısıtın ya da ağırlığını kademeli artırın.

Hash halkası diyagramı

Nasıl okunur:

• Daire hash uzayıdır. Konumlar saat yönünde artar; en üst, en büyük değerin sıfıra sarıldığı yerdir.
• Renkli token'lar sanal düğümlerdir. Her renk bir sunucudur ve her sunucu halkaya yayılmış birkaç token'a sahiptir.
• Anahtarlar hash konumlarında durur ve oklar saat yönünde onlara sahip olan token'ı gösterir.
• Kesikli token'lar, eklenmekte olan D sunucusuna aittir. Yalnızca D'nin token'larının hemen saat yönü tersindeki anahtarların sahibi değişir.
• Lejant ve Markdown bloğu sunucuları ve yukarıdaki simülasyondan taşıma rakamlarını listeler.

Hashleme şemalarını net çizmek

• Tablo değil halka çizin. Saat yönü kuralı görseldir; bir arama tablosu neden yalnızca bazı anahtarların taşındığını gizler.
• Token'ları sunucuya göre renklendirin ve her token'dan sunucusuna bir kenar çizmek yerine bir lejant ekleyin.
• Bir üyelik değişikliği gösterin. Statik bir halka yönlendirmeyi açıklar; bir sunucunun katıldığı halka ise tekniğin tüm amacını açıklar.
• Yanına gerçek rakamlar koyun: taşınan anahtarlar ve yük dağılımı. İnsanları resimden daha çok bunlar ikna eder.

Tutarlı hashleme bu blogdaki sistem tasarımı yazılarının pek çoğunda karşınıza çıkar: veriyi yerleştirmek için veritabanı sharding diyagramında, yapışkan yönlendirme için yük dengeleyici diyagramında ve dağıtık önbellekler için önbellekleme stratejileri diyagramında.

Archboard'da oluşturun

1. Google ya da GitHub ile giriş yapın ve bir diyagram oluşturun.
2. Halka olarak Temel paketinden büyük bir Elips şekli ekleyin.
3. Halkanın üzerine token olarak, sunucuya göre renklendirilmiş küçük Elips şekilleri ekleyin: A, B ve C sunucularının her biri için iki tane ve yeni sunucu D için iki kesikli tane.
4. Lejant olarak halkanın yanına, bir sütun hâlinde ve token'larıyla aynı renkte, Veri paketinden dört Redis düğümü ekleyin.
5. Anahtarları halkanın üzerine Temel paketinden Metin etiketleri olarak ekleyin ve sahibi olan token'lara kısa oklar çizin.
6. Temel paketinden anahtar taşıma ve yük rakamlarını içeren bir Markdown bloğu ekleyin.

Örnek 14 diyagram düğümü kullanıyor ve Free planın sınırları içinde kalıyor.

SSS

Tutarlı hashleme hangi sorunu çözer? Sunucular eklendiğinde ya da çıkarıldığında anahtarların çoğunu aynı sunucuda tutar. Modulo hashlemede sunucu sayısını değiştirmek neredeyse her anahtarı yeniden eşler; tutarlı hashlemede anahtarların yalnızca yaklaşık 1/N kadarı taşınır.

Tutarlı hashlemede sanal düğümler nedir? Her fiziksel sunucu halkaya farklı adlar altında birçok kez yerleştirilir. Daha fazla konum yayları daha eşit yapar, sunucuları kapasiteye göre ağırlıklandırmayı sağlar ve arızalanan bir sunucunun yükünü birçok başka sunucuya yayar.

Her sunucunun kaç sanal düğümü olmalı? Küme boyutunuzda eşit bir dağılım için yeterli sayıda: Simülasyonumuzda sunucu başına 100 sanal düğüm, on sunucuda en yoğun sunucuyu ortalamanın %7'si içinde tuttu. Cassandra 4.0 ve sonrası gibi daha akıllı token tahsisine sahip sistemler çok daha azını kullanır.

Redis Cluster tutarlı hashleme mi? Halka anlamında değil. Redis Cluster anahtarları 16.384 sabit hash slot'una eşler ve slot'ları düğümlere atar; veriyi taşımak, slot'ları açıkça taşımak demektir.

Tutarlı hashleme ile rendezvous hashleme arasındaki fark nedir? İkisi de üyelik değiştiğinde anahtarların yaklaşık 1/N kadarını taşır. Rendezvous hashleme her anahtar için her sunucuyu puanlar ve en yükseğini seçer; halka gerektirmez ama arama başına O(N) maliyeti vardır.

Ücretsiz başlayın — tek kullanıcı, kredi kartı gerekmez.