Section 7: Move the Code, Not the Data - Deep Dive: Scheduling, Locality & the Shuffle

Executive Summary: The network is the budget. We pick M ≈ 156,000 map tasks and R = 4,000 reduce tasks, far more than machines, buying load balancing and fast recovery for a ≈ 624 MB master table. A locality ladder (replica-local, then rack-local, then anywhere) keeps ≥ 95% of the 10 TB input off the wire; without it, 9.8 TB crosses racks in 392 s, longer than the whole map phase. The 1 TB shuffle averages only ≈ 13% of the root, but as 624 M fetches of 1.6 KB it would choke. Batching fetches per map machine (our refinement, not the 2004 paper's) cuts that to 8 M. Each reducer then sorts its 250 MB partition in memory.

Interviewer: "Walk me through what actually decides the runtime: how many tasks, where they run, and how the intermediate data moves."

You: "Three decisions, one constraint underneath all of them. Section 3 showed map demand of 32 GB/s against a 25 GB/s root. Every choice here is about keeping bytes off that root."

Choosing M and R: Far More Tasks Than Machines

One 64 MB GFS chunk per split gives M ≈ 156,000 map tasks for 4,000 map slots: 39 waves of 8 s, about 78 tasks per machine over the job. The 2004 paper argues for exactly this shape, with M and R much larger than the number of workers. Its typical example is M = 200,000 and R = 5,000 on 2,000 workers.

Fine-grained tasks buy two things:

• Dynamic load balancing. A fast machine comes back for more; a slow one finishes fewer tasks, and nobody waits on a fixed share.
• Fast recovery. A dead worker's completed maps scatter across the 3,998 other map slots: they run in parallel, so recovery costs one 8-s task, not 78 of them back to back on one machine. Section 8 counts that cost.

Interviewer: "So why not make splits tiny and balance even better?"

You: "Because the master pays per pair. The 2004 paper puts its state at about one byte per (map, reduce) pair, so ours is 156,000 × 4,000 ≈ 624 MB of RAM. It also makes O(M + R) scheduling decisions, about 160,000 per job. Quartering the split size quadruples M, the table and the region count. One task per machine fails the other way: no balancing, and every failure costs a machine's full share. That's Decision 5; I'd flip toward bigger splits or merged per-machine map output once master RAM or fetch count binds."

R works differently: R is the number of output files, which is why, the 2004 paper notes, users constrain it. We set R = 4,000 = reduce slots, so every reduce runs in a single wave, fetching while the maps run. Each reducer owns 1 TB / 4,000 = 250 MB. Riya's record lands in partition hash("www.example.org/") mod 4,000 = 1,729. That's Decision 6's hash partitioner, and we'd switch it to a sampled range partitioner only if someone needs globally sorted output.

Quick check before moving on: