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