MapReduce
優點：可在短時間內完成大量工作。 缺點：算法必須經過重寫，需要對系統工程有一定的理解。 適用數據類型：數值型和標稱型數據。
MapReduce是一個軟件框架，可以將單個計算作業分配給多台計算機執行。它假定這些作業在單機上需要很長的運行時間，因此使用多台機器縮短運行時間。常見的例子是日常統計數字的匯總，該任務單機上執行時間將超過一整天。
儘管有人聲稱他們已經獨立開發過類似的框架，美國還是把MapReduce的專利頒發給了Google。Google公司的Jeffrey Dean和Sanjay Ghemawat在2004年的一篇論文中第一次提出了這個思想，該論文的題目是「MapReduce：Simplified Data Processing on Large Clusters」1MapReduce的名字由函數式編程中常用的map和reduce兩個單詞組成。
1. J. Dean, S. Ghemawat, 「MapReduce: Si mplified Data Processing on Large Cl usters,」 OSDI 』04: 6th Symposium on Operating System Design and Implementa tion, San Francisco, CA, December, 2004.
MapReduce在大量節點組成的集群上運行。它的工作流程是：單個作業被分成很多小份，輸入數據也被切片分發到每個節點，各個節點只在本地數據上做運算，對應的運算代碼稱為mapper，這個過程被稱作map2階段。每個mapper的輸出通過某種方式組合（一般還會做排序）。排序後的結果再被分成小份分發到各個節點進行下一步處理工作。第二步的處理階段被稱為reduce階段，對應的運行代碼被稱為reducer。reducer的輸出就是程序的最終執行結果。
2 map、reduce一般都不翻譯，sort、combine有人分別翻譯成排序、合併。mapper和reducer分別是指進行map和reduce操作的程序或節點，key/value有人翻譯成 鍵/值。這幾個詞，在本章均未翻譯。——譯者注
MapReduce的優勢在於，它使得程序以並行方式執行。如果集群由10個節點組成，而原先的作業需要10個小時來完成，那麼應用MapReduce，該作業將在一個多小時之後得到同樣的結果。舉個例子，給出過去100年內中國每個省每天的正確氣溫數據，我們想知道近100年中國國內的最高氣溫。這裡的數據格式為：<province><data><temp>。為了統計該時段內的最高溫度，可以先將這些數據根據節點數分成很多份，每個節點各自尋找本機數據集上的最高溫度。這樣每個mapper將產生一個溫度，形如<\"max\"><temp>，也就是所有的mapper都會產生相同的key：\"max\"字符串。最後只需要一個reducer來比較所有mapper的輸出，就能得到全局的最高溫度值。
注意：在任何時候，每個mapper或reducer之間都不進行通信3 。每個節點只處理自己的事務，且在本地分配的數據集上運算。
3.這是指mapper各自之間不通信，reducer各自之間不通信，而reducer會接收mapper生成的數據。——譯者注
不同類型的作業可能需要不同數目的reducer。再回到溫度統計的例子，雖然這次使用的數據集相同，但不同的是這裡要找出每年的最高溫度。這樣的話，mapper應先找到每年的最大溫度並輸出，所以中間數據的格式將形如。此外，還需要保證所有同一年的數據傳遞給同一個reducer，這由map和reduce階段中間的sort階段來完成。該例中也給出了MapReduce中值得注意的一點，即數據會以key/value對的形式傳遞。這裡，年代（year）是key，溫度（temp）是value。因此sort階段將按照年代把數據分類，之後合併。最終每個reducer就會收到相同的key值。
從上述例子可以看出，reducer的數量並不是固定的。此外，在MapReduce的框架中還有其他一些靈活的配置選項。MapReduce的整個編配工作由主節點（masternode）控制。這些主節點控制整個MapReduce作業編配，包括每份數據存放的節點位置，以及map、sort和reduce等階段的時序控制等。此外，主節點還要包含容錯機制。一般地，每份mapper的輸入數據會同時分發到多個節點形成多份副本，用於事務的失效處理。一個MapReduce集群的示意圖如圖15-1所示。
圖 15-1 MapReduce框架的示意圖。在該集群中有3台雙核機器，如果機器0失效，作業仍可以正常繼續
圖15-1的每台機器都有兩個處理器，可以同時處理兩個map或者reduce任務。如果機器0在map階段宕機，主節點將會發現這一點。主節點在發現該問題之後，會將機器0移出集群，並在剩餘的節點上繼續執行作業。在一些MapReduce的實現中，在多個機器上都保存有數據的多個備份，例如在機器0上存放的輸入數據可能還存放在機器1上，以防機器0出現問題。同時，每個節點都必須與主節點通信，表明自己工作正常。如果某節點失效或者工作異常，主節點將重啟該節點或者將該節點移出可用機器池。
總結一下上面幾個例子中關於MapReduce的學習要點：
- 主節點控制MapReduce的作業流程；
- MapReduce的作業可以分成map任務和reduce任務；
- map任務之間不做數據交流，reduce任務也一樣；
- 在map和reduce階段中間，有一個sort或combine階段；
- 數據被重複存放在不同的機器上，以防某個機器失效；
- mapper和reducer傳輸的數據形式為key/value對。
Apache的Hadoop項目是MapReduce框架的一個實現。下一節將開始討論Hadoop項目，並介紹如何在Python中使用它。