Rendezvous Hashing Membatasi Perpindahan Key saat Membership Berubah

Aturan partisi memiliki dua tugas yang dapat saling tarik-menarik. Key perlu tersebar di antara node yang tersedia, tetapi sebagian besar key juga sebaiknya tetap di tempatnya ketika kumpulan node berubah. Aturan modulo sederhana menangani tugas pertama dengan baik pada cluster yang stabil, tetapi buruk untuk tugas kedua.

Rendezvous hashing, yang juga disebut highest-random-weight hashing, memberi score deterministik kepada setiap pasangan key dan node yang eligible. Node dengan score tertinggi menjadi pemilik key. Penambahan atau penghapusan node hanya mengubah perbandingan yang melibatkan member tersebut, sehingga key dengan pemenang yang tidak terpengaruh tetap pada penempatannya.

Penempatan modulo mengikat setiap key pada ukuran cluster

Aturan awal yang umum memetakan hash ke indeks node:

node_index = hash(key) % node_count

Dengan empat node, key yang memiliki hash 37 dipetakan ke indeks 1. Dengan lima node, hash yang sama dipetakan ke indeks 2. Key tidak berubah, tetapi pembaginya berubah. Efek tersebut berlaku di seluruh keyspace dan menyebabkan pemetaan ulang secara luas setelah perubahan membership biasa.

Pemetaan ulang yang luas dapat mengubah scale event rutin menjadi transfer data besar. Cache hit rate dapat turun, partisi storage mungkin perlu dimigrasikan, dan banyak node dapat menghabiskan bandwidth untuk memindahkan data yang tidak memiliki hubungan langsung dengan member baru.

Fungsi penempatan karena itu membutuhkan stabilitas selain distribusi.

Setiap key memberi peringkat pada node kandidat

Rendezvous hashing mengevaluasi fungsi deterministik atas pasangan (key, node):

score = H(key, node_identity)
owner = node dengan score maksimum

Untuk satu key, score dapat terlihat seperti berikut:

A -> 41
B -> 88
C -> 63

owner = B

Setiap pihak yang memiliki membership view, identitas node, fungsi hash, dan aturan serialisasi yang sama akan menghasilkan pilihan yang sama. Tabel penempatan terpusat tidak diperlukan untuk langkah seleksi dasar.

Output hash perlu memiliki sifat acak efektif yang memadai agar peringkat node tersebar dengan baik. Representasi byte untuk key dan identitas node juga harus kanonis. Dua implementasi yang menggabungkan field dengan cara berbeda dapat memilih owner berbeda walaupun memakai algoritma hash yang sama.

Penambahan satu node hanya menciptakan kontes baru

Misalkan node D bergabung. Score yang sudah ada untuk A, B, dan C tidak berubah. Perhitungan penempatan hanya mendapat satu kandidat baru:

A -> 41
B -> 88
C -> 63
D -> 72

owner = B

Key ini tetap berada di B karena D tidak mengalahkan pemenang sebelumnya. Key lain berpindah ke D hanya ketika D memperoleh score tertinggi untuk key tersebut.

Dengan node yang seimbang dan fungsi scoring yang sesuai, node baru mengambil sebagian key alih-alih memaksa reshuffle global. Fraksi persisnya bervariasi pada keyset terbatas dan workload yang skew, tetapi sifat strukturalnya tetap: perubahan penempatan terkait dengan kandidat baru yang memenangkan peringkat sebuah key.

Penghapusan memiliki efek lokal yang serupa. Jika C keluar, hanya key yang sebelumnya dimiliki C yang memerlukan pemenang baru. Untuk key lainnya, node surviving dengan peringkat tertinggi memang sudah menjadi owner.

Peringkat yang sama juga menyediakan kandidat replica

Peringkat lengkap dapat memilih lebih dari satu tujuan. Alih-alih hanya menyimpan score tertinggi, sistem dapat mengambil R node teratas untuk replication factor R:

score untuk key K:
B -> 88
D -> 72
C -> 63
A -> 41

replica untuk R=3: B, D, C

Primary dan penempatan replica dengan demikian berasal dari satu urutan deterministik. Jika primary tidak tersedia, node eligible berikutnya dalam peringkat sudah terdefinisi.

Urutan tersebut tidak menggantikan semantik replication protocol. Daftar kandidat deterministik menunjukkan lokasi replica; daftar itu tidak menetapkan quorum rule, consistency guarantee, leader election, repair, atau durability data dengan sendirinya.

Constraint failure domain juga perlu ditangani secara eksplisit. Mengambil tiga score teratas secara mentah dapat memilih tiga node dalam satu rack atau zone. Placement layer dapat menelusuri peringkat lalu menerima kandidat hanya jika memenuhi topology policy, misalnya zone yang berbeda. Filter tersebut menjadi bagian dari kontrak penempatan deterministik dan harus diterapkan secara konsisten.

Kapasitas berbobot mengubah aturan scoring

Peringkat setara mengasumsikan kapasitas penempatan yang setara. Cluster nyata sering mencampur ukuran node atau menyediakan fraksi kapasitas yang berbeda. Mengulang identitas node beberapa kali dapat mendekati weighting, tetapi cara itu menambahkan identitas virtual dan membuat perubahan weight kurang langsung.

Varian weighted rendezvous memasukkan weight node ke transformasi score sehingga porsi yang diharapkan mengikuti kapasitas yang dikonfigurasi. Formulanya penting: mengalikan nilai hash uniform dengan weight tidak secara umum menghasilkan probabilitas seleksi yang diinginkan. Skema weighted yang valid secara matematis perlu dipilih dan diuji terhadap porsi yang diharapkan.

Weight juga memengaruhi perpindahan. Menaikkan weight node seharusnya membuatnya memenangkan key tambahan; menurunkannya seharusnya melepaskan sebagian key. Perubahan weight yang besar tetap dapat memindahkan data dalam jumlah besar meskipun algoritma penempatan menghindari reshuffle yang tidak terkait.

Kesepakatan membership tetap merupakan masalah terpisah

Penempatan deterministik hanya deterministik terhadap input yang dipakai. Jika dua client tidak sepakat tentang kumpulan node eligible, keduanya dapat memilih owner berbeda untuk key yang sama.

client 1 melihat: A B C
client 2 melihat: A B C D

Untuk key yang menempatkan D pada peringkat pertama, kedua client tidak sepakat sampai membership view mereka konvergen. Desain production karena itu memerlukan sumber membership dengan versioning, propagation, dan failure semantics yang sesuai.

Identitas node juga harus stabil. Mengganti process sambil tanpa sengaja memberi identitas baru membuat placement layer memperlakukannya sebagai member baru. Sebaliknya, memakai kembali identitas untuk storage yang tidak terkait dapat mengarahkan key lama ke node yang tidak memiliki datanya.

Placement epoch atau membership version dapat membuat transisi terlihat secara operasional. Keduanya juga memberi migration code source view dan target view yang konkret, bukan gagasan implisit mengenai cluster saat ini.

Perpindahan minimal tidak menghapus pekerjaan migrasi

Ketika node baru memenangkan sebuah key, data tetap harus sampai ke node tersebut. Aturan penempatan menentukan tujuan; aturan itu tidak menyalin byte, mengoordinasikan dual read, atau menentukan kapan salinan lama boleh dihapus.

Jalur migrasi sering memerlukan transition state yang eksplisit:

old owner -> copy -> new owner
              |
              +-> verify

switch routing
retire old copy setelah policy mengizinkan

Traffic write selama interval tersebut membutuhkan aturan yang jelas. Bergantung pada model storage, sistem dapat mengarahkan write ke satu authoritative owner, mereplikasi sementara ke kedua penempatan, atau memakai migration protocol yang mencatat perubahan saat bulk copy berjalan. Pilihannya harus mempertahankan consistency contract yang sudah diberikan service.

Rate limiting sama pentingnya. Perpindahan key yang terbatas pun dapat berarti terabyte data pada cluster besar. Rebalancing perlu menghormati foreground latency, kapasitas network, storage I/O, dan recovery traffic, bukan memperlakukan setiap perbedaan penempatan sebagai perintah transfer segera.

Kualitas penempatan perlu diukur pada level workload

Jumlah key yang merata tidak menjamin workload yang merata. Satu key dapat menerima jutaan request sementara key lain hampir tidak aktif. Rendezvous hashing mendistribusikan identitas hash; algoritma ini tidak menyimpulkan traffic aplikasi atau ukuran object dari sebuah key kecuali signal tersebut masuk ke placement policy terpisah.

Pemeriksaan yang berguna mencakup jumlah key per node, byte tersimpan, request rate, kebutuhan CPU, volume migrasi, dan fraksi key yang berpindah antar-membership version. Pengujian sintetis juga dapat membuat keyset besar, menerapkan perubahan membership, lalu membandingkan porsi penempatan aktual dengan distribusi yang dituju.

Manfaat utamanya bersifat sempit tetapi bernilai. Rendezvous hashing mengubah perubahan membership menjadi perubahan peringkat lokal alih-alih mengubah modulus global. Sistem terpartisi mendapat aturan penempatan deterministik dengan perpindahan key terbatas serta urutan replica yang terbentuk secara alami. Koordinasi membership, topology constraint, migrasi, consistency, dan capacity control tetap menjadi tanggung jawab engineering terpisah di sekitar aturan tersebut.