MapReduce

How MapReduce splits a big batch job into map, shuffle and reduce across many machines, how it survives failures, and why dataflow engines replaced it.

Overview

The idea

MapReduce is a way to process a dataset too big for one machine. Google described it in a 2004 paper by Jeffrey Dean and Sanjay Ghemawat, and Apache Hadoop made an open-source version widely used. The programmer writes two small functions. The framework runs them on thousands of machines and handles splitting the input, moving data, and recovering from failures.

Map runs once for each input record, on its own, and emits zero or more key-value pairs.
Shuffle is the framework's step: it collects every pair with the same key and brings them to one place, sorted by key.
Reduce runs once for each key, with all the values for that key, and writes the output.

The same shape in a few lines of Python, run on one machine, makes the three steps concrete.

How a job runs on a cluster

A master process splits the input into M pieces and plans R reduce tasks. It hands map tasks to idle workers, trying to run each one on a machine that already stores a copy of that piece of input.

Each map task reads its split and runs the map function.
It divides its output into R partitions, by default with hash(key) mod R, and writes them, sorted, to its own local disk.
Each reduce task fetches its partition from every map task over the network. This is the shuffle.
The reducer merges the sorted runs so that all values for a key sit together, calls reduce for each key, and writes one output file to the distributed file system.

Map — Input split in the distributed file system, ideally a local copy — Sorted partitions on the mapper's local disk
Shuffle — Every mapper's local disk, over the network — The reducer's local disk and memory
Reduce — The merged, sorted partition — Output file in the distributed file system, replicated

The paper gives a sense of scale: its authors often ran jobs with M = 200,000 and R = 5,000 on 2,000 worker machines.

Bring the computation to the data

Network bandwidth was the scarce resource. The input lives in a distributed file system (GFS at Google, HDFS in Hadoop) that splits files into large blocks and keeps several copies of each. Google's GFS used 64 MB blocks with typically three copies; HDFS today defaults to 128 MB blocks and three replicas. The master schedules each map task on a machine holding a copy of its block, or failing that on one nearby, so most input is read from local disk.

The combiner

A combiner is an optional mini-reduce that runs on the mapper's machine before the shuffle. In word count, one mapper may emit the pair (the, 1) thousands of times; a combiner adds them into one pair first, so far less data crosses the network. It is only safe when the reduce operation is commutative and associative, such as a sum, count or max. An average is not: combine sums and counts instead, and divide at the end.

Surviving failure

At thousands of machines, some fail during every large job. MapReduce handles this by re-running tasks, which is safe because each task only reads its input and writes its own output.

Atomic output. Each reduce task writes to a temporary file and renames it to the final name when done. The file system's atomic rename means readers see one complete output, even if two copies of the task ran.
Backup tasks. Near the end of a job, a few slow machines, called stragglers, can hold up everything. The master starts duplicate copies of the last running tasks and takes whichever finishes first. Hadoop calls this speculative execution. In the paper, a sort job took 44% longer with backup tasks turned off.
Determinism. Re-running and duplicating tasks gives the same result as a single run only if map and reduce give the same output for the same input. The paper offers weaker guarantees for tasks that are not deterministic. Functions that read the clock, use randomness without a fixed seed, or call outside services break this.

Where MapReduce falls short

Each job is exactly map, then reduce — Real pipelines chain many jobs, and each job writes its full output to the replicated file system before the next can start
Reduce waits for every map — One slow mapper delays every reducer, because no reduce function can start until all map output is in
Iterative algorithms — Machine learning and graph algorithms re-read the same input from disk on every pass
Low-level API — Joins, filters and aggregations must be hand-written as map and reduce functions

These limits led to higher-level tools on top (Hive and Pig turn SQL-like queries into chains of jobs) and then to dataflow engines such as Spark, Tez and Flink, which run a whole pipeline as one graph. The Spark paper measured Spark up to 20 times faster than Hadoop on iterative machine learning and graph jobs, mainly by keeping reused data in memory. Plain MapReduce jobs are rare in new systems, but the model (partition, shuffle by key, aggregate) is still what those engines do underneath.

What you will be able to do

Trace a word count through map, shuffle and reduce, and say where each piece of data is stored.
Explain data locality and why the combiner saves network traffic, and when a combiner is not safe.
Explain how MapReduce recovers from a failed worker, and why determinism matters.
Say what limits MapReduce has and what replaced it.

Key concepts

Map: A function run on each input record independently. It emits zero or more key-value pairs.
Shuffle: The framework step that routes every pair with the same key to the same reducer, sorted by key. It moves data across the network and is usually the most expensive step.
Reduce: A function run once per key, with all its values. It aggregates them and writes the output.
Partitioner: Decides which reducer a key goes to. The default is a hash of the key modulo the number of reducers.
Combiner: An optional local reduce on the mapper's machine before the shuffle. Safe only for commutative and associative operations.
Data locality: Running a map task on the machine that stores its input block, so the input is read from local disk instead of the network.
Straggler: A task that runs much slower than its peers, often because of a failing disk or a busy machine. Backup tasks work around it.
HDFS: The Hadoop Distributed File System. It splits files into blocks, 128 MB by default, and keeps 3 replicas of each by default.

When to use it

Explaining the batch processing model that Spark, Flink and SQL-on-Hadoop engines still use underneath: partition, shuffle by key, aggregate.
Designing a large offline job, such as building a search index, computing daily aggregates or joining two big datasets.
Discussing data locality, the shuffle, and why network traffic is the main cost of a distributed batch job.
Explaining why task retries require deterministic, side-effect-free functions.

Interview questions

Walk through a MapReduce job end to end. Where does each piece of data live?
How does MapReduce handle worker failures and slow machines?
How would you join two large datasets with MapReduce?
Why did Spark and other dataflow engines replace MapReduce?