Consistent hashing, explained

When a cache or a database is spread over many machines, every key needs a home. The obvious rule is to hash the key and take the remainder after dividing by the number of machines. It works until the number of machines changes.

The trouble with remainders

Add a fifth server to a cluster of four and the divisor changes from four to five. Almost every key now lands on a different server, so nearly the whole cache misses at once and the database behind it takes the full load.

What we want instead is a rule where adding or removing one machine moves only the keys that machine should own, about one key in n, and leaves the rest where they were.

The ring

Consistent hashing maps both machines and keys onto the same circle of hash values. A key belongs to the first machine found by walking clockwise from the key's position.

When a machine joins, it takes over only the arc between itself and the machine before it. When one leaves, its arc passes to the next machine along. Every other key stays put.

Virtual nodes

With only a few machines on the ring, the arcs come out uneven and one machine can end up owning far more than its share. The fix is to place each machine on the ring many times, as virtual nodes, so the arcs average out.

Virtual nodes also make weighting simple: a machine with twice the memory gets twice as many points on the ring.

Where it is used

Distributed caches, peer-to-peer networks and partitioned databases such as Dynamo and Cassandra all place data this way. Load balancers use it too, to keep a returning client on the same backend.