1、 Jeffrey Dean and Sanjay Ghemawat 制作人：鄭雅潔制作人：鄭雅潔 2015.10.31Jeff Dean，Google的軟件架構天才。Google大型并發編程框架Map/Reduce作者。 在Google，公司最頂尖的編程高手Jeff Dean曾發明過一種先進的方法，該方法可以讓一個程序員在幾分鐘內完成以前需要一個團隊做幾個月的項目。他還發明了一種神奇的計算機語言，可以讓程序員同時在上萬臺機器上用最短的時間完成極為復雜的計算任務。 Jeff Dean于1999年加入Google，目前是Google系統架構小組的成員。他在Google主要負責開發Google的網頁

2、抓取、索引、查詢服務以及廣告系統等，他對搜索質量實現了多次改進，并實現了Google分布式計算架構的多個部分。 在加入Google之前，他工作于 DEC/Compaq的Western實驗室，主要從事軟件分析工具、微處理器架構以及信息檢索等方面的研究。他于1996年在華盛頓大學獲得了博士學位，與Craig Chambers一起從事面向對象語言的編譯器優化技術方面的研究。在畢業之前，他還在世界衛生組織的艾滋病全球規劃署工作過。 What is Map Reduce？ Why do we need Map Reduce？ What is Map Reduce for？什么是Map Reduce？ M

3、apReduce是一個編程模型 概念“Map”和“Reduce”，是他們的主要思想。 微軟著名的C+大師Herb Sutter曾經說過：“The Free Lunch Is Over！”。 隨著摩爾定律的提前終結，免費的午餐終究還要回去。那個依靠硬件升級來提高程序性能的時代已經一去不復返了，面對這一改變，一次全新的軟件開發革命就顯得尤為重要。Map Reduce 應時而生！為什么需要為什么需要Map ReduceMap Reduce？ 在Google，MapReduce用在非常廣泛的應用程序中，包括“分布grep，分布排序，web連接圖反轉，每臺機器的詞矢量，web訪問日志分析，反向索引構建，

4、文檔聚類,機器學習，基于統計的機器翻譯.”值得注意的是，MapReduce實現以后，它被用來重新生成Google的整個索引，并取代老的ad hoc程序去更新索引。Map Reduce 的用途 簡單理解，它主要是兩個過程： map過程，負責把一個龐大的任務，細分成為一個小任務，然后分配到不同的服務器上運行。 reduce過程，則是負責把已經細分的任務的計算結果，重新合并成為想要的完整結果。Map Reduce 的編程模型Example:計算一個大的文檔集合中每個單詞出現的次數map(String key, String value):/ key: document name/ value: do

5、cument contentsfor each word w in value:EmitIntermediate(w, “1);比如我們有篇文檔，內容是 “I am a programmer, you are also a programmer”。經過Map運算后輸出的中間文件將會是：(I,1) ,(am,1) ,(a,1) ,(programmer,1) ,(you,1) ,(are,1) ,(also,1) ,(a,1),(programmer,1).Reduce操作的輸入是單詞和出現次數的序列。用上面的例子 (”I”, 1), (”am”, 1), (”programmer”, 1,1)

6、, (”are”, 1), (”a”, 1,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);最后輸出的最終結果就會是：(”I”, 1), (”a”, 2)Map Reduce 的實現 MapReduce模型可以有多種不同的實現方式。如何正確選擇取決于具體的環境。 Google內部

7、廣泛使用的運算環境的實現：1.x86架構、運行Linux操作系統、雙處理器、2-4GB內存的機器。2.普通的網絡硬件設備，每個機器的帶寬為百兆或者千兆。3.集群中包含成百上千的機器。4.存儲為廉價的內置IDE硬盤。5.用戶提交工作（job）給調度系統。每個工作（job）都包含一系列的任務（task），調度系統將這些任務調度到集群中多臺可用的機器上。Google MapReduce ArchitectureSingle Master nodeMany worker beesMany worker beesMapReduce OperationInitial data splitinto 64MB

8、 blocksComputed, resultslocally storedM sends datalocation to R workersFinal output writtenMaster informed ofresult locations storage location source file ：GFS Map ：local-storage Reduce ：GFS journal ：GFSGFS 也就是 google File System，google公司為了存儲海量搜索數據而設計的專用文件系統。Master的數據結構它存儲每一個Map和Reduce任務的狀態，以及Worker

9、機器(非空閑任務的機器)的標識。 Master就像一個數據管道，中間文件存儲區域的位置信息通過這個管道從Map傳遞到Reduce。 容錯處理 必要性：MapReduce庫的設計初衷是使用由成百上千的機器組成的集群來處理超大規模的數據，所以，這個庫必須要能很好的處理機器故障。兩種主要故障Worker FailureMaster Failure master周期性的ping每個worker。如果在一個約定的時間范圍內沒有收到worker返回的信息，master將把這worker標記為失效。重新執行該節點上正在執行或尚未執行的Map任務重新執行該節點上尚未完成的Reduce任務讓master周期性的

10、將上面描述的數據結構寫入磁盤，即檢查點（checkpoint）。中止MapReduce運算，從檢查點恢復。Task Granularity 任務粒度 在之前的執行概括中，我們把Map拆分成了M個片段、把Reduce拆分成R個片段。理想情況下，M和R應當比集群中worker的機器數量要多得多。在每臺worker機器都執行大量的不同任務能夠提高集群的動態的負載均衡能力，并且能夠加快故障恢復的速度。 但是實際上，在我們的具體實現中對M和R的取值都有一定的客觀限制，因為master必須執行O(M+R)次調度，并且在內存中保存O(M*R)個狀態。 我們把R值設置為我們想使用的worker機器數量的倍數。

11、我們通常會用這樣的比例來執行MapReduce：M=200000，R=5000，使用2000臺worker機器。 Backup Tasks備用任務進程機制類似于木桶效應中的短板，影響一個MapReduce的總執行時間最通常的因素是“Straggler”。 由于其他任務占用資源 磁盤損壞解決辦法：當一個MapReduce操作接近完成的時候，master調度多個backup tasks去完成尚未完成的任務。 誰先完成，就算誰的顯著提高執行效率 Locality本地化策略Master調度策略向GFS詢問獲得輸入文件blocks副本的位置信息 Map Tasks的輸入數據通常按64MB的大小劃分（GF

12、S的block大小） 盡量將一個Map任務調度在包含相關輸入數據拷貝的機器上執行效果 大部分機器從本地讀取輸入文件，節省大量帶寬Refinements技巧Partitioning Function分區函數MapReduce的使用者通常會指定Reduce任務和Reduce任務輸出文件的數量（R）。我們在中間key上使用分區函數來對數據進行分區，之后再輸入到后續任務執行進程。 一個缺省的分區函數是使用hash方法(比如，hash(key) mod R)進行分區。 擴展：使用“hash(Hostname(urlkey) mod R”作為分區函數就可以把所有來自同一個主機的URLs保存在同一個輸出文件

13、中。Refinements技巧Ordering Guarantees順序保證我們確保在給定的分區中，中間key/value pair數據的處理順序是按照key值增量順序處理的。 這樣的順序保證對每個分區生成一個有序的輸出文件 這對于需要對輸出文件按key值隨機存取的應用非常有意義 對在排序輸出的數據集也很有幫助 Refinements技巧 Combiner 函數在某些情況下，Map函數產生的中間key值的重復數據會占很大的比重，并且，用戶自定義的Reduce函數滿足結合律和交換律。我們允許用戶指定一個可選的combiner函數，combiner函數首先在本地將這些記錄進行一次合并，然后將合并的結果發送給Reducer。 Combiner函數在每臺執行Map任務的機器上都會被執行一次 Combiner函數和Reduce函數之間唯一的區別是Reduce函數的輸出被保存在最終的輸出文件里，而Combiner函數的輸出被寫到中間文件里部分的合并中間結果可以顯著的提