A reduce-side join partitions events to reducer md5(key) % R. With uniform keys the load is even (max/mean 1.02) and doubling R halves the wall-clock. One celebrity who is 85% of the events hashes entirely to one reducer — it holds 86.9% of the job while seven idle — and adding reducers does nothing (at R=64 the straggler still holds 85.2%). Salt the hot key into celebrity#0..#15 and the straggler collapses 868,616 → 178,614 on the same 8 reducers.
Run a reduce-side join as a tiny in-process MapReduce: every event is keyed by user_id and shuffled to reducer md5(user_id) % R, where the matching reducer joins it against that user's profile row. With a uniform key distribution the R reducers get near-equal load (max/mean 1.02), and doubling R halves the straggler's work — near-linear speedup. Now introduce one dominant key: a celebrity who accounts for 85% of the events. Every one of those records hashes to the same reducer, which now holds 86.9% of the whole job while the other seven idle. Then try the obvious fix — add reducers — and watch it do nothing: at R=64 the hot reducer still holds 85.2% (852,410 records), because a key is atomic under hashing and always lands on one reducer. The real fix is to salt the hot key: rewrite celebrity into celebrity#0..celebrity#15 on the fact side and replicate its dim row across all 16 salts. The salts hash independently, the straggler collapses from 868,616 → 178,614 records (4.9× lighter) on the same 8 reducers, and its hot-key share drops from 86.9% to 17.9%.
Designing Data-Intensive Applications, 2nd ed. (Kleppmann & Riccomini, 2025), Chapter 11 — Batch Processing, §"Shuffling Data" and §"Reduce-Side Joins and Grouping":
...a hash of the key ... determine[s] which reducer ... receives ... a particular key ... all the records with the same key end up at the same reducer.
The book warns this is exactly where skew bites: "if there is a very large amount of data associated with a single key ... [it] can lead to significant skew ... one reducer that must process significantly more records than the others." This exercise turns that sentence into numbers you predict — the straggler, the failed attempt to fix it with more reducers, and the salting technique the book prescribes.
The surprise is that a key is an indivisible unit of work under hashing, so one hot key is a serial bottleneck no amount of parallelism relieves. These help; each line notes where it shows up.
k to reducer md5(k) % R, so every record sharing a key meets at one reducer (that is what makes the join work). It shows up as the partition() function and the balanced Step 1 histogram.celebrity here is 85% of the events. It shows up in Step 2 as one reducer holding 86.9% of the job.celebrity#0..#15 and the collapsed straggler.random.Random(42); the partitioner is int(hashlib.md5(key.encode()).hexdigest(), 16) % R — not Python's built-in hash() (salted per process, would not reproduce). 1,000,000 events; the celebrity draws ~85%; the tail is 10,000 users. Wall-clock is modeled as the max reducer's record count (unit time per record, reducers in parallel), so "speedup" is max_load(R=8) / max_load(R).
One shuffle, three workloads laid on top of it.
md5(key) % R; that reducer receives every record for the key and joins it to the key's one dim row. A key is therefore an atomic unit: all of its records go to exactly one reducer, and hashing can never split them.celebrity is 85% of the events. All 850k of its records hash to one reducer. Because the wall-clock is the slowest reducer, the job is now ~85% serial: seven reducers finish in a blink and idle while the eighth runs almost the whole job. Adding reducers shrinks the tail's share of each reducer but leaves the celebrity's 850k glued to one reducer — the straggler is stuck.celebrity#0..celebrity#15) by appending a random suffix on the fact side, and replicate the celebrity's dim row to all S salts so the join still matches. Now the 850k records split across up to S reducers. You have broken the atomicity — at the cost of S copies of the dim row and a recombine step for anything that reads the celebrity back.The whole thing is one deterministic script, code/skewed_join_hot_reducer.py.
cd study/ddia/ch11
python3 code/skewed_join_hot_reducer.pyDo not read the output yet — make each prediction first.
Predict. 1,000,000 events over 10,000 uniformly-random users, partitioned to R=8 reducers by md5(user_id) % 8. How even is the per-reducer load (max/mean)? And if you go from R=8 to R=16 to R=64, how does the straggler's load — the wall-clock — move?
max/mean = 1.02, and 8× the reducers gives ~6.9× the speedup. With no hot key, load divides evenly and parallelism pays off almost linearly. This is the world the MapReduce speedup story assumes.
Predict. Same shuffle, same R=8. Now 85% of the events belong to a single celebrity user. What fraction of the whole job lands on the one reducer that holds celebrity? What is max/mean?
Reducer 0 holds 868,616 records — 86.9% of the job — while the other seven hold ~18,800 each. max/mean jumped from 1.02 to 6.95. The seven light reducers finish almost instantly and then sit idle; the job's wall-clock is now essentially the time for one reducer to grind through 85% of the data. Eight reducers, but the work is ~85% serial.
Predict. The obvious move: throw more reducers at it. Go R=8 → 16 → 64 on the skewed workload. Does the hot reducer's absolute load fall (does the job get faster)? What happens to max/mean?
8× the reducers buys ~1× the speedup. The hot reducer's load goes 868,616 → 858,826 → 852,410 — it barely moves, because those ~849,833 celebrity records all hash to the same reducer no matter how many reducers exist. Adding reducers only splits the tiny tail more finely, so max/mean rises (13.74, 54.55) purely because the mean collapses. The straggler is untouched. More parallelism cannot help a unit of work that refuses to divide.
Predict. Rewrite the hot key on the fact side: celebrity becomes one of celebrity#0..celebrity#15 (S=16 salts), and replicate the celebrity's dim row across all 16 salts so the join still matches. Same R=8. What does the straggler's load drop to, and what is the new max/mean?
The straggler collapses from 868,616 to 178,614 — 4.9× lighter — on the same 8 reducers, and max/mean falls from 6.95 to 1.43. Splitting the one hot key into 16 independently-hashed sub-keys let its load spread across 7 of the 8 reducers. It's not perfectly flat (16 salts don't divide evenly into 8 distinct reducers, so some reducers caught 3 salts at ~178k while reducer 5 caught none and kept only its 18,651 tail records) — but the serial bottleneck is gone. The cost: the celebrity's dim row now exists in 16 copies, and reading the celebrity back means re-uniting all 16 salted groups.
MapReduce's speedup story rests on one assumption: that the work divides evenly across reducers. The shuffle sends record k to reducer md5(k) % R, which is a promise about grouping — every record for a key meets at one reducer so the join can happen — and, incidentally, a near-uniform spread when keys are distinct and roughly equally frequent. That is Step 1: 10,000 users over 8 reducers land ~125,000 each, and because each reducer runs in parallel and the job finishes with the slowest one, halving each reducer's share by doubling R halves the wall-clock. 6.9× faster for 8× the reducers.
The hot key breaks the assumption at its root. md5("celebrity") is a single fixed value, so all 849,833 celebrity records hash to one reducer — the key is an atomic unit of work, indivisible by hashing. That reducer now holds 86.9% of the data while the mean is 12.5%: max/mean 6.95. And since wall-clock is the max, not the mean, the job is ~85% serial. This is why Step 3's fix fails: adding reducers only repartitions the 15% tail into ever-smaller slivers; the celebrity's 850k stay welded to one reducer, so its absolute load (868,616 → 852,410) and thus the wall-clock barely move. max/mean climbs to 54.55 not because the straggler got worse but because the mean fell — a vivid reminder that max/mean measures imbalance, and the number that sets your bill is the max. You cannot parallelize past an atomic unit of work.
Salting attacks the atomicity itself. Appending a random suffix turns the one key celebrity into S=16 keys celebrity#0..celebrity#15, and because each suffix hashes independently, the 850k records split into ~16 groups that scatter across reducers — the straggler drops to 178,614, a 4.9× win on the same 8 reducers. The price is paid on the dim side: the join only matches if the celebrity's profile row exists under every salt, so it is replicated S times, and anything that later reads "the celebrity" must re-union all 16 salted groups. You have traded a modest amount of replication and a recombine step for the ability to split an otherwise-atomic key.
null/default key that swallows unmatched rows is the other classic offender). Everywhere else it is pure overhead. The general law: a hash gives you grouping for free and balance only when the key frequencies are already even; a single skewed key is a serial bottleneck that more machines cannot touch, and the only way out is to stop treating it as one key.
Both are the same phenomenon — one hot key that hashing sends to one place, fixed by the same salting trick — but at opposite ends of the pipeline. Ch. 7's hot-key-skew is a serving-time hot shard: a celebrity's requests pile onto one shard, and splitting the key spreads writes but amplifies reads. This exercise is the batch-job twin: a celebrity's records pile onto one reducer, the job's wall-clock waits on that straggler, and the same split spreads the load at the cost of dim-row replication. Read them together to see that "a hash makes a key atomic, so one hot key is indivisible" is a single idea that resurfaces wherever a hash decides placement.
Sources: DDIA 2e, Ch. 11, §"Shuffling Data", §"Reduce-Side Joins and Grouping", §"Handling skew", §"Map-Side Joins".