The problem with plain modulo
A simple way to place a key on one of N servers is to take a hash and compute it modulo N. It works until N changes. Add or remove one server and almost every key now maps somewhere new, forcing a massive reshuffle of data and cache misses everywhere.
The ring
Consistent hashing places both servers and keys on a circular hash space, often pictured as a ring. A key belongs to the first server found by walking clockwise from the key position.
- Adding a server only steals keys from its immediate neighbor.
- Removing a server hands its keys only to the next server clockwise.
So a change of one node moves on average just one over N of the keys instead of nearly all of them.
Virtual nodes
A single position per server leads to uneven splits. The fix is virtual nodes, where each physical server is placed at many points around the ring. This evens out the load and lets stronger machines own more virtual nodes.
Consistent hashing powers distributed caches, sharded databases, and content delivery routing.
Key idea
Hashing keys onto a ring means adding or removing a node moves only a small fraction of the keys.