第一部分：MapReduce究竟解決什么問題。

很多時候，定義清楚問題比解決問題更難。

1. 什么是MapReduce？

它不是一個產(chǎn)品，而是一種解決問題的思路，它有多個工程實現(xiàn)，Google在論文中也給出了它自己的工程架構(gòu)實現(xiàn)。

2. MapReduce這個編程模型解決什么問題？

能夠用分治法解決的問題，例如：

• 網(wǎng)頁抓取；
• 日志處理；
• 索引倒排；
• 查詢請求匯總；
• …

畫外音：現(xiàn)實中有許多基于分治的應用需求。

3. 為什么是Google，發(fā)明了這個模型？

Google網(wǎng)頁抓取，分析，倒排的多個應用場景，當時的技術(shù)體系，解決不了Google大數(shù)據(jù)量高并發(fā)量的需求，Google被迫進行技術(shù)創(chuàng)新，思考出了這個模型。

畫外音：誰痛誰想辦法。

4. 為什么MapReduce對“能夠用分治法解決的問題”特別有效？

分治法，是將一個大規(guī)模的問題，分解成多個小規(guī)模的問題(分)，多個小規(guī)模問題解決，再統(tǒng)籌小問題的解(合)，就能夠解決大規(guī)模的問題。

5. Google MapReduce為什么能夠成功？

Google為了方便用戶使用系統(tǒng)，提供給了用戶很少的接口，去解決復雜的問題。

• Map函數(shù)接口：處理一個基于key/value(后簡稱kv)的成對(pair)數(shù)據(jù)集合，同時也輸出基于kv的數(shù)據(jù)集合；
• Reduce函數(shù)接口：用來合并Map輸出的kv數(shù)據(jù)集合；

畫外音：MapReduce系統(tǒng)架構(gòu)，能在大規(guī)模普通PC集群上實現(xiàn)并行處理，和GFS等典型的互聯(lián)網(wǎng)架構(gòu)類似。

用戶僅僅關(guān)注少量接口，不用關(guān)心并行、容錯、數(shù)據(jù)分布、負載均衡等細節(jié)，又能夠解決很多實際的問題，還有這等好事！

6. 能不能舉一個例子，說明下MapReduce的Map函數(shù)與Reduce函數(shù)是如何解決實際問題的？

舉例：假設(shè)要統(tǒng)計大量文檔中單詞出現(xiàn)的個數(shù)。

(1) Map

• 輸入KV：pair(文檔名稱，文檔內(nèi)容)
• 輸出KV：pair(單詞，1)

畫外音：一個單詞出現(xiàn)一次，就輸出一個1。

(2) Reduce

• 輸入KV：pair(單詞，1)
• 輸入KV：pair(單詞，總計數(shù))

以下是一段偽代碼：Map(list<pair($doc_name, $doc_content)>){

Map(list<pair($doc_name, $doc_content)>){
    foreach(pair in list)
        foreach($word in $doc_content)
            echo pair($word, 1); // 輸出list<k,v>
}

畫外音：如果有多個Map進程，輸入可以是一個pair，不是一個list。

Reduce(list<pair($word, $count)>){// 大量(單詞,1)
    map<string,int> result;
    foreach(pair in list)
        result[$word] += $count;
    foreach($keyin result)
        echo pair($key, result[$key]); // 輸出list<k,v>
}

畫外音：即使有多個Reduce進程，輸入也是list<pair>，因為它的輸入是Map的輸出。

最早在單機的體系下計算，輸入數(shù)據(jù)量巨大的時候，處理很慢。如何能夠在短時間內(nèi)完成處理，很容易想到的思路是，將這些計算分布在成百上千的主機上，但此時，會遇到各種復雜的問題，例如：

• 并行計算
• 數(shù)據(jù)分發(fā)
• 錯誤處理
• 集群通訊
• …

這些綜合到一起，就成為了一個困難的問題，這也是Google MapReduce工程架構(gòu)要解決的問題。

第二部分：MapReduce的核心優(yōu)化思路。

為了解決上述場景遇到的各種復雜問題，MapReduce的核心優(yōu)化思路是：

• 并行；
• 先分再合；

下圖簡述了MR計算“詞頻統(tǒng)計”的過程。

從左到右四個部分，分別是：

• 輸入文件；
• 分：M個并行的map計算實例；
• 合：R個并行的reduce計算實例；
• 輸出結(jié)果；

先看最后一步，reduce輸出最終結(jié)果。

可以看到，R個reduce實例并發(fā)進行處理，直接輸出最后的計數(shù)結(jié)果。

• 實例1輸出：(a, 256)(able, 128)(emacs, 1)
• 實例2輸出：(f*ck, 32768) (coding, 65535)
• 實例3輸出：(vim,65535)(x, 16)(zero, 258)

畫外音：這就是總結(jié)果，可以看到vim比emacs受歡迎很多。

需要理解的是，由于這是業(yè)務(wù)計算的最終結(jié)果，一個單詞的計數(shù)不會出現(xiàn)在兩個實例里。即：如果(a, 256)出現(xiàn)在了實例1的輸出里，就一定不會出現(xiàn)在其他實例的輸出里。

畫外音：否則的話，還需要合并，就不是最終結(jié)果了。

再看中間步驟，map到reduce的過程。

可以看到，M個map實例的輸出，會作為R個reduce實例的輸入。

1. 潛在問題一：

每個map都有可能輸出(a, 1)，而最終結(jié)果(a, 256)必須由一個reduce輸出，那如何保證每個map輸出的同一個key，落到同一個reduce上去呢？

這就是“分區(qū)函數(shù)”的作用。

(1) 什么是分區(qū)函數(shù)？

分區(qū)函數(shù)，是使用MapReduce的用戶需要實現(xiàn)的，決定map輸出的每一個key應當落到哪個reduce上的函數(shù)。

畫外音：如果用戶沒有實現(xiàn)，會使用默認分區(qū)函數(shù)。

以詞頻統(tǒng)計的應用為例，分區(qū)函數(shù)可能是：

• 以[a-g]開頭的key落到第一個reduce實例；
• 以[h-n]開頭的key落到第二個reduce實例；
• 以[o-z]開頭的key落到第三個reduce實例；

畫外音：有點像數(shù)據(jù)庫水平切分的“范圍法”。

(2) 分區(qū)函數(shù)實現(xiàn)要點是什么？

為了保證每一個reduce實例都能夠差不多時間結(jié)束工作任務(wù)，分區(qū)函數(shù)的實現(xiàn)要點是：盡量負載均衡。

畫外音：即數(shù)據(jù)均勻分攤。

上述詞頻統(tǒng)計的分區(qū)函數(shù)，就不是負載均衡的，有些reduce實例處理的單詞多，有些reduce處理的單詞少，這樣就可能出現(xiàn)，所有reduce實例都處理結(jié)束，最后等待一個長尾reduce的情況。

對于詞頻統(tǒng)計，負載更為均衡的分區(qū)函數(shù)為：

hash(key) % 3

畫外音：有點像數(shù)據(jù)庫水平切分的“哈希法”。

2. 潛在問題二：

每個map都有可能輸出多個(a, 1)，這樣無形中增大了網(wǎng)絡(luò)帶寬資源，以及reduce的計算資源，有沒有辦法進行優(yōu)化呢？

這就是“合并函數(shù)”的作用。

(1) 什么是合并函數(shù)？

有時，map產(chǎn)生的中間key的重復數(shù)據(jù)比重很大，可以提供給用戶一個自定義函數(shù)，在一個map實例完成工作后，本地就做一次合并，這樣網(wǎng)絡(luò)傳輸與reduce計算資源都能節(jié)省很多。

合并函數(shù)在每個map任務(wù)結(jié)束前都會執(zhí)行一次，一般來說，合并函數(shù)與reduce函數(shù)是一樣的，區(qū)別是：

• 合并函數(shù)執(zhí)行map實例本地數(shù)據(jù)合并；
• reduce函數(shù)執(zhí)行最終的合并，會收集多個map實例的數(shù)據(jù)；

對于詞頻統(tǒng)計應用，合并函數(shù)可以將：

一個map實例的多個(a, 1)合并成一個(a, $count)輸出。

最后看第一個個步驟，輸入文件到map的過程。

3. 潛在問題三：如何確定文件到map的輸入呢？

隨意即可，只要負載均衡，均勻切分輸入文件大小就行，不用管分到哪個map實例。

畫外音：無論分到那個map都能正確處理。

結(jié)論，Google MapReduce實施了一系列的優(yōu)化：

• 分區(qū)函數(shù)：保證不同map輸出的相同key，落到同一個reduce里；
• 合并函數(shù)：在map結(jié)束時，對相同key的多個輸出做本地合并，節(jié)省總體資源；
• 輸入文件到map如何切分：隨意，切分均勻就行；

第三部分：MapReduce的工程架構(gòu)實踐。

1. 上述優(yōu)化后的執(zhí)行流程，Google MapReduce通過怎樣的工程架構(gòu)實現(xiàn)的呢？

先看下總體架構(gòu)圖，有個直觀的印象。

2. 用戶使用GoogleMR系統(tǒng)，必須輸入的是什么？

(1) 輸入數(shù)據(jù)，必選

畫外音：否則系統(tǒng)處理啥。

(2) map函數(shù)，必選

(3) reduce函數(shù)，必選

畫外音：分治法，分與合的業(yè)務(wù)邏輯。

(4) 分區(qū)函數(shù)，必選

畫外音：保證同一個key，在合并階段，必須落到同一個reduce上，系統(tǒng)提供默認hash(key)法。

(5) 合并函數(shù)，可選

畫外音：看用戶是否需要在map結(jié)束階段進行優(yōu)化。

3. 用戶提供各個輸入后，GoogleMR的執(zhí)行流程是什么？

畫外音：不妨假設(shè)，用戶設(shè)置了M個map節(jié)點，R個reduce節(jié)點；例如：M=500，R=200。

(1) 在集群中創(chuàng)建大量可執(zhí)行實例副本(fork)；

(2) 這些副本中有一個master，其他均為worker，任務(wù)的分配由master完成， M個map實例和R個reduce實例由worker完成；

(3) 將輸入數(shù)據(jù)分成M份，然后被分配到map任務(wù)的worker，從其中一份讀取輸入數(shù)據(jù)，執(zhí)行用戶的map函數(shù)處理，并在本地內(nèi)存生成臨時數(shù)據(jù)；

(4) 本地內(nèi)存臨時數(shù)據(jù)，通過分區(qū)函數(shù)，被分成R份，周期性的寫到本地磁盤，由master調(diào)度，傳給被分配到reduce任務(wù)的worker；

(5) 負責reduce任務(wù)的worker，從遠程讀取多個map輸出的數(shù)據(jù)，執(zhí)行用戶的reduce函數(shù)處理，處理結(jié)果寫入輸出文件；

畫外音：可能對key要進行外部排序。

(6) 所有map和reduce的worker都結(jié)束工作后，master喚醒用戶程序，MapReduce調(diào)用返回，結(jié)果被輸出到了R個文件中。

4. GoogleMR系統(tǒng)里的master和worker是啥？

(1) master：單點master會存儲一些元數(shù)據(jù)，監(jiān)控所有map與reduce的狀態(tài)，記錄哪個數(shù)據(jù)要給哪個map，哪個數(shù)據(jù)要給哪個reduce，掌控全局視野，做中控；

畫外音：是不是和GFS的master非常像？

(2) worker：多個worker進行業(yè)務(wù)邏輯處理，具體一個worker是用來執(zhí)行map還是reduce，是由master調(diào)度的；

畫外音：是不是和工作線程池非常像？這里的worker是分布在多臺機器上的而已。

5. master的高可用是如何保證的？

一個簡單的方法是，將元數(shù)據(jù)固化到磁盤上，用一個shadow-master來做高可用。

畫外音：GFS不就是這么干的么？

然而現(xiàn)實情況是：沒有將元數(shù)據(jù)固化到磁盤上，元數(shù)據(jù)被存放在master的內(nèi)存里用以提高工作效率，當master掛掉后，通知用戶“任務(wù)執(zhí)行失敗”，讓其選擇重新執(zhí)行。

畫外音：

• (單點master，掌控全局視野，能讓系統(tǒng)的復雜性降低非常多；
• master掛掉的概率很小；
• 不做高可用，能讓系統(tǒng)的復雜性降低非常多；

6. worker的高可用是如何保證的？

master會周期性的ping每個worker，如果超時未返回，master會把對應的worker置為無效，把這個worker的工作任務(wù)重新執(zhí)行：

• 如果重新執(zhí)行的是reduce任務(wù)，不需要有額外的通知；
• 如果重新執(zhí)行的是map任務(wù)，需要通知執(zhí)行reduce的worker節(jié)點，輸入數(shù)據(jù)換了一個worker；

7. 隨時都可能有map或者reduce掛掉，任務(wù)完成前重新被執(zhí)行，會不會影響MR的最終結(jié)果？

在用戶輸入不變的情況下，MR的輸出一定是不變的，這就要求MR系統(tǒng)必須具備冪等性：

• 對相同的輸入，不管哪個負責map的worker執(zhí)行的結(jié)果，一定是不變的，產(chǎn)出的R個本地輸出文件內(nèi)容也一定是不變的；
• 對于M個map，每個map輸出的R個本地文件，只要這些輸入不變，對應接收這些數(shù)據(jù)的reduce的worker執(zhí)行結(jié)果，一定是不變的，輸出文件內(nèi)容也一定是不變的；

8. 長尾效應怎么解決？

一個MR執(zhí)行時間的最大短板，往往是“長尾worker”。

導致“長尾worker”的原因有很多：

(1) 用戶的分區(qū)函數(shù)設(shè)計得不合理，導致某些reduce負載不均，要處理大量的數(shù)據(jù)；

畫外音：

最壞的情況，所有數(shù)據(jù)最終都落到一個reduce上，分布式并行處理，轉(zhuǎn)變?yōu)榱藛螜C串行處理；

所以，分區(qū)函數(shù)的負載均衡性，是用戶需要考慮的。

(2) 因為系統(tǒng)的原因，worker所在的機器磁盤壞了，CPU有問題，也可能導致任務(wù)執(zhí)行很慢；

GoogleMR有一個“備用worker”的機制，當某些worker的執(zhí)行時間超出預期時，會啟動另一個worker執(zhí)行相同的任務(wù)，以嘗試解決長尾效應。

總結(jié)

Google MapReduce架構(gòu)，體現(xiàn)了很多經(jīng)典架構(gòu)實踐：

• 單點master簡化系統(tǒng)復雜度；
• 單點master不高可用，簡化系統(tǒng)復雜度；
• master對worker的監(jiān)控以及重啟，保證worker高可用；
• 冪等性，保證結(jié)果的正確性；
• 多個worker執(zhí)行同一個任務(wù)優(yōu)化長尾問題；

參考：《GFS 經(jīng)典設(shè)計，給了我們哪些架構(gòu)啟示？》

知其然，知其所以然。

思路比結(jié)論更重要。