Consistent Hashing: Hash Ring, Virtual Node'lar ve C# ile Implementasyon

Sürüm notu: Bu yazıdaki kodlar C# 14 ve .NET 10 ile derlenip denenmiştir; hash fonksiyonu System.IO.Hashing 10.0.14'teki XxHash3, testler xUnit v3 4.0.2 ile koşturuldu.

Önce Tahmin Et

Bookstore'un kitap cache'i dört Redis instance'ına dağıtılmış. Hangi kitabın hangi instance'ta duracağına uygulama karar veriyor: key'in hash'ini alıp instance sayısına bölüyor, kalan instance'ın sırası. Cache'in isabet oranı %95, veritabanı rahat.

Kampanyadan bir gün önce bellek yetmeyecek gibi görünüyor ve ekip beşinci bir Redis instance'ı ekliyor. Ekledikleri anda cache'teki key'lerin yüzde kaçı "yanlış" instance'ta kalır, yani bir sonraki okumada cache miss olur: %20 mi, %50 mi, %80 mi? Ve caching yazısındaki cache stampede'i hatırlayarak söyle: o an veritabanına ne olur?

hash % N Neden Çöker?

Bir key'i N node'dan birine dağıtmanın en basit yolu hash(key) % N. Dağılım düzgün, hesap ucuz, durum tutmak gerekmiyor. Sorun N değiştiğinde ortaya çıkıyor: bir key yerinde kalması için hash % 4 ile hash % 5'in aynı sonucu vermesi gerekiyor, ve bu 20 olası kalan çiftinden yalnız 4'ünde oluyor. Yani key'lerin yalnız beşte biri yerinde kalıyor. 100.000 key ile ölçtüğümüzde:

hash % N        4 -> 5 nodes: 80.2% of keys move

Açılıştaki tahminin cevabı %80. Beşinci instance eklendiği an cache'in %80'i fiilen boşalıyor ve isabet oranı %95'ten %20'nin altına düşüyor; "Caching Stratejileri: Cache-Aside, Write-Through, Write-Behind ve Cache Stampede" yazısındaki stampede bu kez tek bir key için değil, cache'in neredeyse tamamı için aynı anda yaşanıyor. Bir önceki yazıda, "Veri Katmanını Ölçeklemek: Replication, Sharding ve SQL (Structured Query Language) mi NoSQL mi?"de, aynı %80'i shard'lar arasında taşınması gereken siparişler olarak görmüştük. Cache'te bu bir performans felaketi, veritabanında saatler süren bir veri taşıma işi.

İstediğimiz özellik şu: N node'dan N+1'e geçerken yalnız yeni node'un payına düşen key'ler, yani yaklaşık 1/(N+1)'i taşınsın, geri kalanı yerinde kalsın. Bir node çıkarıldığında da yalnız onun key'leri başka node'lara dağılsın.

Hash Ring

Consistent hashing, David Karger ve arkadaşlarının 1997 tarihli "Consistent Hashing and Random Trees" makalesinde, web cache'lerini dağıtmak için önerildi. Fikir, hem key'leri hem node'ları aynı hash uzayına yerleştirmek. Hash uzayı 0'dan 2^32'ye kadar sayılar ve uçları birleştirilmiş bir halka (ring) gibi düşünülüyor. Her node bir ya da birden fazla noktaya yerleşiyor; bir key de hash'inin düştüğü noktadan saat yönünde ilerleyip karşılaştığı ilk node'a ait oluyor.

Figürdeki pozisyonlar aşağıdaki kodun gerçek hash değerleri. book:42 131,5 derecede; saat yönünde ilk karşılaştığı nokta 174,5 derecedeki d#0, yani cache-d. Yeni bir node eklendiğinde ring'e yeni noktalar ekleniyor ve yalnız bu noktaların hemen önündeki aralıklardaki key'ler sahip değiştiriyor; ring'in geri kalanına dokunulmuyor. Bir node çıkarıldığında da onun aralıkları saat yönündeki bir sonraki node'a geçiyor.

C# ile Hash Ring

Ring'i bir SortedDictionary<uint, string> üzerinde tutuyoruz: key ring'deki pozisyon, value node'un adı. SortedDictionary'nin "şu değerden büyük ilk key" sorgusu olmadığı için ring her değiştiğinde key'lerin sıralı bir kopyasını array olarak tutup aramayı Array.BinarySearch ile yapıyoruz. Ring nadiren değişir, sık okunur; bu takas bu yüzden doğru.

public sealed class ConsistentHashRing(int virtualNodes)
{
    private readonly SortedDictionary<uint, string> _ring = [];
    private uint[] _positions = [];

    public void Add(string node)
    {
        for (int i = 0; i < virtualNodes; i++)
            _ring[Hash($"{node}#{i}")] = node;   // her node ring'de virtualNodes kez yer alır
        _positions = [.. _ring.Keys];
    }

    public void Remove(string node)
    {
        for (int i = 0; i < virtualNodes; i++)
            _ring.Remove(Hash($"{node}#{i}"));
        _positions = [.. _ring.Keys];
    }

    // key'in hash'inden saat yönünde ilerleyip karşılaşılan ilk node
    public string GetNode(string key)
    {
        if (_positions.Length == 0) throw new InvalidOperationException("The ring is empty.");
        uint h = Hash(key);
        int index = Array.BinarySearch(_positions, h);
        if (index < 0) index = ~index;                  // h'den büyük ilk pozisyon
        if (index == _positions.Length) index = 0;      // ring'in sonundan başına dön
        return _ring[_positions[index]];
    }

    public static uint Hash(string value) => (uint)XxHash3.HashToUInt64(Encoding.UTF8.GetBytes(value));
}

Array.BinarySearch, aranan değer yoksa "ilk büyük elemanın index'inin bit tümleyenini" döndürüyor; ~index o yüzden doğrudan saat yönündeki ilk pozisyonu veriyor. Ring'in sonuna gelindiyse başa dönüyoruz. Arama O(log V), V ring'deki toplam nokta sayısı. Hash fonksiyonu olarak System.IO.Hashing paketindeki XxHash3'ü kullanıyoruz: hızlı, iyi dağılımlı ve en önemlisi her process'te, her makinede aynı sonucu veriyor. Neden bunun önemli olduğu tuzaklar bölümünde.

Virtual Node'lar

Her node'u ring'e tek bir noktayla koyarsan, dört nokta ring'i dört rastgele uzunlukta yaya böler ve node'ların yükü bu yayların uzunluğu kadar dengesiz olur. Çözüm, her node'u ring'e birçok kez, farklı isimlerle (cache-a#0, cache-a#1…) yerleştirmek: virtual node. Nokta sayısı arttıkça her node'un toplam payı ortalamaya yaklaşıyor. Üç farklı virtual node sayısıyla 4'ten 5 node'a geçiş ve 4 node'daki yük dağılımı:

ring,   1 vnodes 4 -> 5 nodes: 27.9% of keys move, load on 4 nodes: max/avg 2.16, min/avg 0.29
ring,  10 vnodes 4 -> 5 nodes: 17.9% of keys move, load on 4 nodes: max/avg 1.54, min/avg 0.44
ring, 200 vnodes 4 -> 5 nodes: 21.8% of keys move, load on 4 nodes: max/avg 1.07, min/avg 0.91

Tek noktayla en yüklü node ortalamanın 2,16 katı, en az yüklü 0,29 katı key alıyor: bir Redis instance'ı diğerinin yedi katı iş yapıyor. Taşınan oran da şansa bağlı (%27,9), çünkü yeni node'un tek noktası rastgele bir yayın ortasına düşüyor. 200 virtual node ile yük ortalamanın ±%10'u içinde ve taşınan oran ideal %20'ye yakın. Bedeli bellek ve ring'i kurma süresi: 4 node × 200 nokta = 800 elemanlık bir array, ki bu ihmal edilebilir. Virtual node'un bir yan faydası da heterojen makineler: iki kat güçlü bir makineye iki kat virtual node vererek ağırlıklı dağılım yapılabiliyor.

xUnit ile Ölçmek

Consistent hashing'in vaatlerini test olarak yazmak, implementasyonu değiştiren birinin bu özellikleri fark etmeden bozmasını engelliyor:

[Fact]
public void Adding_a_fifth_node_moves_about_one_fifth_of_the_keys()
{
    ConsistentHashRing ring = RingOf("cache-a", "cache-b", "cache-c", "cache-d");
    Dictionary<string, string> before = Keys.ToDictionary(k => k, ring.GetNode);

    ring.Add("cache-e");

    string[] moved = [.. Keys.Where(k => before[k] != ring.GetNode(k))];
    double fraction = moved.Length / (double)Keys.Length;
    Assert.InRange(fraction, 0.15, 0.25);
    Assert.All(moved, k => Assert.Equal("cache-e", ring.GetNode(k)));   // taşınan her key yeni node'a gider
}

[Fact]
public void Removing_a_node_moves_only_the_keys_it_owned()
{
    ConsistentHashRing ring = RingOf("cache-a", "cache-b", "cache-c", "cache-d");
    Dictionary<string, string> before = Keys.ToDictionary(k => k, ring.GetNode);

    ring.Remove("cache-b");

    Assert.All(Keys.Where(k => before[k] != "cache-b"), k => Assert.Equal(before[k], ring.GetNode(k)));
}

Testlerin ikinci yarısı oranlardan daha önemli. İlk testteki son assertion, taşınan her key'in yeni node'a gittiğini söylüyor: mevcut dört node arasında hiçbir key yer değiştirmiyor. İkinci test de bir node çıkarıldığında yalnız onun key'lerinin hareket ettiğini doğruluyor. Bunlar consistent hashing'in tanımı. Dört testin (diğer ikisi 200 virtual node ile yükün ortalamanın %15'i içinde kaldığını ve aynı key'in node'ların ekleniş sırasından bağımsız olarak aynı node'a gittiğini kontrol ediyor) gerçek çıktısı:

=== TEST EXECUTION SUMMARY ===
   Hashing.Tests  Total: 4, Errors: 0, Failed: 0, Skipped: 0, Not Run: 0, Time: 0.130s

Nerede Kullanılır?

Distributed cache client'ları: memcached dünyasında client tarafında consistent hashing yapan Ketama algoritması yaygınlaştı. Veritabanı partitioning'i: Amazon'un 2007 tarihli Dynamo makalesi consistent hashing'i virtual node'larla birlikte kullanıyordu; Apache Cassandra aynı fikri token'larla uyguluyor ve her node'un ring'de kaç token alacağını num_tokens ayarı belirliyor. Load balancing: Envoy proxy'nin ring_hash ve maglev policy'leri, serinin load balancing yazısındaki hash-based dağıtımı instance eklenip çıkarıldığında az bozulacak şekilde yapıyor; Maglev, Google'ın kendi load balancer'ı için geliştirdiği, daha düzgün dağılımlı bir consistent hashing türevi.

Bir istisnayı bilmek gerekiyor: Redis Cluster consistent hashing kullanmıyor. Her key'i CRC16 (Cyclic Redundancy Check) ile 16.384 sabit hash slot'undan birine koyuyor ve slot'ları node'lara dağıtıyor; node eklendiğinde bazı slot'lar yeni node'a taşınıyor. Bu, bir önceki yazıdaki "shard sayısından çok daha fazla mantıksal partition" fikrinin ta kendisi ve aynı sonucu veriyor: yalnız taşınan slot'ların key'leri hareket ediyor. StackExchange.Redis cluster'a bağlandığında slot haritasını sunucudan öğreniyor; bu durumda key dağıtımını sen yapmıyorsun. Kendi consistent hashing'ini yazman gereken yer, birbirinden habersiz instance'lara (birden fazla bağımsız Redis, kendi cache node'ların, sharding yapan kendi router'ın) uygulama tarafında dağıtım yaptığın yer.

Rendezvous Hashing'e Kısa Bakış

Aynı problemin daha eski ve daha basit bir çözümü var: rendezvous hashing ya da HRW (Highest Random Weight), David Thaler ve Chinya Ravishankar'ın 1990'ların sonundaki çalışması. Ring yok: her key için her node'a bir skor hesaplanıyor ve en yüksek skoru alan node kazanıyor.

public static class RendezvousHashing
{
    // her node için hash(key + node) hesaplanır, en yüksek skoru alan node kazanır
    public static string GetNode(string key, IEnumerable<string> nodes) =>
        nodes.MaxBy(node => ConsistentHashRing.Hash($"{key}|{node}"))!;
}

rendezvous      4 -> 5 nodes: 20.0% of keys move, load on 4 nodes: max/avg 1.01, min/avg 0.99

Taşınan oran tam olarak beklenen %20 ve dağılım virtual node'suz bile neredeyse kusursuz. Yeni node bir key'i ancak kendi skoru o key'in mevcut sahibinin skorundan yüksekse alıyor; diğer node'lar arasında hiçbir şey değişmiyor. Bedeli arama maliyeti: her key için N hash hesaplanıyor, O(N). Birkaç, birkaç düzine node için bu hiç sorun değil ve kod çok daha basit; binlerce node ya da çok sık arama gerektiğinde ring'in O(log V) araması öne geçiyor.

Sık Düşülen Tuzaklar

string.GetHashCode() kullanmak. .NET'te string hash'i her process için rastgele bir seed ile hesaplanıyor. Aynı programı iki kez çalıştırdığımızda:

string.GetHashCode("book:42") in this process: -1390271829
XxHash3 of "book:42":                        1568342426
string.GetHashCode("book:42") in this process: 1265436331
XxHash3 of "book:42":                        1568342426

GetHashCode her çalıştırmada farklı, XxHash3 aynı. Ring'i GetHashCode ile kuran üç instance'lı bir uygulamada her instance aynı key'i farklı bir node'a gönderir ve cache hiç isabet etmez. Dağıtım için kullanılan hash deterministik ve platformdan bağımsız olmalı.

Virtual node sayısını sonradan değiştirmek. Virtual node sayısı da ring'in bir parçası; 100'den 200'e çıkarmak, yeni bir node eklemek gibi key'lerin bir kısmını taşır. Bütün client'ların aynı node listesini ve aynı virtual node sayısını kullandığından emin ol.

Consistent hashing'in veriyi taşıdığını sanmak. Algoritma yalnız "bu key artık nerede" sorusunu cevaplıyor. Cache'te bu yeterli, eski konumdaki kayıt zamanla expire oluyor. Veritabanında ise taşınan key'lerin verisini kopyalamak, kopyalama sırasında gelen yazmaları yönetmek ve okumaları doğru zamanda yeni node'a çevirmek ayrı bir iş.

Hot key'i çözdüğünü sanmak. Consistent hashing key'leri dengeler, trafiği değil. Bütün kampanya trafiğini alan tek bir key hâlâ tek bir node'a gider; çaresi caching yazısındaki L1 (level 1, process içi) cache ve key çoğaltma.

Client'ların farklı node listeleri görmesi. Bir instance'ın listesi güncellenip diğerinin güncellenmemesi, aynı key'in bir süre iki farklı node'da yaşaması demek; node listesi tek bir kaynaktan (configuration ya da service discovery) gelmeli.

Küçük Bir Deneme

★☆☆ Demo'da node sayısını 4 yerine 10 yap ve 10'dan 11'e geçişte hash % N ile ring'in taşıdığı oranları karşılaştır. Beklediğin oran 1/11 mi?

★★☆ ConsistentHashRing'e ağırlık desteği ekle: Add(string node, int weight) virtual node sayısını ağırlıkla çarpsın. cache-e'ye iki kat ağırlık verip yük dağılımını ölç ve bir xUnit testiyle sabitle.

★★★ Ring'e replication ekle: GetNodes(string key, int replicas) saat yönünde ilerleyip birbirinden farklı ilk replicas fiziksel node'u dönsün (aynı node'un iki virtual node'unu iki kez sayma). Bir node çıkarıldığında her key'in en az bir kopyasının yerinde kaldığını test et.

Key'leri node'lara dağıtmayı çözdük. Bir sonraki yazıda başka bir yük problemine bakıyoruz: request'in içinde yapılması gerekmeyen ağır işler. Queue, worker, fan-out, backpressure ve 202 Accepted ile fatura PDF'ini API'den (Application Programming Interface) worker'a taşıyacağız.