批次處理跑在有界 (bounded) 的固定資料集上：吃一大堆輸入、跑一段時間、產出結果，沒有使用者在等。它在乎的不是回應時間而是吞吐量。從 Unix 管線到 MapReduce 再到 Spark/Flink，變的是規模，不變的是一套哲學：輸入不可變、輸出完整替換、無副作用——正因如此，失敗可以安全重跑。
🧠 Intuition
TIP
把批次作業想成一條放大到整個叢集的 Unix 管線。cat log | awk | sort | uniq -c | sort -rn | head 之所以能被信任，是因為每一步都不改輸入、輸出可以被截斷檢視、跑壞了重跑就好。MapReduce 只是把 sort 那步搬到幾千台機器上——本質沒變。
- 三類系統定位：線上服務在乎回應時間、串流在乎低延遲、批次在乎吞吐量。批次沒有人在等，所以可以為了處理量而犧牲單筆延遲。
- Unix 哲學是根：讓每個程式做好一件事、輸出成為下一個的輸入、用統一介面（一切皆位元組流）串接。邏輯與接線分離（stdin/stdout）＝一種控制反轉。
- 不可變輸入是超能力：輸入不改，於是能反覆執行、任一點截斷檢視、失敗自動重試、同一份輸入餵多個 job。這正是批次比就地更新的線上系統「好推理」的原因。
- MapReduce = 分散式的 Unix：差別只在讀寫的是分散式檔案系統 (HDFS) 而非 stdin/stdout；map 提取 key-value、框架按 key 排序 (shuffle)、reduce 合併同 key。
⚖️ Tradeoffs
MapReduce 執行流程 — map、shuffle、reduce
- Map：讀輸入區塊、每筆記錄提取 key-value。map task 數由輸入區塊數決定。
- Shuffle（隱含）：框架用 key 的 hash 決定每筆送往哪個 reducer；每個 mapper 先在本地依 reducer partition 分割並排序（技術類似 SSTable），reducer 再從各 mapper 拉取對應 partition 合併。
- Reduce：遍歷排序後的 key-value，合併相同 key 的值。reduce task 數由使用者配置。
- 單一 job 能力有限，實務把多個 job 串成 workflow（前一個的輸出目錄＝後一個的輸入目錄），由 Airflow/Oozie 管依賴。
Join 演算法 — reduce-side vs map-side
- Reduce-side sort-merge join：兩邊都以 join key 為 key 送進 shuffle，框架排序後同 key 相鄰落到同一 reducer；用 secondary sort 讓維度記錄先到，reducer 只需在記憶體留一筆維度資料即可 join——不對輸入做任何假設，但排序＋搬運代價高。
- Broadcast hash join（map-side）：大表 join 一個小到可放進記憶體的表時，每個 mapper 啟動先把小表載成 hash table，再掃大表探查。省掉 reducer 與排序。
- Partitioned hash join（map-side）：兩邊以相同方式分區（同 key、同 hash、同 partition 數）時，每個 mapper 只需載入對應 partition 的小表。
- 選哪種取決於資料的物理佈局（是否已分區/已排序）——這類 metadata 由 Hive metastore / HCatalog 維護。
資料傾斜 (Skew) — 熱 key 拖垮單一 reducer
- 某些 key 資料量爆大（名人的社群活動），對應的 reducer 負載遠超其他，成為 hot spot。
- 取樣分散（Pig skewed join）：先取樣找出 hot key，隨機打散到多個 reducer，另一側複製到所有對應 reducer。
- 兩階段聚合：第一階段加隨機前綴做局部聚合、第二階段合併——把一個熱 key 攤成多個。
- 這與分區那一章的熱點問題同源：分散式系統裡「分佈不均」是反覆出現的敵人。
批次輸出的哲學 — 為何是整批替換而非就地寫
- 產物是結構化資料（搜尋索引、ML 模型、推薦資料庫），不是報表。
- 不要在 reducer 裡直接寫線上資料庫：慢、會壓垮 DB、且破壞 all-or-nothing。正解是產出全新的唯讀資料庫檔，載入後原子性切換、失敗可回退。
- 承襲 Unix：輸入不可變、輸出完整替換、無副作用 → 帶來可回滾（改完程式重跑即恢復）、自動重試（輸入不變，失敗 task 安全重跑）、可監控。
超越 MapReduce — 資料流引擎 (Spark / Flink / Tez)
- MapReduce 的痛點是中間狀態物化：每個 job 把輸出整批寫進 HDFS，下個 job 才能開始——straggler 被放大、mapper 常只是多餘地重讀重排、臨時資料被過度複製。
- 資料流引擎把整個 workflow 視為一個 job，處理函式是可自由組合的 operator（不必嚴格 map/reduce 交替）：排序只在需要時做、中間狀態留在記憶體/本地磁碟、operator 輸入就緒即開跑。
- 容錯改用重算：Spark 用 RDD lineage 追血統、Flink 用 operator checkpoint。前提是 operator 確定性（消除 hash 迭代序、亂數、系統時鐘等非確定性）；若中間資料遠小於源或計算極貴，物化反而更划算。
- 高階 API（Hive/Pig/Spark SQL）走宣告式，交給 cost-based optimizer 選 join 演算法與順序，再靠 column 儲存 + vectorized 執行逼近 MPP 資料庫效能，同時保有跑任意程式碼的彈性。
圖處理 — Pregel 與 BSP 模型
- PageRank 這類演算法要反覆遍歷邊、傳播資訊直到收斂，無法用單次 MapReduce pass 表達。
- Pregel（BSP）：每個頂點沿邊發訊息，框架按固定輪次把上一輪的訊息餵給頂點函式；頂點狀態在迭代間留在記憶體、且持久容錯（定期 checkpoint，失敗回滾整圖）。
- 務實提醒：圖若塞得進單機記憶體（甚至單機磁碟，用 GraphChi），單機演算法通常比分散式 Pregel 快——分散式只在圖大到單機裝不下時才划算。
🔑 Takeaways
- 批次的定位是吞吐量優先、沒人在等；它的可靠性來自 Unix 哲學：輸入不可變、輸出整批替換、無副作用，所以失敗能安全重跑、程式改完重跑即恢復。
- MapReduce ＝ 分散式的 Unix：map 提取、按 key hash 做 shuffle 排序、reduce 合併；多個 job 串成 workflow。
- Join 選型看資料物理佈局：無假設就用 reduce-side sort-merge，小表可放記憶體就用 broadcast hash，兩邊同分區就用 partitioned hash；熱 key 造成的傾斜要靠取樣分散或兩階段聚合。
- 資料流引擎 (Spark/Flink) 去掉 MapReduce 的中間狀態物化、改用 lineage/checkpoint 重算容錯，再以宣告式 optimizer + 欄式/vectorized 執行逼近 MPP——批次與 MPP 資料庫正日漸趨同。
No notes yet — jot your takeaways or Q&A here.