Consistent hashing sounds scary. It isn't. It's a trick for spreading data across servers so that adding or removing a server moves as little data as possible.
That's the whole idea. Everything below is just how you get there.
The problem with the obvious approach
Say you have data you want to split across servers. Cache entries, user sessions, shards of a database, whatever. You need a rule that, given a key, tells you which server holds it.
The obvious rule is modulo. Hash the key to a number, then take that number mod the count of servers.
server = hash(key) % number_of_servers
With 4 servers, hash(key) % 4 gives you 0, 1, 2, or 3. Done. It spreads keys evenly and it's fast.
It works fine until the server count changes. Add a fifth server and your rule becomes % 5. Almost every key now maps to a different server than before. For a cache, that means almost every lookup misses and you re-fetch everything at once. For a database, it means moving almost all your data.
That's the failure. Modulo couples every key to the exact number of servers. Change the number, reshuffle the world.
The ring
Consistent hashing fixes this by not using the server count in the formula at all.
Picture a circle. Hash values run around it from 0 back to 0. A common version uses the range of a 32-bit or 64-bit hash, but the size doesn't matter for the idea.
Now place your servers on that circle. Hash each server's name or IP and drop it at that point on the ring.
To find which server owns a key, hash the key to get a point on the ring, then walk clockwise until you hit the first server. That server owns the key. That's it.
key -> hash -> point on ring -> walk clockwise -> first server you meet
The count of servers never appears in that lookup. Each server is just responsible for the arc of the ring between itself and the previous server going counter-clockwise.
Why adding a server is cheap now
Add a new server. It hashes to some point and slots into the ring. The only keys that move are the ones in the arc it just took over, and those come from one neighbor.
Everything else stays where it was. No global reshuffle.
Remove a server, say it crashed, and its arc gets absorbed by the next server clockwise. Again, only that one slice of keys moves.
Compare that to modulo, where one change touches nearly everything. With consistent hashing, adding or removing one server out of N moves roughly 1/N of the keys. That's the payoff, and it's the line worth remembering.
The uneven load problem, and virtual nodes
There's a catch with the basic ring. If you only place each server at one random point, the arcs come out uneven. One server might own a huge slice and another a tiny one. Random points don't space themselves out neatly.
The fix is virtual nodes. Instead of placing each physical server once, place it many times, say 100 or 200 points, by hashing server-name-1, server-name-2, and so on. Each physical server now owns many small arcs scattered around the ring instead of one big one.
More points means the slices average out and load gets more even. It also makes failure smoother. When a server dies, its many small arcs spread across all the remaining servers instead of dumping onto one unlucky neighbor.
Virtual nodes are the part people forget in interviews. Mention them and you sound like you've actually used this.
Where you'll meet it
You don't have to implement consistent hashing yourself to run into it. It shows up in distributed caches like a memcached cluster behind a smart client, in databases like Cassandra and DynamoDB-style systems for partitioning, and in load balancers that want the same client to keep landing on the same backend.
If you've used any of those, you've used consistent hashing without writing a line of it.
How to explain it in an interview
Keep it in this order and you'll cover what matters:
- State the problem. Modulo reshuffles almost all keys when the server count changes.
- Describe the ring. Servers and keys both hash onto a circle; a key belongs to the first server clockwise.
- Give the payoff. Adding or removing one server moves about 1/N of the keys, not all of them.
- Add virtual nodes. Multiple points per server even out the load and smooth out failures.
If you can draw the circle, place three servers, drop a key, and walk it clockwise to its owner, you've shown you understand it for real. That beats reciting a definition.
This is one of those topics that's easy to nod along to and hard to explain cold. Try saying it out loud, ideally in a mock interview, until the four steps come without thinking. That's the difference between recognizing consistent hashing and being able to teach it on a whiteboard.