Consistent Hashing

Suppose you run a cache or a database split across several servers, and you decide which server owns a key with simple modulo arithmetic: server = hash(key) % N, where N is the number of servers. With three servers this is fine. The trouble starts the moment N changes.

Add a fourth server and N goes from 3 to 4. Now hash(key) % 4 gives a different answer than hash(key) % 3 for almost every key. In practice somewhere around 75 to 100 percent of keys suddenly map to a different server. For a cache that means a near-total miss storm: every lookup misses, every miss falls through to the database, and the database gets hit with the full traffic it was being shielded from. For a sharded database it means moving almost all of your data between nodes just to add one machine.

Servers do not stay fixed. They crash, they get added during traffic spikes, they get removed when load drops. A scheme that reshuffles everything on each change is unusable at scale. Consistent hashing exists to make that change cheap.

Instead of hashing into a small range of server indexes, consistent hashing hashes into a large fixed space, for example the integers from 0 to 2^32 minus 1, and treats that space as a circle. The end wraps back around to the start.

Every server is hashed onto a point on this circle, usually by hashing its name or IP address. Every key is hashed onto the circle the same way. To find which server owns a key, you start at the key's position and walk clockwise until you hit the first server. That server owns the key.

The important part is what happens on change. When you add a server, it lands somewhere on the circle and takes over only the keys that sit between it and the previous server going counter-clockwise. Every other key keeps the same owner. When a server leaves, only its keys move, and they all go to the next server clockwise. Either way you disturb roughly 1/N of the keys, not the whole set.

A plain ring has two weaknesses. First, with only a few servers placed at random points, the gaps between them are uneven, so one server can end up responsible for a much larger arc of the circle, and therefore much more traffic, than the others. Second, when a server dies, its entire share lands on the single neighbor clockwise from it, which can overload that one machine.

The fix is virtual nodes. Each physical server is placed on the ring not once but many times, often 100 to 200 times, by hashing names like server-A#1, server-A#2, and so on. Now each physical server owns many small arcs scattered around the circle instead of one big arc. The load evens out, and when a server fails its share is spread across many neighbors rather than dumped on one.

Virtual nodes also let you weight servers. A machine with twice the memory can be given twice as many points on the ring, so it naturally takes twice the share of keys.

Consistent hashing is more complex than modulo. You need a sorted structure of ring positions, typically a balanced tree or a sorted array with binary search, so that the clockwise lookup is fast. With virtual nodes you also store many more positions, which costs a little memory and makes the ring metadata something every node has to agree on.

It reduces how many keys move on a membership change, but it does not give you fault tolerance by itself. If the single server that owns a key dies, that key is gone unless you also replicate it. Real systems combine consistent hashing for placement with replication to the next few servers clockwise for durability.

Choosing the number of virtual nodes is a tuning decision. Too few and the load is lumpy. Too many and the ring metadata and rebalancing bookkeeping grow. Most production systems settle somewhere in the low hundreds per physical node.