Notesbatch๐ฑ seedling
MapReduce
Also: Map Reduce ยท Map/Reduce ยท MR
A batch programming model where you write map (record โ key-value pairs) and reduce (key, all its values โ output), and the framework handles partitioning, the shuffle, scheduling and failures across thousands of machines.
Why it exists
Running one computation over terabytes means thousands of machines, and at that scale machines fail during almost every job. MapReduce hid distribution and failure behind two pure functions.
How it works
- Input in a distributed file system is split into chunks (16โ64 MB in Google's original; the 128 MB HDFS block in Hadoop); one map task per split, scheduled near a replica of its data.
- Map output is partitioned by hash(key) mod R and written to the mapper's local disk (Hadoop sorts it there; Google's original sorted on the reducer); each of R reducers fetches its partition from every mapper (the Shuffle).
- Reduce is called once per key with all its values; output goes to the replicated file system.
- Failures: a master pings workers and reruns tasks of dead ones, including their completed map tasks (their output was local). Correct because tasks are deterministic and inputs immutable.
- Stragglers: near the end, backup copies of in-progress tasks run; the first to finish wins.
Trade-offs
| Gains | Costs |
|---|---|
| scales to thousands of machines | rigid shape: one map, one shuffle, one reduce |
| fault tolerance by re-execution | multi-step pipelines write replicated intermediate files |
| simple model, any language | high start-up latency; no iteration in memory |
In practice
- Google's 2004 paper: about 150 s to grep 1 TB, and 891 s to sort 1 TB, on about 1,800 machines. Disabling backup tasks made the sort 44% slower.
- By 2008 Google ran about 100,000 MapReduce jobs a day over 20 PB, before replacing it with FlumeJava and Dataflow.
Pitfalls
- Non-deterministic map or reduce code (random numbers, clock, external calls) makes reruns and backup tasks give different results.
Connections
- Part of
- Batch Processing
- Builds on this
- Dataflow Engine
- In real systems
- Hadoop
Recall
These cards are also in your review deck, scheduled with spaced repetition.