分散式系統基礎 (二)：MapReduce 計算框架深度解析

MapReduce 核心模型

Google MapReduce / Hadoop 採用兩階段分治：

1. Map 階段：將輸入資料分塊，分發至多節點並行處理，產出 中間鍵值對 (格式與最終輸出一致，僅含部分資料)。
2. Reduce 階段：蒐集所有 Map 輸出，按鍵分組合併，產生最終結果。

關鍵創新：中間檔案 解耦 Map/Reduce，賦予無限水平擴展能力。

術語對照表

架構拓撲

• Client：提交 JobConf，輪詢狀態 (非長連線)。
• JobTracker：單點，RPC 介面 JobSubmissionProtocol (提交) / InterTrackerProtocol (心跳/指令)。
• TaskTracker：多節點，運行 JVM 子進程隔離用戶代碼 (安全/穩定)。
• HDFS：輸入/輸出/中間資料存儲，DataNode 本地讀取優化網路流量。

通訊協議：Hadoop 以 RPC + Protocol 介面解耦，Client↔TaskTracker 無直連，統由 JobTracker 協調。

計算流程詳解

1. 作業提交

• 用戶實作 Mapper、Reducer、Partitioner 等介面。
• 構建 JobConf 設定輸入/輸出路徑、類別、格式類 (InputFormat/OutputFormat)。
• JobClient.runJob(conf) → JobSubmissionProtocol.submitJob() 提交 → 輪詢 getTaskCompletionEvents() 監控。

2. Map 任務分派

• JobTracker 生成 JobInProgress，按 HDFS 區塊位置預分派 Map Task 到對應 TaskTracker (資料局部性)。
• TaskScheduler (可插拔) 決定分派策略：預設 JobQueueTaskScheduler 依優先級分配，保留高優先級任務槽位。
• JobInProgress.findNewMapTask() 從近到遠尋找未分派任務，支援推測執行重跑。

3. Map 任務執行

• TaskTracker 心跳回報狀態，請求新任務。
• TaskLauncher 線程啟動 MapTaskRunner → TaskRunner 下載資源 → JvmManager 池化管理 JVM 子進程。
• 子進程 Child.main() 解析參數，實例化 Mapper 執行 map()。
• 輸出兩種模式：
  • Direct：每筆 collect() 直接寫本地檔 (簡單但 IO 密集)。
  • Buffer + Sort + Spill (預設)：記憶體緩衝 → 閾值觸發背景執行緒 排序 + Combiner 合併 + 溢寫磁碟 → 任務結束多路歸並排序產出最終分區檔。
• Combiner：本地預聚合 (通常與 Reducer 同邏輯)，減少網路傳輸。
• Partitioner：決定鍵屬於哪個 Reduce 分區 (預設 Hash)，實現「水平分區」而非「垂直分片」。

4. Reduce 任務分派與執行

• 所有 Map 完成後，空閒 TaskTracker 獲派 Reduce Task (分配簡單，無局部性優化)。
• 三階段：Copy (拉取 Map 輸出) → Sort (多路歸並排序) → Reduce (逐組鍵呼叫 reduce())。
• ReduceCopier 多執行緒並行下載，同步進行記憶體/磁碟歸並合併。
• 輸出直接寫 HDFS (RecordWriter + OutputFormat)。

5. 容錯機制

• TaskTracker 心跳失效：JobTracker 標記其任務失敗，重新分派。
• 推測執行：慢任務在別節點重跑，先完成者採納。
• 輸入資料錯誤跳過：SkippingRecordReader 記錄讀取位置，失敗重試時跳過壞記錄 (位置資訊經心跳上報 JobTracker)。
• JobTracker 故障恢復：JobHistory 日誌 (存 HDFS) + RecoveryManager 重放狀態，支援遷移部署。

關鍵設計洞見

1. 中間檔案 + 分區排序 將 Reduce 輸入從「垂直分片 (各取部分 Map)」轉為「水平分區 (各取全 Map 的一部分鍵)」，完美支援多 Reduce 並行聚合。
2. Combiner 是 Map 端預聚合，極大降低 Shuffle 流量。
3. 推測執行 + 跳過壞記錄 解決「木桶效應」與「資料髒汙」雙重挑戰。
4. JVM 隔離 + 池化 平衡安全性與啟動開銷 (但早期實作池化機制有缺陷)。
5. 可插拔 Scheduler/Partitioner/Combiner 使框架適應多樣負載特徵。