MapReduce原理

MapReduce是一種程式設計模型，用於大規模資料集（大於1TB）的平行運算。概念"Map（映射）"和"Reduce（歸約）"，是它們的主要思想，都是從函數式程式語言裡借來的，還有從向量程式語言裡借來的特性。

它大大方便了程式設計人員在不會分散式並行程式設計的情況下，將自己的程式運行在分散式系統上。目前的軟體實作是指定一個Map（映射）函數，用來把一組鍵值對映射成一組新的鍵值對，指定並發的Reduce（歸約）函數，用來確保所有映射的鍵值對中的每一個共享相同的鍵組。

工作原理(推薦學習：Java影片教學)

#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作業最終也會對應一個輸出檔。

更多Java相關技術文章，請造訪Java開發教學欄位進行學習！

以上是MapReduce原理的詳細內容。更多資訊請關注PHP中文網其他相關文章！