Why consistent hashing works the way it does

Suppose a cache lives on four machines. A simple assignment rule is to hash a key and take the result modulo four. It is fast, deterministic, and easy to explain.

Then you add a fifth machine. The same hashes now produce different remainders. A large fraction of keys change owners, even though the cluster changed by only one machine. A small physical change causes a large logical disruption.

Replace the list with a circle

Place both keys and machines on a circular hash space. A key belongs to the first machine encountered when moving clockwise. The end wraps back to the beginning.

Now insert a machine between two existing ones. It takes responsibility for one interval: the keys between its predecessor and itself. Other intervals keep the same owners.

Local change, local consequences

The useful property is not the circle itself. It is the limited movement. With a well-distributed hash and balanced ownership, adding one machine to N existing machines moves approximately 1/(N + 1) of the keys in expectation.

Remove a machine, and its interval passes to the next surviving machine. The system still needs to transfer data, handle requests in flight, and decide when ownership changes take effect. Consistent hashing solves placement; it does not, by itself, solve consistency.

Why virtual nodes exist

Real hash positions are uneven. One physical machine can occupy several positions on the ring, called virtual nodes. Spreading those positions helps distribute load and allows machines with different capacities to own different shares.

The word “helps” matters. A good distribution of key counts does not guarantee balanced request volume. A single popular key can dominate traffic. Replication, request routing, and hot-key handling are separate decisions.

A pattern worth keeping

When the membership of a system changes, ask how much unrelated state must move. The answer often reveals more about an architecture than its steady-state diagram.