Consistent hashing

A store with many nodes has to decide which node holds each key. The simplest rule is hash(key) mod N. It works until N changes, and then almost every key moves. Consistent hashing gives the same spread, but adding or removing a node moves only a small share of the keys.

The big idea

Think of a clock face with the nodes placed around it. A key goes to the first node clockwise from its hash. Adding a node means it takes over the arc just before it. Only the keys on that arc move.

The picture breaks down when nodes have very uneven arcs. One node may then own far more keys than the rest. Virtual nodes fix that.

Walking through it

Compare the two rules on the same keys. Hash values are 0 to 11. The program below runs as written.

keys = range(12)

moved = sum(1 for k in keys if k % 3 != k % 4)
print(f"{moved} of {len(keys)} keys move when going from 3 to 4 nodes")

Output:

9 of 12 keys move when going from 3 to 4 nodes

Modulo-based placement moves 9 of 12 keys, or 75%. On the ring, a new node takes an arc from its neighbor. On average, a fourth node takes about a quarter of the keys, and each one comes from a single neighbor.

Virtual nodes spread that load. Give each physical server 100 to 200 positions on the ring. When a new server joins, only the tokens it claims move. The share moved is roughly the new server's virtual nodes divided by the total.

Streaming the moved data should be throttled, so it does not slow live traffic.

Common mistakes

• One position per server. Arcs come out uneven, and one server takes too much load.
• Expecting the ring to split a hot key. All requests for one key still go to one node. Split or cache that key at the application layer.
• Moving data at full speed. A rebalance can swamp the nodes that serve reads and writes.

Check yourself

1. Why does adding a node to a mod N scheme move most keys? The divisor changes, so most remainders change, and most keys land on a different node.
2. What do virtual nodes fix? Uneven arcs and uneven load, especially across servers of different sizes.

Key takeaways

• Consistent hashing places keys and nodes on a ring.
• A key belongs to the next node clockwise.
• Adding a node moves only the keys on its arc.
• Virtual nodes even out the load across servers.

Further learning

Next, see how replicas are chosen and how many must answer in quorum reads and writes.

For the full design that uses this ring, see the distributed key-value store case study.