# DDIA Ch. 7: consistent hashing moves 9% of keys and 0 of them uselessly; hash%N moves 91% and 163k uselessly ## Concept 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. ## Provenance *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. ## Prerequisites 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. 1. **A good hash spreads inputs like uniform randomness** — `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. 2. **argmax / ranking** — rendezvous hashing places a key on the node whose score is the *maximum*. The whole property flows from a fact about maxima: adding a candidate can only change the argmax if the newcomer *is* the new max. It shows up as `max(range(n_nodes), key=...)` in the script. 3. **The "minimal disruption" property** — the yardstick for a partitioner is how many keys move when N changes. The theoretical floor for growing N→N+1 is ~1/(N+1) of keys (the share the new node must take). It shows up as rendezvous hitting that floor (8.99% ≈ 1/11) while `hash % N` misses it by 10×. ### Where to learn the prerequisites - **Hashing as uniform randomness (#1):** any intro to hash tables; DDIA §"Sharding by hash of key" for why a hash is applied before partitioning. - **The minimal-disruption idea (#3):** Karger et al., "Consistent Hashing and Random Trees" (1997) — the original ring construction with the "adding a node moves few keys" guarantee. - **Rendezvous / HRW hashing (#2–#3):** Thaler & Ravishankar, "A Name-Based Mapping Scheme for Rendezvous" (1998); the Wikipedia "Rendezvous hashing" article is a good, free, worked explainer of the argmax construction used here. If only one is new, make it #2 — the entire monotonicity result is just "adding a candidate only changes an argmax when the newcomer wins." ## Environment Deterministic, so the numbers reproduce exactly: - macOS 26.5.2 (Darwin 25.5.0), arm64 - Python 3.15.0a8, standard library only — no Docker, no deps - Ownership decided by stable `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 ## Mental model 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`. - **Naive `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." - **Rendezvous (HRW) hashing** — a key's owner is the node that *maximizes* `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`. ## Setup ``` cd study/ddia/ch07 python3 code/consistent_hashing.py ``` Do **not** read the output yet — make each prediction first. ## Steps ### Step 1 — the minimum that *must* move **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.) **Observe.** ``` Grow the cluster from 10 nodes to 11, re-placing 200,000 keys. old nodes = ids 0..9 new node = id 10 ``` 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. ### Step 2 — rendezvous hashing: where do the movers land? **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`? **Observe.** ``` RENDEZVOUS (consistent) hashing -- owner = argmax_node md5(key:node): keys moved 10 -> 11 : 17,986 (8.99%) of those, movers landing on an OLD node (id <= 9) : 0 of those, movers landing on the NEW node (id 10) : 17,986 -> every one of the 17,986 moved keys went to the new node; 0 hopped between old nodes. ``` **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. ### Step 3 — the same keys under `hash % N` **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? **Observe.** ``` NAIVE hash % N hashing -- owner = md5(key) % N: keys moved 10 -> 11 : 181,745 (90.87%) of those, movers landing on an OLD node (id <= 9) : 163,493 of those, movers landing on the NEW node (id 10) : 18,252 -> 163,493 moved keys hopped between 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. ## What you should see - **Rendezvous:** **17,986** keys move (**8.99%**, ≈ 1/11), **all** to the new node; **0** movers land on an old node. - **`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. - Same keys, same new node: consistent hashing does ~10× less work *and* wastes none of it; `hash % N` does 10× more work and wastes most of it. ## Why 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.
The boundary — the property is about the maximum, so removal is the mirror image Rendezvous's guarantee comes from one fact: an argmax changes under an added candidate only if the newcomer wins. That immediately tells you the shape of *removal* too. Delete node k, and the only keys affected are the ones k currently owns (k was their max); each is re-placed on *its own* next-highest node — again minimal, again local, with no other key touched. What the property does **not** give you is *balance under skew*: if one key is red-hot, consistent hashing still pins it to a single node (a celebrity-user hot shard), and if you weight nodes unevenly you need weighted HRW or virtual nodes to keep the split fair. Consistent hashing minimizes *movement* when N changes; it does not by itself minimize *load imbalance*, and it does nothing about a single hot key. That is why DDIA pairs it with hot-spot mitigations rather than treating it as the whole answer to sharding.
### Go deeper 1. **Remove a node instead of adding one.** Shrink 11 → 10 and count movers by *source*: predict that only the keys owned by the removed node move, and that they spread across the survivors. Confirm the mirror-image property. 2. **Make nodes uneven.** Give one node 3× the capacity and watch plain rendezvous split load evenly anyway (ignoring the weight). Then implement weighted HRW (score = `-w / ln(u)` from the hash) and see the split follow the weights while *keeping* the minimal-movement property. 3. **Find the hot key.** Route a Zipfian workload through the same placement and watch one node absorb a wildly disproportionate share of *requests* even though *keys* are balanced — the hot-shard problem consistent hashing cannot fix, and the reason the chapter keeps going after it.