MapReduce

出自 MBA智库百科(https://wiki.mbalib.com/)

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

　　（1）數據劃分和計算任務調度

　　系統自動將一個作業（Job）待處理的大數據劃分為很多個數據塊，每個數據塊對應於一個計算任務（Task），並自動 調度計算節點來處理相應的數據塊。作業和任務調度功能主要負責分配和調度計算節點（Map節點或Reduce節點），同時負責監控這些節點的執行狀態，並 負責Map節點執行的同步控制。

　　（2）數據/代碼互定位

　　為了減少數據通信，一個基本原則是本地化數據處理，即一個計算節點儘可能處理其本地磁碟上所分佈存儲的數據，這實現了代碼向 數據的遷移；當無法進行這種本地化數據處理時，再尋找其他可用節點並將數據從網路上傳送給該節點（數據向代碼遷移），但將儘可能從數據所在的本地機架上尋 找可用節點以減少通信延遲。

　　（3）系統優化

　　為了減少數據通信開銷，中間結果數據進入Reduce節點前會進行一定的合併處理；一個Reduce節點所處理的數據可能會來自多個 Map節點，為了避免Reduce計算階段發生數據相關性，Map節點輸出的中間結果需使用一定的策略進行適當的劃分處理，保證相關性數據發送到同一個 Reduce節點；此外，系統還進行一些計算性能優化處理，如對最慢的計算任務採用多備份執行、選最快完成者作為結果。

　　（4）出錯檢測和恢復

　　以低端商用伺服器構成的大規模MapReduce計算集群中，節點硬體（主機、磁碟、記憶體等）出錯和軟體出錯是常態，因此 MapReduce需要能檢測並隔離出錯節點，並調度分配新的節點接管出錯節點的計算任務。同時，系統還將維護數據存儲的可靠性，用多備份冗餘存儲機制提 高數據存儲的可靠性，並能及時檢測和恢復出錯的數據。

　　MapReduce通過把對數據集的大規模操作分發給網路上的每個節點實現可靠性；每個節點會周期性的返回它所完成的工作和最新的狀態。如果一個節點保持沉默超過一個預設的時間間隔，主節點（類同Google File System中的主伺服器）記錄下這個節點狀態為死亡，並把分配給這個節點的數據發到別的節點。每個操作使用命名文件的原子操作以確保不會發生並行線程間的衝突；當文件被改名的時候，系統可能會把他們複製到任務名以外的另一個名字上去。（避免副作用）。

　　化簡操作工作方式與之類似，但是由於化簡操作的可並行性相對較差，主節點會儘量把化簡操作只分配在一個節點上，或者離需要操作的數據儘可能近的節點上；這個特性可以滿足Google的需求，因為他們有足夠的帶寬，他們的內部網路沒有那麼多的機器。[1]

　　在Google，MapReduce用在非常廣泛的應用程式中，包括“分佈grep，分佈排序，web連接圖反轉，每台機器的詞矢量，web訪問日誌分析，反向索引構建，文檔聚類，機器學習，基於統計的機器翻譯...”值得註意的是，MapReduce實現以後，它被用來重新生成Google的整個索引，並取代老的ad hoc程式去更新索引。

　　MapReduce會生成大量的臨時文件，為了提高效率，它利用Google文件系統來管理和訪問這些文件。

　　在谷歌，超過一萬個不同的項目已經採用MapReduce來實現,包括大規模的演算法圖形處理、文字處理、數據挖掘、機器學習、統計機器翻譯以及眾多其他領域。

　　其他實現

　　Nutch項目開發了一個實驗性的MapReduce的實現，也即是後來大名鼎鼎的hadoop

　　Phoenix是斯坦福大學開發的基於多核/多處理器、共用記憶體的MapReduce實現。

　　（1）向“外”橫向擴展，而非向“上”縱向擴展

　　即MapReduce集群的構建完全選用價格便宜、易於擴展的低端商用伺服器，而非價格昂貴、不易擴展的高端伺服器。

　　對於大規模數據處理，由於有大 量數據存儲需要，顯而易見，基於低端伺服器的集群遠比基於高端伺服器的集群優越，這就是為什麼MapReduce並行計算集群會基於低端伺服器實現的原 因。

　　（2）失效被認為是常態

　　MapReduce集群中使用大量的低端伺服器，因此，節點硬體失效和軟體出錯是常態，因而一個良好設計、具有高容錯性的並行計算系統不能因為節點 失效而影響計算服務的質量，任何節點失效都不應當導致結果的不一致或不確定性；任何一個節點失效時，其他節點要能夠無縫接管失效節點的計算任務；當失效節 點恢復後應能自動無縫加入集群，而不需要管理員人工進行系統配置。

　　MapReduce並行計算軟體框架使用了多種有效的錯誤檢測和恢復機制，如節點自動重 啟技術，使集群和計算框架具有對付節點失效的健壯性，能有效處理失效節點的檢測和恢復。

　　（3）把處理向數據遷移

　　傳統高性能計算系統通常有很多處理器節點與一些外存儲器節點相連，如用存儲區域網路（Storage Area，SAN Network）連接的磁碟陣列，因此，大規模數據處理時外存文件數據I/O訪問會成為一個制約系統性能的瓶頸。

　　為了減少大規模數據並行計算系統中的數據 通信開銷，代之以把數據傳送到處理節點（數據向處理器或代碼遷移），應當考慮將處理向數據靠攏和遷移。MapReduce採用了數據/代碼互定位的技術方法，計算節點將首先儘量負責計算其本地存儲的數據，以發揮數據本地化特點，僅當節點無法處理本地數據時，再採用就近原則尋找其他可用計算節點，並把數據傳送到該可用計算節點。

　　（4）順序處理數據、避免隨機訪問數據

　　大規模數據處理的特點決定了大量的數據記錄難以全部存放在記憶體，而通常只能放在外存中進行處理。由於磁碟的順序訪問要遠比隨機訪問快得多，因此 MapReduce主要設計為面向順序式大規模數據的磁碟訪問處理。

　　為了實現面向大數據集批處理的高吞吐量的並行處理，MapReduce可以利用集群中 的大量數據存儲節點同時訪問數據，以此利用分佈集群中大量節點上的磁碟集合提供高帶寬的數據訪問和傳輸。

　　（5）為應用開發者隱藏系統層細節

　　軟體工程實踐指南中，專業程式員認為之所以寫程式困難，是因為程式員需要記住太多的編程細節（從變數名到複雜演算法的邊界情況處理），這對大腦記憶是 一個巨大的認知負擔，需要高度集中註意力；而並行程式編寫有更多困難，如需要考慮多線程中諸如同步等複雜繁瑣的細節。由於併發執行中的不可預測性，程式的 調試查錯也十分困難；而且，大規模數據處理時程式員需要考慮諸如數據分佈存儲管理、數據分發、數據通信和同步、計算結果收集等諸多細節問題。

　　MapReduce提供了一種抽象機制將程式員與系統層細節隔離開來，程式員僅需描述需要計算什麼（What to compute），而具體怎麼去計算（How to compute）就交由系統的執行框架處理，這樣程式員可從系統層細節中解放出來，而致力於其應用本身計算問題的演算法設計。

　　（6）平滑無縫的可擴展性

　　這裡指出的可擴展性主要包括兩層意義上的擴展性：數據擴展和系統規模擴展性。

　　理想的軟體演算法應當能隨著數據規模的擴大而表現出持續的有效性，性能上的下降程度應與數據規模擴大的倍數相當；在集群規模上，要求演算法的計算性能應能隨著節點數的增加保持接近線性程度的增長。絕大多數現有的單機演算法都達不到 以上理想的要求；把中間結果數據維護在記憶體中的單機演算法在大規模數據處理時很快失效；從單機到基於大規模集群的並行計算從根本上需要完全不同的演算法設計。奇妙的是，MapReduce在很多情形下能實現以上理想的擴展性特征。

　　多項研究發現，對於很多計算問題，基於MapReduce的計算性能可隨節點數目增長保持近似於線性的增長。