在《谷歌 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 節點拿輸入數據。

答疑解惑

針對上期遺留的問題逐個進行剖析解答。

猜想：map、reduce 函數中間感覺又觸發了“針對同一個單詞的 value 的組合（也就是把相同單詞出現的次數，串在一起）”，不然 reduce 函數怎么能接收到 values（每個單詞對應的出現次數的一串“1”）。

這不就是歸并的事情么！在“一圖解千愁”以及“如何運轉？”環節中均有答案！

疑問 1：map 產生的中間鍵值對，是放到內存、本地磁盤還是放到了 GFS 上存儲？

在“一圖解千愁”以及“如何運轉？”環節中均有答案！

疑問 2：我們寫好了 Map 函數和 Reduce 函數，怎么就跑到了多臺機器上呢？

在“如何運轉？”環節中已經有答案！

好了，這篇分享都到這兒吧，希望你們能夠喜歡，如果感覺有點幫助，那就動動手指轉發分享一下吧。