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.

0 ---- A(10) ---- B(45) ---- C(80) ---- 99, then back to 0
key 7  -> first node clockwise is A
key 33 -> B
key 52 -> C
key 91 -> past the end, wrap around to A

Virtual nodes

With a single point per server, the gaps between points are left to chance. With 10 servers and one point each, one server may own several times the average while another sits nearly idle. The fix is to hash each server under many names, A#0, A#1, and so on, giving it many points on the ring. These are virtual nodes (vnodes). The more points, the closer each server's total share gets to the average, and when a server leaves, its load spreads over many servers instead of one neighbour. Giving a bigger machine more vnodes expresses a capacity weight.

node = "cache-a"
names = [f"{node}#{i}" for i in range(4)]
print(names)  # ['cache-a#0', 'cache-a#1', 'cache-a#2', 'cache-a#3']
# each name is hashed separately: 4 points on the ring for one server

Other approaches

The ring is not the only design.

• Rendezvous hashing (highest random weight, HRW): for each key, score every server with hash(server, key) and pick the highest. No ring is needed and the code is tiny, but each lookup touches every server.
• Jump consistent hash: published by Lamping and Veach at Google in 2014, it maps a key to a bucket number 0..N-1 using no memory. Buckets can only be added or removed at the end.
• Fixed slots: Redis Cluster does not use a ring. It has 16,384 hash slots (CRC16(key) mod 16384) explicitly assigned to nodes. The goal is similar, the design is different.

Vocabulary

When to use it

Reach for it when membership changes at runtime and moving a key is expensive: a cache miss, a data copy, a lost session. Distributed cache clients, Dynamo-style key-value stores and load balancers that need request affinity are the classic cases. If the node count is fixed, or moving keys costs almost nothing, plain % N is fine.

Summary

• hash % N moves about N/(N+1) of the keys whenever N changes.
• Consistent hashing aims to move only the unavoidable 1/(N+1).
• On a hash ring, the first node clockwise from the key owns it.
• Virtual nodes even out the load and express weights.
• Rendezvous hashing, jump hash and fixed slots solve the same problem differently.