Section 8: Do It Again, Deterministically - Deep Dive: Fault Tolerance & Atomic Commits

Executive Summary: MapReduce doesn't replicate running computation. It re-executes deterministic tasks. The master pings every worker every 5 s and declares one dead after 15 s of silence. When w-0417 dies at minute 6, just before the map phase ends, its in-progress tasks and its completed map tasks both go back to idle, because their output sat on a disk that no longer answers. That is about 75 completed maps and nearly 500 MB. The re-runs run in parallel, so they cost the critical path about 25 s (15 s of detection plus one 8-s task); w-0417's 2 restarted reducers can add up to ≈ 1.5 min more, still well inside the 15-min SLO. Re-execution creates duplicates, so every task commits atomically. A map's output exists only once the master records its completion message, and a reduce's output exists only once its temp GFS file is renamed. With deterministic user code, the result equals a sequential run. The master itself gets no high availability: if it dies, the job aborts and is resubmitted (Section 10 prices that).

Interviewer: "You have 2,000 commodity machines. Something is always broken. Where does that leave Riya's job?"

You: "Finishing anyway, and Riya never finds out. Our assumption is that 1% of machines crash per day. That's about 0.11 crashes during an 8-minute job, so most nights see none, but the framework has to treat a crash as routine. I won't make running work survive a crash. I'll make lost work cheap to redo. Section 4 made map and reduce deterministic for exactly this reason."

Detection: Fifteen Seconds of Silence

Each of the 2,000 workers answers a ping every 5 s, so the master handles 400 heartbeats per second, which is trivial next to its 500 task completions per second at peak. Three misses in a row (15 s) mark a worker dead.

Why 15 s and not 2? A merely slow worker (a long GC pause, a congested uplink) would be declared dead and its work duplicated. The atomic commits below make duplicates safe, so a false positive only wastes compute. A detector that's too patient costs wall-clock time on every real crash. With 8-second map tasks, 15 s is about two waves: a fair price.