Consistent Hashing
Add and remove nodes, watch which keys move, and compare with naive modulo hashing.
How Consistent Hashing Works
The classic way to spread keys across N servers is modulo hashing: server = hash(key) % N. It works great — until you add or remove a server. When N changes, almost every key maps to a different server. If you're running a distributed cache, that's a thundering herd of cache misses.
Consistent hashing fixes this by mapping both servers and keys onto the same circular space — a hash ring. Each server gets a position on the ring (its hash), and each key is assigned to the first server found clockwise from the key's position.
Why only K/N keys move. When you add a 4th node to a 3-node ring, it lands somewhere on the ring and takes over a slice of keys from exactly one existing node. The other nodes are unaffected. On average, only 1/N of keys need to move — around 25% for 4 nodes, compared to ~75% with modulo. Try it above: add a node and watch the stats.
Virtual nodes. With just one position per server, the key distribution can be uneven — one server might own a huge arc while another owns a sliver. Virtual nodes fix this: each physical server gets multiple positions on the ring. More positions means more even distribution. The tradeoff is a bit more bookkeeping, but in practice everyone uses virtual nodes. Toggle them above to see the difference.
Where it's used. Consistent hashing shows up everywhere in distributed systems: Amazon's Dynamo, Apache Cassandra, Memcached, CDN routing, and load balancers. Any time you need to spread load across a changing set of servers without reshuffling everything, consistent hashing is the go-to approach.