Dağıtık Sistemler & Ölçeklenebilirlik 9 dk okuma 3 okunma

Consistent Hashing ile Yük Dağılımı

Consistent Hashing (Tutarlı Karma), dağıtık sistemlerde veri ve yükün düğümler arasında dengeli dağıtılmasını sağlayan, düğüm ekleme/çıkarma durumunda minimum veri taşıma (rebalancing) gerektiren bir algoritmadır. Bu yazıda, klasik modulo hash'in sorunları, hash ring (karma halkası) yapısı, sanal düğümler (virtual nodes), veri taşıma maliyeti, .NET'te uygulama ve gerçek dünya kullanım senaryoları ele alınır.

Consistent Hashing ile Yük Dağılımı

Consistent Hashing ile Yük Dağılımı

Dağıtık sistemlerde, verilerin ve yükün birden fazla düğüm (sunucu, cache, shard) arasında nasıl dağıtılacağı en kritik kararlardan biridir. Klasik yaklaşım olan modulo hash (hash(key) % N), düğüm sayısı değiştiğinde neredeyse tüm verilerin yeniden dağıtılmasını gerektirir. İşte Consistent Hashing (Tutarlı Karma), bu sorunu çözmek için tasarlanmış, düğüm ekleme veya çıkarma durumunda yalnızca küçük bir veri kümesinin taşınmasını sağlayan bir algoritmadır. Bu yazıda, Consistent Hashing'in çalışma prensibini, sanal düğümleri, .NET'te uygulamasını ve gerçek dünya kullanım senaryolarını detaylıca ele alacağız.

1. Klasik Modulo Hash'in Sorunu

Geleneksel yük dağıtımında, bir anahtarın hangi düğüme gideceği şu formülle belirlenir:

text

node_index = hash(key) % N

Burada N, toplam düğüm sayısıdır. Bu yaklaşım basit ve etkilidir, ancak düğüm sayısı değiştiğinde ciddi bir sorun ortaya çıkar.

Örnek: 4 Düğümden 5 Düğüme Geçiş

text

4 düğüm:  node_index = hash(key) % 4
5 düğüm:  node_index = hash(key) % 5

Bir anahtarın hash(key) değeri 100 olsun:

  • 4 düğümde: 100 % 4 = 0 → Düğüm 0

  • 5 düğümde: 100 % 5 = 0 → Düğüm 0 (şanslı)

Başka bir anahtarın hash değeri 101 olsun:

  • 4 düğümde: 101 % 4 = 1 → Düğüm 1

  • 5 düğümde: 101 % 5 = 1 → Düğüm 1 (şanslı)

Ancak hash değeri 102 olan anahtar:

  • 4 düğümde: 102 % 4 = 2 → Düğüm 2

  • 5 düğümde: 102 % 5 = 2 → Düğüm 2

Aslında istatistiksel olarak, düğüm sayısı N'den N+1'e çıktığında, anahtarların yaklaşık N/(N+1) oranı yeni düğüme taşınır. 4'ten 5'e geçişte bu oran %80'dir. Yani neredeyse tüm veriler yeniden dağıtılır.

Sonuç: Cache invalidation, veritabanı sharding veya yük dengeleme sistemlerinde bu, ciddi performans kaybına ve kesintiye yol açar.

2. Consistent Hashing: Hash Ring (Karma Halkası)

Consistent Hashing, tüm hash uzayını (ör. 0 ile 2^32-1 arası) bir halka (ring) olarak düşünür. Hem düğümler hem de anahtarlar bu halka üzerinde konumlandırılır.

Temel Akış:

  1. Düğümleri Halkaya Yerleştir: Her düğümün adı (veya IP'si) hash'lenir ve halka üzerinde bir konuma yerleştirilir. Örneğin:

    text

    hash("Node-A") = 100  → Halkada 100. konum
hash("Node-B") = 500  → Halkada 500. konum
hash("Node-C") = 900  → Halkada 900. konum

  2. Anahtarları Halkaya Yerleştir: Her anahtar da hash'lenir ve halka üzerinde bir konuma yerleştirilir.

  3. Anahtarı Düğüme Ata: Bir anahtar için, halkada saat yönünde ilerleyerek karşılaşılan ilk düğüm, o anahtarın sorumlusudur.

Örnek:

text

Halka: 0 ------------------------------------------- 2^32
        [Node-A:100]      [Node-B:500]      [Node-C:900]

Anahtar "user:123" → hash = 300
Saat yönünde ilk düğüm: Node-B (500)
Sonuç: "user:123" → Node-B

Anahtar "user:456" → hash = 700
Saat yönünde ilk düğüm: Node-C (900)
Sonuç: "user:456" → Node-C

Anahtar "user:789" → hash = 50
Saat yönünde ilk düğüm: Node-A (100)
Sonuç: "user:789" → Node-A

3. Consistent Hashing'in Sihri: Minimum Veri Taşıma

Consistent Hashing'in en büyük avantajı, bir düğüm eklendiğinde veya çıkarıldığında yalnızca o düğüme komşu olan anahtarların etkilenmesidir.

Yeni Düğüm Ekleme (Node-D):

text

Halka: 0 ------------------------------------------- 2^32
        [Node-A:100]   [Node-D:350]   [Node-B:500]   [Node-C:900]

Node-D, 350 konumuna yerleştirildiğinde:

  • Eskiden Node-B'ye (500) giden anahtarlar arasında, hash değeri 350'den küçük ve 100'den büyük olanlar (yani 100-350 arası) artık Node-D'ye gider.

  • Diğer tüm anahtarlar etkilenmez.

Veri Taşıma Oranı: Yalnızca 1/N oranında veri taşınır (N düğüm sayısı). 4 düğümden 5'e geçişte bu oran %20'dir (klasik modulo hash'te %80'di).

Düğüm Çıkarma (Node-B Çökerse):

Node-B çöktüğünde, ona ait tüm anahtarlar saat yönündeki bir sonraki düğüme (Node-C) aktarılır. Diğer düğümler etkilenmez.

4. Sanal Düğümler (Virtual Nodes - VNodes)

Temel Consistent Hashing'in bir sorunu vardır: Düğümler halka üzerinde eşit dağılmazsa, yük dengesiz olur. Örneğin, Node-A ile Node-B arasındaki mesafe çok küçükse, Node-B aşırı yüklenir.

Çözüm: Sanal Düğümler

Her fiziksel düğüm, halka üzerinde birden fazla sanal düğüm (replica) ile temsil edilir. Örneğin, Node-A şu sanal düğümlere sahip olabilir:

text

hash("Node-A#1") = 100
hash("Node-A#2") = 450
hash("Node-A#3") = 800
hash("Node-A#4") = 1200

Sanal Düğümlerin Avantajları:

  • Daha Dengeli Dağılım: Sanal düğümler sayesinde her fiziksel düğüm halka üzerinde daha eşit dağılır.

  • Daha İyi Yük Dengesi: Bir düğüm çöktüğünde, yükü birden fazla düğüme dağılır (tek bir düğüme yüklenmez).

  • Heterojen Düğümler: Daha güçlü düğümlere daha fazla sanal düğüm atanarak kapasiteleri oranında yük almaları sağlanır.

Tipik Sanal Düğüm Sayısı: 100-200 arası. Örneğin, Cassandra varsayılan olarak 256 sanal düğüm kullanır.

Örnek (VNode'lu Halka):

text

Halka: [A#1:100] [B#1:150] [C#1:200] [A#2:300] [B#2:350] [C#2:400] [A#3:500] ...

Bu sayede, anahtarlar fiziksel düğümler arasında çok daha dengeli dağılır.

5. .NET'te Consistent Hashing Uygulaması

A. Basit Consistent Hash Ring (Sanal Düğümsüz)

csharp

public class ConsistentHashRing<T>
{
    private readonly SortedDictionary<uint, T> _ring = new();
    private readonly Func<T, uint> _hashFunction;

    public ConsistentHashRing(Func<T, uint> hashFunction)
    {
        _hashFunction = hashFunction;
    }

    public void AddNode(T node)
    {
        var hash = _hashFunction(node);
        _ring[hash] = node;
    }

    public void RemoveNode(T node)
    {
        var hash = _hashFunction(node);
        _ring.Remove(hash);
    }

    public T GetNode(string key)
    {
        if (_ring.Count == 0)
            throw new InvalidOperationException("Halkada düğüm yok.");

        var hash = ComputeHash(key);

        // Saat yönünde ilk düğümü bul
        foreach (var entry in _ring)
        {
            if (entry.Key >= hash)
                return entry.Value;
        }

        // Halkanın sonuna geldiyse, başa dön
        return _ring.First().Value;
    }

    private uint ComputeHash(string key)
    {
        using var sha1 = SHA1.Create();
        var bytes = sha1.ComputeHash(Encoding.UTF8.GetBytes(key));
        return BitConverter.ToUInt32(bytes, 0);
    }
}

B. Sanal Düğümlü Consistent Hash Ring (Önerilen)

csharp

public class ConsistentHashRing<T>
{
    private readonly SortedDictionary<uint, T> _ring = new();
    private readonly int _virtualNodeCount;
    private readonly Func<string, uint> _hashFunction;

    public ConsistentHashRing(int virtualNodeCount = 150, 
        Func<string, uint>? hashFunction = null)
    {
        _virtualNodeCount = virtualNodeCount;
        _hashFunction = hashFunction ?? DefaultHash;
    }

    public void AddNode(T node)
    {
        for (int i = 0; i < _virtualNodeCount; i++)
        {
            var vnodeKey = $"{node}#VN{i}";
            var hash = _hashFunction(vnodeKey);
            _ring[hash] = node;
        }
    }

    public void RemoveNode(T node)
    {
        for (int i = 0; i < _virtualNodeCount; i++)
        {
            var vnodeKey = $"{node}#VN{i}";
            var hash = _hashFunction(vnodeKey);
            _ring.Remove(hash);
        }
    }

    public T GetNode(string key)
    {
        if (_ring.Count == 0)
            throw new InvalidOperationException("Halkada düğüm yok.");

        var hash = _hashFunction(key);

        // Saat yönünde ilk düğümü bul
        foreach (var entry in _ring)
        {
            if (entry.Key >= hash)
                return entry.Value;
        }

        return _ring.First().Value;
    }

    private static uint DefaultHash(string key)
    {
        using var sha1 = SHA1.Create();
        var bytes = sha1.ComputeHash(Encoding.UTF8.GetBytes(key));
        return BitConverter.ToUInt32(bytes, 0);
    }
}

Kullanım:

csharp

var ring = new ConsistentHashRing<string>(virtualNodeCount: 150);
ring.AddNode("cache-server-1");
ring.AddNode("cache-server-2");
ring.AddNode("cache-server-3");

var node = ring.GetNode("user:12345");
Console.WriteLine($"user:12345 → {node}");

// Yeni düğüm ekle
ring.AddNode("cache-server-4");
// Yalnızca ~1/4 veri taşınır

C. Üçüncü Parti Kütüphaneler

  • ServiceStack.Redis: Consistent hashing destekli Redis cluster istemcisi.

  • StackExchange.Redis: Redis Cluster için kendi hash slot mekanizmasını kullanır (16384 slot).

  • CassandraCSharpDriver: Cassandra'nın token-aware routing'i için consistent hashing kullanır.

6. Gerçek Dünya Kullanım Senaryoları

Consistent Hashing, birçok dağıtık sistemde kritik bir rol oynar:

Sistem Kullanım Amacı
Amazon DynamoDB Veri sharding ve partition dağılımı
Apache Cassandra Veri merkezleri arası veri dağıtımı (token ring)
Redis Cluster 16384 hash slot ile anahtar dağılımı
Memcached Clients Çoklu cache sunucusu arasında anahtar dağılımı
Akamai CDN İçerik isteklerinin edge sunuculara dağıtımı
Discord Kullanıcı-sunucu eşleştirmesi
Kubernetes Ingress Consistent hashing ile session affinity
NGINX hash $request_uri consistent ile yük dengeleme

Örnek: Dağıtık Cache Sistemi

csharp

public class DistributedCache
{
    private readonly ConsistentHashRing<string> _ring;
    private readonly Dictionary<string, IMemoryCache> _caches;

    public DistributedCache(IEnumerable<string> cacheServers)
    {
        _ring = new ConsistentHashRing<string>(virtualNodeCount: 150);
        _caches = new Dictionary<string, IMemoryCache>();

        foreach (var server in cacheServers)
        {
            _ring.AddNode(server);
            _caches[server] = new MemoryCache(new MemoryCacheOptions());
        }
    }

    public void Set(string key, object value, TimeSpan ttl)
    {
        var server = _ring.GetNode(key);
        _caches[server].Set(key, value, ttl);
    }

    public object? Get(string key)
    {
        var server = _ring.GetNode(key);
        return _caches[server].Get(key);
    }
}

Bu yapılandırmada, bir cache sunucusu eklendiğinde veya çıkarıldığında, yalnızca o sunucuya ait anahtarlar taşınır; diğer anahtarlar etkilenmez.

7. Fencing ve Rebalancing Stratejileri

A. Rebalancing (Yeniden Dengeleme)

Consistent Hashing, minimum veri taşıma sağlasa da, yeni düğüm eklendiğinde bazı anahtarların taşınması gerekir. Bu taşıma işlemine rebalancing denir.

Rebalancing Stratejileri:

  • Lazy Rebalancing: Taşıma işlemi arka planda, düşük öncelikli olarak yapılır. Kullanıcı istekleri etkilenmez.

  • Active Rebalancing: Taşıma işlemi hemen yapılır; ancak geçici performans düşüşü olabilir.

  • Consistent Hashing with Bounded Loads: Google tarafından önerilen bu yaklaşım, her düğümün kapasitesini sınırlar ve aşırı yüklenmeyi önler.

B. Fencing (Çit) Token

Distributed locking'de olduğu gibi, Consistent Hashing'de de eski düğümlerin hala veri tutması sorun olabilir. Bunu önlemek için fencing token veya epoch numarası kullanılır.

8. En İyi Pratikler

Pratik Açıklama
Sanal Düğüm Sayısını İyi Ayarlayın 100-200 arası iyi bir dengedir. Çok az → dengesiz; çok fazla → bellek yükü.
İyi Bir Hash Fonksiyonu Seçin SHA-1 veya MD5 gibi kriptografik hash'ler kullanın; dağılım daha dengeli olur.
Heterojen Düğümleri Destekleyin Daha güçlü düğümlere daha fazla sanal düğüm atayın.
Rebalancing'i Otomatikleştirin Düğüm ekleme/çıkarma sırasında veri taşıma işlemini otomatik yönetin.
Monitoring Kurun Anahtarların düğümlere dağılımını izleyin; dengesizlik varsa sanal düğüm sayısını artırın.
Fencing Token Kullanın Eski düğümlerin hala veri tutması durumunda, monotonic token ile çakışmayı önleyin.
Hot Key'leri İzleyin Bazı anahtarlar çok sık erişiliyorsa, bu anahtarlar için ayrı bir strateji (replication) geliştirin.

9. Consistent Hashing'in Sınırları

Sınır Açıklama Çözüm
Hot Key Sorunu Bazı anahtarlar çok sık erişiliyorsa, o düğüm aşırı yüklenir. Hot key'leri kopyalayın (replication) veya bölün.
Sanal Düğüm Bellek Maliyeti Çok fazla sanal düğüm, bellek tüketimini artırır. Sanal düğüm sayısını iyi ayarlayın.
Halka Yönetimi Düğüm ekleme/çıkarma sırasında halka senkronize edilmeli. Merkezi bir koordinasyon servisi (ZooKeeper, Consul) kullanın.
Range Query Zorluğu Aralık sorguları (range query) etkin değildir. Aralık sorguları için B-Tree tabanlı sistemler kullanın.

10. Gerçek Dünya Senaryosu

Senaryo: Bir e-ticaret uygulamasında, 5 cache sunucusu (Redis) kullanılıyor ve milyonlarca ürün anahtarı bu sunuculara dağıtılıyor.

Problem: Cache sunucularından biri arızalandığında, tüm anahtarların yeniden dağıtılması gerekiyor ve cache %80 oranında ıskalıyor (cache miss).

Çözüm: Consistent Hashing ile sanal düğümler.

csharp

var cacheServers = new[] { "redis-1", "redis-2", "redis-3", "redis-4", "redis-5" };
var ring = new ConsistentHashRing<string>(virtualNodeCount: 150);

foreach (var server in cacheServers)
    ring.AddNode(server);

// 1 milyon anahtar dağıt
var distribution = new Dictionary<string, int>();
for (int i = 0; i < 1_000_000; i++)
{
    var key = $"product:{i}";
    var server = ring.GetNode(key);
    distribution[server] = distribution.GetValueOrDefault(server) + 1;
}

// Dağılımı kontrol et
foreach (var (server, count) in distribution)
{
    Console.WriteLine($"{server}: {count} anahtar ({count / 1_000_000.0:P2})");
}
// Sonuç: Her sunucu yaklaşık %20 (200.000) anahtar tutar.

Redis-3 arızalandığında:

  • Yalnızca Redis-3'e ait olan ~%20 anahtar Redis-4 ve Redis-5 arasında paylaşılır.

  • Diğer sunucular (Redis-1, Redis-2) hiç etkilenmez.

  • Cache miss oranı yalnızca ~%20'dir (klasik modulo hash'te ~%80).

Sonuç

Consistent Hashing, dağıtık sistemlerde veri ve yük dağılımının temel taşlarından biridir. Modulo hash'in düğüm değişikliklerindeki yetersizliğini çözer; düğüm ekleme/çıkarma durumunda yalnızca 1/N oranında veri taşınmasını sağlar. Sanal düğümler, yükün daha dengeli dağılmasını ve heterojen düğümlerin desteklenmesini mümkün kılar. DynamoDB, Cassandra, Redis Cluster, CDN'ler ve yük dengeleyiciler gibi birçok sistem, Consistent Hashing'i temel algoritma olarak kullanır. .NET ekosisteminde, SortedDictionary tabanlı basit bir uygulama ile bu algoritmayı kolayca hayata geçirebilirsiniz. Unutmayın: İyi bir Consistent Hashing uygulaması, sisteminizin ölçeklenebilirliğini ve dayanıklılığını doğrudan etkiler; düğüm ekleme/çıkarma sırasında sisteminizin çökmesini engeller.

Tüm yazılar Soru ya da yorumun mu var? Yaz