A 10-node cluster grows to 11. Assign keys straight to nodes by hash(key) % N and 909,138 of 1,000,000 keys (90.91%) must move — 817,949 of them to a node that already existed. Put 1000 fixed shards between keys and nodes and the same growth moves 89,813 keys (8.98%): 10.1× less data over the network, from one layer of indirection.
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.
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.
The whole result is one modular-arithmetic fact plus one systems idea. Each line notes where it shows up.
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.hash().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.
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.
Same million keys, same growth from 10 to 11 nodes — only the mapping differs.
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."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.
cd study/ddia/ch07
python3 code/mod_n_rebalancing.pyDo not read the output yet — make each prediction first.
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?
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.
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?
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.
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?
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.
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?
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.
hash % N, growing 10→11, moves 909,138 of 1,000,000 keys — 90.91%.hash % N.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.
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.
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.S is chosen large once and left alone, the one migration fixed shards don't make cheap.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.Sources: DDIA 2e, Ch. 7, §"Sharding by hash of key", §"Hash modulo number of nodes", §"Fixed number of shards" (Figures 7-3 and 7-4).