Üç cache sunucunuz var. Bir anahtarın hangi sunucuda olduğunu şöyle buluyorsunuz:
server = hash(key) % 3
Basit, hızlı ve dengeli.
Trafik artıyor ve dördüncü bir sunucu ekliyorsunuz:
server = hash(key) % 4
Şimdi anahtarların büyük çoğunluğu farklı bir sunucuya düşüyor.
Cache hit oranı bir anda sıfıra yakın bir değere iniyor. Bütün istekler veritabanına gidiyor.
Kapasite eklemek, sistemi tam en yoğun anda zorlamış oluyor.
Modulo’nun problemi
hash(key) % N formülünde N değiştiğinde neredeyse her anahtarın sonucu değişir. 3’ten 4’e geçerken anahtarların yaklaşık dörtte üçü yer değiştirir.
İdeal durumda ise sadece yeni sunucuya düşmesi gereken anahtarlar taşınmalı. Dört sunucuya geçerken toplam anahtarların yaklaşık dörtte biri.
Halka
Consistent hashing, hem sunucuları hem de anahtarları aynı hash uzayına yerleştirir. Bu uzayı bir halka olarak düşünün.
Her sunucu, adının hash’i ile halkada bir noktaya konur.
Bir anahtarın sahibi, halkada saat yönünde ilerlerken karşılaşılan ilk sunucudur.
Yeni bir sunucu eklendiğinde halkada bir noktaya yerleşir. Sadece kendisi ile önceki sunucu arasındaki anahtarları devralır. Diğer bütün anahtarlar yerinde kalır.
Bir sunucu çıktığında da sadece onun anahtarları bir sonraki sunucuya geçer.
Virtual node
Basit halka modelinde bir problem var. Üç sunucu halkaya rastgele yerleştiğinde aralarındaki mesafeler eşit olmaz. Bir sunucu halkanın yüzde 50’sini, diğeri yüzde 15’ini alabilir.
Çözüm, her sunucuyu halkaya birden fazla kez yerleştirmektir:
server-a#0, server-a#1, ... server-a#149
server-b#0, server-b#1, ... server-b#149
Her fiziksel sunucu halkada yüzlerce noktaya dağılır. İstatistiksel olarak yük çok daha dengeli olur.
Virtual node’ların bir avantajı daha var: farklı kapasitedeki sunuculara farklı sayıda nokta verilebilir. İki kat güçlü bir sunucu, iki kat fazla virtual node alır.
Bir sunucu çıktığında da yükü tek bir komşuya değil, halkadaki birçok sunucuya dağıtılır.
Nerede kullanılıyor?
Bu fikir 1997’de Karger ve arkadaşlarının makalesiyle ortaya çıktı ve dağıtık sistemlerin temel yapı taşlarından biri oldu.
Amazon’un Dynamo makalesi, Cassandra’nın veri dağıtımı ve birçok memcached client’ı bu yaklaşımı kullanıyor. Load balancer’larda aynı kullanıcının isteklerini aynı backend’e yönlendirmek için de sık kullanılıyor.
Redis Cluster ise biraz farklı bir yol seçiyor. Anahtar uzayını 16384 sabit slot’a bölüyor ve slot’ları sunuculara atıyor. Sunucu eklendiğinde slot’lar taşınıyor. Fikir aynı: değişiklik olduğunda sadece verinin küçük bir kısmı hareket etmeli.
Alternatif: rendezvous hashing
Daha az bilinen ama oldukça zarif bir alternatif var. Her anahtar için her sunucuyla birlikte bir skor hesaplanır ve en yüksek skoru alan sunucu seçilir:
owner = argmax(hash(key + server))
Halka veya virtual node gerekmez. Dağılım doğal olarak dengelidir. Bedeli, her aramada bütün sunucular için hash hesaplamaktır. Sunucu sayısı az olduğunda bu ihmal edilebilir.
Consistent hashing’i çoğu zaman doğrudan implement etmeniz gerekmez. Kullandığınız client veya veritabanı bunu sizin yerinize yapar.
Ama arkasındaki fikri bilmek, “neden yeni sunucu eklediğimizde cache boşaldı?” sorusunun cevabını aramaya başlamadan bilmenizi sağlar.
