實現(xiàn)機(jī)制
MapReduce操作的執(zhí)行流程圖如圖2-3所示。
用戶程序調(diào)用MapReduce函數(shù)后，會引起下面的操作過程（圖中的數(shù)字標(biāo)示和下面的數(shù)字標(biāo)示相同)：
(1)MapRedube函數(shù)首先把輸入文件分成從塊，每塊大概(可以通過參數(shù)決定)，接著在集群的機(jī)器上執(zhí)行分派處理程序。
(2)這些分派的執(zhí)行程序中有一個程序比較特別，它是主控程序Master。剩下的執(zhí)行程序都是作為Master分派工作的Worker (工作機(jī))?？偣灿蠱個Map任務(wù)和及個Reduce任務(wù)需要分派，Master選擇空閑的Worker來分配這些Map或Reduce任務(wù)。
(3)—個被分配了Map任務(wù)的Worker讀取并處理相關(guān)的輸入塊。它處理輸入的數(shù)據(jù)，并且將分析出的<key,value>對傳遞給用戶定義的Map函數(shù)。Map函數(shù)產(chǎn)生的中間結(jié)果<key，value>對暫時緩沖到內(nèi)存。
(4)這些緩沖到內(nèi)存的中間結(jié)果將被定時寫到本地硬盤，這些數(shù)據(jù)通過分區(qū)函數(shù)分成R個區(qū)。中間結(jié)果在本地硬盤的位置信息將被發(fā)送回Master,然后Master負(fù)責(zé)把這些位置信息傳送給Reduce Worker。
(5)當(dāng)Master通知執(zhí)行Reduce的Worker關(guān)于中間<key,value>對的位置時，它調(diào)用遠(yuǎn)程過程，從Map Worker的本地硬盤上讀取緩沖的中間數(shù)據(jù)。當(dāng)Reduce Worker讀到所有的中間數(shù)據(jù)，它就使用中間key進(jìn)行排序，這樣可使相同key的值都在一起。因為有許多不同key的Map都對應(yīng)相同的Reduce任務(wù)，所以，排序是必需的。如果中間結(jié)果集過于龐大，那么就需要使用外排序。
(6)Reduce Worker根據(jù)每一個唯一中間key來遍歷所有的排序后的中間數(shù)據(jù)，并且把key和相關(guān)的中間結(jié)果值集合傳遞給用戶定義的Reduce函數(shù)。Reduce函數(shù)的結(jié)果寫到一個最終的輸出文件。
(7)當(dāng)所有的Map任務(wù)和Reduce任務(wù)都完成的時候，Master激活用戶程序。此時MapReduce返回用戶程序的調(diào)用點。
由于MapReduce在成百上千臺機(jī)器上處理海量數(shù)據(jù)，所以容錯機(jī)制是不可或缺的?？偟恼f來，MapReduce通過重新執(zhí)行失效的地方來實現(xiàn)容錯。
1. Master 失效
Master會周期性地設(shè)置檢査點（checkpoint),并導(dǎo)出Master的數(shù)據(jù)。一旦某個任務(wù)失效，系統(tǒng)就從最近的一個檢査點恢復(fù)并重新執(zhí)行。由于只有一個Master在運行，如果Master失效了，則只能終止整個MapReduce程序的運行并重新開始。
2. Worker 失效
相對于Master失效而言，Worker失效算是一種常見的狀態(tài)。Master會周期性地給 Worker發(fā)送ping命令，如果沒有Worker的應(yīng)答，則Master認(rèn)為Worker失效，終止對這個 Worker的任務(wù)調(diào)度，把失效Woricer的任務(wù)調(diào)度到其他Worker上重新執(zhí)行。
案例分析
排序通常用于衡量分布式數(shù)據(jù)處理框架的數(shù)據(jù)處理能力，下面介紹如何利用MapReduce進(jìn)行數(shù)據(jù)排序。假設(shè)有一批海量的數(shù)據(jù)，每個數(shù)據(jù)都是由26個字母組成的字符串，原始的數(shù)據(jù)集合是完全無序的，怎樣通過MapReduce完成排序工作，使其有序（字典序）呢？可以通過以下三個步驟來完成。
(1)對原始的數(shù)據(jù)進(jìn)行分割(Split),得到W個不同的數(shù)據(jù)分塊，如圖2-4所示。
(2)對每一個數(shù)據(jù)塊都啟動一個Map進(jìn)行處理，采用桶排序的方法，每個Map中按照首字母將字符串分配到26個不同的桶中，圖2-5是Map的過程及其得到的中間結(jié)果。
(3)對于Map之后得到的中間結(jié)果，啟動26個Reduce。按照首字母將Map中不同桶中的字符串集合放置到相應(yīng)的Reduce中進(jìn)行處理。具體來說就是首字母為a的字符串全部放在Reducel中處理，首字母為b的字符串全部放在RedUCe2,以此類推。每個Reduce對于其中的字符串進(jìn)行排序，結(jié)果直接輸出。由于Map過程中已經(jīng)做到了首字母 有序，Reduce輸出的結(jié)果就是最終的排序結(jié)果。這一過程如圖2-6所示。
從上述過程中可以看出，由于能夠?qū)崿F(xiàn)處理過程的完全并行化，因此利用MapReduce處理海量數(shù)據(jù)是非常適合的。
