Consistent hashing
Consistent hashing changes how keys map to servers so that adding or removing a node moves as few
keys as possible — about 1/N instead of (N−1)/N.
- Rehashing problem
- With hash(key) % N, changing N by one remaps (N−1)/N of all keys, causing a cache avalanche onto the backing store.
- Virtual node
- One of many ring positions mapped back to the same physical server, used to even out how much of the ring each server owns.
The ring
Place both servers and keys on a circular hash space (0 to 2³²−1). To find a key’s owner, hash the key to a position and walk clockwise to the first server you meet. Adding a server only steals keys from the segment immediately behind it; removing one hands its segment to the next server clockwise. Everything else stays put.
Virtual nodes
With only a few servers, random ring positions produce lopsided segments — one server owns half the ring, another a sliver. The fix is to give each physical server many positions (typically 100–200 virtual nodes), so the law of averages flattens the load. More virtual nodes means smoother balance at the cost of a larger ring table.
Where it’s used
Amazon DynamoDB and Apache Cassandra partition data this way; Discord uses it to route sessions, and CDNs like Akamai use it to pin content to edge caches. Any system that adds and removes nodes without reshuffling the whole dataset is leaning on consistent hashing.
Check yourself
1You route cache keys with hash(key) % N. One of 10 nodes dies. Roughly how many keys remap?
Changing N from 10 to 9 changes the modulo result for about (N−1)/N ≈ 90% of keys — they all miss cache at once and stampede the database.
2How does consistent hashing bound the damage when a node is added or removed?
Keys and servers share one hash ring. Adding/removing a node only reassigns the keys on the affected segment — about 1/N — not the whole keyspace.
3What problem do virtual nodes solve?
A handful of physical servers placed at random ring positions own wildly uneven arcs. Giving each server 100–200 virtual positions averages the load out.