MapReduce Fault Tolerance

1. The Core Philosophy: Failure Detection and Re-execution

The cornerstone of MapReduce's fault tolerance is simple: detect failure and re-execute the work. This is managed by the central master process. Since the overall job is composed of many small, independent tasks (M map tasks and R reduce tasks), the system can treat each task as a unit of recovery.

The master detects failures by periodically pinging each worker process. In distributed systems parlance, this is a heartbeat mechanism. If a worker does not respond within a configured timeout period, the master marks it as failed and makes all tasks previously assigned to that worker eligible for rescheduling on other, healthy workers.

Let's explore how this plays out for different types of failures.

2. Worker Failures

The consequences of a worker failure depend entirely on the type of task it was running and the state of that task's output. This is where the design decision we discussed previously—writing intermediate data to local disk versus final data to a global file system—becomes critically important.

Map Task Failures

When a worker running a map task fails, the master must re-schedule it. This applies to both in-progress and completed map tasks.

• In-progress map tasks: If a task was still running, its work is lost, so it is simply reset to an idle state and rescheduled on another worker.
• Completed map tasks: This is the more interesting case. A completed map task has written its output (the R intermediate partition files) to the local disk of the failed worker. Because that machine is now unreachable, the output is also inaccessible. Therefore, the master must re-execute the completed map task on a different worker to regenerate this lost intermediate data.

Once the task is re-executed on a new worker (say, Worker B), the master updates its internal state to record the new location of the intermediate files. Any reduce worker that had not yet fetched data from the original failed worker (Worker A) will be notified by the master to fetch it from Worker B instead.

Reduce Task Failures

The handling of reduce task failures differs significantly.

• In-progress reduce tasks: Like map tasks, an in-progress reduce task is reset to idle and rescheduled. The new worker will start the process over, pulling the necessary intermediate data from the map workers.
• Completed reduce tasks: A completed reduce task does not need to be re-executed. This is because its final output is written to a global, replicated file system (like GFS). This output is durable and accessible independently of the worker that created it. The system relies on the underlying file system's replication to ensure the data survives the worker's failure.

The following diagram perfectly illustrates this fundamental difference in recovery strategy.

3. Master Failure

In the original MapReduce design described in the 2004 paper, the master process is a single point of failure (SPOF). The authors acknowledge this and state that their implementation simply aborts the entire MapReduce computation if the master fails.

This might seem like a significant weakness, but it was a pragmatic trade-off. The authors argue that master failure is unlikely. Since MapReduce jobs are for offline batch processing, the client program that initiated the job can simply detect the failure and retry the entire operation.

The paper does suggest a path for improvement: periodically checkpointing the master's state (its data structures tracking task status and intermediate file locations). If the master died, a new one could start from the last checkpoint. This is precisely the direction that later systems took. For instance, Hadoop YARN, the successor to the original Hadoop MapReduce, implements a high-availability mode for its master-equivalent (the ResourceManager) using leader election and state replication, often backed by a coordination service like Apache ZooKeeper.

4. Semantics and Stragglers

Let's dig into the details of failure handling by turning to the source material.

To reinforce these concepts, the following video provides a clear visual walkthrough of the failure scenarios.

Let's synthesize what you've just studied.

• Semantic Guarantees: When your map and reduce functions are deterministic (meaning they always produce the same output for the same input), the system guarantees that the final output is identical to what a non-faulting, sequential execution would have produced. This is achieved via atomic renames in the file system for the final output files. If two workers try to write the same output file due to speculative execution, the file system's atomic rename ensures only one succeeds. If the functions are non-deterministic, the guarantees are weaker, and different reduce partitions might reflect outputs from different runs of the same map task.

• Stragglers (Performance Failures): A "straggler" is a machine that takes an unusually long time to complete one of the final tasks, becoming a bottleneck for the entire job. This is not a crash failure but a performance issue. MapReduce's solution is speculative execution (called "backup tasks" in the paper). When a job is nearly finished, the master schedules redundant executions of the few remaining tasks. Whichever copy finishes first wins, and the master kills the other attempt. As the paper notes, this simple mechanism dramatically reduces the "long tail" of job completion times.

The paper provides compelling evidence of this resilience. In one experiment described in Section 5.5, the engineers intentionally killed 200 worker processes during a large sort job. The MapReduce master simply re-executed the lost work, and the entire job finished only 5% slower than a normal execution.

Conclusion

In this lesson, we've examined the pragmatic and effective fault tolerance mechanisms at the heart of the MapReduce framework. These strategies were designed for an environment where component failures were not an exception, but the norm.

Your key takeaways should be:

• MapReduce's primary fault tolerance strategy is re-execution, orchestrated by a central master that detects worker failures via heartbeats.
• Worker failures trigger the re-execution of all their assigned tasks. Critically, completed map tasks are re-run because their output is on local disk, while completed reduce tasks are not, as their output is in a global, replicated file system.
• The master was a single point of failure in the original design, a trade-off that prioritized simplicity for restartable batch jobs.
• Performance failures, or stragglers, are mitigated through speculative execution, where backup tasks are launched for the last few tasks in a job to avoid long-tail latency.

We've now covered the what, how, and why of MapReduce's model, execution, and reliability. In the next lesson, we will look closer at the final piece of the puzzle: the task scheduling strategy, focusing on how the master uses data locality and the speculative execution we just discussed to optimize job performance.