5.1 MapReduce: Partitioning, Shuffle, and Failure Recovery

Distributed batch processing splits input into parallel tasks, retries deterministic work on node failures, and uses Shuffle to route intermediate results by key to the same Reduce partition.

The value of MapReduce isn't just in the two functions; it's in the framework handling scheduling, data locality, retries, sorting, and output commit.

Data flow

Input splits
   ↓
Map tasks: (k1, v1) → [(k2, v2)]
   ↓ local spill / sort
Partition + Shuffle
   ↓
Reduce tasks: (k2, [v2]) → [(k3, v3)]
   ↓
Committed output

Map tasks run in parallel over input splits. A split is a logical work unit defined by the input format, not necessarily one file or storage block. The Partitioner determines which reducer receives each intermediate key; the same key must be routed to the same partition. Shuffle involves local disk writes, network transmission, merging, and sorting, and is typically the most expensive phase.

Combiner Needs Algebraic Properties

Combiner can aggregate on the map side to reduce network bytes, but the framework may run it zero or multiple times. Whether partial combining occurs must not change the final answer. The operation must be closed over input and output types and satisfy associative and commutative semantics that allow safe partitioning.

Summing works well; directly averaging doesn't, because "averaging the averages across shards" ignores sample counts. Pass (sum, count) and divide at the end. If shard A contains [0, 10] and B contains [100], averaging their averages gives (5 + 100) / 2 = 52.5, while the actual mean is 110 / 3. Combining (10, 2) and (100, 1) into (110, 3) preserves the weights.

Associativity here is a requirement on the business operation. Floating-point addition is not strictly associative at the bit level because of rounding. Reproducible results also need an agreed numeric type, precision, and comparison tolerance.

Recover Failed Tasks by Re-execution

After a Worker fails, the framework can retry Map/Reduce tasks on other nodes, provided the task can be safely re-executed on the same input and external side effects are controlled.

If a Mapper directly calls external payment services or sends emails, task retries will result in repeated side effects. In distributed computing, outputs should be written under the management of a framework's commit protocol, and external effects should be handled through idempotent consumption.

Speculative execution can start another attempt for a slow task. The commit protocol selects one successful attempt’s output and cancels the others. This can mitigate occasional stragglers, but not a large partition caused by a hot key. Multiple copies processing the same enormous input mostly add activity. External side effects can still repeat.

Output commit to avoid half-finished work

Tasks commonly write temporary output, and the commit protocol publishes one successful attempt’s result. Publishing one result per task does not make every partition of a job appear atomically. Consumers must use the engine’s completion marker, manifest, or table transaction. A general approach writes each run to its own version directory and switches the readers’ version pointer only after the whole run succeeds. Failed directories never become the current version.

The rename semantics on object storage differ from those in a file system; specific engines must implement manifest management, commit protocols, or atomic metadata updates. It's not safe to assume that directory renames across all storage systems are cheap or atomic.

Data skew determines the long tail

An average of 10 GB per partition doesn't mean each partition is close to 10 GB. Popular keys could push a single reducer to hundreds of GB, causing all other nodes to wait.

Possible remedies:

• Use sampling to estimate the key distribution;
• Salt splittable hot keys and perform two-phase aggregation;
• Broadcast a small dimension table to avoid large shuffle;
• Custom partitioner;
• Handle super keys individually when business allows.

Salting requires a second stage that restores the original key: first aggregate (sum, count) by (original key, salt), then remove the salt and combine. Salting without that final aggregation splits one business result into several rows. Sorting within MapReduce partitions also does not make all output partitions globally ordered.

Capacity and Correctness Metrics

• Input/output bytes and record counts;
• shuffle read/write, spill, and network latency;
• Task distribution, p50/p99 latency, and straggler issues;
• Retries, failures, and speculation attempt;
• Data skew and largest partition;
• Output count, checksum, and business invariants.

The next lesson examines how Spark’s DAG engine optimizes multi-stage computations using lineage, narrow/wide dependencies, and structured plans.

References

• Apache Hadoop, MapReduce Tutorial

• Apache Hadoop, S3A Committers

• Dean, Ghemawat, MapReduce: Simplified Data Processing on Large Clusters