MapReduce: Simplified Data Processing on Large Clusters

The problem: a thousand machines, one program, every time

By 2003 Google had crawled billions of pages, and the useful questions about them were simple to state. How many times does each word appear? Which pages link to this one? What are the most requested URLs today? Each answer is a few lines of logic. The difficulty was that the input was terabytes, so the logic had to run on hundreds or thousands of machines at once, and the machines were cheap commodity boxes that failed every day.

So every such program had to solve the same hard problems again: split the input, ship work to machines, move intermediate results between them, balance the load, notice a dead machine, redo its work, and merge the output. The simple logic was buried under a mountain of scaffolding, written slightly differently each time and debugged at three in the morning. Jeff Dean and Sanjay Ghemawat noticed that nearly all of these programs had the same shape, and that the scaffolding could therefore be written once.

The idea: two functions, and a library that does the rest

The shape is borrowed from functional programming. You write a map function that takes one input record and emits any number of (key, value) pairs, and a reduce function that takes one key and all the values emitted for it and produces the output. Word count is the paper’s example: map emits (word, 1) for every word on a line; reduce sums the ones. Everything else, the part that was hard, is the library.

How it works

A master process splits the input into pieces of 16 to 64 megabytes and assigns map tasks to workers, preferring a worker holding the input chunk locally on the Google File System, so most reads never cross the network. Each map worker writes its pairs to local disk in R partitions, one per reducer, chosen by hashing the key. When the maps finish, each reduce worker fetches its partition from every map worker, sorts it so that equal keys sit together, and calls reduce once per key. Output lands on GFS, one file per reducer.

Failure handling is where the design shows its teeth. The master pings every worker. If one stops answering, every map task it completed is scheduled again on another machine, because the intermediate files lived on the disk that just died. Completed reduce tasks are left alone: their output is already safe on GFS. If the master itself dies, the paper simply aborts the job; one master in thousands of machines fails rarely enough that this was the right trade.

The subtler trick is for stragglers, a machine that is slow rather than dead because of a bad disk or a noisy neighbour. Near the end of a job the master launches backup copies of the remaining tasks and takes whichever finishes first. The paper reports that this cost a few per cent of resources and cut the sort benchmark’s running time by 44 per cent. Ten years later the same idea reappears for individual requests as hedging in “The Tail at Scale”.

The numbers the paper gives are from 2004 and still impressive: a grep through ten billion 100-byte records on 1,800 machines finished in about 150 seconds, and a terabyte sort in 891 seconds. The sentence that mattered most inside Google was about code, not speed: rewriting the production indexing system as a sequence of MapReduce jobs shrank one of its phases from 3,800 lines to 700.

What it changed

Outside Google the paper became Hadoop, an open-source MapReduce on an open-source GFS, and for a decade “big data” meant Hadoop. Then its limits became the next generation’s design brief. Writing every intermediate result to disk made iterative algorithms and interactive queries painfully slow, and chaining jobs by hand was brittle. Spark (2010) kept the functional model but held data in memory and generalised two stages to a graph of them; Google itself moved on to Flume and Dataflow. MapReduce as a product is history. MapReduce as a shape, partition, apply, shuffle, aggregate, is how every distributed query engine works.

Where you meet it today

• Any distributed SQL. A GROUP BY in Spark, BigQuery, Snowflake or Trino is a map, a shuffle by key, and a reduce; the explain plan will show you the exchange.
• Stream processors. Kafka Streams and Flink apply the same key-partitioned aggregation to data that never stops arriving.
• Re-execution as fault tolerance. Idempotent tasks that can be rerun anywhere are now the default design for batch systems, from Airflow DAGs to CI pipelines.
• Backup tasks. Speculative execution in Hadoop and Spark, and hedged requests in RPC frameworks, descend from the straggler fix.