Bangun hash ring

Pertanyaan

Bagaimana menentukan node pemilik sebuah key tanpa memindahkan hampir semua data setiap kali jumlah node berubah?

Setelah baca ini, kamu bisa menulis pencarian pemilik di hash ring, menjelaskan peran virtual node, dan menghitung berapa key yang berpindah saat node ditambah.

Prasyarat dan contoh

Kamu sudah paham partisi hash dari M07.01 Pilih partition key dan fungsi hash dasar.

Cara paling sederhana memetakan key ke node adalah hash(key) mod N. Dengan 10 node, key dengan hash 1.234 mendarat di node 4. Masalah muncul saat node ke-11 masuk: hash mod 11 menghasilkan jawaban lain untuk hampir semua key. Hanya key yang hash mod 10 == hash mod 11 yang tetap, yaitu sekitar 1/11. Jadi kira-kira 10/11, atau 91%, data harus pindah. Untuk cache, itu berarti hampir semua entri hilang sekaligus. Untuk penyimpanan 5 TB, itu berarti memindahkan sekitar 4,5 TB.

Hash ring memperbaiki ini: saat node ke-11 masuk, hanya sekitar 1/11 key (9%) yang berpindah, dan semuanya pindah ke node baru.

Mekanisme

Bayangkan ruang hash 0 sampai 2^32-1 dilipat jadi lingkaran.

1. Hash setiap node (misalnya dari "node-a") menjadi satu titik di lingkaran.
2. Hash key menjadi titik juga.
3. Pemilik key adalah node pertama yang ditemui bergerak searah jarum jam dari titik key (titik node dengan hash lebih besar atau sama, lalu berputar ke awal kalau sudah lewat ujung).

// ring: daftar { token, node } terurut menurut token
function owner(ring: Token[], key: string): string {
  const h = hash(key);
  // binary search: token pertama >= h
  let lo = 0, hi = ring.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (ring[mid].token < h) lo = mid + 1; else hi = mid;
  }
  return ring[lo % ring.length].node; // putar ke awal di ujung
}

Pencarian binary search, O(log T) untuk T token. Syarat deterministik: semua klien harus memakai fungsi hash yang sama, urutan tie-break yang sama (misalnya urutkan token, lalu nama node bila token kembar), dan daftar node yang sama. Kalau dua klien melihat daftar node berbeda, mereka akan menulis key yang sama ke dua node.

Masalah satu titik per node. Dengan satu token per node, jarak antar token acak. Pada 10 node, node paling berat bisa memegang beberapa kali lipat rata-rata, dan saat satu node hilang, seluruh beban rentangnya jatuh ke satu tetangga saja.

Virtual node (vnode). Beri setiap node banyak token, misalnya 128 (hash("node-a#0"), hash("node-a#1"), ...). Rentang milik satu node jadi terpecah menjadi banyak potongan kecil di seluruh lingkaran. Sebaran beban membaik kira-kira dengan faktor 1/sqrt(v): dengan 128 vnode, simpangan beban kurang lebih 9% dari rata-rata. Saat node hilang, bebannya terbagi ke banyak node, bukan ke satu tetangga.

Vnode juga memungkinkan bobot: node dengan disk dua kali lebih besar diberi 256 vnode, bukan 128.

Untuk replikasi, banyak sistem memilih node berikutnya di ring sebagai replika. Pilih replika dari node fisik yang berbeda, bukan vnode berikutnya, karena dua vnode tetangga bisa saja milik node fisik yang sama.

Saat rancangan ini gagal

• Vnode terlalu sedikit. Dengan 4 vnode per node, sebaran beban masih timpang puluhan persen, dan satu node yang jatuh menumpukkan bebannya ke sedikit tetangga.
• Vnode terlalu banyak. 10.000 vnode per node membuat tabel token besar, dan setiap perubahan keanggotaan harus disebarkan dan dihitung ulang.
• Replika di node yang sama. Replika dipilih dari vnode berikutnya tanpa memeriksa node fisik, sehingga tiga replika sebuah key ternyata berada di satu mesin. Satu kegagalan menghilangkan semua salinan.
• Klien dengan pandangan berbeda. Setelah node ditambah, klien yang belum memperbarui daftar menulis ke pemilik lama. Itu menimbulkan data yang tersebar di dua node, dan topik M07.04 serta M07.05.
• Ring bukan pemerata beban. Ring meratakan key, bukan request. Satu key populer tetap menghantam satu node (M07.03).

Latihan

Ring dengan 3 node (A, B, C), masing-masing satu token: A=100, B=200, C=300, ruang hash 0 sampai 359.

1. Siapa pemilik key dengan hash 150, 250, dan 350?
2. Node D dengan token 260 bergabung. Key mana dari ketiga tadi yang pindah, dan dari node mana ke node mana?
3. Kalau kamu memakai mod N (N=3 jadi N=4), kenapa jawabannya jauh lebih buruk?

Lihat pembahasan+

1. Pemilik adalah token pertama yang >= hash, dengan putaran. Hash 150 menuju B (200). Hash 250 menuju C (300). Hash 350 melewati 300, jadi berputar ke A (100).
2. Token D=260 mengambil rentang (200, 260] dari C. Hash 250 ada di rentang itu, jadi key ini pindah dari C ke D. Hash 150 (tetap B) dan 350 (tetap A) nggak berpindah. Perpindahan hanya terjadi dari satu tetangga, yaitu C, karena token D berada tepat sebelum token C.
3. Dengan mod 3 menjadi mod 4, hanya key yang h mod 3 == h mod 4 yang tetap, yaitu sekitar 1/4 key. Sekitar 75% key berpindah, dan perpindahannya terjadi di antara semua pasangan node, bukan hanya ke node baru. Pada ring, hanya sekitar 1/4 key berpindah dan semuanya berakhir di node baru.

Perhatikan catatan: dengan satu token per node, D hanya mengambil beban dari C, bukan dari A dan B. Dengan vnode, pengambilan itu menyebar ke semua node.

Terkait

• Sebelumnya: M07.01 Pilih partition key.
• Lanjut ke M07.03 Bedakan pemerataan key dari pemerataan beban.
• Cara klien tahu daftar node terbaru dibahas di M07.04 Rutekan request.
• Lab L07 dan proyek B04 (hash ring dan pemeriksa penempatan) belum tersedia. Makalah Dynamo (C03) memakai gagasan ini dan belum tersedia sebagai studi kasus.

Catatan

• Asumsi: fungsi hash menyebar seragam, dan perkiraan simpangan 1/sqrt(v) adalah aproksimasi, bukan jaminan.
• Yang nggak dibahas: pemilihan fungsi hash tertentu, kriptografi, dan varian lain seperti rendezvous hashing atau jump hash.
• Ring menjamin sedikit perpindahan kepemilikan, bukan perpindahan data yang aman. Migrasi aman dibahas di M07.05.
• Terakhir ditinjau: 26 Oktober 2026.