Consistent Hashing: Resizing Distributed Systems Gracefully

WHY IT EXISTS In a distributed system with N servers, a simple way to map a key to a server is hash(key) % N. The problem is that if you add or remove a server, N changes, and nearly every key maps to a new server. This forces a massive, system-wide data migration, which can be catastrophic for a distributed cache or database, causing a 'thundering herd' problem.

THE MENTAL MODEL Imagine a clock face or a ring. Consistent hashing places both servers and data keys on this ring based on their hash values. To find which server a key belongs to, you find the key's position on the ring and then walk clockwise until you hit the first server. That server is the owner of the key.

HOW IT WORKS When a new server is added, it's placed on the ring. It only takes ownership of the keys that fall between its position and the server immediately counter-clockwise to it. All other key mappings remain untouched. Similarly, if a server is removed, its keys are simply reassigned to the next server clockwise on the ring. This contains the 'blast radius' of the change, ensuring only a small fraction of keys (k/n on average) are remapped, unlike the near-total remapping of the modulo approach.

WHEN TO USE IT Use consistent hashing when you need to distribute data or requests across a set of servers that can change in size. It is fundamental to distributed caching systems (like Memcached), load balancers, and distributed databases (like Amazon's DynamoDB or Apache Cassandra) where nodes can join or leave the cluster.

WHEN NOT TO USE IT For systems with a fixed, unchanging number of nodes, the simpler modulo-based hashing is sufficient and easier to implement. It's also unnecessary for single-machine, in-memory hash tables where resizing is not a distributed operation.

ONE CANONICAL EXAMPLE A distributed cache with 10 servers uses consistent hashing. If one server fails, only the keys that were stored on that specific server need to be remapped to its clockwise neighbor on the ring. The other 9 servers and their cached data are completely unaffected. If they had used hash(key) % 10, the failure would force a move to hash(key) % 9, causing almost every key to map to a new server and effectively invalidating the entire cache at once.