Partisi dengan hash(key) % N sederhana selama jumlah node tetap. Aritmetika tersebut menjadi disruptif ketika N berubah. Peralihan dari empat node ke lima node mengganti pembagi, sehingga banyak key memilih remainder berbeda meskipun hanya satu node yang bergabung.

Consistent hashing mengubah pemetaan tersebut. Key dan node ditempatkan dalam hash space melingkar yang sama. Sebuah key menjadi milik node pertama yang ditemui dalam arah yang dipilih pada ring. Penambahan atau penghapusan node hanya mengubah kepemilikan range yang berdekatan dengan perubahan membership itu.

Properti yang berguna adalah remapping terbatas, bukan ring yang selalu seimbang sempurna. Desain produksi biasanya menambahkan virtual node, token eksplisit, atau lapisan balancing lain karena sedikit posisi physical node dapat menghasilkan range yang timpang.

Ring mengubah membership menjadi kepemilikan range

Ambil hash space dari 0 hingga 2^m - 1 dan perlakukan kedua ujungnya sebagai titik yang bersebelahan. Setiap node memperoleh satu atau beberapa posisi dalam ruang tersebut. Key di-hash ke domain yang sama lalu diberikan kepada node berikutnya searah jarum jam.

              0
              |
        A ----+---- B
       /             \
      /               \
     D                 C
      \               /
       +-------------+

Misalkan posisi node adalah:

A = 10
B = 30
C = 55
D = 80

Key dengan hasil hash 42 dipetakan ke C. Key dengan hasil hash 72 dipetakan ke D. Key dengan hasil hash 93 melewati ujung ruang lalu dipetakan ke A.

Dengan demikian, setiap node memiliki interval setelah pendahulunya sampai posisinya sendiri, mengikuti konvensi endpoint yang dipakai ring. Konvensi tersebut penting dalam implementasi, tetapi prinsip partisinya tidak bergantung pada pilihan traversal searah atau berlawanan arah jarum jam.

Menambah satu node memindahkan satu range yang berdekatan

Sekarang tambahkan node E pada posisi 45. Sebelum E bergabung, key dalam interval setelah B hingga C dipetakan ke C. Setelah E bergabung, subrange yang berakhir di E dipetakan ke E, sedangkan sisanya tetap pada C.

sebelum:
B -------- key -------- C

        tambahkan E
             |
sesudah:     v
B ---- key ----- E ---- key ----- C

Key milik A dan D tidak berpindah karena hubungan successor mereka tidak berubah. Key di antara E dan C juga tetap berada pada C.

Lokalitas ini menjadi pembeda utama dari partisi modulo. Perubahan membership memodifikasi boundary dalam hash space, bukan mengganti pembagi yang digunakan oleh setiap key.

Pola yang sama berlaku saat E keluar. Range miliknya berpindah ke owner berikutnya pada ring. Range lain dapat tetap berada di tempatnya.

Ring fisik yang kecil tetap dapat sangat timpang

Melakukan hash satu kali terhadap identifier node tidak menjamin ukuran range yang serupa. Empat posisi acak dapat membuat satu node bertanggung jawab atas setengah ring, sedangkan node lain hanya memegang bagian sempit.

0 ---- A - B ---------------- C -- D ---- max

Hashing yang uniform memberi perilaku statistik yang berguna pada banyak posisi, tetapi sampel kecil tetap dapat timpang. Jika setiap physical node hanya memiliki satu token, ketimpangan itu langsung menjadi ketimpangan storage dan request.

Virtual node mengurangi sensitivitas tersebut. Alih-alih satu posisi, setiap physical node memperoleh banyak posisi yang tersebar di ring:

physical A -> A1, A2, A3, ...
physical B -> B1, B2, B3, ...
physical C -> C1, C2, C3, ...

Setiap token memiliki range yang lebih kecil. Total tanggung jawab physical node merupakan gabungan range tersebut. Dengan cukup banyak token yang terdistribusi baik, kepemilikan agregat cenderung lebih rata dan node yang baru bergabung dapat mengambil bagian dari beberapa node lama, bukan satu range besar yang berurutan.

Virtual node juga membawa biaya. Token yang lebih banyak berarti metadata placement lebih banyak, lebih banyak range untuk dilacak, dan berpotensi lebih banyak operasi transfer saat membership berubah. Sistem dengan kontrol placement eksplisit dapat memilih set partisi tetap lalu memindahkan partisi tersebut antar-node.

Kapasitas berbobot memerlukan kepemilikan berbobot

Kepemilikan yang sama besar tidak selalu menjadi target. Node dengan storage atau serving capacity dua kali lebih besar mungkin diharapkan memegang porsi key space yang lebih besar.

Desain virtual-node dapat mendekati weighting dengan memberikan lebih banyak token kepada node yang lebih besar. Desain lain dapat menempatkan token secara eksplisit agar ukuran range mengikuti target kapasitas. Dalam kedua pendekatan, capacity policy berada di atas aturan dasar ring.

Pemisahan ini penting karena hashing tidak memiliki informasi tentang ukuran disk, anggaran CPU, biaya request, atau hardware heterogen. Hashing mendistribusikan posisi; placement policy menentukan physical resource yang menerima posisi tersebut.

Replikasi memperluas kepemilikan melewati node pertama

Ring juga dapat menyediakan urutan kandidat replica. Jika primary owner sebuah key adalah C, physical node berbeda berikutnya pada ring dapat menjadi replica.

key -> C -> D -> A
       ^    ^    ^
     primary replica

Dengan virtual node, pemilihan replica harus menghindari penghitungan beberapa token milik physical node yang sama sebagai failure domain independen. Placement algorithm juga dapat mempertimbangkan rack, zone, atau region agar replica tidak berbagi failure boundary yang berkorelasi.

Consistent hashing memberi urutan yang berguna, tetapi replikasi durable memerlukan aturan tambahan untuk jumlah replica, keragaman failure domain, perilaku quorum, repair, dan membership view yang usang.

Membership view perlu berkonvergensi

Perpindahan key yang terbatas mengasumsikan participant menggunakan membership ring yang kompatibel. Selama proses join, leave, atau failure, proses berbeda dapat sementara memiliki view yang berbeda. Satu proses dapat merutekan key ke owner lama sementara proses lain memilih owner baru.

Karena itu, sistem memerlukan membership protocol dan prosedur transfer di sekitar algoritma ring. Hal yang perlu ditangani mencakup pengumuman token set baru, transfer data yang terdampak, penentuan waktu owner baru boleh melayani traffic, serta overlap yang cukup untuk mencegah gap selama transisi.

Ring tidak membuat transisi tersebut atomik. Ring hanya memberi sistem set range terbatas yang memerlukan penanganan.

Hot key tetap menjadi hot key

Hash space yang seimbang sempurna sekalipun dapat membawa traffic yang timpang. Satu key dapat menerima sebagian besar request, atau sekumpulan kecil key dapat merepresentasikan object yang jauh lebih besar daripada yang lain.

Keseimbangan hash space dan keseimbangan workload adalah dua properti berbeda. Consistent hashing dapat menyebarkan populasi besar key independen, tetapi tidak dapat membagi satu hot key hanya dengan menempatkan key tersebut pada posisi ring lain.

Mitigasi dapat berupa caching, request coalescing, sharding hot object pada level aplikasi, atau read yang memanfaatkan replica. Mekanisme yang sesuai bergantung pada sumber tekanan: request rate, ukuran object, serialisasi write, atau batas resource lain.

Ring mempersempit boundary rebalance

Consistent hashing paling berguna ketika perubahan membership merupakan kejadian normal dan memindahkan seluruh key akan mahal. Ring mengubah perubahan global pada jumlah partisi menjadi perubahan kepemilikan pada range hash tertentu.

Boundary yang lebih sempit itu tetap memerlukan rekayasa di sekelilingnya. Penempatan token mengendalikan balance, capacity weighting menangani node yang tidak setara, replica policy mengendalikan fault tolerance, dan koordinasi membership mengendalikan transisi. Hash ring menyediakan primitive pemetaan yang stabil; sistem di sekelilingnya mengubah primitive tersebut menjadi distributed store atau router yang dapat dioperasikan.

Software Engineering Sistem Terdistribusi Consistent Hashing Partisi