Consistent Hashing
In short: plain sharding with hash(key) % num_nodes reassigns almost
every key the moment num_nodes changes, because the modulus itself changed.
Consistent hashing places both nodes and keys on the same hash
ring (a fixed range like 0..359, wrapping around), and assigns each key
to the first node it meets going clockwise. Adding a node only steals the arc
of keys between it and the previous node clockwise — every other key's
nearest node never changes. With few nodes, one node's arc can still end up
much bigger than another's by chance; virtual nodes (each real node
placed at many positions on the ring) fix that by averaging away the luck.
Only k6 moves — from C to the new D, because D's ring position (16)
sits between B (12) and C (19), right where k6 (15) already was. k1,
k3 and k4 land on positions D can't reach, so their owners don't change
at all.
Add a node without reshuffling the whole cluster
Quarry compares how many of 8 keys actually move when a third node joins, under consistent hashing versus plain modulo sharding:
Consistent hashing moves 1 key; modulo sharding moves 7 of the same
8 — because hash(key) % 2 and hash(key) % 3 agree on almost nothing, even
though only one node was added.
Flatten node load with virtual replicas
With only one ring position per node, luck decides how big each node's arc is — a small cluster can end up badly unbalanced. Quarry places each real node at many ring positions instead, and the imbalance shrinks:
One position per node gives A 53 keys and C only 14 — a 39-key spread out
of 100. Twenty positions per node brings that down to a 20-key spread: more
independent coin-flips per node average out the luck, without moving a
single key off the ring's basic rule.
A common mistake: counting ring positions when you mean to count
nodes. A#0 through A#19 are twenty entries on the ring, but they are
still one node — A — for every purpose except "which arc does this key
land in":
nodes = ["A", "B", "C"]
replicas = 20
ring_entries = len(nodes) * replicas
print(ring_entries == len(nodes))Quick practice
positions = [(40, "A"), (200, "B"), (310, "C")]
key_pos = 350
owner = next((n for pos, n in positions if pos >= key_pos), positions[0][1])
print(owner)counts_plain = {"A": 59, "B": 32, "C": 9}
counts_virtual = {"A": 34, "B": 39, "C": 27}
def spread(counts):
return max(counts.values()) - min(counts.values())
print(spread(counts_plain) > spread(counts_virtual))🎯 Your turn
Build keys_moved_on_add(keys, nodes, new_node, seed): return how many of
keys change which node they're assigned to when new_node joins the ring.
keys_moved_on_add(['k1','k2','k3','k4','k5','k6','k7','k8'], ['A','B'], 'C', seed=1)→1
Hint: assign_keys first — sort (ring_position(node), node) pairs,
then each key goes to the first node whose position is >= the key's,
wrapping to the first node otherwise. Then just compare before/after.
Press ▶ Run, try the Live App chips, then ✓ Check.