MapReduce: Simplified Data Processing on Large Clusters

How to read the original

1. Read Programming Model and restate the map and reduce contracts.
2. Read Implementation and separate scheduling, intermediate storage, and failure recovery.
3. Read the Combiner Function refinement and decide which summaries compose safely.

Restriction gives the runtime room to act

MapReduce exposes map and reduce functions while the runtime organizes partitioning, intermediate grouping, scheduling, and recovery. The restriction is useful because the system can repeat and relocate tasks without asking application code to orchestrate every message. Read the fault-tolerance discussion carefully: re-execution is not automatically safe for arbitrary external effects, and a legal reducer is not necessarily a legal combiner.

Original reconstruction: aggregate measurements correctly

Suppose three input records contain observations (roomA,10), (roomA,20), and (roomA,100). A mapper emits each room as key and a pair (sum,count) as value, initially (temperature,1). The shuffle groups values with equal keys at the same reduce partition. The reducer combines the pairs by adding their components, yielding (130,3), then produces mean 130/3, approximately 43.333.

Now divide the data between two workers. Worker one sees 10 and 20, while worker two sees 100. If each emits only its local mean, the results are 15 and 100. Taking their unweighted mean yields 57.5, which is wrong because the groups have unequal sizes. Carrying (30,2) and (100,1) preserves sufficient information. Their componentwise combination gives the same (130,3) as direct aggregation.

This example identifies a lawful combiner: pair addition is associative and commutative, so the runtime may combine subsets in different groupings without changing the exact mathematical result. Floating-point addition still introduces order-dependent rounding, so bit-for-bit equality needs a numerical policy. The final division belongs after the aggregate count is known; applying it early and dropping the count destroys composability.

Trace a worker failure

Assume a map worker has produced intermediate output on its local storage, then fails before all reducers fetch it. The system may rerun the map task elsewhere and direct reducers to the replacement output. If the mapping is deterministic for the recorded input, the replacement reproduces the intended key/value content.

Suppose instead the mapper sends a payment request each time it sees an input record. Rerunning the task can repeat that side effect even if only one set of intermediate files becomes part of the final result. The runtime’s output-selection protocol does not automatically deduplicate an unrelated external service. A safe design keeps transformation functions free of such effects or gives the external action an explicit idempotency protocol.

Backup execution of a slow task creates the same distinction. Multiple attempts can consume compute even when only one output is committed. Count resource costs separately from logical result multiplicity.

The shuffle is a real resource boundary

For N emitted pairs, network and storage costs depend on pair size, partition distribution, and local aggregation. If one key receives most records, its reducer can dominate completion time even when other workers finish quickly. More machines do not split a single hot key automatically under the basic grouping contract.

A useful experiment records mapper output size before and after lawful combining, per-partition load, task retries, and total completion time. Check that every expected input contributes to the result, then inject one worker failure and compare outputs under the stated deterministic or tolerance-based contract.

The model is well suited to certain batch transformations, but repeated iterations, shared mutable state, and interactive latency can expose its costs. Its enduring lesson is that an application interface can deliberately constrain freedom so a runtime can supply dependable distributed execution. The constraint and the resulting guarantee must be understood together.

Reconstruction exercise

Compute a global average from partitions [2,4,6] and [20]. Show the incorrect average-of-averages result and the correct sum/count combination. Then explain whether a combiner may safely compute the final average and discard counts. Finally, identify what must change if a mapper updates an external account balance and may be retried.

Worked solution

The local means are four and twenty, whose unweighted average is twelve. The true sum is 32 over four observations, so the correct global mean is eight. Pair summaries (12,3) and (20,1) combine to (32,4), preserving the number of observations represented by each partial result. A combiner that emits only an average loses that weighting information and is not safe under arbitrary grouping. It can emit sum and count, or an equivalent summary retaining enough information, and postpone final division. If a mapper changes an external account balance, re-execution can repeat the update even if MapReduce commits only one task output. Keep the mapper as a pure transformation where possible. Otherwise, the external service must identify the logical operation and enforce deduplication or transactional semantics across retries. A task attempt ID alone is usually insufficient because different attempts can represent the same logical update.

Test the limits and transfer the idea

1. Algorithm and trace · allow 40 minutes

Construct a positional inverted index

The paper lists inverted-index construction as an application. Design a positional index for D1="red blue red", D2="blue green", and D3="red", with token positions starting at zero. Output one record per word containing each document ID and its sorted positions. Trace mapper output and final reducer output.

A proposed combiner keeps only one value per document ID. Show precisely what information it loses. Design a lawful combiner with the same input and output value format, and state whether using sets of (document,position) pairs makes retried task output safe to merge indiscriminately. Distinguish a repeated word in the source from a duplicate representation of the same occurrence.

Get a starting hint

Occurrences have identities. Document IDs alone identify documents, not all positions within them.

Compare your reasoning with the worked solution

Emit values that are singleton sets of occurrence pairs. D1 emits red:{(D1,0)}, blue:{(D1,1)}, red:{(D1,2)}. D2 emits blue:{(D2,0)} and green:{(D2,1)}. D3 emits red:{(D3,0)}. After grouping, red maps to D1:[0,2] and D3:[0]; blue maps to D1:[1] and D2:[0]; green maps to D2:[1]. Sort document IDs and positions only when producing the final presentation.

Keeping a single value per document loses one red position in D1. A combiner can instead take the union of its sets and emit one set under the same word key. Union is associative, commutative, and idempotent, and the reducer can use exactly the same aggregation before formatting. This construction assumes one immutable tokenization and one stable document identity per input version. If the same document ID names two different contents, occurrence identities collide.

Idempotence makes duplicate representations of the same occurrence harmless for this particular set-valued result. It does not change the framework's output commit contract or authorize arbitrary merging for other jobs. A word-count job adding integer counts would double-count duplicated attempts. Even this index can mix incompatible snapshots if retries read mutable documents or change tokenization. Preserve source-version identity and deterministic mapping. The two red tokens in D1 are not duplicates: their different positions must survive.

Check your reasoning

• Produces the complete positional index, including both D1 red occurrences.
• Provides a closed, associative combiner and identifies its assumptions.
• Distinguishes occurrence identity, task retries, and mutable-input hazards.

2. Counterexample and contract · allow 40 minutes

Recover two reducers from different attempts

Read the paper's failure semantics for nondeterministic operators. A single map task draws one private random bit b. It emits key X with value b and key Y with value 1-b. X and Y go to different reducers, each of which copies its sole value. In any failure-free sequential execution, X+Y=1.

Construct a failure and re-execution trace in which the committed distributed outputs are X=1 and Y=1 without any reducer reading two attempts for the same logical map input. Explain why each reducer can nevertheless match some sequential execution. Then propose a change that restores the invariant under retries and a test that detects the original failure. Assume only the paper's task-output semantics, not a global snapshot transaction across reducers.

Get a starting hint

Let one reducer fetch an attempt before its worker disappears; let the other fetch the replacement attempt.

Compare your reasoning with the worked solution

Attempt M1 draws b=1 and writes X=1,Y=0 to local intermediate files. Reducer RX fetches X=1. The map worker then fails before RY fetches Y, so the master schedules a replacement. Attempt M2 draws b=0 and produces X=0,Y=1. RY fetches Y=1 from M2. RX and RY each commit one output, yielding (1,1). Each consumed one version of the logical map task, but they consumed different versions.

RX's result agrees with the sequential execution having b=1. RY's result agrees with the sequential execution having b=0. There is no single sequential execution containing both, because every complete attempt preserves X+Y=1. This is exactly the distinction between per-reducer correspondence and a shared global execution. Atomic replacement of a reducer's output does not coordinate the random choices used by all reducers.

One repair makes b a deterministic function of the immutable input identity and a job seed, with the function and seed versioned. Every retry then emits the same pair. Another changes the task boundary so both correlated values are decided and committed together, but that requires its own contract. Test by forcing the first attempt to use 1, permitting RX to fetch, removing the worker, and forcing the retry to use 0. Assert the cross-key invariant on final outputs. A test that checks each value is either zero or one misses the defect. External side effects remain outside this repaired pure-output guarantee.

Check your reasoning

• Gives a realizable fetch, failure, retry, and commit trace.
• Explains per-reducer versus global sequential equivalence.
• Repairs the source of nondeterminism and proposes an invariant-based fault test.

Check your understanding

Which summary supports arbitrary regrouping for an exact arithmetic mean?

• Only each group’s mean.
• A pair containing sum and count.
• Only the largest observation.
• A mapper’s wall-clock completion time.

Explanation

Sum and count preserve both total value and weighting across differently sized groups.

A mapper’s external write occurs twice after a retry. Which assumption failed?

• That key grouping can combine values from different mapper attempts.
• That reducers may finish at different times.
• That intermediate results can be recomputed after a worker fails.
• That task-output recovery also deduplicates arbitrary external effects.

Explanation

The runtime’s result protocol does not automatically cover side effects outside its controlled output path.

Original paper and sources

Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified Data Processing on Large Clusters. Proceedings of OSDI, 2004.

Read the original paper →

Read the primary paper: Google Research

• MapReduce: Simplified Data Processing on Large Clusters: Google Research