Rendezvous Hashing Menjaga Penempatan Key Stabil saat Node Berubah

Sistem terdistribusi sering memerlukan jawaban deterministik untuk penempatan: jika ada sebuah key dan sekumpulan node aktif, node mana yang memiliki key tersebut? Aturan modulo sederhana seperti hash(key) % N memang ringkas, tetapi perubahan N dapat memindahkan sebagian besar key sekaligus.

Rendezvous hashing, yang juga disebut highest-random-weight hashing, memakai aturan berbeda. Untuk setiap key, algoritma menghitung score deterministik bagi setiap node yang eligible lalu memilih node dengan score tertinggi. Penambahan atau penghapusan node hanya mengubah penempatan key yang peringkatnya terdampak oleh perubahan membership tersebut.

Metode ini cocok ketika para client dapat memakai membership view yang sama dan menghitung penempatan secara lokal.

Penempatan berasal dari peringkat untuk setiap key

Untuk key k dan node n, score dibentuk dari kedua identifier:

score = H(k, n)

owner(k) = node with maximum score

H harus berperilaku seperti hash yang stabil dan terdistribusi baik atas pasangan tersebut. Setiap participant dengan key, identifier node, fungsi hash, dan membership set yang sama akan memperoleh peringkat yang sama.

Misalnya terdapat tiga node:

score(K, A) = 0.42
score(K, B) = 0.91
score(K, C) = 0.37

owner(K) = B

Tidak diperlukan posisi global pada ring. Urutan tersebut khusus untuk K; key lain dapat memberi urutan berbeda pada node yang sama.

Sifat ini juga menghasilkan daftar fallback yang alami. Mengurutkan node berdasarkan score memberi pilihan pertama, kedua, dan kandidat berikutnya tanpa struktur penempatan terpisah.

Perubahan membership hanya berdampak lokal

Misalkan node D bergabung. Key yang sudah ada tetap pada owner sebelumnya kecuali D memiliki score lebih tinggi untuk key tersebut.

before: max(A, B, C)
after:  max(A, B, C, D)

Jika D tidak menang, penempatan tidak berubah. Jika D menang, key tersebut berpindah ke D. Urutan relatif node lama tidak berubah karena score mereka tetap sama.

Penghapusan memiliki perilaku yang sepadan. Hanya key yang dimiliki node yang dihapus yang memerlukan pemenang baru; node eligible dengan score tertinggi berikutnya menjadi owner.

Pergerakan terbatas ini menjadi keunggulan operasional utama dibanding penempatan modulo langsung. Membership churn tidak otomatis mengacak ulang key yang tidak terkait ke seluruh fleet.

Identitas node yang stabil merupakan bagian dari kontrak

Score memasukkan identifier node, sehingga kestabilan identifier penting. Mengganti storage-17 dengan node yang secara logis setara tetapi bernama storage-42 tetap merupakan perubahan membership bagi algoritma. Key dapat berpindah walaupun peran mesin dasarnya terlihat sama.

Identifier sebaiknya mewakili identitas penempatan yang memang ingin dipertahankan sistem. Hostname, instance ID, shard ID, atau placement token eksplisit dapat digunakan selama lifecycle-nya sesuai dengan tujuan tersebut.

Encoding (key, node) juga harus tidak ambigu. Menggabungkan string dengan panjang bervariasi tanpa framing dapat membuat collision pada lapisan input: ("ab", "c") dan ("a", "bc") dapat menghasilkan urutan byte yang sama. Length prefix, field berukuran tetap, atau encoding kanonis lain mencegah ambiguitas tersebut.

Replikasi dapat memakai peringkat yang sama

Policy penempatan dengan replikasi dapat memilih R node eligible teratas, bukan hanya node dengan score tertinggi.

rank(K):
1. B
2. D
3. A
4. C

replication factor 3 -> B, D, A

Cara ini praktis, tetapi constraint replikasi tetap perlu ditangani secara eksplisit. Tiga node teratas dapat berada pada rack, availability zone, atau failure domain yang sama. Urutan score murni tidak mengetahui topology kecuali topology ikut menentukan eligibility atau proses pemilihan.

Salah satu pendekatan memilih kandidat dengan peringkat tertinggi lalu melanjutkan ke bawah sambil menerapkan aturan diversity. Pendekatan lain melakukan penempatan secara hierarkis, misalnya memilih failure domain terlebih dahulu lalu node. Policy yang tepat bergantung pada failure model dan consistency protocol.

Rendezvous hashing menyediakan urutan kandidat yang deterministik; mekanisme ini tidak menggantikan semantik replikasi.

Kapasitas berbobot memerlukan aturan scoring yang disengaja

Scoring setara mengasumsikan setiap node sebaiknya menerima porsi yang kurang lebih sama untuk banyak key yang terdistribusi baik. Fleet nyata sering berisi node dengan kapasitas berbeda.

Perkalian sederhana seperti score * weight dapat menghasilkan distribusi yang tidak sesuai dengan rasio kapasitas yang dituju. Skema weighted rendezvous memakai transformasi scoring yang dirancang untuk weighted sampling, bukan faktor skala sembarang.

Implementasi perlu menetapkan arti sebuah weight, cara normalisasinya, serta dampak perubahan weight terhadap perpindahan. Perubahan kapasitas besar merupakan perubahan penempatan dan dapat memindahkan banyak data meskipun membership tetap sama.

Secara operasional, perubahan weight bertahap dapat lebih mudah diserap daripada satu lompatan besar, selama algoritma weighted dan proses migrasinya mendukung policy tersebut.

Kesepakatan membership tetap diperlukan

Hashing deterministik tidak menyelesaikan konsistensi membership. Dua client dengan kumpulan node eligible yang berbeda dapat memilih owner berbeda untuk key yang sama.

Saat rollout, satu client dapat menghitung:

members = [A, B, C]
owner(K) = B

sementara client lain sudah melihat:

members = [A, B, C, D]
owner(K) = D

Apakah perbedaan itu dapat diterima bergantung pada protocol storage atau routing. Sistem dapat menyertakan membership epoch, memusatkan write otoritatif, memakai forwarding selama transisi, atau mengoordinasikan migrasi sebelum mengaktifkan placement view baru.

Aturan hashing membuat penempatan dapat direproduksi untuk sebuah view tertentu. Aturan itu tidak membuat dua view yang berbeda menjadi setara.

Kualitas hash dan lebar score memengaruhi hasil

Fungsi hash merupakan bagian dari placement protocol. Menggantinya dapat memetakan ulang hampir seluruh key, sehingga algoritma beserta encoding persisnya perlu diberi versi dengan disiplin yang sama seperti aturan layout data persisten lain.

Ruang score juga perlu cukup lebar agar tie sangat jarang pada ukuran fleet yang diharapkan. Jika tie tetap mungkin terjadi, setiap implementasi memerlukan aturan tie-break deterministik yang sama, misalnya membandingkan node ID kanonis.

Hash kriptografis tidak selalu diperlukan. Sifat yang relevan adalah output lintas platform yang stabil, distribusi yang memadai bagi workload, serta ketahanan terhadap input adversarial ketika pihak tidak tepercaya dapat memilih key. Kebutuhan keamanan karena itu dapat mengubah pilihan hash yang tepat.

Biaya komputasi bertambah bersama jumlah kandidat

Rendezvous hashing dasar mengevaluasi setiap node eligible untuk setiap keputusan penempatan, sehingga memerlukan O(N) perhitungan score untuk N node. Biaya tersebut sering masih layak untuk membership set kecil atau menengah, terutama jika hasil penempatan di-cache.

Pada skala sangat besar, evaluasi ribuan kandidat untuk setiap key dapat menjadi signifikan. Sistem dapat memperkecil candidate set melalui hierarchy, partitioning, caching, atau varian yang dirancang untuk lookup lebih cepat, tetapi setiap optimasi mengubah tradeoff operasional.

Bentuk dasarnya tetap menarik karena state yang diperlukan kecil: membership list dan aturan scoring deterministik. Tidak ada struktur ring yang harus diseimbangkan atau disinkronkan.

Stabilitas penempatan tetap memerlukan migrasi yang terkendali

Mapping yang stabil membatasi jumlah key yang berpindah, tetapi key yang berpindah tetap memerlukan transfer protocol. Sistem membutuhkan aturan untuk source selection, penyelesaian copy, concurrent write, cutover, retry, dan cleanup.

Membership sebaiknya tidak diaktifkan lebih cepat daripada kemampuan storage layer menyerap perpindahan yang dihasilkan. Rate limit dan aktivasi bertahap dapat mencegah remap yang secara matematis terbatas berubah menjadi lonjakan I/O.

Rendezvous hashing memisahkan dua tanggung jawab dengan jelas. Peringkat menentukan tujuan yang dimaksud bagi setiap key dalam sebuah membership view. Migration protocol menentukan kapan penempatan tersebut menjadi otoritatif. Pemisahan ini membuat perubahan membership lebih mudah dianalisis dan dioperasikan.