Consistent hashing
Add or remove a machine and move only a small slice of the keys, not all of them.
What problem does consistent hashing solve?
The obvious way to spread keys across servers is to hash the key and take the remainder by the server count. It spreads evenly, and it has one fatal property. Change the server count and almost every key maps somewhere new.
For a cache that means nearly every request misses, at the exact moment you were adding capacity. For a datastore it means moving nearly all your data. Consistent hashing makes the change proportional instead.
What consistent hashing costs you
Every concept in here states a cost. A technique with no price is a technique you have not understood yet — and naming the cost out loud is most of what separates a senior answer from a junior one.
When to reach for consistent hashing, and when not to
Use it when
- A cache cluster whose size changes. This is the classic case.
- Sharded datastores where you want to add machines without a full reshuffle.
- Sending users to a specific server, so their connection or their cached data stays put.
Do not, when
- A fixed set of shards that never changes. A plain remainder is simpler, and simpler wins.
- When you can use the pre-sized logical partition trick instead (1024 partitions mapped onto N machines), which is often easier to think about and to run.
How consistent hashing actually works
With a remainder, a key that hashed to 7 moves from server 3 to server 2 for no reason except that the divisor changed. Consistent hashing only reassigns the slice the new server takes over.
The idea: picture the hash space as a circle. Each server sits on the circle at a few positions, decided by hashing its name. A key is hashed onto the same circle, and belongs to the first server clockwise from it. Add a server and it takes over only the arc just behind its positions. Every other key keeps its home. Remove a server and its arc goes to the next server clockwise.
Virtual nodes are not optional. With one position per server, the arcs come out badly uneven, and some servers get twice the keys of others. Worse, removing a server dumps its whole load onto one neighbour. Give each server one or two hundred positions and both problems go away. Load evens out, and a departing server's keys spread across all the remaining ones. It also lets you give a bigger machine more positions, and so more work.
What it does not solve: one key that everyone wants. Consistent hashing decides where a key lives. If that one key gets a million requests a second, its server is hot no matter how neatly you assigned it. That needs the hot key copied to several places, or a separate path. This difference is a common follow-up question.
Where you will meet it: memcached client libraries, Cassandra and Dynamo-style stores for assigning partitions, and layer 7 load balancers routing by session or by cache affinity.
- Describing the ring but leaving out virtual nodes. The balancing behaviour depends on them.
- Claiming it solves hot keys. It does not.
- Using it where a fixed partition count would have been simpler.
The consistent hashing follow-up an interviewer will ask
"You add a cache node. What happens to your database in the next minute?"
It takes a spike, and the question is really about the size of that spike. With remainder hashing, roughly every key just moved, so nearly every request is a miss and the database briefly takes the full read load. At the ratios that made me add a cache in the first place, that may take it down. That is a painful way to fail: your capacity increase caused the outage. With consistent hashing, only about one in N keys moves, so I get a small, survivable spike of misses. Either way I would not just add the node and hope. Bring it in during quiet traffic, warm it first if I can, and make sure misses on the same key are coalesced, so one cold key means one database read instead of ten thousand.
Your turn
Why are virtual nodes necessary? Name the specific failure they prevent.
Learn it from the source
This page gets you interview-ready. These take you to where the idea is actually specified or measured — read them when you want the real depth.
- Consistent hashing ↗The original technique and the virtual-node refinement that makes it usable.