MapReduce worker failure tolerance

MapReduce is designed to run on large clusters of cheap commodity machines, where failures are normal. The library handles failures automatically by re-execution: the master detects the failure and re-schedules the lost work on another healthy worker. The user program does not have to deal with it.

Master (JobTracker / Application Master) keeps the state

The master stores, for every map and reduce task, its state (idle, in-progress, completed) and the identity of the worker machine running it. For each completed map task it also stores the location and size of the R intermediate files.

Worker (map/reduce node) failure

The master pings every worker periodically (heartbeat). If a worker does not respond within a certain time, the master marks it as failed.

• Completed map tasks on the failed worker are re-executed. Their output is stored on the local disk of that machine, so it is no longer reachable after the failure. The tasks are reset to idle and given to other workers.
• In-progress map or reduce tasks on the failed worker are also reset to idle and rescheduled.
• Completed reduce tasks are not re-executed, because their output is already stored in the global file system (GFS/HDFS), which is replicated.
• When a map task is re-executed on another worker, all reducers are notified, so that a reducer which has not yet read the data from the old worker will read it from the new one.

 Master --ping--> Worker A  (no reply)
   |
   +-- mark A failed
   +-- map tasks of A (done/in-progress) -> idle
   +-- reduce tasks of A (in-progress)   -> idle
   +-- reschedule on Worker B, C
   +-- inform reducers of new map locations

Master failure

There is only one master, so its failure is unlikely. The master writes periodic checkpoints of its data structures. If it dies, a new copy can be started from the last checkpoint. Otherwise the job is aborted and the client may retry it. (In Hadoop 1, JobTracker failure killed running jobs; YARN and HA ResourceManager improve this.)

Semantics in the presence of failures

If the user's map and reduce functions are deterministic, the output is the same as that of a fault-free sequential execution. This is guaranteed by atomic commits of task output:

• Each map task writes R temporary files and sends their names to the master when finished. The master ignores a duplicate completion message for a map task that is already completed.
• Each reduce task writes to a temporary output file and atomically renames it to the final file name. If the same reduce task runs on two machines, the atomic rename ensures only one final file exists.

Slow workers (stragglers)

A machine that runs unusually slowly (bad disk, CPU contention) lengthens the total job time. Near the end of the job the master starts backup executions of the remaining in-progress tasks on other machines. The task is marked complete when either the primary or the backup finishes. This is called speculative execution.

Bad records

If a particular input record always crashes the user code, the worker reports it to the master. After the master has seen more than one failure for the same record, it tells the next re-execution to skip that record.

Summary