If you spread data across several servers, your first instinct is the modulo operator: data % number_of_nodes. It is simple, reliable, and it works. Until a node dies, a new one joins, or you simply want to scale the cluster out. At that instant, that number_of_nodes changes and nearly all your data jumps to a different home at once. To avoid that cascade of reallocations there is an elegant idea holding up dozens of production systems: consistent hashing.
The modulo problem
Imagine a distributed cache with four nodes and a hash function that turns every key into a number. With the classic approach, the node that stores user_1234 is computed as hash(key) % 4. All is well while there are four. If a node dies and you drop to three, hash(key) % 3 maps almost every key to a different output: between 75 and 100 percent of your data would need to migrate. For a cache, that means a massive cache miss, and behind it, every data origin suddenly receives an avalanche of requests.
The modulo is only stable while the node set never changes. In real systems it changes constantly: failures, scaling, maintenance. We need a function that absorbs those changes with minimal damage.
The ring idea
Consistent hashing changes the whole picture. Instead of a linear table, imagine a ring (mathematically, a circle with 2^32 positions, the typical hash output range). Hash each server and place it at a ring position. Hash each key too. Then, to find which node holds a key, walk the ring clockwise from the key’s position until you find the first node.
The crux is that each node no longer owns an exact share of the space: it owns the arc running from the previous node’s position up to its own. When a node joins the ring, it only absorbs the keys of that arc, which on average is 1/N of the total. When a node dies, only its keys move to the next neighbour. Instead of migrating almost everything, you migrate a tiny fraction.
Virtual nodes: against skew
The theory is flawless, but node hashes land in random positions. With few nodes, some arcs can end up huge and others tiny: one node may end up with 60% of the keys and another with 5%. To smooth this distribution skew, introduce virtual nodes (vNodes): each physical node is replicated, say, 100 or 150 times, and every replica gets a different ring position with its own hash (for example computed as hash(node + "_" + replica)).
With hundreds of evenly spread points, the space is split far more evenly. The effect mirrors sampling many times: the law of large numbers flattens the irregularities. What was a problem of three points on a circle becomes one of hundreds of points, and the differences vanish.
Where consistent hashing lives today
- Distributed caches: Memcached (the libketama algorithm), DynamoDB, Cassandra and Riak use variants of this idea to spread and replicate data with fault tolerance.
- CDNs and edge caches: decide which edge node serves a request according to the client, minimising rerouting as the infrastructure changes.
- Distributed search (DHT): Chord and Kademlia structure their networks over hash rings; each node is responsible for a key range and barely touches neighbouring indexes when it joins or leaves.
- Load balancers and service discovery: tools such as nginx’s consistent-hash and client libraries pick nodes stably across requests.
Modern alternatives
Classic consistent hashing is not the only answer. Rendezvous hashing (or highest-random-weight) picks the node that maximises hash(key || node), no ring needed and with the same stability property, ideal when nodes have different weights. And jump consistent hash distributes keys flawlessly with a single variable in memory, O(1) memory cost and no virtual nodes, at the price of not supporting extra replicas.
The technical takeaway goes beyond this example: before designing a distributor, define what must survive a resize. If it is the large majority of assignments, modulo is not your friend. A hash ring — or one of its cousins — lets you lose a minimal fraction and keep serving without the whole system suddenly remembering that a node is gone.
