I think the term is pretty self-explanatory. It’s a programming model that involves two main phases: Map and Reduce. Google published it in 2004 for processing huge datasets in parallel across many cheap machines. You write two functions, and the framework handles distribution, scheduling, and failures.
| Phase | Function | What happens |
|---|---|---|
| Map | Your code | Takes a chunk of input and emits key-value pairs |
| Shuffle | Framework | Groups all pairs by key and moves them to the right reducer |
| Reduce | Your code | Takes a key and its list of values and combines them into a result |
Why it is needed
- Often data (terabytes to petabytes) is too big for a single machine to process and so it needs to be split across many machines.
- Writing distributed code by hand means dealing with network failures, machine crashes, load balancing, and data movement. MapReduce hides all of that.
- Machines fail constantly at scale specially in the context of distributed systems. The framework re-runs failed tasks on other machines automatically.
Example: word count over many web pages
{
"map": "the cat sat on the mat",
"emitted_pairs": [
{"the": 1},
{"cat": 1},
{"sat": 1},
{"on": 1},
{"the": 1},
{"mat": 1}
],
"shuffled": {
"the": [1, 1, 1, ...]
},
"reduce": {
"the": 4302118
}
}
- Map: One machine reads a sentence and emits
(word, 1)for every word. “the” appears twice, so(the,1)is emitted twice. Nothing is added up yet. - Shuffle: The framework collects pairs from all machines and groups them by key. Every
(the,1)ends up together asthe: [1,1,1,...]. - Reduce: One machine sums the list for each word.
(the, 4,302,118)means “the” appeared about 4.3 million times across all pages. This is just a number for illustration purposes.
Full data flow
- Input: Data is split into chunks and stored in a distributed file system e.g. Google File System (GFS) or Hadoop Distributed File System (HDFS).
- Map: Each map task processes one split, ideally on a machine that already holds that data.
- Local write: Map output goes to the mapper’s own local disk, not to shared storage. It would be a wasted effort to replicate it to multiple machines since it’s temporary. If a mapper dies, the framework re-runs it elsewhere.
- Each mapper splits its own output into one bucket per reducer, usually using
hash(key) % number_of_reducers. This guarantees every(the,1)goes to the same reducer.
- Each mapper splits its own output into one bucket per reducer, usually using
- Shuffle: This is the network-heavy step where each reducer pulls its bucket from every mapper’s disk over the network. That is why the arrows spread across all disks to all reducers.
- Reduce: Each reducer processes its keys, for example by summing counts per word.
- Output: Each reducer writes its result to durable, replicated storage. One reducer produces one output file.
Real-world use
Google originally used MapReduce to build its web search index, for example computing which pages link to which and counting term frequencies across the whole web.
Concept in modern systems
Google’s original implementation is largely retired, but the concept lives on in modern technologies such as:
- Apache Spark
- Hadoop MapReduce
- Tools like AWS EMR and BigQuery