MapReduce

MapReduce is two functions you write plus a framework that runs them at scale. The map function takes one input record and emits zero or more key-value pairs. The reduce function takes one key and the list of all values that were emitted for it, then produces the output. You write only those two functions; the framework handles splitting the data, scheduling tasks, moving data between machines, and recovering from failures.

The classic example is counting words across billions of documents. Map reads a chunk of text and emits the pair word, 1 for every word it sees. The framework groups all those pairs so that every 1 emitted for the word database arrives at the same reducer. Reduce then sums the list of 1s and emits word, total. The same shape, emit keyed pairs then aggregate per key, covers building search indexes, computing log statistics, and joining datasets.

The point of the model is that map tasks are independent of each other and reduce tasks are independent of each other. That independence is what lets the framework run thousands of tasks at once on cheap hardware instead of one expensive machine.

The framework first splits the input into pieces, typically 64 MB or 128 MB blocks living in a distributed file system like GFS or HDFS. It launches a map task per split, and it tries to run that task on the same machine that already holds the data so it does not have to ship gigabytes over the network. This is called data locality and it is a major reason the model scales.

Each map task writes its key-value output to local disk, partitioned by key, usually with a hash of the key modulo the number of reducers. Between map and reduce sits the shuffle: reducers pull their partition from every map task and sort the incoming pairs so all values for one key sit together. The shuffle is the expensive part, because it moves data across the whole cluster and sorts it.

A single master node tracks the state of every task. If a worker dies or runs slow, the master simply re-runs that task somewhere else, because map and reduce are deterministic and side-effect-free. To fight slow machines, the framework launches backup copies of the last few tasks, a trick called speculative execution, and keeps whichever copy finishes first. An optional combiner runs a mini-reduce on each map output before the shuffle to cut down network traffic.

MapReduce fits large batch jobs where you scan most of a huge dataset once and do not need an answer in seconds: nightly ETL, log aggregation, training-data preparation, and rebuilding search or recommendation indexes. It shines when the work is embarrassingly parallel and the input is far too big for one machine.

The cost is latency and rigidity. Every job writes intermediate results to disk and reads them back, so even simple jobs take minutes, and a multi-step pipeline pays that disk and shuffle cost at every stage. It is a poor fit for low-latency queries, for iterative algorithms like many machine-learning trainers that loop over the same data hundreds of times, and for anything interactive.

Those weaknesses are why Apache Spark largely replaced raw MapReduce for new work. Spark keeps intermediate data in memory and expresses pipelines as a graph instead of forcing a disk write between every map and reduce, which makes iterative and interactive jobs much faster. The MapReduce model is still worth understanding because its ideas, keyed parallelism, shuffle, and fault tolerance through re-execution, live on inside Spark, Flink, and most batch engines.

Google built MapReduce to regenerate its web search index. Crawlers store raw pages in GFS; a chain of MapReduce jobs parses each page, emits an entry for every word found, and the reduce phase collects all the pages that contain a given word into that word's posting list. Running this across thousands of machines turned an index rebuild from an unmanageable single-machine task into a routine batch job.

On the open-source side, Yahoo ran Hadoop MapReduce on clusters of thousands of nodes to power web search and to win the terabyte sort benchmark, sorting a terabyte of data in well under an hour on commodity servers. Many companies then used the same Hadoop stack for clickstream analysis and reporting before in-memory engines took over the hot paths.

A simple way to picture it: you have a year of server logs spread across 500 files. Map reads each line and emits status_code, 1. Reduce receives all the 1s for code 500 and sums them, so you learn exactly how many errors happened that year without ever loading all 500 files into one machine.