Consistent Hashing Membatasi Perpindahan Key Saat Topologi Berubah

Distributed cache atau service yang dipartisi memerlukan aturan untuk memetakan setiap key ke node. Aturan sederhana seperti hash(key) % N menarik selama jumlah node tetap. Masalah muncul ketika N berubah.

Perubahan dari empat node menjadi lima mengganti pembagi untuk setiap key. Sebagian besar remainder ikut berubah, sehingga penambahan kapasitas biasa dapat memetakan ulang bagian besar dataset sekaligus. Pada cache, kondisi ini dapat memicu gelombang miss. Pada storage yang menyimpan state, perubahan tersebut dapat menghasilkan pekerjaan migrasi yang besar.

Consistent hashing memakai model pemetaan berbeda. Key dan node menempati posisi dalam hash space yang sama, lalu sebuah key diberikan kepada node berikutnya pada arah yang ditetapkan. Penambahan atau penghapusan node terutama mengubah ownership di sekitar posisi node tersebut, bukan di seluruh keyspace.

Modulo sharding mengikat placement pada jumlah node

Misalkan sebuah service memiliki empat shard:

shard = hash(key) % 4

Setelah shard kelima ditambahkan:

shard = hash(key) % 5

Key yang sebelumnya menghasilkan remainder 2 belum tentu mempertahankan remainder itu dengan modulus baru. Placement function berubah secara global.

Sifat ini dapat diterima ketika membership tetap atau redistribusi penuh murah. Biayanya meningkat ketika node ditambah, dihapus, diganti, atau dikeluarkan sementara sebagai bagian dari operasi rutin.

Masalah utamanya bukan hashing. Masalahnya adalah jumlah shard dimasukkan langsung ke persamaan placement.

Ring memisahkan placement key dari ukuran membership

Model consistent hashing yang umum memperlakukan nilai hash sebagai titik pada rentang melingkar. Setiap node memperoleh satu atau beberapa posisi pada ring tersebut. Setiap key di-hash ke rentang yang sama dan diberikan kepada node pertama yang ditemui searah jarum jam.

0 ------------------------------------------------ max
^                                                  |
|                                                  v
+--------------------------------------------------+

        A           B                C
        ^           ^                ^
       k1      k2   |           k3   |

Gambar melingkar hanya representasi yang praktis; implementasi dapat menyimpan posisi hash yang terurut dan memakai successor lookup. Jika pencarian melewati posisi terbesar, pencarian kembali ke posisi pertama.

Ketika node D dimasukkan di antara A dan B, D mengambil interval yang sebelumnya dimiliki B:

before: A ----------- B
after:  A ---- D ---- B
             ^^^^^
          moved keys

Key pada interval lain tetap memiliki owner yang sama. Penghapusan bekerja sebaliknya: interval milik node yang keluar berpindah ke successor.

Perpindahan terbatas adalah sifat yang berguna

Consistent hashing tidak berarti key tidak pernah berpindah. Perubahan membership memang harus memindahkan sebagian key karena kapasitas dan ownership berubah.

Sifat pentingnya adalah perpindahan yang terlokalisasi. Dengan hash function yang terdistribusi baik dan posisi node yang seimbang, penambahan satu node ke kumpulan N node berukuran serupa memindahkan key dalam kisaran 1 / (N + 1) menuju node baru. Penghapusan satu node memindahkan key milik node tersebut ke owner lain.

Karakter ini berbeda secara material dari aturan modulo yang pembaginya berubah. Manfaat operasionalnya berupa gangguan cache yang lebih kecil, transfer state yang lebih sedikit, dan periode mixed ownership yang lebih sempit selama perubahan topologi.

Fraksi tepatnya bergantung pada layout ring, bobot node, distribusi hash, dan placement policy. Consistent hashing menyediakan struktur placement; mekanisme ini tidak menjamin balance sempurna dengan sendirinya.

Satu posisi per node dapat menghasilkan balance yang buruk

Pemberian satu posisi ring secara acak untuk setiap physical node dapat menghasilkan interval dengan ukuran sangat berbeda. Node yang kebetulan memiliki interval besar menerima lebih banyak key dibanding node dengan interval kecil.

Virtual node mengurangi variasi tersebut. Alih-alih satu posisi, setiap physical node memiliki banyak posisi yang tersebar pada ring:

A1   B1   C1   A2   C2   B2   A3   B3   C3
|    |    |    |    |    |    |    |    |
+----+----+----+----+----+----+----+----+---

Setiap interval kecil tetap memiliki satu owner, tetapi interval milik sebuah physical node tersebar di hash space. Total ownership cenderung lebih merata ketika jumlah virtual position bertambah.

Virtual node juga mendukung weighting. Node dengan kapasitas yang ditargetkan dua kali lebih besar dapat memperoleh kira-kira dua kali jumlah posisi, sesuai placement policy implementasi.

Posisi tambahan tetap memiliki biaya. Jumlahnya menambah metadata ring, kalkulasi placement, dan banyaknya ownership range yang mungkin terlibat dalam migrasi. Jumlah posisi sebaiknya cukup untuk balance yang dapat diterima tanpa menambah pekerjaan control plane secara berlebihan.

Replication memperluas placement melampaui satu successor

Storage system biasanya membutuhkan lebih dari satu salinan untuk setiap key. Ring dapat memilih primary owner lalu melanjutkan pencarian ke node eligible yang berbeda untuk replica.

Ring walk yang naif dapat menempatkan beberapa replica pada failure domain yang sama. Jika tiga posisi berurutan dimiliki mesin dalam satu rack, kedekatan pada ring saja tidak memberi resilience pada tingkat rack.

Placement produksi karena itu sering menggabungkan consistent hashing dengan constraint topologi:

primary: hash successor
replica 1: next eligible node in another rack
replica 2: next eligible node in another rack or zone

Eligibility rule sama pentingnya dengan ring. Placement layer memerlukan definisi stabil untuk node identity, failure domain, capacity, dan health state.

Virtual node menambah detail lain: pemilihan replica harus melewati posisi milik physical node yang sudah memegang salinan. Replication factor menghitung failure target yang berbeda, bukan sekadar posisi ring yang berbeda.

Perubahan membership memerlukan transition protocol

Ring menghitung ownership yang dituju, tetapi perubahan ring bukan data-migration protocol.

Jika node D menjadi owner baru untuk sebuah range, data lama mungkin masih berada pada B. Mengirim read dan write langsung ke D dapat menampilkan state yang belum tersedia. Transisi yang aman memerlukan fase eksplisit, misalnya:

1. publish D as joining
2. copy the affected range from B to D
3. capture or forward concurrent writes
4. verify the transferred range
5. switch authoritative ownership to D
6. retire the old copy according to policy

Protocol tepatnya bergantung pada storage model. Cache dapat menerima miss lalu mengisi data kembali secara lazy. Durable store memerlukan aturan lebih kuat untuk concurrent write, replica convergence, failure recovery, dan ownership epoch.

Pemisahan ini menjaga dua concern tetap berbeda: consistent hashing memilih tujuan, sedangkan migration protocol menjaga correctness ketika ownership berubah.

Client memerlukan versi ring yang konsisten

Placement dapat gagal walaupun hash algorithm benar jika participant memakai membership view yang berbeda.

Misalnya, client masih merutekan key k dengan ring version 41 ketika server sudah berpindah ke version 42. Old owner dapat menolak request, melakukan proxy, atau menyajikan state lama sesuai protocol yang berlaku.

System biasanya menyertakan epoch atau configuration version pada membership state. Router dapat memperbarui metadata yang stale setelah redirect atau mismatch, sedangkan server dapat menolak ownership claim dari epoch lama.

Ring update juga harus deterministic. Dengan membership record dan hash function yang sama, router independen seharusnya menghasilkan posisi dan owner yang sama. Ketergantungan tersembunyi pada iteration order atau randomness lokal process membuat placement drift sulit didiagnosis.

Hot key tetap menjadi hot key

Balance pada jumlah key tidak berarti load ikut seimbang. Satu key dapat menerima sejuta request sementara ribuan key lain hampir idle. Memetakan hot key itu ke node lain hanya memindahkan hotspot.

Consistent hashing menangani remapping akibat perubahan topologi, bukan skew pada request frequency. Mitigasi hot key dapat memerlukan replication, request coalescing, caching pada layer lain, key splitting, admission control, atau routing khusus workload.

Pembedaan yang sama berlaku untuk ukuran object. Jumlah key yang sama dapat memakai storage sangat berbeda jika ukuran value bervariasi. Capacity planning sebaiknya mengukur byte, request rate, CPU cost, dan network traffic, bukan menganggap jumlah key sebagai metric load yang lengkap.

Desain ring adalah kontrak operasional

Placement scheme menjadi bagian dari perilaku recovery, scaling, dan deployment. Hash function, format node identity, virtual-node policy, replica rule, weighting, membership versioning, dan migration state memerlukan definisi yang stabil.

Perubahan pada salah satu input tersebut dapat memetakan ulang data meskipun physical node tidak berubah. Penggantian hash function, misalnya, dapat setara dengan membangun ulang seluruh ring.

Consistent hashing berguna karena perubahan membership rutin tidak harus memicu full remap rutin. Manfaat itu bertahan hanya jika placement metadata bersifat deterministic dan transisi ownership ditangani sebagai masalah correctness yang terpisah.