A cluster grows from 10 nodes to 11 and 200,000 keys are re-placed. Naive hash % N moves 90.87% of them and sends 163,493 hopping between two old nodes that never changed. Rendezvous (consistent) hashing moves only 8.99% — roughly 1/11 — and every one lands on the new node: the count of movers going anywhere else is exactly 0.
A cluster grows from 10 nodes to 11 and 200,000 keys have to be re-placed. Two ways to decide where each key lives. With naive hash % N, changing N from 10 to 11 re-computes almost every key's home: 90.87% of keys move, and — the part that stings — 163,493 of the movers hop between two old nodes that never changed, pure churn for no reason. With consistent hashing (implemented here as rendezvous / highest-random-weight hashing), only 8.99% of keys move — roughly 1/11 — and every single one of them lands on the brand-new node. The count of movers that go anywhere other than the new node is exactly 0. Same keys, same new node; the only difference is whether the placement function was built to be stable under a change in N.
Designing Data-Intensive Applications, 2nd ed. (Kleppmann & Riccomini, 2025), Chapter 7 — Sharding, §"Consistent hashing":
Consistent hashing [...] avoids the problem [that] adding or removing a node would require almost all the data to be rehashed and moved.
The book contrasts hash-mod-N partitioning — where changing the number of nodes reshuffles nearly all keys — with consistent hashing, where adding or removing a node moves only a minimal, local share of the keys. Rendezvous hashing is one clean way to get that property; here you watch it move ~1/11 of the keys and send every mover to the new node, while hash % N moves ~10/11 and scatters keys between nodes that didn't even change.
The surprise is about which node wins a key and how that decision reacts to adding an eleventh node. These help; each line notes where it shows up.
md5 of a string behaves like an independent uniform draw, so md5(key) % N scatters keys evenly across N buckets, and md5(f"{key}:{node}") gives every (key, node) pair an independent "score." It shows up as the even ~1/11 split and as why the argmax is unbiased.max(range(n_nodes), key=...) in the script.hash % N misses it by 10×.md5 (int(md5(s).hexdigest(), 16)), never Python's per-process randomized hash(), so the counts are fixed every run. Fixed workload: 200,000 keys key0..key199999, cluster grown 10 → 11 nodes.
Two placement functions, the same 200,000 keys, the same cluster growth (10 → 11). Node ids are 0..9 before; growth adds node id 10.
hash % N — a key's owner is md5(key) % N. The owner depends on N through the modulus, so bumping N from 10 to 11 changes the remainder for almost every key. Worse, a key that was on node 3 can land on node 7 — two nodes that were both there the whole time. The function has no notion of "stay put unless you must move."md5(f"{key}:{node}"). Adding node 10 introduces one new score per key; that score is the new maximum for a key only ~1/11 of the time, and when it isn't, the old winner — unchanged — still wins. So a key either moves to node 10 or doesn't move at all. It can never move from one old node to another.Both functions expose the same interface (owner(key, n_nodes)); the exercise runs both against the identical key set and counts movers by destination. The whole thing is one script, code/consistent_hashing.py.
cd study/ddia/ch07
python3 code/consistent_hashing.pyDo not read the output yet — make each prediction first.
Predict. The cluster grows from 10 nodes to 11 and 200,000 keys are re-balanced. In the best imaginable partitioner, roughly what fraction of keys has to move? (Hint: the new node has to end up holding some fair share.)
The floor is 1/11 ≈ 9% — the new node's fair share. Any key that moves without that being forced is wasted work. Keep that 9% in mind; it's the yardstick.
Predict. Under rendezvous hashing, some keys will move when node 10 appears. Of the keys that move, how many land on a node other than the new node 10 — i.e. how many hop between two of the old nodes 0..9?
Exactly 0. All 17,986 movers (8.99%, right on the 1/11 floor) went to node 10. Not one key moved between two old nodes — because a key only moves at all if node 10's score beat its previous winner, and that just hands the key to node 10. The relative ranking among the 10 old nodes is untouched by adding an eleventh candidate, so no old-to-old move is even possible.
Predict. Now the identical 200,000 keys, placed by md5(key) % N, with N going 10 → 11. How many keys move, and of those, how many hop between two old nodes that never changed?
90.87% moved — and 163,493 of those went old-to-old, pure churn. Changing the modulus from 10 to 11 rewrites almost every remainder, so a key on node 3 blindly recomputes to node 7. Only about 18,252 of the movers happened to land on the new node; the overwhelming majority just shuffled between nodes that were there all along. That is exactly the "almost all the data must move" failure the book warns about — 10× the theoretical floor, most of it useless.
hash % N: 181,745 keys move (90.87%), of which 163,493 hop between two old nodes that never changed — churn the cluster gains nothing from.hash % N does 10× more work and wastes most of it.The two functions differ in how a key's owner depends on N, and that difference is the whole result.
Under hash % N, the owner is a remainder, and the remainder of a fixed number mod 10 tells you essentially nothing about its remainder mod 11. So going 10 → 11 is, for each key, an almost-independent re-draw of its home among 11 nodes. A key stays put only by luck — roughly a 1/11 chance its old and new owner coincide — which is why ~10/11 ≈ 90.9% move. And because the new owner is drawn uniformly over all 11 nodes, most movers land on one of the 10 old nodes: nothing about "node 3 didn't change" protects a key that lived on node 3. The 163,493 old-to-old movers are keys the cluster paid to relocate for no structural reason at all.
Rendezvous hashing owns a key by the node with the maximum score md5(f"{key}:{node}"). Adding node 10 adds exactly one new score to each key's list of 11 candidates and changes none of the other 10. A maximum can only be disturbed by a new entry if that new entry is the new maximum — so for any given key, exactly one of two things happens: (a) md5(f"{key}:10") is the largest of the 11, and the key moves to node 10; or (b) it isn't, the old maximum among nodes 0..9 is still the largest, and the key does not move at all. Case (a) happens with probability ~1/11 because all 11 scores are i.i.d. and any one is equally likely to be the max — that's the 8.99% you measured, right on the floor. Crucially, case (a) is the only way to move, and it always moves to node 10, so the old-to-old count is not "small," it is structurally 0: the ranking among the old nodes is a property of their 10 scores, which adding an 11th candidate leaves completely intact. That is the monotonicity guarantee the book calls consistent hashing — minimal and local.
-w / ln(u) from the hash) and see the split follow the weights while keeping the minimal-movement property.Sources: DDIA 2e, Ch. 7, §"Consistent hashing", §"Sharding by hash of key" · Karger et al., "Consistent Hashing and Random Trees" (1997) · Thaler & Ravishankar, "A Name-Based Mapping Scheme for Rendezvous" (1998).