mapreduce工作原理

Hadoop簡介

Hadoop就是一個實作了Google雲計算系統的開源系統，包括并行計算模型Map/Reduce，分布式檔案系統HDFS，以及分布式資料庫Hbase，同時Hadoop的相關項目也很豐富，包括ZooKeeper，Pig，Chukwa，Hive，Hbase，Mahout，flume等.

1.什麼是Map/Reduce，看下面的各種解釋：

(1)MapReduce是hadoop的核心元件之一，hadoop要分布式包括兩部分，一是分布式檔案系統hdfs,一部是分布式計算框，就是mapreduce,缺一不可，也就是說，可以通過mapreduce很容易在hadoop平台上進行分布式的計算程式設計。

(2)Mapreduce是一種程式設計模型，是一種程式設計方法，抽象理論。

如果想統計下過去10年計算機論文出現最多的幾個單詞，看看大家都在研究些什麼，那收集好論文後，該怎麼辦呢？

 方法一：

     我可以寫一個小程式，把所有論文按順序周遊一遍，統計每一個遇到的單詞的出現次數，最後就可以知道哪幾個單詞最熱門了。 這種方法在資料集比較小時，是非常有效的，而且實作最簡單，用來解決這個問題很合适。

　方法二：

      寫一個多線程程式，并發周遊論文。

 這個問題理論上是可以高度并發的，因為統計一個檔案時不會影響統計另一個檔案。當我們的機器是多核或者多處理器，方法二肯定比方法一高效。但是寫一個多線程程式要比方法一困難多了，我們必須自己同步共享資料，比如要防止兩個線程重複統計檔案。

方法三：

     把作業交給多個計算機去完成。

 我們可以使用方法一的程式，部署到N台機器上去，然後把論文集分成N份，一台機器跑一個作業。這個方法跑得足夠快，但是部署起來很麻煩，我們要人工把程式copy到别的機器，要人工把論文集分開，最痛苦的是還要把N個運作結果進行整合（當然我們也可以再寫一個程式）。

 方法四：

     讓MapReduce來幫幫我們吧！

 MapReduce本質上就是方法三，但是如何拆分檔案集，如何copy程式，如何整合結果這些都是架構定義好的。我們隻要定義好這個任務（使用者程式），其它都交給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）。

工作原理

 上圖是論文裡給出的流程圖。一切都是從最上方的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函數産生的輸出會添加到這個分區的輸出檔案中。

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

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

面試題部分：

https://blog.csdn.net/wyqwilliam/article/details/81009792