一、什么是MapReduce？

MapReduce是一種編程模型，用于大規(guī)模數(shù)據(jù)集（大于1TB）的并行運(yùn)算。概念"Map（映射）"和"Reduce（歸約）"，是它們的主要思想，都是從函數(shù)式編程語(yǔ)言里借來(lái)的，還有從矢量編程語(yǔ)言里借來(lái)的特性。它極大地方便了編程人員在不會(huì)分布式并行編程的情況下，將自己的程序運(yùn)行在分布式系統(tǒng)上。 當(dāng)前的軟件實(shí)現(xiàn)是指定一個(gè)Map（映射）函數(shù)，用來(lái)把一組鍵值對(duì)映射成一組新的鍵值對(duì)，指定并發(fā)的Reduce（歸約）函數(shù)，用來(lái)保證所有映射的鍵值對(duì)中的每一個(gè)共享相同的鍵組。

說(shuō)著挺抽象，我們來(lái)看下圖，首先明確MapReduce在Hadoop項(xiàng)目中的位置。

Hadoop實(shí)際上就是谷歌三寶的開(kāi)源實(shí)現(xiàn)，Hadoop MapReduce對(duì)應(yīng)Google MapReduce，HBase對(duì)應(yīng)BigTable，HDFS對(duì)應(yīng)GFS。HDFS（或GFS）為上層提供高效的非結(jié)構(gòu)化存儲(chǔ)服務(wù)，HBase（或BigTable）是提供結(jié)構(gòu)化數(shù)據(jù)服務(wù)的分布式數(shù)據(jù)庫(kù)，Hadoop MapReduce（或Google MapReduce）是一種并行計(jì)算的編程模型，用于作業(yè)調(diào)度。

簡(jiǎn)單概括的說(shuō)，MapReduce是將一個(gè)大作業(yè)拆分為多個(gè)小作業(yè)的框架（大作業(yè)和小作業(yè)應(yīng)該本質(zhì)是一樣的，只是規(guī)模不同），用戶需要做的就是決定拆成多少份，以及定義作業(yè)本身。

二、map函數(shù)和reduce函數(shù)

map函數(shù)和reduce函數(shù)是交給用戶實(shí)現(xiàn)的，這兩個(gè)函數(shù)定義了任務(wù)本身。

map函數(shù)：接受一個(gè)鍵值對(duì)（key-value pair），產(chǎn)生一組中間鍵值對(duì)。MapReduce框架會(huì)將map函數(shù)產(chǎn)生的中間鍵值對(duì)里鍵相同的值傳遞給一個(gè)reduce函數(shù)。

reduce函數(shù)：接受一個(gè)鍵，以及相關(guān)的一組值，將這組值進(jìn)行合并產(chǎn)生一組規(guī)模更小的值（通常只有一個(gè)或零個(gè)值）。

統(tǒng)計(jì)詞頻的MapReduce函數(shù)的核心代碼非常簡(jiǎn)短，主要就是實(shí)現(xiàn)這兩個(gè)函數(shù)。

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));  

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

三、MapReduce工作原理

上圖是論文里給出的流程圖。一切都是從最上方的user program開(kāi)始的，user program鏈接了MapReduce庫(kù)，實(shí)現(xiàn)了最基本的Map函數(shù)和Reduce函數(shù)。圖中執(zhí)行的順序都用數(shù)字標(biāo)記了。

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

2、user program的副本中有一個(gè)稱(chēng)為master，其余稱(chēng)為worker，master是負(fù)責(zé)調(diào)度的，為空閑worker分配作業(yè)（Map作業(yè)或者Reduce作業(yè)），worker的數(shù)量也是可以由用戶指定的。

3、被分配了Map作業(yè)的worker，開(kāi)始讀取對(duì)應(yīng)分片的輸入數(shù)據(jù)，Map作業(yè)數(shù)量是由M決定的，和split一一對(duì)應(yīng)；Map作業(yè)從輸入數(shù)據(jù)中抽取出鍵值對(duì)，每一個(gè)鍵值對(duì)都作為參數(shù)傳遞給map函數(shù)，map函數(shù)產(chǎn)生的中間鍵值對(duì)被緩存在內(nèi)存中。

4、緩存的中間鍵值對(duì)會(huì)被定期寫(xiě)入本地磁盤(pán)，而且被分為R個(gè)區(qū)，R的大小是由用戶定義的，將來(lái)每個(gè)區(qū)會(huì)對(duì)應(yīng)一個(gè)Reduce作業(yè)；這些中間鍵值對(duì)的位置會(huì)被通報(bào)給master，master負(fù)責(zé)將信息轉(zhuǎn)發(fā)給Reduce worker。

5、master通知分配了Reduce作業(yè)的worker它負(fù)責(zé)的分區(qū)在什么位置（肯定不止一個(gè)地方，每個(gè)Map作業(yè)產(chǎn)生的中間鍵值對(duì)都可能映射到所有R個(gè)不同分區(qū)），當(dāng)Reduce worker把所有它負(fù)責(zé)的中間鍵值對(duì)都讀過(guò)來(lái)后，先對(duì)它們進(jìn)行排序，使得相同鍵的鍵值對(duì)聚集在一起。因?yàn)椴煌逆I可能會(huì)映射到同一個(gè)分區(qū)也就是同一個(gè)Reduce作業(yè)（誰(shuí)讓分區(qū)少呢），所以排序是必須的。

6、reduce worker遍歷排序后的中間鍵值對(duì)，對(duì)于每個(gè)唯一的鍵，都將鍵與關(guān)聯(lián)的值傳遞給reduce函數(shù)，reduce函數(shù)產(chǎn)生的輸出會(huì)添加到這個(gè)分區(qū)的輸出文件中。

7、當(dāng)所有的Map和Reduce作業(yè)都完成了，master喚醒正版的user program，MapReduce函數(shù)調(diào)用返回user program的代碼。

所有執(zhí)行完畢后，MapReduce輸出放在了R個(gè)分區(qū)的輸出文件中（分別對(duì)應(yīng)一個(gè)Reduce作業(yè)）。用戶通常并不需要合并這R個(gè)文件，而是將其作為輸入交給另一個(gè)MapReduce程序處理。整個(gè)過(guò)程中，輸入數(shù)據(jù)是來(lái)自底層分布式文件系統(tǒng)（GFS）的，中間數(shù)據(jù)是放在本地文件系統(tǒng)的，最終輸出數(shù)據(jù)是寫(xiě)入底層分布式文件系統(tǒng)（GFS）的。而且我們要注意Map/Reduce作業(yè)和map/reduce函數(shù)的區(qū)別：Map作業(yè)處理一個(gè)輸入數(shù)據(jù)的分片，可能需要調(diào)用多次map函數(shù)來(lái)處理每個(gè)輸入鍵值對(duì)；Reduce作業(yè)處理一個(gè)分區(qū)的中間鍵值對(duì)，期間要對(duì)每個(gè)不同的鍵調(diào)用一次reduce函數(shù)，Reduce作業(yè)最終也對(duì)應(yīng)一個(gè)輸出文件。

本文參考自  轉(zhuǎn)載請(qǐng)注明文章轉(zhuǎn)載自：慧都控件網(wǎng)