MapReduce turns a large batch job into two user functions and a runtime-managed data movement phase.
map(k1, v1) → [(k2, v2)]
shuffle groups all values by k2
reduce(k2, [v2]) → outputFor word count, mappers emit (word, 1) and reducers sum counts. The simple API hides input splitting, scheduling, partitioning, transfer, retry, and output commit.
The shuffle is the expensive middle
A partitioner decides which reducer owns each intermediate key. All equal keys must reach the same reducer. Combiners can aggregate locally before transfer when the operation is associative and commutative, reducing network bytes.
Data locality schedules map tasks near their input blocks. Reduce tasks still need their partitions from every mapper, so shuffle, skew, and the slowest partition often dominate elapsed time.
Fault tolerance through deterministic tasks
The coordinator tracks tasks and re-executes lost work. Mapper output on a failed worker can be recomputed from replicated input. Reducer output becomes visible only after an atomic commit. This works best when tasks are deterministic and side-effect free.
Speculative execution runs duplicate copies of unusually slow tasks; the first valid result wins. It helps random stragglers but wastes capacity when slowness comes from systematic skew.
In plain terms: MapReduce often stores the recipe and input instead of trying to preserve every intermediate calculation.
Review card
- Map transforms records; reduce aggregates one key’s values.
- Shuffle is distributed grouping and network movement.
- Partitioning determines reducer balance.
- Combiners are safe only for suitable operations.
- Deterministic tasks make retry-based fault tolerance practical.
- Measure skew and tail tasks, not only average worker time.
MapReduce 把大型 batch job 濃縮成兩個 user function，以及由 runtime 管理的 data-movement phase。
map(k1, v1) → [(k2, v2)]
shuffle groups all values by k2
reduce(k2, [v2]) → outputWord count 中 mapper emit (word, 1)，reducer 加總。簡單 API 隱藏 input split、scheduling、partition、transfer、retry 與 output commit。
Shuffle 是昂貴的中段
Partitioner 決定 intermediate key 屬於哪個 reducer；相同 key 必須到同一處。若 operation associative 且 commutative，combiner 可在 transfer 前 local aggregate，減少 network bytes。
Data locality 讓 map task 靠近 input block。Reduce 仍要從所有 mapper 拉自己的 partition，因此 shuffle、skew 與最慢 partition 常主導 elapsed time。
用 deterministic task 容錯
Coordinator 追蹤 task，失敗時 re-execute。Failed worker 上的 mapper output 可從 replicated input 重算；reducer output 只在 atomic commit 後可見。Task deterministic 且沒有 external side effect 時最安全。
Speculative execution 對異常慢 task 啟動 duplicate copy，第一個 valid result 勝出。它能處理 random straggler；若慢來自 systematic skew，只會浪費 capacity。
白話來說： MapReduce 常保存 input 與 recipe，而不是努力保住每個 intermediate calculation。
複習卡
- Map 轉換 record；reduce 聚合單一 key 的 values。
- Shuffle 是 distributed grouping 與 network movement。
- Partitioning 決定 reducer balance。
- Combiner 只對合適 operation 安全。
- Deterministic task 讓 retry-based fault tolerance 可行。
- 要量 skew／tail task，不只 average worker time。