Consistent Hashing Membatasi Perpindahan Key Saat Membership Berubah

Partisi hash sederhana sering tampak memadai:

owner = hash(key) % node_count

Dengan empat node, setiap key masuk ke salah satu dari empat remainder. Masalah muncul saat membership berubah. Peralihan dari empat node menjadi lima mengubah modulus, sehingga sebagian besar key memilih owner berbeda meski hanya satu node yang ditambahkan.

Reshuffle tersebut mahal bagi distributed cache, sharded service, dan sistem lain yang memiliki biaya pada placement state. Cache hit rate dapat jatuh, network transfer dapat melonjak, dan storage ownership dapat berubah jauh melampaui kapasitas yang disumbangkan node baru.

Consistent hashing mengubah aturan placement sehingga perubahan membership hanya memengaruhi bagian terbatas dari key space.

Key dan node berbagi satu hash space

Model ring yang umum melakukan hash terhadap key dan identitas node ke ruang melingkar yang sama. Sebuah key dimiliki node pertama yang ditemui searah jarum jam dari posisi key tersebut.

        node B
          *
      /       \
 key x         * node C
    *           \
      \         /
          *
        node A

Ring merupakan urutan konseptual. Implementasi umumnya menyimpan hash position yang sudah diurutkan lalu melakukan successor lookup; struktur geometris tidak diperlukan.

Jika node C bergabung di antara B dan A, hanya key pada interval yang sekarang berakhir di C yang berganti primary owner. Key pada interval lain tetap berada di tempatnya.

sebelum:
(B, A] -> A

setelah C bergabung:
(B, C] -> C
(C, A] -> A

Notasi tersebut menggambarkan posisi pada circular hash space. Konvensi endpoint yang tepat merupakan pilihan implementasi, tetapi harus konsisten.

Perubahan membership menjadi perubahan placement lokal

Pada modulo partitioning, perubahan jumlah node mengubah formula placement secara global. Pada consistent hashing, posisi node menjadi bagian dari placement state. Menambah satu posisi menyisipkan satu boundary baru; menghapus satu posisi menghilangkan satu boundary.

Untuk ring dengan distribusi baik dan N owner yang memiliki load sebanding, penambahan satu owner sekelas memindahkan kira-kira 1 / (N + 1) bagian key secara ekspektasi. Perpindahan aktual bergantung pada distribusi hash dan jumlah posisi yang dimiliki setiap physical node.

Properti ini tidak membuat rebalancing gratis. Range yang berpindah masih dapat berisi object besar atau hot key. Properti tersebut membatasi cakupan perubahan ownership agar membership churn tidak otomatis memicu reshuffle yang hampir global.

Satu posisi per node menghasilkan load yang tidak rata

Melakukan hash terhadap setiap physical node ke satu titik dapat menciptakan gap besar antar-node yang berdekatan. Owner setelah gap besar menerima lebih banyak key dibanding owner setelah gap kecil.

ring intervals

A ----------- B -- C ---------------- D
   large          very large
   interval       interval

Uniform hash function menyebarkan posisi secara acak; fungsi tersebut tidak menjamin jarak yang sama untuk jumlah node yang kecil.

Virtual node mengatasi kondisi ini dengan memberi beberapa hash position kepada setiap physical node. Alih-alih satu titik untuk server A, ring dapat memiliki A1, A2, A3, dan banyak posisi lain yang tersebar di seluruh ruang.

A1  B1  C1  A2  C2  B2  A3  B3  C3

Setiap virtual position memiliki interval setelahnya, sedangkan semua posisi dengan physical identity yang sama tetap diarahkan ke server yang sama. Lebih banyak posisi umumnya meratakan aggregate share yang diterima setiap server.

Jumlah virtual node memiliki tradeoff

Jumlah virtual node yang lebih besar memperbaiki statistical balance dan memberi granularitas rebalancing yang lebih halus. Biayanya adalah placement metadata yang lebih banyak serta lebih banyak range yang mungkin berpindah saat membership berubah.

Jumlahnya tidak harus identik ketika kapasitas node berbeda. Server yang lebih besar dapat menerima lebih banyak posisi daripada server kecil sehingga expected share pada ring juga lebih besar.

Capacity weighting memerlukan policy yang stabil. Mengubah assignment virtual node terlalu cepat sebagai respons terhadap utilization jangka pendek dapat menimbulkan placement churn yang lebih mahal daripada imbalance yang hendak dikoreksi.

Ring menggambarkan ownership yang dituju; perpindahan operasional tetap memerlukan rate limit, transfer scheduling, dan failure handling.

Replication berjalan melewati primary owner

Sistem yang memakai replication dapat memilih owner tambahan dengan melanjutkan perjalanan pada ring setelah primary position.

key -> primary A -> replica C -> replica B

Memilih posisi berikutnya begitu saja tidak cukup ketika beberapa virtual position dimiliki physical node yang sama. Replica selection harus melewati physical identity yang duplikat. Sistem lintas rack atau zone juga dapat menerapkan topology constraint agar salinan tidak berada pada failure domain yang sama.

Aturan placement karena itu memiliki dua lapisan: hash-space ordering menentukan kandidat, lalu replica policy menyaring kandidat berdasarkan physical identity dan topology.

Replication factor dan consistency semantics tetap merupakan urusan terpisah. Consistent hashing memilih placement; mekanisme ini tidak menetapkan quorum behavior, conflict resolution, atau read freshness.

Hot key tetap menjadi hot key

Distribusi berdasarkan jumlah key yang sempurna sekalipun dapat menghasilkan load balance buruk ketika frekuensi akses berbeda. Satu key dapat menerima sebagian besar traffic, dan consistent hashing tetap menempatkan key tersebut pada satu primary owner.

Virtual node meratakan banyak key; mekanisme ini tidak membagi satu hot key.

Penanganan hot key dapat memerlukan request coalescing, replication untuk read, caching pada layer lain, key splitting ketika semantik mengizinkan, atau routing eksplisit untuk key tertentu. Kontrol tersebut menangani workload skew, bukan hash-space skew.

Perbedaannya penting secara operasional. Jumlah key yang seimbang tidak berarti CPU, network, storage bandwidth, atau request rate juga seimbang.

Failure detection mengubah routing state

Ketika sebuah node dinyatakan unavailable, client atau router memerlukan membership view yang konsisten sebelum dapat mengalihkan routing dari posisi node tersebut. Jika participant memakai versi ring yang berbeda, mereka dapat tidak sepakat tentang owner untuk key yang sama.

Sebagian sistem menoleransi perbedaan sementara karena request dapat diteruskan ke owner saat ini. Sistem lain mendistribusikan versioned placement map dan menolak routing state yang stale. Mekanisme yang tepat bergantung pada model storage dan consistency.

Membership karena itu memerlukan control plane yang eksplisit. Consistent hashing memberi mapping deterministik untuk membership set tertentu; mekanisme ini tidak membentuk consensus tentang set tersebut.

Kualitas hash menjadi bagian dari kualitas placement

Hash function perlu menyebarkan key dan node-position identifier ke seluruh ruang yang dikonfigurasi. Output yang berkorelasi atau bias dapat menciptakan placement skew yang menetap.

Kekuatan kriptografis tidak selalu diperlukan. Distribution quality, kecepatan, output lintas platform yang stabil, dan resistance terhadap adversarial key merupakan requirement terpisah. Public service yang melakukan hash terhadap key yang dikendalikan attacker dapat memerlukan collision resistance lebih kuat dibanding internal cache dengan identifier tepercaya.

Mengganti hash function merupakan placement migration. Existing key dan node position dapat berpindah secara luas, sehingga upgrade hash function memerlukan kehati-hatian yang sama seperti perubahan format partitioning.

Perpindahan perlu diukur dalam byte dan load

Properti ring yang elegan biasanya dinyatakan sebagai fraksi key yang berpindah. Production system juga memperhatikan byte, transfer time, cache warmth, dan traffic.

Range dengan beberapa object sangat besar dapat lebih mahal dipindahkan daripada range dengan banyak object kecil. Range dengan hot key dapat langsung mengubah request load meski stored byte count sangat kecil.

Rebalancing telemetry karena itu perlu mencakup range ownership, object count, bytes transferred, transfer backlog, request rate per node, dan resource saturation. Placement balance memiliki banyak dimensi.

Ring adalah mekanisme placement, bukan sharding system lengkap

Consistent hashing menangani satu ketidakstabilan spesifik pada hash-based placement: membership dapat berubah tanpa mengganti owner untuk hampir setiap key. Virtual node memperbaiki statistical balance, sedangkan topology-aware replica selection dapat memperluas ordering yang sama ke replicated placement.

Beberapa tanggung jawab tetap berada di luar ring: membership agreement, data transfer, replica consistency, overload control, hot-key mitigation, dan recovery setelah partial failure.

Boundary tersebut perlu tetap eksplisit. Ring menentukan arah ownership untuk placement map tertentu; sistem di sekitarnya menentukan cara ownership tersebut menjadi aman, mutakhir, dan dapat digunakan.