MapReduce and Batch Data Processing

Core Idea

MapReduce is a programming model for processing very large datasets on clusters of ordinary machines. The programmer writes two functions: map, which turns each input record into intermediate key-value pairs, and reduce, which receives one key with all of its values and produces the output for that key. The framework handles everything else: splitting the input, running thousands of tasks in parallel, grouping intermediate pairs by key (the shuffle), and re-running tasks on machines that fail. Jeffrey Dean and Sanjay Ghemawat described Google's system in 2004, and Apache Hadoop became its widely used open-source counterpart.

How It's Best Learned

Start with word count on paper: split a short text into three chunks, apply map to each, sort and group the pairs by word, and apply reduce. Then write map and reduce for a second task, such as building an inverted index or counting page views per URL, without being told the answer. Finally, examine what the runtime does when a worker dies midway, and why the model struggles with algorithms that repeat many passes over the same data.

Common Misconceptions

• The programmer must write code to distribute data and coordinate machines. (The framework partitions input, schedules tasks, moves intermediate data and handles failures; the programmer supplies only map and reduce, plus optional helpers.)
• A reducer sees all the data. (Each reduce call receives one key and the list of values for that key; different keys can be reduced on different machines.)
• MapReduce suits every large computation. (Each job reads input from and writes output to distributed storage, so iterative algorithms that make many passes, such as many machine-learning methods, run slowly; systems such as Apache Spark keep data in memory between steps.)

Explainer

Suppose you must count how often each word appears in a billion web pages. One machine would take weeks. Spreading the work over a thousand machines is the obvious answer, but then you must split the data, run tasks, move partial results, and cope with the fact that in a cluster that large some machine is likely to fail during the job. MapReduce lets programmers ignore almost all of that.

The model is drawn from the map and reduce operations of functional programming. The programmer writes two functions:

• map(key, value) processes one input record and emits zero or more intermediate pairs. For word count, the input is a document, and map emits (word, 1) for every word.
• reduce(key, values) receives one intermediate key and all the values emitted for it, and produces output. For word count, it sums the list and emits (word, total).

The framework runs the job in three phases. In the map phase, the input, stored in a distributed file system, is divided into splits, typically 16 to 64 MB each in the original paper. The master assigns map tasks to workers, preferring machines that already hold a copy of the split, so little data crosses the network. Each mapper divides its output into R partitions, usually by hash(key) mod R. In the shuffle, each reducer fetches its partition from every mapper and sorts by key, so that all values for one key end up together. In the reduce phase, the reducer calls reduce once per key and writes its output to the distributed file system.

Fault tolerance is built into the design. The master pings workers. If one stops responding, the master reschedules its tasks on other machines. Re-execution is safe because map and reduce are expected to be deterministic and to have no side effects. Near the end of a job, the master also starts backup copies of the slowest remaining tasks, called stragglers, and uses whichever copy finishes first.

Optional extras improve performance. A combiner pre-aggregates each mapper's output locally before the shuffle. A custom partitioner controls which keys go to which reducer.

Google's 2004 paper by Dean and Ghemawat inspired Apache Hadoop, which brought the model to many companies. Its main weakness is that each job writes its results to disk before the next one starts, which slows iterative and interactive work. Later systems such as Apache Spark keep the same data-parallel idea but hold intermediate data in memory.