Consistent hashing, in one ring
You have K keys spread across N cache servers. A server dies, or you add one. How many
keys have to move? With naive hash(key) mod N the answer is "almost all of them." Consistent
hashing gets it down to roughly K / N. Here's why.
The trick: hash onto a circle, not a line
Map both nodes and keys onto the same ring (the hash output space, wrapped around). A key belongs to the first node found by walking clockwise from the key's position. When a node leaves, only the keys in its arc reassign — to the next node round — and everything else stays put.
Colored arcs show ownership. Removing a node hands its arc to its clockwise neighbor; every dot outside that arc keeps its color. That's the whole idea.
Versus mod N
| hash mod N | consistent hashing | |
|---|---|---|
| Keys moved when N→N+1 | ~ (N−1)/N of all keys | ~ 1/(N+1) |
| Hot-spot risk | even by construction | uneven — fix with virtual nodes |
| Lookup cost | O(1) | O(log N) (binary search on ring) |
| Used by | array sharding, simple LB | Dynamo, Cassandra, Memcached clients, Envoy |
Where you'll meet it
Any time you're spreading state across a pool that changes size: cache fleets, partitioned queues, object storage, request routing with sticky sessions. The virtual-node variant (each physical node owns many small arcs instead of one big one) is what production systems actually run, because it smooths out load and makes rebalancing even gentler.