MapReduce有什么用

本篇內(nèi)容主要講解“MapReduce有什么用”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“MapReduce有什么用”吧!

1. MapReduce是干啥的

Hadoop實(shí)際上就是谷歌三寶的開源實(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)度。

GFS和BigTable已經(jīng)為我們提供了高性能、高并發(fā)的服務(wù)，但是并行編程可不是所有程序員都玩得轉(zhuǎn)的活兒，如果我們的應(yīng)用本身不能并發(fā)，那GFS、BigTable也都是沒(méi)有意義的。MapReduce的偉大之處就在于讓不熟悉并行編程的程序員也能充分發(fā)揮分布式系統(tǒng)的威力。

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

下面用一個(gè)貫穿全文的例子來(lái)解釋MapReduce是如何工作的。

2. 例子：統(tǒng)計(jì)詞頻

如果我想統(tǒng)計(jì)下過(guò)去10年計(jì)算機(jī)論文出現(xiàn)最多的幾個(gè)單詞，看看大家都在研究些什么，那我收集好論文后，該怎么辦呢？

方法一：我可以寫一個(gè)小程序，把所有論文按順序遍歷一遍，統(tǒng)計(jì)每一個(gè)遇到的單詞的出現(xiàn)次數(shù)，最后就可以知道哪幾個(gè)單詞最熱門了。

這種方法在數(shù)據(jù)集比較小時(shí)，是非常有效的，而且實(shí)現(xiàn)最簡(jiǎn)單，用來(lái)解決這個(gè)問(wèn)題很合適。

方法二：寫一個(gè)多線程程序，并發(fā)遍歷論文。

這個(gè)問(wèn)題理論上是可以高度并發(fā)的，因?yàn)榻y(tǒng)計(jì)一個(gè)文件時(shí)不會(huì)影響統(tǒng)計(jì)另一個(gè)文件。當(dāng)我們的機(jī)器是多核或者多處理器，方法二肯定比方法一高效。但是寫一個(gè)多線程程序要比方法一困難多了，我們必須自己同步共享數(shù)據(jù)，比如要防止兩個(gè)線程重復(fù)統(tǒng)計(jì)文件。

方法三：把作業(yè)交給多個(gè)計(jì)算機(jī)去完成。

我們可以使用方法一的程序，部署到N臺(tái)機(jī)器上去，然后把論文集分成N份，一臺(tái)機(jī)器跑一個(gè)作業(yè)。這個(gè)方法跑得足夠快，但是部署起來(lái)很麻煩，我們要人工把程序copy到別的機(jī)器，要人工把論文集分開，最痛苦的是還要把N個(gè)運(yùn)行結(jié)果進(jìn)行整合（當(dāng)然我們也可以再寫一個(gè)程序）。

方法四：讓MapReduce來(lái)幫幫我們吧！

MapReduce本質(zhì)上就是方法三，但是如何拆分文件集，如何copy程序，如何整合結(jié)果這些都是框架定義好的。我們只要定義好這個(gè)任務(wù)（用戶程序），其它都交給MapReduce。

在介紹MapReduce如何工作之前，先講講兩個(gè)核心函數(shù)map和reduce以及MapReduce的偽代碼。

3. 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ù)。

[plain] view plain copy

 print?

1. map(String key, String value):  

2.     // key: document name  

3.     // value: document contents  

4.     for each word w in value:  

5.         EmitIntermediate(w, "1");  

6.   

7. reduce(String key, Iterator values):  

8.     // key: a word  

9.     // values: a list of counts  

10.     int result = 0;  

11.     for each v in values:  

12.         result += ParseInt(v);  

13.         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ì)被寫到用戶定義的位置，存儲(chǔ)在底層的分布式存儲(chǔ)系統(tǒng)（GFS或HDFS）。

4. MapReduce是如何工作的

一切都是從最上方的user program開始的，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è)稱為master，其余稱為worker，master是負(fù)責(zé)調(diào)度的，為空閑worker分配作業(yè)（Map作業(yè)或者Reduce作業(yè)），worker的數(shù)量也是可以由用戶指定的。

3. 被分配了Map作業(yè)的worker，開始讀取對(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ì)被定期寫入本地磁盤，而且被分為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ù)是寫入底層分布式文件系統(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è)輸出文件。

我更喜歡把流程分為三個(gè)階段。第一階段是準(zhǔn)備階段，包括1、2，主角是MapReduce庫(kù)，完成拆分作業(yè)和拷貝用戶程序等任務(wù)；第二階段是運(yùn)行階段，包括3、4、5、6，主角是用戶定義的map和reduce函數(shù)，每個(gè)小作業(yè)都獨(dú)立運(yùn)行著；第三階段是掃尾階段，這時(shí)作業(yè)已經(jīng)完成，作業(yè)結(jié)果被放在輸出文件里，就看用戶想怎么處理這些輸出了。

5. 詞頻是怎么統(tǒng)計(jì)出來(lái)的

結(jié)合第四節(jié)，我們就可以知道第三節(jié)的代碼是如何工作的了。假設(shè)咱們定義M=5，R=3，并且有6臺(tái)機(jī)器，一臺(tái)master。

這幅圖描述了MapReduce如何處理詞頻統(tǒng)計(jì)。由于map worker數(shù)量不夠，首先處理了分片1、3、4，并產(chǎn)生中間鍵值對(duì)；當(dāng)所有中間值都準(zhǔn)備好了，Reduce作業(yè)就開始讀取對(duì)應(yīng)分區(qū)，并輸出統(tǒng)計(jì)結(jié)果。

6. 用戶的權(quán)利

用戶最主要的任務(wù)是實(shí)現(xiàn)map和reduce接口，但還有一些有用的接口是向用戶開放的。

• an input reader。這個(gè)函數(shù)會(huì)將輸入分為M個(gè)部分，并且定義了如何從數(shù)據(jù)中抽取最初的鍵值對(duì)，比如詞頻的例子中定義文件名和文件內(nèi)容是鍵值對(duì)。

• a partition function。這個(gè)函數(shù)用于將map函數(shù)產(chǎn)生的中間鍵值對(duì)映射到一個(gè)分區(qū)里去，最簡(jiǎn)單的實(shí)現(xiàn)就是將鍵求哈希再對(duì)R取模。

• a compare function。這個(gè)函數(shù)用于Reduce作業(yè)排序，這個(gè)函數(shù)定義了鍵的大小關(guān)系。

• an output writer。負(fù)責(zé)將結(jié)果寫入底層分布式文件系統(tǒng)。

• a combiner function。實(shí)際就是reduce函數(shù)，這是用于前面提到的優(yōu)化的，比如統(tǒng)計(jì)詞頻時(shí)，如果每個(gè)<w, "1">要讀一次，因?yàn)閞educe和map通常不在一臺(tái)機(jī)器，非常浪費(fèi)時(shí)間，所以可以在map執(zhí)行的地方先運(yùn)行一次combiner，這樣reduce只需要讀一次<w, "n">了。

• map和reduce函數(shù)就不多說(shuō)了。

7. MapReduce的實(shí)現(xiàn)

目前MapReduce已經(jīng)有多種實(shí)現(xiàn)，除了谷歌自己的實(shí)現(xiàn)外，還有著名的hadoop，區(qū)別是谷歌是c++，而hadoop是用java。另外斯坦福大學(xué)實(shí)現(xiàn)了一個(gè)在多核/多處理器、共享內(nèi)存環(huán)境內(nèi)運(yùn)行的MapReduce，稱為Phoenix（介紹）。

到此，相信大家對(duì)“MapReduce有什么用”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！