在《谷歌 MapReduce 初探》中，我們通過統計詞頻的 WordCount 經典案例，對 Google 推出的 MapReduce 編程模型有了一個認識，但是那種認識，還只是停留在知道有那么個模型存在，并沒有認識到骨子里，而且上次初探，也遺留了很多猜想和疑問，這次不妨讓我們深入去認識一下 MapReduce，希望能達到一個質的認識，

重點回顧

MapReduce 主要思想是分治法，采取分而治之的思想，將一個大規模的問題，分成多個小規模的問題，把多個小規模問題解決，然后再合并小規模問題的結果，就能夠解決大規模的問題，

這么聊下去，我感徑訓讓你們很懵圈！那不妨舉點栗子，舉栗解千愁，

舉個不太恰當的栗子，不知道大家有沒有在農村掰過玉米，我小時候還沒有自動收割機，每當玉米熟了的時候，都是靠人工去掰，要是家庭里只有一個勞動力，那只能一垅一垅的去掰；如果家庭勞動力比較多，就可以分配任務，同時去掰多垅玉米，人手一垅玉米，掰的程序放到籃子里或者地上就行，因為有專門的人手負責打包裝車，這樣很快一畝地就掰完了，而且能很快統計出掰了幾車玉米，

人多力量大，不知道大家能否感受到一絲“分而治之”的理念；多個勞動力人手一行玉米，不知道大家有沒有感覺到一絲 “MapReduce 之 Map”的概念；專門的人力負責打包裝車，不知道大家有沒有感覺到一絲“Map Reduce 之 Reduce”的概念，

再為你假設一個場景，面試的時候給你一個陣列：{10,6,7,1,3,9,4,2} 要實作排序，

實作方式會有千萬種，而我們只提“歸并排序”，因為它是建立在歸并操作上的一種有效的排序演算法，并且是采用分治法（Divide and Conquer）的一個非常典型的應用，

如上圖示意，歸并排序的程序已經把分治的思想表達的很清楚了，有對演算法感興趣的可以自行深入，

一圖解千愁

為了我們更清晰的了解 MapReduce 的流程，懶癌犯了，就不畫圖了，肆意找了一張圖貼上，圖上字字珠璣，一定要好好揣摩要傳達的意思，切記一定要記住整個流程（重點是磁區，歸并），

重拾案例

通過上面不太恰當的例子和圖，稍微對 MapRedcue 的思想抽象了一下，不知道大家有沒有什么感觸呢？接下來讓我們重拾上次分享提到的“WordCount”的經典案例，窺探一下具體的執行程序，

剖析背后，如圖示意，主要參與者角色分為 User Program、Master 以及系列 Worker，

User Program 顧名思義就是我們實作好的業務邏輯處理的 MapReduce 程式代碼；

Master 從圖中也能夠看出來承擔了任務分配，能夠把任務指派給 map worker 和 reduce worker（應該會存盤一些元資料，記錄哪些資料要給哪些 map worker，哪些資料要給哪些 reduce worker），猜想應該也會跟蹤維護任務的狀態；其實也就是皇上，掌控全域，

Worker 從圖中能夠看出主要分為 Map Worker、Reduce Worker，

Map Worker 從圖中也能看出來負責接收用戶的輸入，然后執行用戶實作的 map 操作，結果寫入本地中間檔案，

Reduce Worker 從圖中能夠看出來能夠讀取 Map Worker 產生的中間檔案，并執行用戶實作的 reduce 操作，并把結果輸出（例如寫到 GFS 存盤），

如何運轉？這里要提一本書《大資料技術原理與應用》，因為下面這段剖析來自于這本書，

（1）執行 WordCount 的用戶程式（采用 MapReduce 撰寫），會被系統分發部署到集群中的多臺機器上，其中一臺機器作為 Master，負責協調調度作業的執行，其余機器作為 Worker，可以執行 Map 或 Reduce 任務，

（2）系統分配一部分 Worker 執行 Map 任務，一部分 Worker 執行 Reduce 任務；MapReduce 將輸入檔案切分成 M 個分片，Master 將 M 個分片分給處于空閑狀態的 N 個 Worker 來處理，

（3）執行 Map 任務的 Worker 讀取輸入檔案，執行 Map 操作，生成一系列 <key,value> 形式的中間結果，并將中間結果保存在記憶體的緩沖區中，

（4）緩沖區中的中間結果會被定期刷寫到本地磁盤上，并被劃分為 R 個磁區，這 R 個磁區會被分發給 R 個執行 Reduce 任務的 Worker 進行處理；Master 會記錄這 R 個磁區在磁盤上的存盤位置，并通知 R 個執行 Reduce 任務的 Worker 來“領取”屬于自己處理的那些磁區的資料，

（5）執行 Reduce 任務的 Worker 收到 Master 的通知后，就到相應的 Map 機器上“領回”屬于自己處理的磁區，不過可能會從多個 Map 機器上領取資料，因此當所有 Map 機器上的屬于自己處理的資料都已經領取回來以后，這個 Reduce 任務的 Worker 會對領取的鍵值對進行排序（如果記憶體中放不下需要用到外部排序），使得具有相同 Key 的鍵值對聚集在一起，然后就可以開始執行具體的 Reduce 操作了，

（6）執行 Reduce 任務的 Worker 遍歷中間資料，對每一個唯一 key 進行 Reduce 函式，結果寫入到輸出檔案中；執行完畢后，喚醒用戶程式，回傳結果，

可靠性保證？

Master 的可用性？認為 Master 掛掉幾率很小，如果掛掉任務就執行失敗，

Worker 的可用性？Master 每隔一段時間會 ping 每個 Worker，如果 Worker 長時間沒回復，Master 就將它標記為失效，如果失效的的 Worker 執行的是 Map 任務，則需要通知對應的 reduce 的 Worker 節點去新的 Map Worker 節點拿輸入資料，