Concepts
MapReduce: fault-tolerant batch execution
Intuition
Imagine counting the words in thousands of books by splitting the books among many people, each one jotting down their counts, and then merging the notes by word. With so many people working, someone is going to get sick or become very slow along the way. Instead of trying to prevent this, the coordinator simply hands the missing person's piece to someone else again and, near the end, gives a copy of the straggler's piece to someone else, with whoever finishes first winning; the final result comes out the same.
How it works
The programmer writes only two functions: map, which transforms an input key/value pair into intermediate key/value pairs, and reduce, which combines all the values of the same intermediate key. The library splits the input into M splits (typically 16 to 64 MB) and a master assigns map and reduce tasks to idle workers, preferring machines that already hold a replica of the block in GFS to save network. Map workers write the intermediate data to local disk, partitioned into R regions (by default hash(key) mod R), and reduce workers read them remotely and sort by key. The master checks workers periodically; if one does not respond, it is marked as failed. Map tasks it had completed are re-executed, because the output was on a local disk that is now inaccessible, while its completed reduce tasks are not, because the output is already in the global file system. Commits are atomic: each task writes to a temporary file and the reduce atomically renames it to the final one, so, with deterministic map and reduce, the result equals that of a sequential execution without failures. For stragglers, near the end the master launches backup executions of the remaining tasks and whichever finishes first wins. The master is a single one, and the implementation described aborts the computation if it fails, leaving it to the client to try again.
In practice
The paper reports a sort of about 1 TB in 891 seconds, which took 933 seconds (about 5% more) with 200 workers deliberately killed, and a case in which network maintenance took down groups of 80 machines and the job finished anyway; without the backup tasks, the sort took 44% longer. Choose this model for batch processing of large volumes of data (inverted indexes, counts, distributed grep and sorting, graphs) on clusters of commodity machines where failures are routine, with input and output on a replicated file system such as GFS. It works best when map and reduce are deterministic and re-executable, and it is not suited to low-latency interactive workloads.
Use it in a design
Practice the cases that rely on this concept in the System Design school.