MapReduce 設計與實現

文章摘要： Master排程Job Worker執行任務重新分配相關worker重新執行一遍故障節點的任務

我曾經多次提到過，我涉獵廣泛，但是沒有有個精通的技能，在大資料領域幾年，也沒什麼成果。

我開始嘗試改變，未來很長一段時間注重修煉內功，是什麼讓我有這樣的改變？ 極客時間 購買《朱贇的技術管理課》， 安姐 聊到很多技術管理經驗，介紹演算法一節： 招式在花哨，敵不過內功深厚 。 安姐 重寫了四遍《演算法導論》中的習題，讓她演算法特別厲害，也介紹演算法的實際意義和價值。

我未來計劃往分散式資料庫相關領域研究，制定一系列計劃，當然去年底就開始執行，通過相關專案、論文、書籍，深入理解電腦科學技術。

歡迎star: https://github.com/jikelab/paper

我的開源專案 企業級流分析平臺 ，即將上線，辛苦碼文件中，已釋出預覽版，月底和大家見面，稍待。

廢話已然太多，今天我們談MapReduce的核心原理，我的閱讀筆記。

MapReduce設計初衷:

[1] x86架構，Linux系統，2-4G內容

[2] 普通網路硬體裝置，百兆/千兆頻寬

[3] 叢集規模成百上千臺，機器故障是常態

[4] Schedule -> Job -> n Task

MapReduce為何如此簡單，很快被大規模應用。MapReduce利用限制性程式設計模式實現了使用者的自動併發處理，並且提供了透明的容錯處理功能。

MapReduce執行流程

Master數據結構，主要排程、監視、Job Metadata資訊(儲存中間臨時資料儲存區域、大小與位置)。

Worker執行任務，Master排程Job Worker執行任務，通過RPC遠端過程呼叫，Worker週期性執行Job狀態彙報，通過心跳機制，超時未彙報，標記為故障節點，Master會進行處理。

容錯特性，設計初衷使成百上千臺機器組成叢集，從而處理大規模資料。

Worker故障

情況一：

master週期性的ping worker節點，如果都能正常反饋，說明無故障。

情況二：

如果超時無反饋，master標記worker節點為失效節點。

故障情況下，master需要重置故障節點任務，重新分配相關worker重新執行一遍故障節點的任務。具體分配策略，根據ping反饋的節點負載情況排程。

Master故障

預防master故障，master需要週期性的寫checkpoint，並且刷落磁碟。Master故障，可以從checkpoint恢復Job故障時的Job執行狀態，繼續執行任務。

確定性函式

Map和Reduce操作是確定性函式，重複執行，保障順序，執行輸出的結果總是一樣的。

input(確定輸入) -> Map(規則函式) -> Reduce(規則函式) -> output(必然確定輸出)

資料本地性

Master在排程worker執行tasks時，會充分考慮資料本地性，儘量本地讀取資料，本地計算，這樣可以大大節省網路頻寬，Master在排程任務時會傳輸相關檔案位置資訊給worker，即使本地性失敗，也會選擇就近的機架伺服器執行計算。

任務粒度

MapReduce任務粒度：M=200000 ,R=5000, 使用2000臺worker機器。

通常第一次批量載入資料進MapReduce程式，我們很難控制並行度，預設由檔案個數決定。很多時候任務都是又多個MapReduce構成，所以Reduce常常是由使用者自己控制，進而控制接下來Map的並行度。

備用任務

在一個大的Job中，有大量的任務，有些任務執行緩慢，我們稱之為 落伍者 ，它會拖慢整體進度。

造成 落伍者 情況有很多，網路問題、硬體故障、系統負載、資源搶佔。當大多數任務均執行完畢，通過Worker任務週期性彙報Master，獲知 落伍者 執行的任務情況，這個時候master會啟用備用任務，執行相同的task，通常比正常多消耗百分之幾的資源，加速任務執行時間。

分割槽函式

[1] 控制Reduce任務 -> 控制任務輸出檔案數

[2] 預設分割槽函式 -> hash(key) mod R

[3] hash是平衡分割槽比較合理的方式

[4] 使用者自定義分割槽 -> 產生相同key資料輸出到同一個檔案的效果

分割槽中，中間key/value pari資料，保障key增量順序處理。保障每個檔案是有序的預設支援，對於基於key隨機存取，排序資料友好，可加速處理。

combiner函式

特殊應用場景需要使用combiner處理，比如：單詞記數程式，Map出現大量的重複記資料，而在Reduce階段需要合併，如果在map -> reduce之間加一層combiner操作，無疑可加速reduce處理時間。

計數器

通過統計task時間發生的次數，master週期性ping worker，在反饋資料包中傳輸任務執行詳細情況。幫助記錄和監控各個節點任務執行階段和評估預計執行時間，通過詳細的統計資訊，幫助優化MapReduce程式。比如：跳過損壞記錄，可把跳過檔案路徑，檔名，跳過的檔案行詳細資訊反饋到計數器頁面，幫助開發人員，定位資料質量或程式錯誤。

小結

MR封裝，為何能在資料分析領域大規模應用。

[1] 並行處理 [2] 負載均衡 [3] 容錯處理 [4] 易於使用 [5] 資料本地化優化

除以上MapReduce優勢，還得益於一個強大的分散式檔案系統GFS，提供超強的高可擴充套件的檔案管理。

我們也從 MapReduce 開發過程中學到了不少東西。首先，約束程式設計模式使得並行和分散式計算非常容易，也易於構造容錯的計算環境;其次，網路頻寬是稀有資源。大量的系統優化是針對減少網路傳輸量為目的的: 資料本地化優化策略使大量的資料從本地磁碟讀取，中間檔案寫入本地磁碟、並且只寫一份中間檔案也節約了網路頻寬;第三，多次執行相同的任務可以減少效能緩慢的機器帶來的負面影響(alex 注: 即硬體配置不平衡)，同時解決了由於機器失效導致的資料丟失問題。