# DDIA Ch. 7: `hash % N` moves 91% of keys to add one node; fixed shards move 9% ## Concept A cluster of 10 nodes grows to 11. If you assign each key to a node directly by `hash(key) % N`, adding that one node forces **909,138 of 1,000,000 keys** (90.91%) to move to a different node — and 817,949 of those movers land on a node that *already existed*, pure churn that has nothing to do with the new capacity. Put a fixed number of shards (1000) between keys and nodes — `hash(key) % 1000`, then a shard→node mapping — and the same 10→11 growth moves only **89,813 keys** (8.98%), the new node's fair share. Same data, same one extra node; **10.1× the bytes over the network**, bought back by a single layer of indirection. ## Provenance *Designing Data-Intensive Applications*, 2nd ed. (Kleppmann & Riccomini, 2025), Chapter 7 — *Sharding*, §"Sharding by hash of key" → §"Hash modulo number of nodes" and §"Fixed number of shards" (the book's Figure 7-3 vs 7-4): > The problem with the *mod N* approach is that if the number of nodes N > changes, most of the keys will need to be moved from one node to another. The book's fix is to create many more shards than there are nodes and assign several shards to each node; when a node is added, it steals a few whole shards from the existing nodes and nothing else moves. This exercise makes you predict the two rebalancing costs, then measures both against a million real keys. ## Prerequisites The whole result is one modular-arithmetic fact plus one systems idea. Each line notes where it shows up. 1. **Modular arithmetic (`x mod N`)** — a key's node is the remainder of its hash divided by the node count. The catastrophe is that changing `N` changes the remainder for almost every `x`: it shows up as `h % 10` vs `h % 11` disagreeing for 10 of every 11 keys. 2. **A level of indirection** — instead of mapping keys straight to nodes, map keys to a *fixed* set of shards, then map shards to nodes. The key→shard map never changes; only the small shard→node map does. It shows up as Scheme B moving whole shards, never recomputing any key's home. 3. **Hashing must be stable across processes** — the hash that decides a key's shard has to give the same answer on every machine and every restart, or keys scatter. It shows up as the script using md5, not Python's per-process-salted `hash()`. ### Where to learn the prerequisites - **Modular arithmetic (#1):** Khan Academy, "Modular arithmetic" (khanacademy.org/computing/computer-science/cryptography/modarithmetic) — the `mod` operation and why `a mod 10` and `a mod 11` are essentially unrelated. - **Indirection & fixed shards (#2):** DDIA §"Fixed number of shards"; the classic framing is "every problem in computer science can be solved by another level of indirection" (David Wheeler). - **Why built-in hashes aren't stable (#3):** the CPython docs on `PYTHONHASHSEED` (hash randomization) — the direct analogue of the book's warning that Java's `Object.hashCode()` is unsafe for sharding because it differs across processes. If only one is new, make it #1 — that `h % 10 == h % 11` holds for just ~1/11 of keys is the entire reason `mod N` is a catastrophe. ## 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 - Stable hashing: `int(md5(key).hexdigest(), 16)`, **not** Python's `hash()`, which is salted per process by `PYTHONHASHSEED` - Fixed workload: 1,000,000 keys `key0`..`key999999`; the one free choice (which shards move to the new node) is seeded with 42 ## Mental model Same million keys, same growth from 10 to 11 nodes — only the mapping differs. - **Scheme A — direct `hash(key) % N`.** A key's node *is* `h % N`. The node count `N` is baked into every key's address, so the moment `N` changes from 10 to 11 every key recomputes its home, and it lands on a different node unless `h % 10` and `h % 11` happen to coincide. There is no notion of "this key already lives in the right place." - **Scheme B — fixed shards + a shard→node map.** A key's *shard* is `h % 1000`, and that never changes because 1000 never changes. A separate, tiny table says which node currently serves each shard. Growth edits only that table: hand the new node ~91 whole shards taken off the over-full nodes, and every key inside a shard that didn't move stays exactly where it was. Both schemes hash the identical keys with the identical function; the only difference is whether the node count sits *inside* the key's address (A) or *outside* it in a small remappable table (B). The whole thing is one script, `code/mod_n_rebalancing.py`. ## Setup ``` cd study/ddia/ch07 python3 code/mod_n_rebalancing.py ``` Do **not** read the output yet — make each prediction first. ## Steps ### Step 1 — grow `hash % N` from 10 to 11 nodes **Predict.** A key's node is `hash(key) % N`. With 1,000,000 keys, you go from 10 nodes to 11. What fraction of the keys have to move to a new node — 1/11 (just the new node's share)? 1/10? More? **Observe.** ``` Scheme A -- direct: node = hash(key) % N, grow N 10 -> 11 keys that move : 909,138 of 1,000,000 fraction moved : 90.91% a key stays put ONLY when (h % 10) == (h % 11) ``` **Nearly everything moves — 90.91%.** A key keeps its home only when `h % 10 == h % 11`, which happens for about 1 key in 11; the other ~10/11 are reshuffled. Adding 10% capacity rewrites 91% of the placement. ### Step 2 — where do the movers land? **Predict.** Of those 909,138 keys that moved, how many actually moved *onto the new node 10* (the only move that buys you anything), versus moving from one old node to another old node — churn that ships data for no capacity gain? **Observe.** ``` of the movers, 817,949 land on an OLD node (id 0-9), not the new node -- pure churn between nodes that already existed. ``` **817,949 of the 909,138 movers — 90% of the movement — never touches the new node.** Only ~91k keys were "supposed" to move (the new node's fair share); the rest is `mod N` re-deriving addresses that happened to change, sloshing data between nodes that already existed. The network pays for placement math, not for rebalancing. ### Step 3 — grow fixed shards from 10 to 11 nodes **Predict.** Now the same million keys are hashed into 1000 fixed shards (`h % 1000`), and shards are mapped to nodes. To grow to 11 nodes you move ~91 whole shards onto the new node and leave the rest untouched. What fraction of keys move now? **Observe.** ``` Scheme B -- fixed shards: shard = hash(key) % 1000, map shards -> nodes 1000 shards, 10 nodes own 100 each; grow to 11 nodes move 9 whole shards off each old node -> new node 10 shards moved : 90 of 1,000 keys moved : 89,813 of 1,000,000 fraction moved : 8.98% final shards/node: 10 old nodes -> 91 each, new node 10 -> 90 ``` **8.98% — the new node's fair share and essentially nothing else.** The key→shard map (`h % 1000`) never moved a single key; only 90 of 1000 shards changed owner, each old node shedding 9 shards to balance out at 91. Every key in the other 910 shards stayed home. ### Step 4 — the magnitude **Predict.** Put the two together. Roughly how many times more data does `hash % N` ship over the network than fixed shards, to accomplish the *identical* 10→11 growth? **Observe.** ``` The gap hash % N moves 90.91% (909,138 keys) fixed shards moves 8.98% (89,813 keys) ratio : 10.1x more data shipped by hash % N same 1,000,000 keys, same +1 node -- 10.1x the network. ``` **10.1×.** Same keys, same one added node; one scheme moves 909k keys and the other 90k. The entire difference is where the node count `N` lives — inside every key's address, or outside it in a 1000-entry table. ## What you should see - `hash % N`, growing 10→11, moves **909,138** of 1,000,000 keys — **90.91%**. - **817,949** of those movers land on an **old** node — churn, not rebalancing. - Fixed shards (1000), same growth, moves **89,813** keys — **8.98%** — by relocating just **90 of 1000** shards. - The ratio is **10.1×** more data shipped by `hash % N`. ## Why The catastrophe is a fact about remainders. When a key's node is `h % N`, the node count `N` is *part of the address*, so changing `N` re-addresses everything. A key stays put across 10→11 only if `h % 10 == h % 11`. By the Chinese Remainder Theorem the pair `(h % 10, h % 11)` cycles with period lcm(10,11) = 110, and within each period of 110 consecutive hash values exactly **10** satisfy `h % 10 == h % 11` (the values 0, 1, …, 9 — where both remainders equal `h` itself — repeat once per period). So the survival probability is 10/110 = **1/11 ≈ 9.09%**, and the move probability is **10/11 ≈ 90.91%** — which is exactly the 909,138 the run produced. Worse, when a moved key recomputes `h % 11`, its new node is essentially a fresh draw over 11 nodes; only 1 of those 11 is the genuinely-new node, so ~10/11 of the movers (817,949) land back on a node that already existed. `mod N` doesn't just move too much — most of what it moves is pointless. Fixed shards move the node count *out* of the key's address. The key→shard map is `h % S` with `S = 1000` fixed forever, so no key is ever re-addressed. What changes is a tiny shard→node table with 1000 entries. Balancing 1000 shards over 11 nodes wants ~1000/11 ≈ 90.9 shards each, so the new node takes ~91 shards and each old node sheds ~9 (100 → 91). Only the keys inside those 90 relocated shards move: 90/1000 = 9% of keys, ≈ 1/11 of the data — the new node's fair share, the information-theoretic minimum for rebalancing onto one new node. The 10× gap is 90.91% ÷ 8.98%: one scheme moves ~10/11 of the data, the other ~1/11, and the ratio of those is ~10. **The boundary — the catastrophe is entirely about `N` changing.** If the number of nodes never changes, `mod N` is fine: it distributes keys evenly and moves nothing, because nothing triggers a re-address. The 91% cost is paid *only* at a resize, and it's the resize that fixed shards make cheap. Two things fixed shards do **not** fix: the shard count `S` itself is hard to change later (splitting all 1000 shards is its own migration, which is why systems pick `S` large up front), and shards can grow lopsided if the key distribution is skewed (a hot shard is one node's problem no mapping can rebalance away). Consistent hashing / rendezvous hashing solve the same 10→11 problem differently — moving ~1/11 without pinning a fixed shard count — but the lesson is identical: never let the node count `N` sit inside a key's permanent address. ### Go deeper 1. **Double instead of +1.** Grow `mod N` from 10 to 20 and predict the fraction moved — is doubling special? (It isn't: a key survives only when `h % 10 == h % 20`, still ~1/20-ish coincidences, not the ~1/2 intuition suggests.) Watch the fixed-shard version stay near its fair share. 2. **Shrink, don't grow.** Remove a node from the fixed-shard cluster (11→10) and confirm only the departing node's shards move — rebalancing is symmetric, and still ~1/11. 3. **Change the shard count.** Try to go from 1000 shards to 2000 and measure the keys moved — discover why `S` is chosen large once and left alone, the one migration fixed shards *don't* make cheap. 4. **Break the hash.** Swap md5 for Python's built-in `hash()` and run twice in two processes — watch the same key land in different shards across runs, the live version of the book's Java-`hashCode` warning.