Consistent Hashing
Plain hash % n reshuffles almost everything when the cluster changes size. Consistent hashing makes only a small slice move.
Intermediate
TopNotchNote
Notes that matter
the problem plain hashing has when the cluster changes size
The obvious way to pick which of
n shards owns a key is hash(key) % n. This works fine until n changes. Going from 4 shards to 5 changes the modulo result for nearly every key at once — almost the entire dataset has to move, even though only one shard was added.
hash(user) % 4 = shard # 4 shards
hash(user) % 5 = shard # 5 shards — a completely different assignment for almost every user
For a large PlateRoute deployment, that means adding one cache or database node to handle a traffic spike would trigger a mass data migration at exactly the moment the system is already under stress — the opposite of what's needed.
the idea: put keys and nodes on the same ring
Consistent hashing removes the number of nodes from the formula entirely. Both data keys and node identifiers are hashed into the same fixed output space (say, a 32-bit integer range), which is then treated as a circle, or ring, running from 0 back around to the maximum value.
Each node's hash places it at a point on the ring. A key is assigned to whichever node's position is the first one reached going clockwise from the key's own hash position. Because both keys and nodes live in the same fixed space, adding or removing one node only changes ownership for the narrow slice of the ring between that node and its neighbor — not the whole ring.
worked example
Ring positions (out of 0-359 for illustration):
Node A: 40 Node B: 150 Node C: 280
Key "order_918" hashes to 95 -> owned by Node B (first node clockwise from 95)
Key "order_204" hashes to 310 -> owned by Node A (wraps around past 360 back to 40)
Adding Node D at position 100:
Only keys between 40 and 100 (previously owned by Node B) now move to Node D.
Everything else on the ring is unaffected.
Removing a node works the same way in reverse: its slice of the ring is simply absorbed by the next node clockwise, and only the keys that lived on the removed node need to move.
the uneven-load problem, and virtual nodes
A ring with only a few real nodes can end up badly unbalanced by chance — if three nodes happen to hash close together on one side of the ring, the fourth node ends up responsible for a disproportionate arc. The fix is virtual nodes: each physical node is hashed onto the ring multiple times under different virtual identifiers (e.g.
NodeA-1, NodeA-2, ... NodeA-20), scattering its presence across many points instead of one.| Benefit of virtual nodes | Why it helps |
|---|---|
| More even load distribution | With many virtual points per node, the law of large numbers smooths out the ring, so no single physical node gets an outsized arc by bad luck. |
| Smoother recovery from a failed node | When one node fails, its many small virtual slices spread the recovered load across many other nodes instead of dumping it all onto one neighbor. |
| Heterogeneous hardware support | A more powerful node can simply be given more virtual node identifiers than a weaker one, taking a proportionally larger share of the ring. |
where this shows up across the rest of this track
Consistent hashing isn't a one-off trick — it's the standard answer whenever a system needs to distribute keys across a changing set of machines without a full reshuffle on every change: it underlies database sharding, Dynamo-style key-value stores, and distributed caches alike.