THE CONSISTENT HASHING — a dart

THE CONSISTENT HASHING a ring, so adding a node barely moves keys

Sharding by key mod n is a disaster: add one server and almost every key remaps. Consistent hashing puts nodes and keys on a ring; a key belongs to the next node clockwise. Add a node and only the keys in its arc move — about 1/n of them. Here adding a node at position 30 moves the key at 15 (from node 50 to 30) but leaves the key at 60 on node 90.

THE TECHNIQUE key → first node clockwise on the ring

The demo assigns keys to nodes on a ring, then adds a node and checks only the nearby key moved: live demo

HISTORY & CREDIT Karger et al. · 1997

“Consistent hashing balances load perfectly.” — a plain ring is lumpy; real systems add virtual nodes (many ring points per server) to smooth it. cited

the ring · hash nodes and keys onto a circle; key → next node clockwise.
the arc · adding a node steals only its clockwise arc — ~1/n keys move.
1997 · David Karger et al., MIT — born for web caching, now in Dynamo, Cassandra, CDNs.

Elastic sharding with minimal churn. data structure

RECOMMEND FOR I-13 minimal remap, on the compiler

On i-13 (nodes 10,50,90), adding node 30 moves key 15 (50→30) but key 60 stays on 90:

$ i13 run hs_consistent.i13 RUN OK · 337 step(s) · peak stack 6 n3a = 50 -- key 15 -> node 50 after_a = 30 -- add node 30 -> key 15 moves moved = 1 n3b_stable = 1 -- key 60 stays on node 90

Recommend as a NULL — resource/robustness (B40) + a pinned map (B39). On a fixed ring, key→node is a pinned function; “minimal remap” is a property of how the map changes when the config changes — not a same-input, same-function difference. NULL — a ring that barely moves.