Unit 5.8 · about 2 h
273 / 324MapReduce execution and data-local scheduling
This optional unit connects local process and RPC mechanisms to a distributed batch execution model. It is a scheduling and failure vocabulary bridge, not an invitation to implement Raft or a production batch engine.
- explain
You can now
- Trace map, partition, shuffle, group and reduce stages for a small batch job.
- Explain local-input scheduling, lost intermediate output and retried task attempts.
- Separate duplicate computation from duplicate publication of output.
Covers
- MapReduce execution and data-local scheduling
Study, in this order
1 steps
- DDIA, 2nd edition: batch scheduling and MapReduceDesigning Data-Intensive Applications, 2nd edition - distributed data path
Chapter 11, DFS data-local execution on p. 461; Distributed Job Orchestration through Handling faults, pp. 461 to 466; MapReduce, pp. 466 to 467; Shuffling Data, pp. 469 to 470
Depth · Skip resource-allocation algorithm derivations and Dataflow Engines. Stop after Figure 11-1's task/shard explanation on p. 470; joins and full batch-framework implementation are outside this gate.
Focus on
- Map tasks read input shards. The shuffle routes equal keys to one reducer and groups their values; it is not a random permutation.
- Locality means scheduling computation near a replica of its input in a colocated storage/compute design. Object-store separation and resource availability can make remote execution appropriate.
- Retries may run the same logical task more than once. Attempt outputs must remain private until one successful attempt is selected for publication.
- Lost local intermediate files require recomputation or another surviving copy. Deterministic tasks over immutable inputs support replay; arbitrary external side effects do not become safe automatically.
Reproduce closed-book
Closed-book, trace word count for two input shards,
'a b a' and 'b c'. Emit \((\text{word},1)\), route \(a\) and \(c\) to reducer 0 and \(b\) to reducer 1, group by word and sum: \(a=2\),\(b=2\),\(c=1\). Place each map on a node holding its input replica, then fail the first map's node after it produces private intermediate output but before publication. Retry from an unchanged surviving input replica and publish only the accepted attempt for each logical map task. A Python Counter oracle gives the same counts. If you instead publish both first-map attempts, the wrong result is \(a=4\),\(b=3\),\(c=1\). Label which bytes are input replicas, local intermediate output and published final output. This is a trace and counter model, not a measured locality speedup.Traps
- Publishing every successful attempt as new logical work. Retrying a task does not authorize double-counting its output.
- Treating shuffle as randomization or assuming map placement eliminates the reducer's network traffic.
- Claiming data-local scheduling is always faster without accounting for load, storage architecture and a measured workload.
Practice
The section mini-project covers this: an optional two-map batch trace over the retained log, a failed attempt with private output, and a retry checked against a sequential word-count oracle. No distributed batch engine is required.
Self-test
-
Why must equal keys meet at the same reducer?
That reducer needs the full group to compute the job's per-key result. Partitioning by a different identity can split the group and produce incomplete results. -
Does a map retry violate effectively-once output?
Not if only one successful attempt's output is published for each logical task. Computation can repeat while visible output remains equivalent to one execution. -
Can the scheduler prefer a nonlocal node?
Yes. A local node may be unavailable or overloaded, and disaggregated object storage may not offer colocated compute at all. -
What breaks replay if a mapper sends an email for every input record?
Attempt-output selection cannot retract an external email. Retrying may send it again unless that external effect has its own cooperating idempotency boundary.
Completion criterion
Stop when
You trace both reducers, explain the retry's correct and double-published counts, and identify when locality is available without claiming a speedup.
Mark passed, then open 6.1 Only mark this when you can do it without notes.Resources for this unit
- Designing Data-Intensive Applications, 2nd edition - distributed data path Read the selected chapters on replication, partitioning, distributed-system trouble, consistency and consensus, batch processing and stream processing. For each guarantee, write its assumptions, a confirming history and one counterexample outside the boundary.
Also in this section
- Gossip Glomers - Echo, Unique ID and Broadcast Complete Challenge 1 Echo, Challenge 2 Unique ID Generation and Challenge 3a Single-Node Broadcast. Add 3b Multi-Node Broadcast only after writing the delivery, duplicate and partition assumptions. Preserve protocol histories rather than relying on a success banner.
- MIT 6.5840 - MapReduce, RPC and consistency bridge Use the introductory MapReduce, RPC, GFS and consistency lectures after the local RPC and store gates. The MapReduce lab is optional. Do not begin Raft or sharded KV as foundation work.
- Apache Kafka documentation - design Read Persistence, The Consumer (Consumer Position), Message Delivery Semantics, Using Transactions, Replication and Log Compaction for a concrete log: offsets, consumer positions, the at-most-once, at-least-once and exactly-once boundaries, in-sync replicas and compaction guarantees. Map each guarantee onto your own log before trusting it.
- Building Distributed Systems from Scratch - one challenge path Choose one messaging, durable-log or partitioning challenge that matches a failed checkpoint. State the model, failures and evidence independently because interactive grading behavior has not been verified.
- AlgoMaster System Design - distributed fundamentals slice Use Database Replication, Consistency Models, Logical Clocks, Vector Clocks, Network Partitions, Split Brain Problem, Leader Election, Database Partitioning, Consistent Hashing, Delivery Semantics, Dead Letter Queues, Idempotency, Two-Phase Commit (2PC), Outbox Pattern and Streaming Engines as bounded review after DDIA. Attempt only the exercise that matches your implemented history, then challenge its assumptions with a node-loss, delay or duplicate case.