一、什么是MapReduce？

MapReduce是一種編程模型，用于大規模數據集（大于1TB）的并行運算。概念"Map（映射）"和"Reduce（歸約）"，是它們的主要思想，都是從函數式編程語言里借來的，還有從矢量編程語言里借來的特性。它極大地方便了編程人員在不會分布式并行編程的情況下，將自己的程序運行在分布式系統上。 當前的軟件實現是指定一個Map（映射）函數，用來把一組鍵值對映射成一組新的鍵值對，指定并發的Reduce（歸約）函數，用來保證所有映射的鍵值對中的每一個共享相同的鍵組。

說著挺抽象，我們來看下圖，首先明確MapReduce在Hadoop項目中的位置。

Hadoop實際上就是谷歌三寶的開源實現，Hadoop MapReduce對應Google MapReduce，HBase對應BigTable，HDFS對應GFS。HDFS（或GFS）為上層提供高效的非結構化存儲服務，HBase（或BigTable）是提供結構化數據服務的分布式數據庫，Hadoop MapReduce（或Google MapReduce）是一種并行計算的編程模型，用于作業調度。

簡單概括的說，MapReduce是將一個大作業拆分為多個小作業的框架（大作業和小作業應該本質是一樣的，只是規模不同），用戶需要做的就是決定拆成多少份，以及定義作業本身。

二、map函數和reduce函數

map函數和reduce函數是交給用戶實現的，這兩個函數定義了任務本身。

map函數：接受一個鍵值對（key-value pair），產生一組中間鍵值對。MapReduce框架會將map函數產生的中間鍵值對里鍵相同的值傳遞給一個reduce函數。

reduce函數：接受一個鍵，以及相關的一組值，將這組值進行合并產生一組規模更小的值（通常只有一個或零個值）。

統計詞頻的MapReduce函數的核心代碼非常簡短，主要就是實現這兩個函數。

map(String key, String value):  
    // key: document name  
    // value: document contents  
    for each word w in value:  
        EmitIntermediate(w, "1");  
  
reduce(String key, Iterator values):  
    // key: a word  
    // values: a list of counts  
    int result = 0;  
    for each v in values:  
        result += ParseInt(v);  
        Emit(AsString(result));  

在統計詞頻的例子里，map函數接受的鍵是文件名，值是文件的內容，map逐個遍歷單詞，每遇到一個單詞w，就產生一個中間鍵值對<w, "1">，這表示單詞w咱又找到了一個；MapReduce將鍵相同（都是單詞w）的鍵值對傳給reduce函數，這樣reduce函數接受的鍵就是單詞w，值是一串"1"（最基本的實現是這樣，但可以優化），個數等于鍵為w的鍵值對的個數，然后將這些“1”累加就得到單詞w的出現次數。最后這些單詞的出現次數會被寫到用戶定義的位置，存儲在底層的分布式存儲系統（GFS或HDFS）。

三、MapReduce工作原理

上圖是論文里給出的流程圖。一切都是從最上方的user program開始的，user program鏈接了MapReduce庫，實現了最基本的Map函數和Reduce函數。圖中執行的順序都用數字標記了。

1、MapReduce庫先把user program的輸入文件劃分為M份（M為用戶定義），每一份通常有16MB到64MB，如圖左方所示分成了split0~4；然后使用fork將用戶進程拷貝到集群內其它機器上。

2、user program的副本中有一個稱為master，其余稱為worker，master是負責調度的，為空閑worker分配作業（Map作業或者Reduce作業），worker的數量也是可以由用戶指定的。

3、被分配了Map作業的worker，開始讀取對應分片的輸入數據，Map作業數量是由M決定的，和split一一對應；Map作業從輸入數據中抽取出鍵值對，每一個鍵值對都作為參數傳遞給map函數，map函數產生的中間鍵值對被緩存在內存中。

4、緩存的中間鍵值對會被定期寫入本地磁盤，而且被分為R個區，R的大小是由用戶定義的，將來每個區會對應一個Reduce作業；這些中間鍵值對的位置會被通報給master，master負責將信息轉發給Reduce worker。

5、master通知分配了Reduce作業的worker它負責的分區在什么位置（肯定不止一個地方，每個Map作業產生的中間鍵值對都可能映射到所有R個不同分區），當Reduce worker把所有它負責的中間鍵值對都讀過來后，先對它們進行排序，使得相同鍵的鍵值對聚集在一起。因為不同的鍵可能會映射到同一個分區也就是同一個Reduce作業（誰讓分區少呢），所以排序是必須的。

6、reduce worker遍歷排序后的中間鍵值對，對于每個唯一的鍵，都將鍵與關聯的值傳遞給reduce函數，reduce函數產生的輸出會添加到這個分區的輸出文件中。

7、當所有的Map和Reduce作業都完成了，master喚醒正版的user program，MapReduce函數調用返回user program的代碼。

所有執行完畢后，MapReduce輸出放在了R個分區的輸出文件中（分別對應一個Reduce作業）。用戶通常并不需要合并這R個文件，而是將其作為輸入交給另一個MapReduce程序處理。整個過程中，輸入數據是來自底層分布式文件系統（GFS）的，中間數據是放在本地文件系統的，最終輸出數據是寫入底層分布式文件系統（GFS）的。而且我們要注意Map/Reduce作業和map/reduce函數的區別：Map作業處理一個輸入數據的分片，可能需要調用多次map函數來處理每個輸入鍵值對；Reduce作業處理一個分區的中間鍵值對，期間要對每個不同的鍵調用一次reduce函數，Reduce作業最終也對應一個輸出文件。

本文參考自  轉載請注明文章轉載自：慧都控件網