教材:10710周志遠教授平行程式
https://www.youtube.com/playlist?list=PLS0SUwlYe8cxqw70UHOE5n4Lm-mXFXbZT

20250917 筆記
內容可能有錯僅供參考
在這個章節開始投影片和10710周志遠教授平行程式有差異，接下來以
NTHU-PP-2021 (Chinese) 為主

[NTHU-PP-Chap11-MapReduce-Part1 and 2](https://www.youtube.com/watch?v=OE2K5R-UqnE&list=PLQTDfc8kgjhMKtgumyK0gmEelnTtqJGsp&index=25)

搭配 23A~23D Advancing Programming for MapReduce

今日大綱
1.Hadoop 運作原理與程式
2.MapReduce 程式設計模型
3.Hadoop MapReduce 的執行過程與函式
4.進階程式設計技巧

**1. MapReduce 簡介與版本差異**
* **目的**：學習如何撰寫分散式執行的程式，儘管使用者不需要有平行程式設計的概念。
* **作業焦點**：作業將著重於實作 MapReduce 本身，而非 MapReduce 應用。
* **Hadoop (H)**：MapReduce 的一個開源實作，由 Yahoo! 團隊開發，主要使用 Java 語言。
* **版本差異**：
* **Hadoop 1.0 與 2.0 (YARN)**：主要差異在於 2.0 增加了資源管理容器 (resource management container)，提升了執行上的資源配置優勢，但程式設計模型本身變化不大。
* **Hadoop 3.0**：文中提到當時仍處於 2.0 版本，但基本程式設計差異不大。
* **現今應用**：目前 Hadoop 的使用率較少，Scala Spark 應用更為普遍。但對於解決特定分散式計算問題，Hadoop 仍是重要工具。

**2. Hadoop 運作原理與程式提交**
* **管理集群**：Hadoop 是一個管理集群進行分散式計算的軟體。
* **運作流程**：類似於平行程式計算集群：
1. 使用者將程式提交給排程主控端 (schedule master)。
2. 主控端開始產生可分散式計算的任務 (tasks)。
3. 主控端管理這些任務，並處理執行時的錯誤回復 (fault recovery) 等問題。
* **程式執行**：使用者執行一個程式，實際上是在提交一個工作 (job)，由 Hadoop 進行排程與執行。
* **程式撰寫**：需要引用 Hadoop 的相關套件 (package)。

**3. Hadoop MapReduce 套件 (Package) 的區別**
* **舊版**：`org.apache.hadoop.mapred`。
* **新版**：`org.apache.hadoop.mapreduce`。
* **重要提示**：在撰寫或參考範例程式碼時，切勿混用這兩個套件，否則可能產生奇怪的問題。本課程以 `mapreduce` 套件進行解釋。

**4. MapReduce 程式設計模型**
* **Java OO 方式**：透過繼承 (inheritance) 與覆寫 (override) 類別 (class) 中的部分方法來實現。
* **優點**：程式碼量相對較少，只需覆寫特定部分。
* **缺點**：較不直觀，因無法看到整個程式的完整流程。使用者需要了解 Hadoop 框架中各類別的運作方式。
* **可覆寫的函式 (functions)**：
* `Mapper class` 中的 `map function`。
* `Reducer class` 中的 `reduce function`。
* `Partitioner class` 中的 `getPartition function`。
* **核心概念**：需要想像這些類別和覆寫的方法如何協同運作，以實現整個 MapReduce 程式的執行過程。

**5. 關鍵類別 (Key Classes)**
除了 Mapper、Reducer 和 Partitioner 函式之外，主要還有兩個核心類別：
* **`Configuration` 類別**：主要用於設定集群 (cluster) 的參數，決定 MapReduce 引擎如何根據設定來執行和管理工作。
* **`Job` 類別**：描述一個工作 (job)。一個程式 (program) 可以提交多個工作，甚至協調這些工作的運作，將其視為一個單一應用程式。
* 程式提交工作後，可透過 API 查詢工作狀態 (`map progress`, `reduce progress`)、控制工作 (如 `kill job`, `kill task`) 或修改執行時設定。
* **同步 (Synchronous) 提交**：使用 `waitForCompletion()`，主程式會阻塞 (block) 直到工作完成。
* **非同步 (Asynchronous) 提交**：使用 `submit()`，主程式提交後可繼續執行其他任務，並透過 API 查詢工作狀態或進行控制。

**6. Hadoop MapReduce 的執行過程與函式 (Hadoop's Implementation)**
Hadoop 將 MapReduce 的執行過程分為兩個主要階段：Map Phase (M Face) 和 Reduce Phase (Reduce Face)。

**6.1. Map Phase**
由以下幾個過程和函式組成：
* **Split (輸入切割)**：
* `InputFormat class`：負責處理輸入資料的切割。
* **`split` 函式**：讀取一塊資料 (chunk of data)，決定輸出鍵值對 (key-value pair) 的記錄。
* **預設切割**：通常以「一行」作為一個記錄 (record)。
* **Text Input Format**：預設的實作，鍵 (key) 為行號 (line number)，值 (value) 為該行所有文字。
* **KeyValueText Input Format**：可指定分隔符號 (separator character/byte) 來切割一行內的鍵值對。
* **自訂切割**：可以在 `map` 函式內部進一步細切記錄。
* **Map 函式**：
* 每個記錄 (record) 會被傳遞給 `map` 函式。
* 生成零個或多個中間鍵值對 (intermediate key-value pairs)。
* **輸出方式**：透過 `Context object` 來輸出鍵值對。
* **物件生命週期**：輸出的 `Writable object` 必須在類別層級 (class level) 宣告，而非 `map` 函式內部，以避免記憶體釋放導致程式崩潰。
* **Partitioner (分區)**：
* `Partitioner class` 中的 `getPartition` 函式。
* 根據鍵 (key) 的雜湊值 (hash code) 或其他邏輯，決定將記錄發送到哪個 Reducer。
* **目的**：確保每個 Reducer 處理的資料量大致相同 (負載平衡, load balance)，或將特定鍵分配到同一 Reducer 進行處理。
* **回傳值**：Reduer ID (範圍在 0 到 Reducer 數量減一之間)。
* **Combiner (組合器)**：
* **選用 (Optional)**：框架會根據資料量大小決定是否呼叫 Combiner，程式設計師無法控制。
* **功能**：在 Mapper 端進行類似 Reduce 的預先處理，減少傳輸到 Reducer 的資料量，優化網路頻寬。
* **限制**：
* Combiner 的輸出鍵值對資料型別必須與 Mapper 的輸出鍵值對資料型別一致，不能做型別轉換。
* Combiner 必須是「可重複套用」的 (idempotent)，即使多次呼叫或不呼叫，最終結果也必須正確。
* 不適用於需要「全局視圖」的聚合操作 (如中位數計算)。
* **程式碼**：與 Reducer 函式非常相似。

**6.2. Shuffle and Sort Phase (洗牌與排序)**
發生在 Map Phase 和 Reduce Phase 之間。
* **資料傳輸**：Reducer 會從各個 Mapper 任務中拉取 (copy) 其分區後的暫存資料。
* **Shuffle (洗牌)**：
* 在資料傳輸過程中，會使用 `Merge Sort` 演算法進行排序。
* 根據鍵 (key) 的 `compare` 函式定義的順序，收集並排序每個 Mapper 的中間鍵值對。
* **可覆寫**：`Sort Comparator` 函式可用於自訂排序順序 (升序或降序)。
* **Grouping (分組)**：
* 排序完成後，Reducer 拿到的鍵值對已按鍵排序。
* 使用 `Grouping Comparator` 函式，將相同鍵的數值 (values) 合併成一個列表 (list)。
* **可覆寫**：`Grouping Comparator` 函式決定哪些鍵被視為「相同」而分組在一起。
* **結果**：每個鍵會對應一個數值列表。

**6.3. Reduce Phase**
* **Reduce 函式**：
* 針對每個分組後的鍵和其對應的數值列表 (list of values) 進行聚合 (aggregation)。
* 每個鍵會搭配一個值迭代器 (Iterator of values)。
* **Output (輸出)**：
* `OutputFormat class`：負責將結果寫出。
* **`write` 函式**：將處理後的鍵值對寫入最終輸出檔案。
* **預設格式**：通常一個輸出鍵對應一行。
* **可覆寫**：可以自訂輸出格式，例如不換行、只輸出值不輸出鍵等。
* **Text Output Format**：預設的實作，一個鍵值對對應一行。

**7. 資料型別 (Data Types)**
* **強型別 (Strongly Typed)**：Java 要求明確定義資料型別並進行正確的型別轉換。
* **`Writable` 介面**：所有鍵值對的資料型別都必須實作此介面，因為這些物件將在不同類別間處理。
* **`ComparableWritable` 介面**：鍵 (key) 的資料型別除了 `Writable` 外，還必須實作 `Comparable` 介面，以便進行排序。
* **實作方法**：`write()` 和 `readFields()` (用於序列化/反序列化)、`compareTo()` (用於排序)、`hashCode()` (用於 Partitioner)。
* **可定義的型別**：
* `setInputFormatClass`：控制初始輸入鍵值對的型別。
* `setMapOutputKeyClass` / `setMapOutputValueClass`：控制 Mapper 輸出鍵值對的型別。
* `setOutputKeyClass` / `setOutputValueClass`：控制 Reducer 輸出鍵值對的型別 (最終輸出)。
* `setOutputFormatClass`：控制輸出檔案的寫入格式。
* **範例型別**：`IntWritable` (對應 Java int)、`Text` (對應 Java String)，這些都實作了 `Writable` 及 `Comparable` 介面。
* **自訂資料型別**：
* 透過實作 `Writable` 和 `ComparableWritable` 介面，可以自訂複雜的資料型別，如 3D 座標作為鍵。
* 避免在 `map` 函式內進行繁瑣的字串解析和組合，使程式碼更直觀。

**8. Reducer 數量的設定**
* **Mapper 數量**：由輸入檔案的大小和切割方式決定，不可手動設定。
* **Reducer 數量**：可透過 `setNumReduceTasks()` 函式來設定。
* **Reducer 數量過多**：
* 每個 Reducer 處理的工作量減少，導致啟動/停止 Reducer 的開銷 (overhead) 佔比較高。
* 產生過多的輸出檔案，且每個檔案內的鍵可能無法有效排序。
* **Reducer 數量過少 (如一個)**：
* 失去平行處理的優勢，降低平行度。
* **優勢**：可實現「全域排序 (global sorting)」，將所有結果排序在單一輸出檔案中。
* **最佳數量**：通常與 `Reduce slot` 數量相關，應盡量利用硬體資源，但避免過多或過少。

**9. 進階程式設計技巧 (Advanced Programming)**
除了基本的 `map` 和 `reduce` 函式，還可以覆寫其他類別的函式，實現更複雜或高效的計算。

* **1. 自訂資料型別 (Custom Data Types)**
* **目的**：定義特殊的鍵 (key) 或值 (value) 型別，如 3D 座標。
* **實現**：
* 值 (value) 實作 `Writable` 介面。
* 鍵 (key) 實作 `Comparable` 和 `Writable` 介面。
* **需要覆寫的方法**：
* `write(DataOutput out)` 和 `readFields(DataInput in)`：用於資料的序列化 (serialize) 和反序列化 (deserialize)，供 Input/Output Format 類別使用。
* `compareTo(Object o)`：供排序函式 (Sort Comparator) 比較物件大小。
* `hashCode()`：供 Partitioner 函式決定分區。

* **2. 自訂 Partitioner (分區器)**
* **目的**：精確控制鍵值對分配到哪個 Reducer，實現負載平衡或特定鍵的分組。
* **實現**：覆寫 `Partitioner` 類別的 `getPartition` 函式。
* **範例**：將 A-K 開頭的鍵丟到第一個 Reducer，L-Z 開頭的鍵丟到第二個 Reducer。
* **進階應用**：透過資料分析 (profiling/sampling) 了解鍵的分布，進行更精確的負載平衡。

* **3. 自訂 Comparators (比較器)**
* **a. Sort Comparator (排序比較器)**
* **目的**：在 Shuffle 階段定義鍵的排序邏輯。
* **實現**：覆寫 `WritableComparator` 或實作 `RawComparator` 介面。
* **範例**：自訂按鍵的第一個字元排序。
* **b. Grouping Comparator (分組比較器)**
* **目的**：在 Reduce 階段定義哪些鍵被視為「相同」而分組在一起，即使它們在排序上是不同的。
* **實現**：覆寫 `WritableComparator` 或實作 `RawComparator` 介面。
* **範例**：只比較鍵的第一個字元來進行分組。
* **注意**：分組後，Reduer 會將該組的第一個鍵作為代表鍵，並將所有對應的值作為列表處理。

* **4. 二級排序 (Secondary Sort)**
* **問題**：除了按鍵排序，還希望對鍵所對應的值進行排序。例如，按年/月分組，然後按溫度排序。
* **傳統做法的缺點**：將所有值拉到 Reducer 端再排序效率低下。
* **高效實作方法 (Solution 2 - Composite Key)**：
1. **Composite Key (組合鍵)**：在 Mapper 輸出時，將希望進行排序的值也包含在鍵中 (例如：`年,月,溫度` 作為一個鍵)。
2. **自訂 Partitioner**：確保只有年和月相同的記錄被送往同一個 Reducer (Partitioner 只看組合鍵的前半部分，例如年和月)。
3. **自訂 Sort Comparator**：定義排序規則，先按年、月排序，如果年、月相同，再按溫度排序。
4. **自訂 Grouping Comparator**：定義分組規則，只按年、月進行分組，忽略溫度部分。
5. **Reducer 處理**：Reducer 接收到年/月相同但溫度已排序的記錄組。在 `reduce` 函式中，去除鍵中多餘的溫度部分，只輸出年/月和排序過的值列表。
* **優勢**：利用 MapReduce 框架自動化的排序功能，實現值內部的排序，效率高。

---
其他課程連結

[平行程式1C~2B Introduction parallel programming](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/Syxh3H7Kxe)
[平行程式3A~3D The Latest Developments and Applications Using Parallel Programming](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/HJh7QFVKle)
[平行程式4A~4B IO Parallel IO and Program Analysis](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/HJLMsuHFgg)
[平行程式5A~5B The Latest Developments and Applications Using Parallel Programming](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/SJh57hIFle)
[平行程式6A~6B Communication Routines and Parallel Function Code](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/r1X9kX_Fle)
[平行程式 6C~6D Communication Routines and Parallel Function Code](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/S1DPjoYFlx)
[平行程式 7A~8A Pthread:Synchronization Problem & Tools](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/HJu-_0tKge)
[平行程式 8B~8D Synchronization Tools & Open Multi-Processing(OpenMP)](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/H1ki4E2Fee)
[平行程式 9A~9B Synchronization Construct](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/BJTYMrpKlx)
[平行程式 10A~10B Synchronization Tools & Open Multi-Processing Synchronization Construct](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/B1cY6M1qee)
[平行程式 10C~10D Synchronization Tools & Open Multi-Processing Synchronization Construct](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/BkgFaNg5gg)
[平行程式 11A~11B Parallel Work Pool and Termination / Parallel Sorting](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/H1hfOw-5xl)
[平行程式 12A~12B Parallel Sorting and Pipelined Computations](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/Symo-zQ9eg)
[平行程式 12C~12D Parallel Sorting and Pipelined Computations](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/BJYNKDVceg)
[平行程式 13A-13B Sychronous Parallelism](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/HJ2UJ2Bqex)
[平行程式 14A~14B Heterogeneous Computing](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/BksS4yP5eg)
[平行程式 14C~14D Heterogeneous Computing](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/BJrfTUd9xx)
[平行程式 15A~15B Parallel Programming Model on GPU](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/ByWnl-t5gg)
[平行程式 16A~16B What is Compute Unified Device Architecture(CUDA)?](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/HyYpsjcqgl)
[平行程式 17A~18A 平行運算的CUDA](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/H1dUeBT5lg)
[平行程式 18B~19A 記憶體層級 / CUDA的優化](https://hackmd.io/@JuitingChen/HyF44e1jge)
[平行程式 19B~19D 記憶體層級 / CUDA的優化 ](https://hackmd.io/@JuitingChen/ryPEu4lieg)
[平行程式 20A~20B CUDA優化全域和區域記憶體/共享記憶體](https://hackmd.io/@JuitingChen/r1X659Zoxl)
[平行程式 21A~21B Parallel Reduction / Distributed Computing Framework](https://hackmd.io/@JuitingChen/HyiOpozjxl)
[平行程式 NTHU-PP-Chap10-Big Data-Part1 ](https://hackmd.io/@JuitingChen/Hyc-e3Golx)
[平行程式 NTHU-PP-Chap10-Big Data-Part2 ](https://hackmd.io/@JuitingChen/ryC_QTXoxl)
[平行程式 NTHU-PP-Chap11-MapReduce](https://hackmd.io/@JuitingChen/HJgBXJOsge)
[平行程式 NTHU-PP-Chap12-Distributed Training-Part1](https://hackmd.io/@JuitingChen/ryh5hBtsge)
[平行程式 NTHU-PP-Chap12-Distributed Training-Part2](https://hackmd.io/@JuitingChen/rJ2G7kdjxg)
[平行程式 NTHU-PP-Chap12-Distributed Training-Part3](https://hackmd.io/@JuitingChen/HkA471dilx)
[平行程式 NTHU-PP-Chap13-UCX-Part1](https://hackmd.io/@JuitingChen/rJbq103ieg)
[平行程式 NTHU-PP-Chap13-UCX-Part2](https://hackmd.io/@JuitingChen/SJpNmk_ixl)
[平行程式 NTHU-PP-Chap13-UCX-Part3](https://hackmd.io/@JuitingChen/HkIUYa13xe)