IAli
Tüm Yazılar
Tutarlı Karma (Consistent Hashing) Yüzüğü ve Sanal Düğümler Analizi

Tutarlı Karma (Consistent Hashing) Yüzüğü ve Sanal Düğümler Analizi

Dağıtık sistemlerde tutarlı karma (consistent hashing) halkası, sanal düğümler (vnodes), düğüm değişiminde K/N veri taşınması ve yük dağılımı.

Dağıtık önbellek sistemlerinde (Memcached, Redis) ve anahtar-değer depolarında (Amazon DynamoDB, Apache Cassandra) verileri N adet sunucuya dağıtmanın en ilkel yolu modülo aritmetiğidir: hash(anahtar) % N. Ancak kümedeki sunucu sayısı değiştiğinde (yeni bir düğüm eklendiğinde veya bir düğüm arızalandığında) N değeri değişir. Bu formül mevcut tüm anahtarların yaklaşık %90'ından fazlasının farklı bir sunucuya taşınmasına sebep olur. Önbellekler tamamen boşalır, arka plan veritabanları çığ etkisiyle (cache stampede) kilitlenir. Karger ve ekibinin 1997 yılında geliştirdiği Tutarlı Karma (Consistent Hashing) algoritması, veri taşınma oranını yalnızca k/N seviyesine indirerek bu krizi çözer.

Kapsam Notu: Bu rehber MIT Karger algoritması, Amazon Dynamo mimarisi ve Cassandra sanal düğüm (vnode) tasarımı temel alınarak hazırlanmıştır.

Tutarlı Karma Halkası (Hash Ring) Modeli

Tutarlı karma mantığında hem veriler hem de veriyi saklayacak sunucular aynı matematiksel aralıkta bir dairesel halka (hash ring) üzerine yerleştirilir.

Aralık genellikle $[0, 2^{32} - 1]$ (örneğin 32-bit MurmurHash) olarak belirlenir:

TEXT
                       Düğüm A (0x20000000)
                             /      \
                            /        \
                           /          \
    Düğüm C (0xC0000000)  |  HALKA   |  Düğüm B (0x70000000)
                           \          /
                            \        /
                             \      /
                             (2^32 - 1)
  1. Düğümlerin Konumu: Her fiziksel sunucu IP adresi veya ana bilgisayar adı karma fonksiyonundan geçirilerek halka üzerinde bir açıya yerleştirilir.
  2. Anahtarların Konumu: Saklanacak veri anahtarı da aynı fonksiyonla hash edilir ve halka üzerinde bir noktaya denk gelir.
  3. Eşleştirme Kuralı: Bir anahtarın hangi sunucuda saklanacağını bulmak için o anahtarın noktasından başlanarak halka üzerinde saat yönünde (clockwise) ilerlenir. Karşılaşılan ilk sunucu o anahtarın sahibidir.

Düğüm Ekleme ve Çıkarma Dinamiği

Halkaya yeni bir sunucu (Düğüm D) eklendiğinde klasik modülo algoritmasının aksine tüm sistem sarsılmaz:

  • Yalnızca Düğüm D'nin saat yönündeki komşusundan devraldığı yay parçasındaki anahtarlar yeni sunucuya taşınır.
  • Halkanın geri kalanındaki tüm anahtarlar eski sunucularında kalmaya devam eder.
  • Taşınan veri miktarı teorik olarak $K / N$ seviyesindedir ($K$: toplam anahtar sayısı, $N$: yeni sunucu sayısı).
TEXT
Düğüm D Eklendiğinde:
[Düğüm C] ------------ (Yeni Düğüm D) ------------> [Düğüm A]
                ^
                | Sadece bu aralıktaki anahtarlar C'den D'ye taşınır.

Benzer şekilde bir sunucu çöktüğünde yalnızca o sunucunun sorumlu olduğu aralık bir sonraki saat yönü komşusuna devredilir.

Dengesiz Dağılım ve Sanal Düğümler (Virtual Nodes - Vnodes)

Saf tutarlı karma halkasında fiziksel düğüm sayısı az olduğunda (örneğin 3 veya 5 sunucu) rastgele karma fonksiyonu noktaları homojen dağıtmayabilir. Bir sunucu halkanın %70'ini kapsarken diğer ikisi %15'er pay alabilir. Bu durum sıcak nokta (hotspot) yaratır.

Amazon Dynamo ve Apache Cassandra bu adaletsizliği Sanal Düğümler (vnodes) ile çözer:

TEXT
Fiziksel Sunucu 1 -> [Vnode 1A, Vnode 1B, Vnode 1C, ...] (256 Sanal Nokta)
Fiziksel Sunucu 2 -> [Vnode 2A, Vnode 2B, Vnode 2C, ...] (256 Sanal Nokta)
Fiziksel Sunucu 3 -> [Vnode 3A, Vnode 3B, Vnode 3C, ...] (256 Sanal Nokta)
  • Her fiziksel sunucu halka üzerinde yüzlerce sanal düğüm (varsayılan 128 veya 256 vnode) ile temsil edilir.
  • Sanal noktalar tüm halkanın çevresine eşit ve homojen biçimde saçılır.
  • Bir fiziksel sunucu arızalandığında üzerindeki yüzlerce sanal düğümün yükü tek bir komşuya değil, kümedeki diğer tüm fiziksel sunuculara dengeli olarak dağılır.
  • Farklı donanım güçlerine sahip sunucular varsa güçlü sunucuya daha fazla vnode atanarak ağırlıklı yük dengeleme sağlanabilir.

İstemci Yönlendirme Algoritması

İstemci kütüphaneleri (örneğin Ketama algoritması) halkadaki düğüm konumlarını bellek içi dengeli bir ikili arama ağacında (Binary Search Tree / Red-Black Tree) sıralı dizi olarak tutar:

TEXT
Sıralı Halka Dizisi: [0x15A, 0x48C, 0x89F, 0xDF2]
Anahtar Karması: 0x510
İkili Arama (Binary Search): İlk büyük değer bulunur -> 0x89F (Hedef Düğüm)

Bu işlem $O(\log M)$ sürede ($M$: toplam vnode sayısı) mikro saniyeler içinde tamamlanır.

Tutarlı karma, modern dağıtık mimarilerde kesintisiz büyüme ve veri dengesi sağlayan en zarif algoritmalardan biridir.

Yazıyı Değerlendir

0 tepki

Fikirlerinizi tek tıkla paylaşarak geri bildirim bırakın.

Bu teknik notu çevrenizle paylaşın

Ali Purtaş

@alipurtas • Hey, This is Ali!

İletişime Geç

Kendi halinde yazılım geliştiren bir öğrenci. Sistemler kuruyor, deniyor, bozuyor ve öğrendiği gerçek çözümleri burada belgeliyor.

Konu Kümesi & Önerilen Yazılar

İç Bağlantılı Mimari
Yorumlar yükleniyor...