MapReduce：把 Computation 移到 Data，失敗時重新計算

MapReduce 把大型 batch job 濃縮成兩個 user function，以及由 runtime 管理的 data-movement phase。

map(k1, v1) → [(k2, v2)]
shuffle groups all values by k2
reduce(k2, [v2]) → output

Word 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。