Consistent hashing concepts

The first idea most people have for spreading keys over several servers is hash(key) % N: hash the key and use the remainder modulo the server count as the server index. It is fast and evenly balanced, but it has one serious flaw: when N changes, almost every key lands on a different server. Consistent hashing, introduced by Karger et al. in 1997 for distributed web caching, is designed so that adding or removing a server moves only the keys that really have to move.

The trouble with mod-N sharding

Picture a cache with 10,000 keys spread over 4 servers. Grow it to 5 servers and only keys with h % 4 == h % 5 stay put. With well-spread hashes that is about 1/(N+1) of them, so roughly N/(N+1) of the keys, 80% here, move. Going from 10 to 11 servers moves about 91%.

import hashlib

def h(key: str) -> int:
    return int.from_bytes(hashlib.md5(key.encode()).digest()[:8], "big")

keys = [h(f"user:{i}") for i in range(100_000)]
for n in (4, 10):
    moved = sum(k % n != k % (n + 1) for k in keys)
    print(n, "->", n + 1, f"{moved / len(keys):.0%}")
# 4 -> 5 80%
# 10 -> 11 91%

For a cache, that means the hit rate collapses to nearly zero and every request falls through to the database at once. For a data store it means reshuffling the whole dataset. Losing a server to a failure triggers exactly the same storm.

The ideal

When N servers become N+1, the newcomer needs a fair share, so 1/(N+1) of the keys must move to it. Consistent hashing aims to move exactly that much, and only onto the new server; existing servers never trade keys among themselves. When a server leaves, only its own keys are redistributed.

Properties of a good scheme

The original paper lists the properties a good distribution scheme should have:

• Balance: keys are spread evenly across nodes.
• Monotonicity: when a node is added, keys move only from old nodes to the new one, never between old nodes.
• Spread and load: even when clients have slightly different views of the node list, a key is not scattered over too many nodes and no node receives too many keys.

The hash ring

The best-known form is the hash ring. Treat the whole hash space, say 0 to 2^64 - 1, as a circle whose end wraps around to the start.

• Hash each server's name to a point on the ring (its token or position).
• Hash each key with the same function to a point on the ring.
• Walk clockwise from the key; the first server you meet owns the key.
• If you pass the largest position, wrap around to 0 and keep looking.

When a server joins, only the keys between its position and the previous server (counter-clockwise) change owner. The rest of the ring is untouched.