Sharding With Consistent Hashing: Why Adding a Server Moves So Few Keys

The obvious rule: hash, then mod

The first rule most people try: a hash function turns the user id into a big number: the same id always gives the same number, and different ids spread evenly.

Then divide by the number of servers and keep the remainder, called mod and written %. With 4 servers, hash % 4 gives 0, 1, 2 or 3, which picks s0, s1, s2 or s3. The trouble starts the day the server count changes.

Count what moves

Now apply the rule to every key, not just one. A key stays on its server only when hash % 4 and hash % 5 happen to give the same answer.

In a fair world the new server takes a fifth of the keys and nothing else changes. Mod is not that fair.

Bend the line into a ring

Consistent hashing asks a different question. Picture every possible hash value laid out round a circle, like a clock face. To keep the numbers small, we use positions 0 to 99.

Servers go on the same circle: hash each server's name, and the result is its position. A lands at 10, B at 40 and C at 75. Keys are hashed onto the circle too, so servers and keys share one map.

Walk clockwise

To find a key's server, start at the key's position and walk clockwise until you meet a server. Key 42 walks past 43, 44 and onwards until it reaches C at 75, so C owns it. Key 90 walks past 99, wraps round to 0 and stops at A at 10. Each server owns the stretch of ring just before it.

Add a server

Now add server D. Its name hashes to position 55, between B at 40 and C at 75.

Nothing else on the ring moves: A, B and C keep their positions, and so does every key. Only a key whose clockwise walk now meets D before anything else can change hands.

Measured on a million keys

Back to a million keys and a real hash function, MD5. In this test each server sat at one position on the ring. Growing from 4 servers to 5 moved 17.21% of the keys, against 80.03% for mod.

Every key that moved went to the new server, and none moved between two old ones. Why 17% and not a fair 20%? The next step shows.

The catch: uneven arcs

Servers land wherever their hash puts them, so the stretches between them have random lengths. With one point per server, our five servers ended up owning 27.9, 1.8, 26.7, 26.4 and 17.2 percent of the keys. One server held almost nothing while three carried more than a quarter each, and even load was the reason we sharded in the first place.

Virtual nodes

The usual fix is virtual nodes. Node is another word for server. Instead of hashing a server's name once, hash it 100 times under slightly different names: s0#0, s0#1, s0#2 and so on.

Each server now owns 100 small arcs instead of one big one, and the random lengths average out. With 100 points each, our five servers held between 18.3 and 21.0 percent of the keys.

And removing a server

With 100 virtual nodes, growing from 4 to 5 servers moved 19.85% of the keys, close to the fifth the new server should own.

Removing a server works the same way in reverse. Only its keys move. Its points are scattered round the ring, so its keys spread over all the remaining servers instead of piling onto one neighbour.

Run it yourself

Here is the same experiment, small enough to run in your browser: 20,000 user ids, hash mod N against a ring. Press Run.

Then change VNODES to 1 and run it again, or set AFTER to 6 or to 3. Watch two numbers each time: the share of keys that moved, and how evenly the servers are loaded afterwards.

import hashlib, bisect

KEYS = 20_000          # user ids to place
BEFORE, AFTER = 4, 5   # servers before and after the change
VNODES = 100           # points per server on the ring (try 1)

def h(s):
    return int.from_bytes(hashlib.md5(s.encode()).digest()[:8], "big")

keys = [h(f"user:{i}") for i in range(KEYS)]

def ring(n):
    pts = sorted((h(f"s{s}#{v}"), f"s{s}") for s in range(n) for v in range(VNODES))
    return [p for p, _ in pts], [s for _, s in pts]

def owner(r, x):
    i = bisect.bisect(r[0], x) % len(r[0])
    return r[1][i]

old, new = ring(BEFORE), ring(AFTER)
moved_mod = sum(x % BEFORE != x % AFTER for x in keys)
moved_ring = sum(owner(old, x) != owner(new, x) for x in keys)
print(f"hash % N  : {100 * moved_mod / KEYS:.1f}% of keys moved")
print(f"hash ring : {100 * moved_ring / KEYS:.1f}% of keys moved")

load = {}
for x in keys:
    s = owner(new, x)
    load[s] = load.get(s, 0) + 1
print("ring load :", ", ".join(f"{s} {100 * n / KEYS:.1f}%" for s, n in sorted(load.items())))

Python, running in your browser. With the defaults it printed 80.1% for mod, 20.0% for the ring, and loads of 18.2% to 21.1%.

Where you meet it

Apache Cassandra, a database built to run on many servers, places data this way. Its documentation says each node owns one or more tokens, which are positions on a hash ring, and a key belongs to the node found by walking the ring in one direction.

Copies go to further nodes along that walk. The same ring idea appears in load balancers and caches that keep each user on one server.

What it does not fix

Consistent hashing spreads keys. It does nothing for one key that gets far more traffic than the rest. A celebrity's profile still hashes to one point, so one server takes all of its load.

And because hashing scatters neighbouring ids, a query for a range of users, say ids 1 to 1,000, has to ask every server.

Mod against the ring, side by side

With hash mod N, every key depends on the server count, so changing the count reshuffles most of them: 80% when we went from 4 servers to 5.

On a ring, a key depends only on the next server point clockwise. A new server takes the arcs just before its points, about a fifth here, and virtual nodes keep the arcs even. One hot key still has one owner.