Jawaban singkat untuk pertanyaan yang paling sering diajukan pembaca tentang topik ini.
Apa itu consistent hashing, kenapa cache dan database memakainya, dan hitungan berapa key yang pindah saat node ditambah, lengkap dengan hash ring TypeScript yang bisa dijalankan.
Matthews Wong
Software Engineer
Ringkasan Utama
Consistent hashing menempatkan key dan node pada ruang hash melingkar, dan setiap key dimiliki node berikutnya searah jarum jam. Menambah atau menghapus node hanya memindahkan sekitar 1/N key, sedangkan hash modulo N memindahkan hampir semuanya. Cache dan database terdistribusi memakainya agar tidak terjadi cache miss massal dan rebalancing besar.
Pertanyaan ini muncul saat satu instance Redis tidak lagi cukup. Anda memasang cache kedua dan ketiga di belakang aplikasi, memilih node dengan hash(key) % 3, dan semuanya berjalan lancar sampai hari Anda menambah node keempat. Tiba-tiba sebagian besar cache jadi dingin, karena sebagian besar key kini menunjuk ke server yang berbeda.
Post ini menjawab apa itu consistent hashing dan kenapa cache serta database terdistribusi memakainya. Semuanya berupa worked example dengan perhitungan yang ditunjukkan, ditambah hash ring TypeScript kecil yang bisa Anda jalankan sendiri. Angkanya berasal dari derivasi dan dari menjalankan kode itu pada key sintetis, bukan dari benchmark production.
Consistent hashing adalah cara membagi key ke node sehingga perubahan jumlah node memindahkan key sesedikit mungkin. Alih-alih membagi hash dengan jumlah node, Anda me-hash nama node dan key ke ruang melingkar yang sama, biasanya 0 sampai 2^32 - 1, lalu memberikan setiap key ke node pertama yang ditemui bergerak searah jarum jam dari posisi key.
Idenya berasal dari Karger dan rekan-rekannya di MIT pada 1997, awalnya untuk web caching. Sifat yang penting adalah satu node memiliki satu busur lingkaran, jadi menambah atau menghapus node hanya mengubah kepemilikan busur di sebelahnya. Semua key lain tetap pada pemiliknya.
Karena jumlah node menjadi bagian dari alamat setiap key. Sebuah key hanya tetap di tempatnya kalau hash % N dan hash % (N+1) kebetulan sama, dan untuk nilai hash berurutan itu jarang terjadi. Dari 4 ke 5 node, polanya berulang setiap 20 nilai, dan hanya 4 dari 20 key yang tetap di node-nya.
// Wrong: the node count is baked into every key's address.
const nodeFor = (hash: number, nodes: number) => hash % nodes;
// Grow from 4 nodes to 5. Over any 20 consecutive hash values
// (20 = lcm(4, 5)) the two answers agree only when hash % 4 === hash % 5:
//
// hash 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
// % 4 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3
// % 5 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4
// same Y Y Y Y . . . . . . . . . . . . . . . .
//
// 4 of 20 stay put, 16 of 20 move -> 80% of keys change node.
// General rule, N -> N+1 nodes: N / (N + 1) of keys move.
// 10 -> 11 nodes: 10/11 = 90.9% of keys move.Untuk cache, artinya 80 persen lookup miss tepat setelah resize, dan setiap miss jatuh ke database pada saat yang sama. Untuk database lebih parah, sebab 80 persen baris harus disalin secara fisik ke shard lain. Biayanya naik seiring ukuran cluster, karena N / (N + 1) mendekati 1.
Simpan array terurut berisi posisi di ring, masing-masing ditandai dengan node fisik pemiliknya. Untuk lookup, hash key lalu binary search posisi pertama yang sama atau lebih besar, dan kembali ke awal bila melewati ujung. Virtual nodes artinya setiap node fisik memasukkan banyak posisi, di sini 150, dengan me-hash nama plus suffix.
// hash-ring.ts: runs on Node 22.18+ as-is (node hash-ring.ts), no build step.
import { createHash } from "node:crypto";
// First 4 bytes of SHA-1 as an unsigned 32-bit position on the ring.
const point = (s: string): number =>
createHash("sha1").update(s).digest().readUInt32BE(0);
class HashRing {
private points: { pos: number; node: string }[] = [];
private vnodes: number;
constructor(vnodes = 150) {
this.vnodes = vnodes;
}
add(node: string): void {
// Each physical node claims many positions: "a#0", "a#1", ...
for (let i = 0; i < this.vnodes; i++) {
this.points.push({ pos: point(node + "#" + i), node });
}
this.points.sort((a, b) => a.pos - b.pos);
}
// First virtual node clockwise from the key; wrap to index 0 past the end.
get(key: string): string {
const p = point(key);
let lo = 0, hi = this.points.length;
while (lo < hi) {
const mid = (lo + hi) >>> 1;
if (this.points[mid].pos < p) lo = mid + 1; else hi = mid;
}
return this.points[lo % this.points.length].node;
}
}Seluruh struktur hanyalah array terurut dan binary search, jadi lookup berbiaya O(log V) untuk V total virtual nodes. Membangun ulang ring saat membership berubah murah pada skala ini. Kodenya berjalan di Node.js terbaru tanpa build step, karena menghindari sintaks khusus TypeScript seperti constructor parameter properties.
Turunkan dulu hitungannya. Dengan modulo, N ke N+1 node memindahkan N / (N + 1) key: 4 ke 5 berarti 4/5, atau 80 persen. Pada ring, node baru mengambil sebagian dari tiap busur yang ada, dan idealnya memiliki 1 / (N + 1) lingkaran, jadi 4 ke 5 berarti 1/5, atau 20 persen. Lalu jalankan pada 100.000 key sintetis.
const KEYS = Array.from({ length: 100_000 }, (_, i) => "order:" + i);
const nodes = ["a", "b", "c", "d"];
// Modulo: a key moves when hash % 4 differs from hash % 5.
const modMoved = KEYS.filter((k) => point(k) % 4 !== point(k) % 5).length;
const before = new HashRing();
nodes.forEach((n) => before.add(n));
const after = new HashRing();
[...nodes, "e"].forEach((n) => after.add(n));
let ringMoved = 0, toNewNode = 0;
for (const k of KEYS) {
const [x, y] = [before.get(k), after.get(k)];
if (x !== y) { ringMoved++; if (y === "e") toNewNode++; }
}
console.log("modulo moved:", modMoved / KEYS.length);
console.log("ring moved:", ringMoved / KEYS.length, "all to e:", ringMoved === toNewNode);
// modulo moved: 0.79931 (arithmetic says 0.80)
// ring moved: 0.2166 (arithmetic says 1/5 = 0.20)
// all to e: true (no key shuffled between a, b, c, d)Hasil simulasi mendekati kedua prediksi. Hasil ring sedikit di atas 20 persen karena 150 virtual nodes memberi pembagian yang kira-kira merata, bukan persis. Baris terakhir adalah sifat yang membuat cache selamat dari resize: setiap key yang pindah menuju node baru, dan tidak ada yang berpindah antar empat node lama.
Angka-angka ini berasal dari satu kali run pada key sintetis dengan SHA-1 dan 150 virtual nodes. Ini ilustrasi dari derivasi, bukan benchmark Redis, nginx, atau database apa pun. Hash function atau jumlah virtual nodes yang berbeda akan menggeser hasil ring beberapa poin.
Dengan satu posisi per node, busurnya acak dan sangat tidak merata. Pada run 100.000 key yang sama, satu posisi per node memberi keempat node antara 4.595 dan 51.932 key, padahal idealnya 25.000 masing-masing. Dengan 150 posisi per node, sebarannya menyempit menjadi antara 23.553 dan 27.004.
| Node | Key dengan 1 posisi per node | Key dengan 150 posisi per node |
|---|---|---|
| a | 31,181 | 24,708 |
| b | 12,292 | 23,553 |
| c | 4,595 | 24,735 |
| d | 51,932 | 27,004 |
Virtual nodes juga memungkinkan pembobotan: beri mesin dengan memori dua kali lipat dua kali lipat posisi. Dan saat sebuah node mati, bebannya menyebar ke banyak tetangga, bukan menumpuk pada satu node berikutnya, yang disebut paper Dynamo sebagai salah satu keunggulan virtual nodes.
Paper Dynamo dari Amazon menjelaskan partitioning dengan consistent hashing dan virtual nodes, dan desain itu memengaruhi banyak store setelahnya. nginx menyediakannya di upstream module lewat parameter consistent. Redis Cluster adalah contoh pembanding yang berguna: ia tidak menaruh node di ring, tetapi membagi ruang key menjadi 16384 hash slot tetap, dihitung sebagai CRC16 dari key mod 16384, lalu menugaskan slot ke node.
| Pendekatan | Key yang pindah, N ke N+1 | Tempat mapping disimpan | Cocok untuk |
|---|---|---|---|
| Hash modulo N | N / (N + 1), jadi 80 persen untuk 4 ke 5 | Tidak ada, hanya jumlah node | Pool berukuran tetap yang tidak pernah di-resize |
| Hash ring dengan virtual nodes | Sekitar 1 / (N + 1), jadi 20 persen untuk 4 ke 5 | Dihitung dari daftar node | Cache pool, load balancing berdasarkan key |
| Hash slot tetap | Hanya slot yang Anda migrasikan | Tabel slot eksplisit di dalam cluster | Store sharded bergaya Redis Cluster |
# nginx: route by request URI, remapping few keys when the upstream list changes.
upstream cache_pool {
hash $request_uri consistent; # "consistent" selects the ketama method
server 10.0.0.11:8080;
server 10.0.0.12:8080;
server 10.0.0.13:8080;
}Hash slot adalah saudara dekat consistent hashing. Anda membagi ruang key menjadi banyak bucket kecil dan memindahkan bucket utuh antar node, sehingga resize hanya memindahkan bucket yang Anda pilih. Trade-off-nya, tabel slot adalah state eksplisit yang harus disepakati cluster, sedangkan ring dihitung dari daftar node saja.
Setup saya sendiri adalah satu VPS yang menjalankan Postgres, Redis, dan NestJS di Docker untuk pekerjaan ERP dan POS, dan pada bentuk itu saya belum pernah butuh ring. Satu instance Redis tidak punya node untuk dipilih. Kebutuhannya muncul saat cache atau data tier tersebar di beberapa mesin dan membership berubah. Pakai checklist ini.
Kalau memang menulis sendiri, taruh ring di balik interface kecil agar hash function dan jumlah virtual nodes bisa diganti, dan uji fraksi key yang pindah seperti contoh di atas.
Hash nama node fisik ditambah suffix yang stabil, jangan pernah IP yang berubah saat restart. Kalau node yang sama ter-hash ke posisi berbeda setelah redeploy, ring diam-diam teracak ulang dan Anda kehilangan sifat yang menjadi alasan memakainya.
Aturan yang bisa dibawa: hash modulo N mengikat setiap key pada jumlah node, sehingga memindahkan N / (N + 1) key saat resize, sedangkan ring dengan virtual nodes memindahkan sekitar 1 / (N + 1) dan hanya ke node baru. Kalau key Anda ada di satu mesin, Anda tidak butuh ini. Kalau ada di beberapa mesin dan himpunannya berubah, Anda butuh.
Sumber dan bacaan lanjutan