MapReduce & Batch Data-Parallel Processing

MapReduce turns one large batch computation into many restartable tasks. Its important contribution is not the map and reduce names—the functions are small—but the execution contract around them: partition input, move all values for the same key to one reducer, retry failed attempts, and publish only committed output.

That contract works best when the input is bounded, each record can initially be processed independently, and the required cross-record coordination can be expressed as grouping by key. It is a poor fit for interactive latency, fine-grained mutable state, or algorithms that need many tightly coupled iterations.

The contract #

Conceptually, the user supplies two transformations:

map(k1, v1)       -> zero or more (k2, v2)
reduce(k2, [v2])  -> zero or more output records

The runtime supplies everything between them:

1. split the bounded input into map tasks;
2. run each map and buffer its intermediate key-value pairs;
3. choose a reducer partition for every intermediate key;
4. transfer each partition across the network;
5. sort/group records so one reducer invocation sees all values for a key;
6. write each reducer's output privately, then publish the winning attempt.

The shuffle is the semantic hinge. Without it, map tasks are merely parallel file readers. After it, every occurrence of a key is routed to the same reduce partition, so the reducer can compute a complete per-key result.

The default partitioner is usually equivalent to

$$p(k) = h(k) \bmod R,$$

where $R$ is the reducer count. Equality must imply the same partition, so a custom key comparison and custom partitioner must agree. A partition function that separates two equal keys silently produces two incomplete answers.

Worked example: word counts #

For the two records red blue red and blue green, maps emit:

map A -> (red,1) (blue,1) (red,1)
map B -> (blue,1) (green,1)

Partition, transfer, and sort produce groups:

blue  -> [1,1]
green -> [1]
red   -> [1,1]

Reducers sum each list and emit (blue,2), (green,1), (red,2). The input keys and output keys need not be related; grouping is defined by the intermediate key.

A combiner may sum repeated words on each mapper before transfer. This can turn millions of (word,1) pairs into one partial count per word per map. But the runtime may run a combiner zero, one, or several times. A safe combiner therefore behaves like a regroupable algebraic aggregation: its output type must be acceptable as input again, and regrouping must not change the result. Integer sum, minimum, and maximum qualify. Mean does not if represented by one number; represent it as (sum, count) so partial results can be merged.

The shuffle is usually the bill #

Let map $i$ emit $B_i$ intermediate bytes. Ignoring replication and protocol overhead, the job must at least materialize, sort, and transfer roughly

$$B_{shuffle} = \sum_i B_i.$$

The same logical record can consume memory, local disk write and read, network bandwidth, reducer disk, decompression CPU, and merge-sort CPU. That is why projections, filters, local aggregation, compression, and compact serialization before the shuffle are architectural choices rather than minor optimizations.

The mean partition size hides the tail. A reducer cannot complete before its largest partition does. If one key owns 40% of the data, hashing cannot spread that key: the grouping guarantee deliberately sends every value to one reducer. Remedies depend on the operation:

• pre-aggregate at maps when the operation is safely mergeable;
• salt a hot key into several partial keys, then merge those partial results in a second stage;
• use a range or domain-aware partitioner when boundaries are known;
• isolate exceptional keys into a separate path with explicit semantics.

Salting is not free. It inserts another aggregation boundary and is invalid when the reducer needs one indivisible, ordered value sequence.

Tasks, attempts, and committed effects #

A task is a logical piece of the job. An attempt is one execution of that task. The runtime may start another attempt after a crash, machine loss, or straggler diagnosis; two attempts can temporarily execute the same logical task.

Map output is normally disposable intermediate state. If its worker fails, the map can be rerun and reducers fetch the replacement output. Reduce output is final state, so each attempt writes to a private destination and a commit protocol selects one winner. This is the boundary that converts duplicate execution into one published batch result.

Speculative execution uses the same attempt model: when a task is unusually slow, launch a duplicate elsewhere and accept the first correct completion. This cuts tail latency when one machine is anomalous. It wastes resources when the task is slow because its partition is genuinely larger, and it can amplify load on an already constrained dependency.

Locality, granularity, and the long tail #

Moving compute near input data avoids consuming network bandwidth before the map. The original Google design scheduled maps near GFS replicas; modern deployments may instead read shared or object storage, but the principle survives: place computation where the largest immutable input already is, or accept the transfer as part of the cost model.

Task size balances competing costs. More, smaller tasks improve load balance, failure recovery, and straggler isolation, but increase scheduler state, process/container startup, file count, and merge overhead. Fewer large tasks reduce coordination overhead but create coarse recovery units and a longer tail. Input file layout matters because millions of tiny files can dominate useful computation with metadata and startup work.

Job completion is a maximum, not an average:

$$T_{job} \approx T_{setup} + \max_j(T_{map,j}) + T_{shuffle} + \max_r(T_{reduce,r}) + T_{commit}.$$

The phases overlap in real implementations, but the maxima explain why one bad partition or machine controls the visible completion time.

Multi-stage jobs #

One shuffle groups by one intermediate key. A computation that needs two different grouping boundaries needs at least two stages. For example, a salting stage computes partial totals by (customer, bucket) and the next stage regroups by customer. Each stage materializes a durable boundary that supports restart, inspection, and lineage, while adding I/O and latency.

MapReduce therefore favors acyclic pipelines whose stages can be restarted from immutable inputs. Iterative machine learning repeatedly rereads and reshuffles stable state; streaming systems need continuously updated state and event-time coordination. Those workloads motivated execution engines that retain in-memory state, execute a general DAG, or process unbounded streams.

Diagnosing a slow or wrong job #

The key diagnostic distinction is between more work and slower work. A large partition is a data-distribution problem; a normal partition on one slow host is a scheduling or infrastructure problem. Speculation helps only the second.

When the model fits #

MapReduce remains a useful mental model for bounded ETL, indexing, joins, large aggregations, offline feature generation, and any pipeline where recomputation from immutable input is simpler than maintaining mutable incremental state. Its strengths are explicit dataflow, restartable units, commodity-machine fault tolerance, and predictable per-key coordination.

Choose another model when the requirement is subsecond response, continuous event-time processing, repeated low-latency iteration over shared state, fine-grained transactions, or arbitrary graph communication. The deciding question is not whether a framework exposes map; it is whether a bounded shuffle-and-commit barrier matches the computation's real coordination boundary.