MapReduce

Why it matters

MapReduce taught the industry to process petabytes on thousands of unreliable machines with programs a single engineer could write. Hardly anyone writes raw MapReduce today, but every batch engine (Spark, Hive, BigQuery, Snowflake's execution) still maps, shuffles and reduces under the hood, and the shuffle is still the expensive step that decides whether a job takes minutes or hours. Understanding the model is understanding how distributed joins and aggregations actually execute.

The idea

A MapReduce job has two user-written functions. Map takes one input record and emits zero or more (key, value) pairs. Reduce takes one key and all the values emitted for it and produces output. Between them, the framework shuffles: it partitions all map output by key, sorts it, and delivers each key's values to exactly one reducer.

What the framework does

1. 1

   Split and schedule with locality

   Input files are split into chunks (the distributed file system's blocks). The scheduler runs each map task on a machine that already holds that chunk, so the computation moves to the data rather than the data to the computation.
2. 2

   Map and partition

   Each mapper writes its output to local disk, partitioned by hash(key) mod R into one file per reducer, sorted by key.
3. 3

   Shuffle

   Each reducer pulls its partition from every mapper over the network and merge-sorts them. This all-to-all transfer is the costliest phase.
4. 4

   Reduce and write

   Each reducer processes its keys in order and writes output to the distributed file system, replicated.
5. 5

   Survive failures by re-execution

   A failed or slow task is simply rerun elsewhere from its input; map output is deterministic and reduce input is re-fetched. Slow tasks (stragglers) get speculative duplicate copies, and the first to finish wins.

Making it fast

A combiner runs a mini-reduce on each mapper's output before the shuffle (summing word counts locally) so far less data crosses the network. A custom partitioner controls which reducer gets which keys, for range-partitioned output or to spread a skewed key. Data skew is the classic problem: if one key (the empty string, a celebrity user) has a huge share of values, its reducer runs for hours while the others finish in minutes; salting the key across several reducers and combining afterwards fixes it.

Joins in MapReduce

A reduce-side join maps both datasets to (join key, tagged record), and each reducer sees all records for one key from both sides and joins them: general but shuffles everything. A map-side (broadcast) join copies a small dataset to every mapper in memory and joins locally with no shuffle: fast when one side is small. These two strategies, shuffle join and broadcast join, are exactly what Spark and SQL planners choose between today.

Why it was superseded

Each MapReduce job writes its full output to the replicated file system, and a multi-step pipeline chains jobs, so intermediate data hits disk three times between every stage. Iterative algorithms (machine learning, graph processing) run dozens of passes and suffer most. Spark keeps intermediate data in memory across a DAG of stages, recomputes lost partitions from lineage instead of replicating them, and offers a rich API and SQL; it runs the same workloads tens of times faster. SQL engines on warehouses compile queries into the same map, shuffle and reduce stages automatically. The model survives as the execution substrate; the hand-written API does not.