Consistent Hashing

Tutarlı Hashleme

Okunuşu: kınsistınt heşing

Güncellendi 3 Ekim 20262 dk okuma

Kısaca

Consistent hashing (tutarlı hashleme), anahtarları sunuculara, sunucu eklenip çıkarıldığında yalnızca küçük bir kısmı yer değiştirecek şekilde dağıtır.

Consistent hashing nedir?

Bir anahtar için sunucu seçmenin basit yolu hash(key) % number_of_servers'dır. Anahtarları eşit dağıtır, ama bir sunucu eklendiğinde ya da çıkarıldığında sonuç neredeyse her anahtar için değişir; önbellekler birden ıskalar ve verinin her yere taşınması gerekir. Web önbelleklerini dağıtmak için 1997'de bir makalede tanıtılan consistent hashing bundan kaçınır.

Hash değerleri uzayını bir halka gibi düşünün. Her sunucu halkada kendi hash'inin konumuna yerleştirilir; her anahtar da anahtarın konumundan saat yönünde ilerlerken bulunan ilk sunucuya aittir. Bir sunucu katıldığında yalnızca onunla komşusu arasındaki anahtarları devralır; biri ayrıldığında da yalnızca onun anahtarları bir sonraki sunucuya taşınır. Ortalamada her n anahtardan yaklaşık biri taşınır; burada n sunucu sayısıdır.

Yalnızca birkaç sunucuyla halka dengesiz olabilir; bu yüzden her fiziksel sunucuya genellikle sanal düğüm (virtual node) adı verilen çok sayıda konum verilir; bu da yükü daha eşit dağıtır ve daha güçlü makinelerin daha fazlasını almasını sağlar. Consistent hashing; DynamoDB ve Cassandra tarafından veriyi yerleştirmek, CDN'ler ve önbellek katmanları tarafından sunucu seçmek, aynı istemcinin aynı arka uca ulaşmaya devam etmesi gereken yük dengeleyiciler tarafından da kullanılır.

Sık yapılan bir yanlış, consistent hashing'in yükü kusursuz dengelediğini düşünmektir. Trafiği değil anahtarları dengeler: çok popüler tek bir anahtar, yani sıcak bir anahtar (hot key), sahibi olan sunucuyu yine aşırı yükleyebilir. Sistemler bu durumlar için replikasyon, sıcak anahtarları bölme ya da ek önbellekleme ekler; bazıları da rendezvous hashing gibi alternatifler kullanır.

Önemli noktalar

Consistent hashing, anahtarları bir hash halkası üzerinde sunuculara eşler.
Bir sunucu eklemek ya da çıkarmak anahtarların yalnızca yaklaşık 1/n'ini taşır.
Düz modulo hash'leme, sunucular değiştiğinde neredeyse her anahtarı taşır.
Sanal düğümler eşit bir dağılım için her sunucuya birçok konum verir.
DynamoDB, Cassandra, CDN'ler ve önbellekler onu kullanır; sıcak anahtarlar yine özen ister.

Örnek

Sanal düğümlü küçük bir hash halkası (Python)python

import bisect, hashlib

def h(value):
    return int(hashlib.md5(value.encode()).hexdigest(), 16)

class HashRing:
    def __init__(self, servers, vnodes=100):
        self.ring = sorted((h(f"{s}#{i}"), s) for s in servers for i in range(vnodes))
        self.keys = [position for position, _ in self.ring]

    def server_for(self, key):
        i = bisect.bisect(self.keys, h(key)) % len(self.ring)   # first server clockwise
        return self.ring[i][1]

ring = HashRing(["cache-a", "cache-b", "cache-c"])
print(ring.server_for("user:42"))
# Adding "cache-d" later moves only about a quarter of the keys.

Sık sorulan sorular

Neden yalnızca hash(key) modulo sunucu sayısı kullanılmıyor?

Çünkü sunucu sayısını değiştirmek neredeyse her anahtarın sonucunu değiştirir; böylece önbellekteki ya da saklanan verinin neredeyse tamamı birden yanlış sunucuda kalır. Consistent hashing taşınan miktarı küçük bir kısımla sınırlar.

Sanal düğümler (virtual nodes) nedir?

Her fiziksel sunucu için hash halkasındaki ek konumlardır. Sunucu başına çok sayıda kullanmak anahtarların dağılımını dengeler ve daha güçlü sunucuların daha büyük bir pay almasını sağlar.

Consistent hashing nerede kullanılır?

Cassandra ve DynamoDB gibi dağıtık veritabanlarında hangi düğümlerin hangi veriyi saklayacağına karar vermek için, dağıtık önbelleklerde, CDN'lerde ve bir istemciyi aynı sunucuda tutan yük dengeleyicilerde.

İlgili sayfalar

Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin