🔬 BACOT — Sesi Deep Learning: Consistent Hashing

📚 Topik

Consistent Hashing — teknik distribusi data/kunci ke sekumpulan node yang tahan terhadap perubahan jumlah node, tanpa harus me-remap hampir seluruh kunci.

Kategori: Distributed Systems · Level: Intermediate–Advanced (diff 3)

🎯 Tujuan Belajar

Setelah sesi ini kamu harus bisa: 1. Menjelaskan kenapa hashing modulo n naif gagal di sistem terdistribusi. 2. Menjelaskan mekanisme hash ring dan kenapa ia memetakan ulang hanya ~K/n kunci saat satu node berubah. 3. Memahami virtual nodes (vnodes) sebagai solusi untuk masalah distribusi tidak merata. 4. Menyebut implementasi nyata dan trade-off-nya.

🧠 Penjelasan Inti

Masalah yang diselesaikan

Bayangkan kamu punya cache atau database terdistribusi dengan n server. Cara termudah menaruh kunci k ke server:

server_index = hash(k) mod n

Ini bekerja sampai n berubah. Kalau satu server mati atau ditambah, n → n±1, dan hampir semua kunci berubah pemetaan:

pindah  = (n_lama / n_baru)  ≈ 100%   # untuk n yang berubah sedikit

Contoh: n=10 → n=11. Hanya hash(k) mod 10 == hash(k) mod 11 yang tidak pindah = 1/11 ≈ 9%. Artinya ~91% kunci remap. Untuk cache, ini = cache miss massal (thundering herd) > database overload > potentially cascading failure. Ini yang disebut rehashing problem / redistribution storm.

Consistent hashing (Karger et al., 1997 — paper yang mempopulerkannya, dipakai di Akamai CDN) memecahkan ini: saat n berubah, hanya sekitar K/n kunci (≈ 1/n) yang pindah — yaitu kunci yang memang "milik" node yang berubah.

Ide inti

Bayangkan ruang hash sebagai lingkaran/ring (biasanya [0, 2^32) atau [0, 2^128)).
Setiap node di-hash ke satu titik di ring → node menempati posisi.
Setiap kunci di-hash ke titik di ring.
Kunci dimiliki oleh node pertama yang ditemui searah jarum jam dari posisi kunci.

        hash(k1)
           |
   [N1]----o----------[N2]
     \                 \
      \                 o hash(k2)
       \               /
        [N3]---------'

k1 → N2, k2 → N3, dst. Aturannya sederhana: clockwise successor.

⚙️ Cara Kerja Internal

1. Lookup

pos_key = hash(key)                      # titik di ring
node    = cari node terkecil >= pos_key  # clockwise successor
# kalau tidak ada (pos_key > semua node), wrap ke node pertama

Implementasi efisien: simpan posisi node di array terurut → binary search O(log n). Alternatif: balanced BST.

2. Kenapa hanya ~1/n kunci pindah saat node berubah

Bukti intuitif: node N_new menyisip ke ring di suatu titik. Ia hanya mengambil alih arc (segmen busur) dari predecessor-nya sampai posisinya sendiri — yaitu 1/n dari total ring rata-rata. Kunci di arc itu yang berpindah ke N_new; sisanya tak tersentuh.

Saat node N_off keluar: arc-nya jatuh ke successor-nya. Hanya kunci milik N_off yang remap. Jadi K/n, bukan K.

Ini bukan "lebih cepat dihitung" — biaya lookup sama-sama sekali hash. Yang berubah adalah stabilitas pemetaan: jumlah kunci yang bergerak proporsional ke perubahan, bukan ke total.

3. Masalah distribusi tidak merata

Dengan node acak di ring, arc-nya tidak sama besar. Ini masalah klasik balls-and-bins: dengan n node acak, rasio beban terberat/tertinggi bisa jauh dari rata. Bahkan dengan banyak node, deviasi bisa ~log n faktor. Node "sial" yang duduk di arc besar akan kebanjiran.

4. Solusi: Virtual Nodes (vnodes)

Setiap node fisik di-hash ke banyak titik di ring (mis. 100–256 vnodes per node). Node fisik memiliki banyak "placeholder" yang tersebar acak.

Efeknya: - Beban makin merata (law of large numbers antar-vnode). - Saat node masuk/keluar, kuncinya terdistribusi ke banyak node lain, bukan menumpuk di satu successor (mengurangi hot spot). - Node dengan kapasitas beda bisa diberi bobot: node besar → lebih banyak vnode. - Cost: metadata lebih besar (n × vnodes entri), lookup tetap O(log(n·v)).

Ini standar di industri — Dynamo (Amazon), Cassandra, Riak semuanya pakai vnodes.

5. Replikasi & failure (kenapa ini bukan cuma soal distribusi)

Di sistem nyata, tiap kunci direplikasi ke R node berikutnya searah jarum jam (N1→N2→N3). Kalau satu node mati, replica-nya masih ada. Ini yang membuat Dynamo tahan node death tanpa downtime data. Consistent hashing + replication preference list = fondasi storage terdistribusi.

6. Termination & kenapa tanpa koordinasi

Karena ring bisa dihitung deterministik dari daftar node, setiap client/node bisa menghitung pemetaan secara lokal — tak perlu registry terpusat. Ideal untuk sistem P2P dan sistem yang toleran partisi.

💡 Contoh Konkret

Cache layer: 3 node, K=10⁶ kunci, hash range 0–999 agar jelas.

Posisi (acak): N1=150, N2=520, N3=880.

Kunci	hash	Owner (clockwise)
a	100	N1 (150)
b	149	N1 (150)
c	151	N2 (520)
d	900	N1 (150, wrap)
e	519	N2 (520)

Sekarang tambah N4=300: - Arc N1→sebelumnya: N1 rentang (150, 520). N4 di 300 → ambil alih kunci dengan hash ∈ (150, 300]. - Hanya kunci di window selebar 150 (≈15% ring) yang pindah. Realita dengan n node acak → rata-rata ~1/n pindah. - Bandingkan mod 3→4: ~75% kunci remap. Bedanya dramatis.

Dengan vnodes (10 per node), N1 punya N1a..N1j tersebar. Hapus N1 → beban terbagi ke banyak node, bukan satu tetangga.

Analogi: Meja bundar dengan kursi. Tamu (kunci) duduk di kursi kosong terdekat searah jarum jam dari mereka. Kursi (node) dicopot/ditambah → hanya tetangga terdekat yang terganggu, bukan semua orang harus ganti tempat. Virtual nodes = setiap orang duduk di banyak tempat sekaligus dengan nama berbeda, jadi semua kursi lebih terisi merata.

⚠️ Miskonsepsi Umum

"Consistent hashing = hashing yang konsisten (deterministik)." Salah. Semua hash deterministik. "Consistent" di sini spesifik: kestabilan pemetaan saat anggota berubah. Bukan tentang determinisme.
"Node di-hash sekali, itu cukup." Dalam praktik hampir selalu tidak — tanpa vnodes, distribusi buruk. Implementasi produksi wajib pakai vnodes.
"Consistent hashing butuh koordinasi/registry pusat." Tidak. Ia justru menghindari itu; semua pihak hitung lokal dari daftar node.
"Hanya ~1/n kunci pindah, jadi beban juga imbalanced 1/n." Tidak benar tanpa vnodes. Yang pindah jumlahnya kecil, tapi siapa yang menerima bisa menumpuk (satu successor kewalahan). Vnodes memperbaiki ini.
"Ini menggantikan replication." Tidak. Ini penempatan; durability tetap butuh replication/failure detection. Keduanya komplementer.
"Hash ring = satu-satunya jawaban." Ada alternatif nyata: rendezvous hashing (HRW) — bahas di trade-off.

⚖️ Trade-off & Limitasi

Consistent hashing (hash ring + vnodes) - Pro: pemetaan stabil, scalable, tanpa koordinator, dukung node berbobot. - Kontra: kompleksitas metadata (n × v entri); perlu vnodes untuk balance; hotspot tetap mungkin kalau data skewed (mis. kunci populer).

Rendezvous hashing (Highest Random Weight / HRW) - Pro: sederhana (tak ada ring, tak ada vnode); balance lebih baik; minimal movement. - Kontra: O(n) per lookup (bandingkan semua node) vs O(log n) ring — masalah untuk n besar. Ada varian (Skeleton/anchored) untuk memperbaiki ini.

Jump consistent hash (Lamping & Veach, 2014, Google) - Pro: sangat ringan, O(log n), memori konstan, distribusi nyaris sempurna. - Kontra: hanya mendukung tambah/hapus di ujung (bukti bucket sequential); tidak bisa hapus node arbitrer. Cocok untuk sharding yang tumbuh monoton (contoh: memcached bucket add).

Belum tuntas / area sulit: - Hot keys — consistent hashing mendistribusi kunci, bukan beban. Satu kunci viral tetap = satu node. Butuh mekanisme lain (key splitting, local caching). - Data migration cost — jumlah kunci yang pindah stabil, tapi memindahkan data aktual (jaringan/disk) tetap mahal. Konsistensi selama migrasi (hint handoff di Dynamo) itu rumit. - Awareness topologi (rack/zone-aware placement) bukan bagian dari basic algorithm; butuh lapisan tambahan.

🛠️ Latihan Praktis

Implementasi ring minimal (~30 baris Python) dan uji klaim "hanya ~1/n pindah":

import hashlib, bisect

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

class Ring:
    def __init__(self, nodes, vnodes=100):
        self.vnodes = vnodes
        self.ring = {}                      # pos -> node fisik
        self.sorted = []
        for n in nodes:
            self.add(n)
    def add(self, n):
        for i in range(self.vnodes):
            p = h(f"{n}#{i}")
            self.ring[p] = n
        self.sorted = sorted(self.ring)
    def get(self, key):
        p = h(key)
        i = bisect.bisect(self.sorted, p) % len(self.sorted)
        return self.ring[self.sorted[i]]

# self-check: pindah ~1/n
keys = [f"k{i}" for i in range(10000)]
r1 = Ring(["A","B","C"])
r2 = Ring(["A","B","C","D"])
moved = sum(r1.get(k) != r2.get(k) for k in keys)
assert 0.20 < moved/len(keys) < 0.30   # ~25% ≈ 1/4 dari 3->4

Coba juga: variasi vnodes (1 vs 200) dan ukur standar deviasi beban antar node. Tanpa vnodes (v=1) distribusi jelek; dengan v≥100 mendekati rata. Itu demonstrasi kenapa vnodes wajib.

✅ Cek Pemahaman

Cache 100 node, 10⁸ kunci, pakai consistent hashing. Satu node mati. Kira-kira berapa kunci remap, dan ke node mana? Jawaban: ~1/100 dari kunci (kunci milik node itu), jatuh ke successor clockwise-nya (sebelum vnodes).
Kenapa vnodes memperbaiki masalah di soal 1? Jawaban: vnodes menyebar kepemilikan node yang mati ke banyak node lain, mencegah satu successor kebanjiran.
Kapan kamu tidak pilih consistent hashing? Jawaban: kalau node hanya tumbuh di ujung (→ jump consistent hash lebih ringan), atau n kecil & jarang berubah (→ mod n cukup), atau butuh balance maksimal tanpa vnode (→ rendezvous hashing).

🔑 Poin Kunci

Masalah: mod n me-remap ~100% kunci saat n berubah → cache storm/cascading failure.
Solusi: hash ring; kunci ke clockwise successor → hanya ~K/n kunci pindah.
Vnodes wajib untuk balance + bobot node + hindari hotspot saat failover.
Lookup O(log n), tanpa koordinator pusat — deterministik dari daftar node.
Bukan pengganti replication — mereka komplementer (Dynamo: ring + preference list R).
Alternatif: rendezvous hashing (O(n) tapi simple), jump consistent hash (ringan tapi grow-only).
Batas: hot keys & biaya migrasi data nyata tetap masalah terpisah.

➡️ Eksplorasi Lanjut

Replication strategies di sistem terdistribusi: quorum (R + W > N), hinted handoff, read repair, dan anti-entropy via Merkle trees — bagaimana Dynamo/Cassandra menjaga konsistensi data di atas consistent hashing. Ini jawaban natural untuk "setelah kunci ditempatkan, bagaimana durability & consistency-nya dijaga?"