Consistent hashing
Consistent hashing assigns keys to servers so that adding or removing a server moves only a small share of the keys.
Why it matters
If you place keys with hash(key) % N, adding or removing one server changes N and almost every key moves. For a cache, that means almost every request suddenly misses at once.
The idea
With simple hash(key) % N, changing N from 4 to 5 moves almost every key, which is a disaster for a cache. Consistent hashing places both servers and keys on a ring; each key belongs to the next server clockwise. Adding a server only takes keys from its neighbour. Virtual nodes, where each server appears many times on the ring, keep the load even.
A round table where each guest serves the dishes between themselves and the guest before them. A new guest sitting down only takes dishes from one neighbour.
At a table, guests sit evenly spaced. Random positions on the ring are uneven, so one server can end up with far more keys. Virtual nodes fix this by giving each server many seats.
How it works
- Picture a ring of numbers from 0 up to a huge maximum.
- Hash each server's name to a position on the ring. With virtual nodes, each server gets many positions.
- Hash each key to a position, then walk clockwise to the first server you meet: that server owns the key.
- Add a server: it only takes the keys between itself and the server before it. Everything else stays where it is.
- Remove a server: its keys move to the next server clockwise — spread across many servers if you use virtual nodes.
Example
Going from 4 to 5 servers with hash % N moves about 80% of the keys. With consistent hashing, only about 20% (roughly 1 in 5) move.
Key points
- hash % N moves most keys whenever N changes.
- The ring: a key belongs to the first server clockwise from it.
- Adding or removing a server moves about 1/N of the keys.
- Virtual nodes even out the load and spread a dead server's keys across many others.
- Used in: Cassandra, DynamoDB, distributed caches, some load balancers.
Common mistakes
- Too few virtual nodes, so the load is uneven.
- Assuming it fixes hot keys. It doesn't.
- Forgetting replication: each key usually lives on the next 2–3 servers on the ring, not just one.
Not true: Consistent hashing stops one very popular key from overloading a server.
In fact: It spreads the keys evenly, but one hot key still lives on one server. Hot keys need their own fix, such as caching or splitting the key.
Not true: Routing with hash % N moves only a few keys when a server is added.
In fact: Changing N changes the result for almost every key. On a consistent-hashing ring, adding a server moves only about 1/N of them.
In the interview
For a distributed cache or a sharded store I'd use consistent hashing with virtual nodes. Adding or removing a node then moves only about 1/N of the keys, instead of nearly all of them, and the load stays balanced.
Part of Unit 3: Data: databases, storage and scaling data in the free System Design course.