文章來自于：http://www.cnblogs.com/geekma/p/3139823.html

MapReduce：大型集群上的簡單數(shù)據(jù)處理

摘要

MapReduce是一個(gè)設(shè)計(jì)模型，也是一個(gè)處理和產(chǎn)生海量數(shù)據(jù)的一個(gè)相關(guān)實(shí)現(xiàn)。用戶指定一個(gè)用于處理一個(gè)鍵值（key-value）對生成一組key/value對形式的中間結(jié)果的map函數(shù)，以及一個(gè)將中間結(jié)果鍵相同的鍵值對合并到一起的reduce函數(shù)。許多現(xiàn)實(shí)世界的任務(wù)都能滿足這個(gè)模型，如這篇文章所示。

使用這個(gè)功能形式實(shí)現(xiàn)的程序能夠在大量的普通機(jī)器上并行執(zhí)行。這個(gè)運(yùn)行程序的系統(tǒng)關(guān)心下面的這些細(xì)節(jié)：輸入數(shù)據(jù)的分區(qū)、一組機(jī)器上調(diào)度程序執(zhí)行、處理機(jī)器失敗問題，以及管理所需的機(jī)器內(nèi)部的通信。這使沒有任何并行處理和分布式系統(tǒng)經(jīng)驗(yàn)的程序員能夠利用這個(gè)大型分布式系統(tǒng)的資源。

我們的MapReduce實(shí)現(xiàn)運(yùn)行在一個(gè)由普通機(jī)器組成的大規(guī)模集群上，具有很高的可擴(kuò)展性：一個(gè)典型的MapReduce計(jì)算會在幾千臺機(jī)器上處理許多TB的數(shù)據(jù)。程序員們發(fā)現(xiàn)這個(gè)系統(tǒng)很容易使用：目前已經(jīng)實(shí)現(xiàn)了幾百個(gè)MapReduce程序，在Google的集群上，每天有超過一千個(gè)的MapReduce工作在運(yùn)行。

一、??????? 介紹

在過去的5年中，本文作者和許多Google的程序員已經(jīng)實(shí)現(xiàn)了數(shù)百個(gè)特定用途的計(jì)算程序，處理了海量的原始數(shù)據(jù)，包括抓取到的文檔、網(wǎng)頁請求日志等，計(jì)算各種衍生出來的數(shù)據(jù)，如反向索引、網(wǎng)頁文檔的圖形結(jié)構(gòu)的各種表示、每個(gè)host下抓取到的頁面數(shù)量的總計(jì)、一個(gè)給定日期內(nèi)的最頻繁查詢的集合等。大多數(shù)這種計(jì)算概念明確。然而，輸入數(shù)據(jù)通常都很大，并且計(jì)算必須分布到數(shù)百或數(shù)千臺機(jī)器上以確保在一個(gè)合理的時(shí)間內(nèi)完成。如何并行計(jì)算、分布數(shù)據(jù)、處理錯(cuò)誤等問題使這個(gè)起初很簡單的計(jì)算，由于增加了處理這些問題的很多代碼而變得十分復(fù)雜。

為了解決這個(gè)復(fù)雜問題，我們設(shè)計(jì)了一個(gè)新的抽象模型，它允許我們將想要執(zhí)行的計(jì)算簡單的表示出來，而隱藏其中并行計(jì)算、容錯(cuò)、數(shù)據(jù)分布和負(fù)載均衡等很麻煩的細(xì)節(jié)。我們的抽象概念是受最早出現(xiàn)在lisp和其它結(jié)構(gòu)性語言中的map和reduce啟發(fā)的。我們認(rèn)識到，大多數(shù)的計(jì)算包含對每個(gè)在輸入數(shù)據(jù)中的邏輯記錄執(zhí)行一個(gè)map操作以獲取一組中間key/value對，然后對含有相同key的所有中間值執(zhí)行一個(gè)reduce操作，以此適當(dāng)?shù)暮喜⒅暗难苌鷶?shù)據(jù)。由用戶指定map和reduce操作的功能模型允許我們能夠簡單的進(jìn)行并行海量計(jì)算，并使用re-execution作為主要的容錯(cuò)機(jī)制。

這項(xiàng)工作的最大貢獻(xiàn)是提供了一個(gè)簡單的、強(qiáng)大的接口，使我們能夠自動的進(jìn)行并行和分布式的大規(guī)模計(jì)算，通過在由普通PC組成的大規(guī)模集群上實(shí)現(xiàn)高性能的接口來進(jìn)行合并。

第二章描述了基本的編程模型，并給出了幾個(gè)例子。第三章描述了一個(gè)為我們的聚類計(jì)算環(huán)境定制的MapReduce接口實(shí)現(xiàn)。第四章描述了我們發(fā)現(xiàn)對程序模型很有用的幾個(gè)優(yōu)化。第六章探索了MapReduce在Google內(nèi)部的使用，包括我們在將它作為生產(chǎn)索引系統(tǒng)重寫的基礎(chǔ)的一些經(jīng)驗(yàn)。第七章討論了相關(guān)的和未來的工作。

二、??????? 編程模型

這個(gè)計(jì)算輸入一個(gè)key/value對集合，產(chǎn)生一組輸出key/value對。MapReduce庫的用戶通過兩個(gè)函數(shù)來標(biāo)識這個(gè)計(jì)算：Map和Reduce。

Map，由用戶編寫，接收一個(gè)輸入對，產(chǎn)生一組中間key/value對。MapReduce庫將具有相同中間key I的聚合到一起，然后將它們發(fā)送給Reduce函數(shù)。

Reduce，也是由用戶編寫的，接收中間key I和這個(gè)key的值的集合，將這些值合并起來，形成一個(gè)盡可能小的集合。通常，每個(gè)Reduce調(diào)用只產(chǎn)生0或1個(gè)輸出值。這些中間值經(jīng)過一個(gè)迭代器（iterator）提供給用戶的reduce函數(shù)。這允許我們可以處理由于數(shù)據(jù)量過大而無法載入內(nèi)存的值的鏈表。

2.1 例子

考慮一個(gè)海量文件集中的每個(gè)單詞出現(xiàn)次數(shù)的問題，用戶會寫出類似于下面的偽碼：

?

Map函數(shù)對每個(gè)單詞增加一個(gè)相應(yīng)的出現(xiàn)次數(shù)（在這個(gè)例子中僅僅為“1”）。Reduce函數(shù)將一個(gè)指定單詞所有的計(jì)數(shù)加到一起。

此外，用戶使用輸入和輸出文件的名字、可選的調(diào)節(jié)參數(shù)編寫代碼，來填充一個(gè)mapreduce規(guī)格對象，然后調(diào)用MapReduce函數(shù)，并把這個(gè)對象傳給它。用戶的代碼與MapReduce庫（C++實(shí)現(xiàn)）連接到一起。。附錄A包含了這個(gè)例子的整個(gè)程序。

2.2 類型

盡管之前的偽代碼中使用了字符串格式的輸入和輸出，但是在概念上，用戶定義的map和reduce函數(shù)需要相關(guān)聯(lián)的類型：

map?????? (k1, v1) ? ? ? ? ? ? ? ? ? ? ?--> ? ? ? ? list(k2, v2)

reduce?? (k2, list(v2)) ? ? ? ? ? ? ? ?--> ? ? ? ? ?list(v2)

也就是說，輸入的鍵和值和輸出的鍵和值來自不同的域。此外，中間結(jié)果的鍵和值與輸出的鍵和值有相同的域。

MapReduce的C++實(shí)現(xiàn)與用戶定義的函數(shù)使用字符串類型進(jìn)行參數(shù)傳遞，將類型轉(zhuǎn)換的工作留給用戶的代碼來處理。

2.3 更多的例子

這里有幾個(gè)簡單有趣的程序，能夠使用MapReduce計(jì)算簡單的表示出來。

分布式字符串查找（Distributed Grep）：map函數(shù)將匹配一個(gè)模式的行找出來。Reduce函數(shù)是一個(gè)恒等函數(shù)，只是將中間值拷貝到輸出上。

URL訪問頻率計(jì)數(shù)（Count of URL Access Frequency）：map函數(shù)處理web頁面請求的日志，并輸出<URL, 1>。Reduce函數(shù)將相同URL的值累加到一起，生成一個(gè)<URL, total count>對。

翻轉(zhuǎn)網(wǎng)頁連接圖（Reverse Web-Link Graph）：map函數(shù)為在一個(gè)名為source的頁面中指向目標(biāo)（target）URL的每個(gè)鏈接輸出<target, source>對。Reduce函數(shù)將一個(gè)給定目標(biāo)URL相關(guān)的所有源（source）URLs連接成一個(gè)鏈表，并生成對：<target, list(source)>。

主機(jī)關(guān)鍵向量指標(biāo)（Term-Vector per Host）：一個(gè)檢索詞向量將出現(xiàn)在一個(gè)文檔或是一組文檔中最重要的單詞概述為一個(gè)<word, frequency>對鏈表。Map函數(shù)為每個(gè)輸入文檔產(chǎn)生一個(gè)<hostname, term vector>（hostname來自文檔中的URL）。Reduce函數(shù)接收一個(gè)給定hostname的所有文檔檢索詞向量，它將這些向量累加到一起，將罕見的向量丟掉，然后生成一個(gè)最終的<hostname, term vector>對。

倒排索引（Inverted Index）：map函數(shù)解析每個(gè)文檔，并生成一個(gè)<word, document ID>序列。Reduce函數(shù)接收一個(gè)給定單詞的所有鍵值對，所有的輸出對形成一個(gè)簡單的倒排索引。可以通過對計(jì)算的修改來保持對單詞位置的追蹤。

分布式排序（Distributed Sort）：map函數(shù)將每個(gè)記錄的key抽取出來，并生成一個(gè)<key, record>對。Reduce函數(shù)不會改變?nèi)魏蔚逆I值對。這個(gè)計(jì)算依賴了在4.1節(jié)提到的分區(qū)功能和4.2節(jié)提到的排序?qū)傩浴?/p>

三、??????? 實(shí)現(xiàn)

MapReduce接口有很多不同的實(shí)現(xiàn)，需要根據(jù)環(huán)境來做出合適的選擇。比如，一個(gè)實(shí)現(xiàn)可能適用于一個(gè)小的共享內(nèi)存機(jī)器，而另一個(gè)實(shí)現(xiàn)則適合一個(gè)大的NUMA多處理器機(jī)器，再另一個(gè)可能適合一個(gè)更大的網(wǎng)絡(luò)機(jī)器集合。

這一章主要描述了針對在Google內(nèi)部廣泛使用的計(jì)算環(huán)境的一個(gè)實(shí)現(xiàn)：通過交換以太網(wǎng)將大量的普通PC連接到一起的集群。在我們的環(huán)境中：

（1）??? 機(jī)器通常是雙核x86處理器、運(yùn)行Linux操作系統(tǒng)、有2-4G的內(nèi)存。

（2）??? 使用普通的網(wǎng)絡(luò)硬件—通常是100Mb/s或者是1Gb/s的機(jī)器帶寬，但是平均值遠(yuǎn)小于帶寬的一半。

（3）??? 由數(shù)百臺或者數(shù)千臺機(jī)器組成的集群，因此機(jī)器故障是很平常的事

（4）??? 存儲是由直接裝在不同機(jī)器上的便宜的IDE磁盤提供。一個(gè)內(nèi)部的分布式文件系統(tǒng)用來管理存儲這些磁盤上的數(shù)據(jù)。文件系統(tǒng)在不可靠的硬件上使用副本機(jī)制提供了可用性和可靠性。

（5）??? 用戶將工作提交給一個(gè)調(diào)度系統(tǒng)，每個(gè)工作由一個(gè)任務(wù)集組成，通過調(diào)度者映射到集群中可用機(jī)器的集合上。

3.1 執(zhí)行概述

通過自動的將輸入數(shù)據(jù)分區(qū)成M個(gè)分片，Map調(diào)用被分配到多臺機(jī)器上運(yùn)行。數(shù)據(jù)的分片能夠在不同的機(jī)器上并行處理。使用分區(qū)函數(shù)（如，hash(key) mod R）將中間結(jié)果的key進(jìn)行分區(qū)成R個(gè)分片，Reduce調(diào)用也被分配到多臺機(jī)器上運(yùn)行。分區(qū)的數(shù)量（R）和分區(qū)函數(shù)是由用戶指定的。

?

圖1：執(zhí)行概述

圖1中顯示了我們實(shí)現(xiàn)的一個(gè)MapReduce操作的整個(gè)流程。當(dāng)用戶程序調(diào)用MapReduce函數(shù)時(shí)，下面一系列的行為將會發(fā)生（圖1中所使用的數(shù)字標(biāo)識將與下面列表中的相對應(yīng)）：

1. 用戶程序中的MapReduce庫會先將輸入文件分割成M個(gè)通常為16MB-64MB大小的片（用戶可以通過可選參數(shù)進(jìn)行控制）。然后它將在一個(gè)集群的機(jī)器上啟動許多程序的拷貝。

2. 這些程序拷貝中的一個(gè)是比較特殊的——master。其它的拷貝都是工作進(jìn)程，是由master來分配工作的。有M個(gè)map任務(wù)和R個(gè)reduce任務(wù)被分配。Master挑選出空閑的工作進(jìn)程，并把一個(gè)map任務(wù)或reduce任務(wù)分配到這個(gè)進(jìn)程上。

3. 一個(gè)分配了map任務(wù)的工作進(jìn)程讀取相關(guān)輸入分片的內(nèi)容，它將從輸入數(shù)據(jù)中解析出key/value對，并將其傳遞給用戶定義的Map函數(shù)。Map函數(shù)生成的中間key/value對緩存在內(nèi)存中。

4. 緩存中的鍵值對周期性的寫入到本地磁盤，并通過分區(qū)函數(shù)分割為R個(gè)區(qū)域。將這些緩存在磁盤上的鍵值對的位置信息傳回給master，master負(fù)責(zé)將這些位置信息傳輸給reduce工作進(jìn)程。

5. 當(dāng)一個(gè)reduce工作進(jìn)程接收到master關(guān)于位置信息的通知時(shí)，它將使用遠(yuǎn)程調(diào)用函數(shù)（RPC）從map工作進(jìn)程的磁盤上讀取緩存的數(shù)據(jù)。當(dāng)reduce工作進(jìn)程讀取完所有的中間數(shù)據(jù)后，它將所有的中間數(shù)據(jù)按中間key進(jìn)行排序，以保證相同key的數(shù)據(jù)聚合在一起。這個(gè)排序是需要的，因?yàn)橥ǔＴS多不同的key映射到相同的reduce任務(wù)上。如果中間數(shù)據(jù)的總量太大而無法載入到內(nèi)存中，則需要進(jìn)行外部排序。

6. reduce工作進(jìn)程迭代的訪問已排序的中間數(shù)據(jù)，并且對遇到的每個(gè)不同的中間key，它會將key和相關(guān)的中間values傳遞給用戶的Reduce函數(shù)。Reduce函數(shù)的輸出追加到當(dāng)前reduce分區(qū)一個(gè)最終的輸出文件上。

7. 當(dāng)所有的map任務(wù)和reduce任務(wù)完成后，master會喚醒用戶程序。這時(shí)候，用戶程序中的MapReduce調(diào)用會返回到用戶代碼上。

在成功完成后，MapReduce操作輸出到R個(gè)輸出文件（每個(gè)reduce任務(wù)生成一個(gè)，文件名是由用戶指定的）中的結(jié)果是有效的。通常，用戶不需要合并這R個(gè)輸出文件，它們經(jīng)常會將這些文件作為輸入傳遞給另一個(gè)MapReduce調(diào)用，或者在另一個(gè)處理這些輸入分區(qū)成多個(gè)文件的分布式應(yīng)用中使用。

3.2 Master數(shù)據(jù)結(jié)構(gòu)

Master保留了幾個(gè)數(shù)據(jù)結(jié)構(gòu)。對于每個(gè)Map和Reduce任務(wù)，它存儲了它們的狀態(tài)（idle、in-progress或者completed），以及工作進(jìn)程機(jī)器的特性（對于非空閑任務(wù)）。

Master是中間文件區(qū)域的位置信息從map任務(wù)傳送到reduce任務(wù)的一個(gè)通道。因此，對于每個(gè)完成的map任務(wù)來說，master存儲了map任務(wù)產(chǎn)生的R個(gè)中間文件區(qū)域的位置信息和大小。在map任務(wù)完成時(shí)，master會接收到更新這個(gè)含有位置信息和大小信息的消息。信息被增量的傳輸?shù)竭\(yùn)行in-progress的reduce任務(wù)的工作進(jìn)程上。

3.3 容錯(cuò)

因?yàn)镸apReduce庫是被設(shè)計(jì)成運(yùn)行在數(shù)百或數(shù)千臺機(jī)器上幫助處理海量數(shù)據(jù)的，所以這個(gè)庫必須能夠優(yōu)雅的處理機(jī)器故障。

工作進(jìn)程故障

Master周期性的ping每個(gè)工作進(jìn)程，如果在一個(gè)特定的時(shí)間內(nèi)沒有收到響應(yīng)，則master會將這個(gè)工作進(jìn)程標(biāo)記為失效。任何由失效的工作進(jìn)程完成的map任務(wù)都被標(biāo)記為初始idle狀態(tài)，因此這個(gè)map任務(wù)會被重新分配給其它的工作進(jìn)程。同樣的，任何正在處理的map任務(wù)或reduce任務(wù)也會被置為idle狀態(tài)，進(jìn)而可以被重新調(diào)度。

在一個(gè)失效的節(jié)點(diǎn)上完成的map任務(wù)會被重新執(zhí)行，因?yàn)樗鼈兊妮敵霰淮娣旁谑C(jī)器的本地磁盤上，而磁盤不可訪問。完成的reduce任務(wù)不需要重新執(zhí)行，因?yàn)樗鼈兊妮敵霰淮鎯υ谌治募到y(tǒng)上。

當(dāng)一個(gè)map任務(wù)先被工作進(jìn)程A執(zhí)行，然后再被工作進(jìn)程B執(zhí)行（因?yàn)锳失效了），所有執(zhí)行reduce任務(wù)的工作進(jìn)程都會接收到重新執(zhí)行的通知，任何沒有從工作進(jìn)程A上讀取數(shù)據(jù)的reduce任務(wù)將會從工作進(jìn)程B上讀取數(shù)據(jù)。

MapReduce對于大規(guī)模工作進(jìn)程失效有足夠的彈性。比如，在一個(gè)MapReduce操作處理過程中，網(wǎng)絡(luò)維護(hù)造成了80臺機(jī)器組成的集群幾分鐘內(nèi)不可達(dá)。MapReduce的master會重新執(zhí)行那些在不可達(dá)機(jī)器上完成的工作，并持續(xù)推進(jìn)，最終完成MapReduce操作。

Master故障

將上面提到的master數(shù)據(jù)結(jié)構(gòu)周期性的進(jìn)行寫檢查點(diǎn)操作（checkpoint）是比較容易的。如果master任務(wù)死掉，一個(gè)新的拷貝會從最近的檢查點(diǎn)狀態(tài)上啟動。然而，假定只有一個(gè)單獨(dú)的master，它的故障是不大可能的。因此，如果master故障，我們當(dāng)前的實(shí)現(xiàn)是中止MapReduce計(jì)算。

當(dāng)前故障的語義

當(dāng)用戶提供的map和reduce操作是輸入確定性函數(shù)，我們的分布式實(shí)現(xiàn)與無故障序列執(zhí)行整個(gè)程序所生成的結(jié)果相同。

我們依靠map和reduce任務(wù)輸出的原子性提交來實(shí)現(xiàn)這個(gè)屬性。每個(gè)in-progress任務(wù)將它們的輸出寫入到一個(gè)私有的臨時(shí)文件中。一個(gè)reduce任務(wù)產(chǎn)生一個(gè)這樣的文件，一個(gè)map任務(wù)產(chǎn)生R個(gè)這樣的文件（每個(gè)reduce任務(wù)一個(gè)）。當(dāng)一個(gè)map任務(wù)完成時(shí)，它將發(fā)送給master一個(gè)消息，其中包括R個(gè)臨時(shí)文件的名字。如果master收到一個(gè)已經(jīng)完成的map任務(wù)的完成消息，則忽略這個(gè)消息。否則，它將這R個(gè)文件名記錄在master的數(shù)據(jù)結(jié)構(gòu)中。

當(dāng)一個(gè)reduce任務(wù)完成后，reduce的工作進(jìn)程自動的將臨時(shí)文件更名為最終的輸出文件，如果相同的reduce任務(wù)運(yùn)行在多臺機(jī)器上，會調(diào)用多個(gè)重命名操作將這些文件更名為最終的輸出文件。

絕大部分的map和reduce操作是確定性的，事實(shí)上，在這種情況下我們的語義與一個(gè)序列化的執(zhí)行是相同的，這使程序開發(fā)者能夠簡單的推出他們程序的行為。當(dāng)map和/或reduce操作是不確定性的時(shí)，我們提供較弱但依然合理的語義。在不確定性的操作面前，一個(gè)特定的reduce任務(wù)R1的輸出與一個(gè)序列執(zhí)行的不確定性程序生成的輸出相同。然而，一個(gè)不同的reduce任務(wù)R2的輸出可能與一個(gè)不同的序列執(zhí)行的不確定性程序生成的輸出可能一致。

考慮map任務(wù)M和reduce任務(wù)R1和R2。假定e(R_i)是提交的R_i的執(zhí)行過程（有且僅有這樣一個(gè)過程）。e(R₁)可能從M的一個(gè)執(zhí)行生成的輸出中讀取數(shù)據(jù)，e(R₂)可能從M的一個(gè)不同執(zhí)行生成的輸出中讀取數(shù)據(jù)，則會產(chǎn)生較弱的語義。

3.4 位置

在我們的計(jì)算環(huán)境中，網(wǎng)絡(luò)帶寬是一個(gè)相對不足的資源。我們通過將輸入數(shù)據(jù)存放在組成集群的機(jī)器的本地磁盤來節(jié)省網(wǎng)絡(luò)帶寬。GFS將每個(gè)文件分割成64MB大小的塊，每個(gè)塊會在不同的機(jī)器上存儲幾個(gè)拷貝（通常為3個(gè)）。MapReduce master會考慮文件的位置信息，并試圖將一個(gè)map任務(wù)分配到包含相關(guān)輸入數(shù)據(jù)副本的機(jī)器上。如果這樣做失敗，它會試圖將map任務(wù)調(diào)度到一個(gè)包含任務(wù)輸入數(shù)據(jù)的臨近的機(jī)器上（例如，與包含輸入數(shù)據(jù)機(jī)器在同一個(gè)網(wǎng)絡(luò)下進(jìn)行交互的一個(gè)工作進(jìn)程）。當(dāng)在集群的一個(gè)有效部分上運(yùn)行大規(guī)模的MapReduce操作時(shí)，大多數(shù)輸入數(shù)據(jù)都從本地讀取，不消耗任何網(wǎng)絡(luò)帶寬。

3.5 任務(wù)粒度

根據(jù)上面所提到的，我們將map階段細(xì)分為M個(gè)片，將reduce階段細(xì)分為R個(gè)片。理想情況下，M和R應(yīng)該比工作機(jī)器的數(shù)量大得多，每個(gè)工作進(jìn)程執(zhí)行很多不同的任務(wù)來促使負(fù)載均衡，在一個(gè)工作進(jìn)程失效時(shí)也能夠快速的恢復(fù)：許多完成的map任務(wù)可以傳播到其它所有的工作機(jī)器上。

在我們的實(shí)現(xiàn)中，對于取多大的M和R有一個(gè)實(shí)際的界限，因?yàn)槿缟厦嫣岬降哪菢?#xff0c;master必須進(jìn)行O(M+R)次調(diào)度，在內(nèi)存中保持O(M*R)個(gè)狀態(tài)。（對內(nèi)存使用的恒定因素影響較小，然而：對由每個(gè)map任務(wù)/reduce任務(wù)對占用大約一個(gè)字節(jié)所組成的O(M*R)片的狀態(tài)影響較大。）

此外，R經(jīng)常是由用戶約束的，因?yàn)槊總€(gè)reduce任務(wù)的輸出最終放在一個(gè)分開的輸出文件中。實(shí)際中，我們傾向選擇M值，以使每一個(gè)獨(dú)立的任務(wù)能夠處理大約16MB到64MB的輸入數(shù)據(jù)（可以使上面提到的位置優(yōu)化有更好的效果），把R值設(shè)置為我們想使用的工作機(jī)器的一個(gè)小的倍數(shù)。我們經(jīng)常使用2000個(gè)工作機(jī)器，設(shè)置M=200000和R=5000，來執(zhí)行MapReduce計(jì)算。

3.6 備用任務(wù)

影響一個(gè)MapReduce操作整體執(zhí)行時(shí)間的一個(gè)通常因素是“落后者”：一個(gè)使用了異常的時(shí)間完成了計(jì)算中最后幾個(gè)map任務(wù)或reduce任務(wù)中的一個(gè)的機(jī)器。可能有很多因素導(dǎo)致落后者的出現(xiàn)，例如，一個(gè)含有損壞磁盤的機(jī)器頻繁的處理可校正的錯(cuò)誤，使它的讀取速度從30MB/s下降到了1MB/s。集群調(diào)度者可能將其它的任務(wù)分配到這個(gè)機(jī)器上，由于CPU、內(nèi)存、磁盤或網(wǎng)絡(luò)帶寬的競爭會導(dǎo)致MapReduce代碼執(zhí)行的更慢。我們遇到的最近一個(gè)問題是機(jī)器初始化代碼中的一個(gè)bug，它會使處理器的緩存不可用：受到這個(gè)問題影響的機(jī)器會慢上百倍。

我們使用一個(gè)普通的機(jī)制來緩解落后者問題。當(dāng)一個(gè)MapReduce操作接近完成時(shí)，master調(diào)度備用（backup）任務(wù)執(zhí)行剩下的、處于in-process狀態(tài)的任務(wù)。一旦主任務(wù)或是備用任務(wù)完成，則將這個(gè)任務(wù)標(biāo)識為已經(jīng)完成。我們優(yōu)化了這個(gè)機(jī)制，使它通常能夠僅僅增加少量的操作所使用的計(jì)算資源。我們發(fā)現(xiàn)這能有效的減少完成大規(guī)模MapReduce操作所需要的時(shí)間。作為一個(gè)例子，5.3節(jié)所描述的那種程序在禁用備用任務(wù)機(jī)制的情況下，會需要多消耗44%的時(shí)間。

四、??????? 細(xì)化

盡管簡單的編寫Map和Reduce函數(shù)提供的基本功能足夠滿足大多數(shù)需要，但是，我們發(fā)現(xiàn)一些擴(kuò)展是很有用的。這會在本章進(jìn)行描述。

4.1 分區(qū)函數(shù)

MapReduce的用戶指定所希望的reduce任務(wù)/輸出文件的數(shù)量（R）。使用分區(qū)函數(shù)在中間鍵上將數(shù)據(jù)分區(qū)到這些任務(wù)上。一個(gè)默認(rèn)的分區(qū)函數(shù)使用hash方法（如“hash(key) mod R”），它能產(chǎn)生相當(dāng)平衡的分區(qū)。然而，在一些情況下，需要使用其它的在key上的分區(qū)函數(shù)對數(shù)據(jù)進(jìn)行分區(qū)。為了支持這種情況，MapReduce庫的用戶能夠提供指定的分區(qū)函數(shù)。例如，使用“hash(Hostname(urlkey)) mod R”作為分區(qū)函數(shù)，使所有來自同一個(gè)host的URL最終放到同一個(gè)輸出文件中。

4.2 順序保證

我們保證在一個(gè)給定的分區(qū)內(nèi)，中間key/value對是根據(jù)key值順序增量處理的。順序保證可以使它易于生成一個(gè)有序的輸出文件，這對于輸出文件需要支持有效的隨機(jī)訪問，或者輸出的用戶方便的查找排序的數(shù)據(jù)很有幫助。

4.3 組合（Combiner）函數(shù)

在一些情況下，每個(gè)map任務(wù)產(chǎn)生的中間key會有很多重復(fù)，并且用戶指定的reduce函數(shù)滿足結(jié)合律和交換律。2.1節(jié)中提到的單詞技術(shù)的例子就是一個(gè)很好的例子。因?yàn)閱卧~頻率傾向于zifp分布，每個(gè)map任務(wù)都會產(chǎn)生數(shù)百或數(shù)千個(gè)<the, 1>形式的記錄。所有這些計(jì)數(shù)都會通過網(wǎng)絡(luò)發(fā)送給一個(gè)單獨(dú)的reduce任務(wù)，然后通過Reduce函數(shù)進(jìn)行累加并產(chǎn)生一個(gè)數(shù)字。我們允許用戶指定一個(gè)可選的Combiner函數(shù)，它能在數(shù)據(jù)通過網(wǎng)絡(luò)發(fā)送前先對這些數(shù)據(jù)進(jìn)行局部合并。

Combiner函數(shù)在每臺執(zhí)行map任務(wù)的機(jī)器上執(zhí)行。通常情況下，combiner函數(shù)和reduce函數(shù)的代碼是相同的，兩者唯一不同的是MapReduce庫如何處理函數(shù)的輸出。Reduce函數(shù)的輸出被寫入到一個(gè)最終的輸出文件中，而combiner函數(shù)會寫入到一個(gè)將被發(fā)送給reduce函數(shù)的中間文件中。

局部合并可以有效的對某類MapReduce操作進(jìn)行加速。附錄A包含了一個(gè)使用combiner函數(shù)的例子。

4.4 輸入和輸出類型

MapReduce庫支持幾種不同格式的輸入數(shù)據(jù)。比如，“text”模式的輸入可以講每一行看出一個(gè)key/value對：key是該行在文件中的偏移量，value是該行的內(nèi)容。另一中常見的支持格式是根據(jù)key進(jìn)行排序存儲一個(gè)key/value對的序列。每種輸入類型的實(shí)現(xiàn)知道如何將自己分割成對map任務(wù)處理有意義的區(qū)間（例如，text模式區(qū)間分割確保區(qū)間分割只在行的邊界進(jìn)行）。用戶能夠通過實(shí)現(xiàn)一個(gè)簡單的讀取（reader）接口來增加支持一種新的輸入類型，盡管大多數(shù)用戶僅僅使用了預(yù)定義輸入類型中的一小部分。

Reader并不是必須從文件中讀取數(shù)據(jù)，比如，我們可以容易的定義一個(gè)從數(shù)據(jù)庫中讀取記錄，或者從內(nèi)存的數(shù)據(jù)結(jié)構(gòu)中讀取數(shù)據(jù)的Reader。

類似的，我們提供一組輸出類型來產(chǎn)生不同格式的數(shù)據(jù)，用戶也可以簡單的通過代碼增加對新輸出類型的支持。

4.5 副作用

在一些情況下，MapReduce的用戶發(fā)現(xiàn)為它們的map和/或reduce操作的輸出生成輔助的文件很方便。我們依靠應(yīng)用的writer將這個(gè)副作用變成原子的和冪等的。通常，應(yīng)用會將結(jié)果寫入到一個(gè)臨時(shí)文件，然后在數(shù)據(jù)完全生成后，原子的重命名這個(gè)文件。

如果一個(gè)單獨(dú)任務(wù)產(chǎn)生的多個(gè)輸出文件，我們沒有提供兩階段提交的原子操作。因此，產(chǎn)生多個(gè)輸出文件且對交叉文件有一致性需求的任務(wù)應(yīng)該是確定性的操作。但是在實(shí)際工作中，這個(gè)限制并不是一個(gè)問題。

4.6 跳過損壞的記錄

有時(shí)，在我們的代碼中會存在一些bug，它們會導(dǎo)致Map或Reduce函數(shù)在處理特定的記錄上一定會Crash。這樣的bug會阻止MapReduce操作順利完成。通常的做法是解決這個(gè)bug，但有時(shí)，這是不可行的；可能是由于第三方的庫中的bug，而我們沒有這個(gè)庫的源碼。有時(shí)，忽略一些記錄也是可以接受的，例如，當(dāng)在海量的數(shù)據(jù)集上做數(shù)據(jù)統(tǒng)計(jì)時(shí)。我們提供了一個(gè)可選的運(yùn)行模式，MapReduce庫探測出哪些記錄會導(dǎo)致確定性的Crash，并跳過這些記錄以繼續(xù)執(zhí)行這個(gè)程序。

每個(gè)工作進(jìn)程都安裝了一個(gè)信號處理器，它能捕獲段錯(cuò)誤和總線錯(cuò)誤。在調(diào)用用戶的Map或Reduce操作之前，MapReduce庫將記錄的序號存儲到全局變量中。如果用戶代碼產(chǎn)生一個(gè)信號，這個(gè)信號處理器會向MapReudce master發(fā)送一個(gè)“臨死前”的UDP包，其中包含了這個(gè)序號。當(dāng)master看到對于一個(gè)特定的記錄有多個(gè)失敗信號時(shí)，在相應(yīng)的Map或Reduce任務(wù)下一次重新執(zhí)行時(shí)，master會通知它跳過這個(gè)記錄。

4.7 本地執(zhí)行

在Map或Reduce函數(shù)中調(diào)試問題是很棘手的，因?yàn)閷?shí)際的計(jì)算是發(fā)生在一個(gè)分布式系統(tǒng)上的，通常有幾千臺機(jī)器，并且是由master動態(tài)分配的。為了有助于調(diào)試、性能分析和小規(guī)模測試，我們開發(fā)了一個(gè)MapReduce庫可供選擇的實(shí)現(xiàn)，它將在本地機(jī)器上序列化的執(zhí)行一個(gè)MapReduce的所有工作。這為用戶提供了對MapReduce操作的控制，使計(jì)算能被限制在一個(gè)特定的map任務(wù)上。用戶使用標(biāo)記調(diào)用他們的程序，并能夠簡單的使用它們找到的任何調(diào)試或測試工具（如，gdb）。

4.8 狀態(tài)信息

Master運(yùn)行了一個(gè)內(nèi)部的HTTP服務(wù)，并顯示出狀態(tài)集頁面供人們查看，如，有多少任務(wù)已經(jīng)完成、有多少正在處理、輸入的字節(jié)數(shù)、中間數(shù)據(jù)的字節(jié)數(shù)、輸出的字節(jié)數(shù)、處理速率等。這些頁面也包含了指向每個(gè)任務(wù)生成的標(biāo)準(zhǔn)錯(cuò)誤和標(biāo)準(zhǔn)輸出文件的鏈接。用戶能使用這些數(shù)據(jù)預(yù)測這個(gè)計(jì)算將要持續(xù)多長時(shí)間，以及是否應(yīng)該向這個(gè)計(jì)算添加更多的資源。這些頁面也有助于找出計(jì)算比預(yù)期執(zhí)行慢的多的原因。

此外，頂層的狀態(tài)頁顯示了哪些工作進(jìn)程失效，哪些map和reduce任務(wù)在處理時(shí)失敗。這個(gè)信息對試圖診斷出用戶代碼中的bug很有用。

4.9 計(jì)數(shù)器

MapReduce庫提供了一個(gè)計(jì)數(shù)器，用于統(tǒng)計(jì)不同事件的發(fā)生次數(shù)。比如，用戶代碼想要統(tǒng)計(jì)已經(jīng)處理了多少單詞，或者已經(jīng)對多少德國的文檔建立了索引等。

用戶代碼可以使用這個(gè)計(jì)數(shù)器創(chuàng)建一個(gè)命名的計(jì)數(shù)器對象，然后在Map和/或Reduce函數(shù)中適當(dāng)?shù)脑黾舆@個(gè)計(jì)數(shù)器的計(jì)數(shù)。例如：

?

獨(dú)立的工作機(jī)器的計(jì)數(shù)器值周期性的傳送到master（附在ping的響應(yīng)上）master將從成功的map和reduce任務(wù)上獲取的計(jì)數(shù)器值進(jìn)行匯總，當(dāng)MapReduce操作完成時(shí)，將它們返回給用戶的代碼。當(dāng)前的計(jì)數(shù)器值也被顯示在了master的狀態(tài)頁面上，使人們能夠看到當(dāng)前計(jì)算的進(jìn)度。當(dāng)匯總計(jì)數(shù)器值時(shí)，master通過去掉同一個(gè)map或reduce任務(wù)的多次執(zhí)行所造成的影響來防止重復(fù)計(jì)數(shù)。（重復(fù)執(zhí)行可能會在我們使用備用任務(wù)和重新執(zhí)行失敗的任務(wù)時(shí)出現(xiàn)。）

一些計(jì)數(shù)器的值是由MapReduce庫自動維護(hù)的，如已處理的輸入key/value對的數(shù)量和已生成的輸出key/value對的數(shù)量。

用戶發(fā)現(xiàn)計(jì)數(shù)器對檢查MapReduce操作的行為很有用處。例如，在一些MapReduce操作中，用戶代碼可能想要確保生成的輸出對的數(shù)量是否精確的等于已處理的輸入對的數(shù)量，或者已處理的德國的文檔數(shù)量在已處理的所有文檔數(shù)量中是否被容忍。

五、??????? 性能

在這章中，我們測試兩個(gè)運(yùn)行在一個(gè)大規(guī)模集群上的MapReduce計(jì)算的性能。一個(gè)計(jì)算在大約1TB的數(shù)據(jù)中進(jìn)行特定的模式匹配，另一個(gè)計(jì)算對大約1TB的數(shù)據(jù)進(jìn)行排序。

這兩個(gè)程序能夠代表實(shí)際中大量的由用戶編寫的MapReduce程序，一類程序?qū)?shù)據(jù)從一種表示方式轉(zhuǎn)換成另一種形式；另一類程序是從海里的數(shù)據(jù)集中抽取一小部分感興趣的數(shù)據(jù)。

5.1 集群配置

所有的程序運(yùn)行在一個(gè)由將近1800臺機(jī)器組成的集群上。每個(gè)機(jī)器有兩個(gè)2GHz、支持超線程的Intel Xeon處理器、4GB的內(nèi)存、兩個(gè)160GB的IDE磁盤和一個(gè)1Gbps的以太網(wǎng)鏈路，這些機(jī)器部署在一個(gè)兩層的樹狀交換網(wǎng)絡(luò)中，在根節(jié)點(diǎn)處有大約100-200Gbps的帶寬。所有的機(jī)器都采用相同的部署，因此任意兩個(gè)機(jī)器間的RTT都小于1ms。

在4GB內(nèi)存里，有接近1-1.5GB用于運(yùn)行在集群上的其它任務(wù)。程序在一個(gè)周末的下午開始執(zhí)行，這時(shí)主機(jī)的CPU、磁盤和網(wǎng)絡(luò)基本都是空閑的。

5.2 字符串查找（Grep）

這個(gè)grep程序掃描了大概10¹⁰個(gè)100字節(jié)大小的記錄，查找出現(xiàn)概率相對較小的3個(gè)字符的模式（這個(gè)模式出現(xiàn)在92337個(gè)記錄中）。輸入被分割成接近64MB的片（M=15000），整個(gè)輸出被放到一個(gè)文件中（R=1）。

?

圖2：數(shù)據(jù)傳輸速率

圖2顯示了計(jì)算隨時(shí)間的進(jìn)展情況。Y軸顯示了輸入數(shù)據(jù)的掃描速率，這個(gè)速率會隨著MapReduce計(jì)算的機(jī)器數(shù)量的增長而增長，當(dāng)1764個(gè)工作進(jìn)程參與計(jì)算時(shí)，總的速率超過30GB/s。隨著map任務(wù)的完成，速率開始下降，并在計(jì)算的大約第80秒變?yōu)?，整個(gè)計(jì)算從開始到結(jié)束大約持續(xù)了150秒，這包含了大約1分鐘的啟動時(shí)間開銷，這個(gè)開銷是由將程序傳播到所有工作機(jī)器的時(shí)間、等待GFS文件系統(tǒng)打開1000個(gè)輸入文件集的時(shí)間和獲取位置優(yōu)化所需信息的時(shí)間造成的。

5.3 排序

排序程序?qū)?0¹⁰個(gè)100字節(jié)大小的記錄（接近1TB的數(shù)據(jù)）進(jìn)行排序，這個(gè)程序模仿了TeraSort benchmark。

排序程序由不到50行的用戶代碼組成，一個(gè)三行的Map函數(shù)從一個(gè)文本行中抽取出一個(gè)10字節(jié)的key，并將這個(gè)key和原始的文本行作為中間的key/value對進(jìn)行輸出。我們使用內(nèi)置的Identity函數(shù)作為Reduce操作。這個(gè)函數(shù)將中間key/value對不做任何修改的輸出，最終排序結(jié)果輸出到兩路復(fù)制的GFS文件中（如，該程序輸出了2TB的數(shù)據(jù)）。

如前所述，輸入數(shù)據(jù)被分割為64MB大小的片（M=15000），將輸出結(jié)果分成4000個(gè)文件（R=4000）。分區(qū)函數(shù)使用了key的開頭字符將數(shù)據(jù)分隔到R片中的一個(gè)。

這個(gè)基準(zhǔn)測試的分區(qū)函數(shù)內(nèi)置了key的分區(qū)信息。在一個(gè)普通的排序程序中，我們將增加一個(gè)預(yù)處理MapReduce操作，它能夠?qū)ey進(jìn)行抽樣，通過key的抽樣分布來計(jì)算最終排序處理的分割點(diǎn)。

?

圖3：對于排序程序的不同執(zhí)行過程隨時(shí)間的數(shù)據(jù)傳輸速率

圖3（a）顯示了排序程序的正常執(zhí)行過程。左上方的圖顯示了輸入讀取的速率，這個(gè)速率峰值大約為13GB/s，因?yàn)樗械膍ap任務(wù)執(zhí)行完成，速率也在200秒前下降到了0。注意，這里的輸入速率比字符串查找的要小，這是因?yàn)榕判虺绦虻膍ap任務(wù)花費(fèi)了大約一半的處理時(shí)間和I/O帶寬將終結(jié)結(jié)果輸出到它們的本地磁盤上，字符串查找相應(yīng)的中間結(jié)果輸出幾乎可以忽略。

左邊中間的圖顯示了數(shù)據(jù)通過網(wǎng)絡(luò)從map任務(wù)發(fā)往reduce任務(wù)的速率。這個(gè)緩慢的數(shù)據(jù)移動在第一個(gè)map任務(wù)完成時(shí)會盡快開始。圖中的第一個(gè)峰值是啟動了第一批大概1700個(gè)reduce任務(wù)（整個(gè)MapReduce被分配到大約1700臺機(jī)器上，每個(gè)機(jī)器每次最多只執(zhí)行一個(gè)reduce任務(wù)）。這個(gè)計(jì)算執(zhí)行大概300秒后，第一批reduce任務(wù)中的一些執(zhí)行完成，我們開始執(zhí)行剩下的reduce任務(wù)進(jìn)行數(shù)據(jù)處理。所有的處理在計(jì)算開始后的大約600秒后完成。

左邊下方的圖顯示了reduce任務(wù)就愛那個(gè)排序后的數(shù)據(jù)寫到最終的輸出文件的速率。在第一個(gè)處理周期完成到寫入周期開始間有一個(gè)延遲，因?yàn)闄C(jī)器正在忙于對中間數(shù)據(jù)進(jìn)行排序。寫入的速率會在2-4GB/s上持續(xù)一段時(shí)間。所有的寫操作會在計(jì)算開始后的大約850秒后完成。包括啟動的開銷，整個(gè)計(jì)算耗時(shí)891秒，這與TeraSort benchmark中的最好記錄1057秒相似。

一些事情需要注意：因?yàn)槲覀兊奈恢脙?yōu)化策略，大多數(shù)數(shù)據(jù)從本地磁盤中讀取，繞開了網(wǎng)絡(luò)帶寬的顯示，所以輸入速率比處理速率和輸出速率要高。處理速率要高于輸出速率，因?yàn)檩敵鲞^程要將排序后的數(shù)據(jù)寫入到兩個(gè)拷貝中（為了可靠性和可用性，我們將數(shù)據(jù)寫入到兩個(gè)副本中）。我們將數(shù)據(jù)寫入兩個(gè)副本，因?yàn)槲覀兊牡讓游募到y(tǒng)為了可靠性和可用性提供了相應(yīng)的機(jī)制。如果底層文件系統(tǒng)使用容錯(cuò)編碼（erasure coding）而不是復(fù)制，寫數(shù)據(jù)的網(wǎng)絡(luò)帶寬需求會降低。

5.4 備用任務(wù)的作用

在圖3（b）中，我們顯示了一個(gè)禁用備用任務(wù)的排序程序的執(zhí)行過程。執(zhí)行的流程與如3（a）中所顯示的相似，除了有一個(gè)很長的尾巴，在這期間幾乎沒有寫入行為發(fā)生。在960秒后，除了5個(gè)reduce任務(wù)的所有任務(wù)都執(zhí)行完成。然而，這些落后者只到300秒后才執(zhí)行完成。整個(gè)計(jì)算任務(wù)耗時(shí)1283秒，增加了大約44%的時(shí)間。

5.5 機(jī)器故障

在圖3（c）中，我們顯示了一個(gè)排序程序的執(zhí)行過程，在計(jì)算過程開始都的幾分鐘后，我們故意kill掉了1746個(gè)工作進(jìn)程中的200個(gè)。底層的調(diào)度者會迅速在這些機(jī)器上重啟新的工作進(jìn)程（因?yàn)橹挥羞M(jìn)程被殺掉，機(jī)器本身運(yùn)行正常）。

工作進(jìn)程死掉會出現(xiàn)負(fù)的輸入速率，因?yàn)橐恍┲耙呀?jīng)完成的map工作消失了（因?yàn)橄愀鄣膍ap工作進(jìn)程被kill掉了），并且需要重新執(zhí)行。這個(gè)map任務(wù)會相當(dāng)快的重新執(zhí)行。整個(gè)計(jì)算過程在933秒后完成，包括了啟動開銷（僅僅比普通情況多花費(fèi)了5%的時(shí)間）。

六、??????? 經(jīng)驗(yàn)

我們在2003年2月完成了MapReduce庫的第一個(gè)版本，并在2003年8月做了重大的改進(jìn)，包括位置優(yōu)化、任務(wù)在工作機(jī)器上的動態(tài)負(fù)載均衡執(zhí)行等。從那時(shí)起，我們驚喜的發(fā)現(xiàn)，MapReduce庫能夠廣泛的用于我們工作中的各種問題。它已經(jīng)被用于Google內(nèi)部廣泛的領(lǐng)域，包括：

• 大規(guī)模機(jī)器學(xué)習(xí)問題
• Google新聞和Froogle產(chǎn)品的集群問題
• 抽取數(shù)據(jù)用于公眾查詢的產(chǎn)品報(bào)告
• 從大量新應(yīng)用和新產(chǎn)品的網(wǎng)頁中抽取特性（如，從大量的位置查詢頁面中抽取地理位置信息）
• 大規(guī)模圖形計(jì)算

?

圖4：隨時(shí)間變化的MapReduce實(shí)例

圖4中顯示了在我們的源碼管理系統(tǒng)中，隨著時(shí)間的推移，MapReduce程序的數(shù)量有明顯的增加，從2003年早期的0增加到2004年9月時(shí)的900個(gè)獨(dú)立的實(shí)例。MapReduce如此的成功，因?yàn)樗估冒雮€(gè)小時(shí)編寫的一個(gè)簡單程序能夠高效的運(yùn)行在一千臺機(jī)器上成為可能，這極大的加快了開發(fā)和原型設(shè)計(jì)的周期。此外，它允許沒有分布式和/或并行系統(tǒng)經(jīng)驗(yàn)的開發(fā)者能夠利用這些資源開發(fā)出分布式應(yīng)用。

?

表1： 2004年8月運(yùn)行的MapReduce任務(wù)

在每個(gè)工作的最后，MapReduce庫統(tǒng)計(jì)了工作使用的計(jì)算資源。在表1中，我們看到一些2004年8月在Google內(nèi)部運(yùn)行的MapReduce工作的一些統(tǒng)計(jì)數(shù)據(jù)。

6.1 大規(guī)模索引

目前為止，MapReduce最重要的應(yīng)用之一就是完成了對生產(chǎn)索引系統(tǒng)的重寫，它生成了用于Google網(wǎng)頁搜索服務(wù)的數(shù)據(jù)結(jié)構(gòu)。索引系統(tǒng)的輸入數(shù)據(jù)是通過我們的爬取系統(tǒng)檢索到的海量文檔，存儲為就一個(gè)GFS文件集合。這些文件的原始內(nèi)容還有超過20TB的數(shù)據(jù)。索引程序是一個(gè)包含了5-10個(gè)MapReduce操作的序列。使用MapReduce（代替了之前版本的索引系統(tǒng)中的adhoc分布式處理）有幾個(gè)優(yōu)點(diǎn)：

• 索引程序代碼是一個(gè)簡單、短小、易于理解的代碼，因?yàn)槿蒎e(cuò)、分布式和并行處理都隱藏在了MapReduce庫中。比如，一個(gè)計(jì)算程序的大小由接近3800行的C++代碼減少到使用MapReduce的大約700行的代碼。
• MapReduce庫性能非常好，以至于能夠?qū)⒏拍钌喜幌嚓P(guān)的計(jì)算分開，來代替將這些計(jì)算混合在一起進(jìn)行，避免額外的數(shù)據(jù)處理。這會使索引程序易于改變。比如，對之前的索引系統(tǒng)做一個(gè)改動大概需要幾個(gè)月時(shí)間，而對新的系統(tǒng)則只需要幾天時(shí)間。
• 索引程序變得更易于操作，因?yàn)榇蠖鄶?shù)由于機(jī)器故障、機(jī)器處理速度慢和網(wǎng)絡(luò)的瞬間阻塞等引起的問題都被MapReduce庫自動的處理掉，而無需人為的介入。

七、??????? 相關(guān)工作

許多系統(tǒng)都提供了有限的程序模型，并且對自動的并行計(jì)算使用了限制。比如，一個(gè)結(jié)合函數(shù)可以在logN時(shí)間內(nèi)在N個(gè)處理器上對一個(gè)包含N個(gè)元素的數(shù)組使用并行前綴計(jì)算，來獲取所有的前綴[6，9，13]。MapReduce被認(rèn)為是這些模型中基于我們對大規(guī)模工作計(jì)算的經(jīng)驗(yàn)的簡化和精華。更為重要的是，我們提供了一個(gè)在數(shù)千個(gè)處理器上的容錯(cuò)實(shí)現(xiàn)。相反的，大多數(shù)并行處理系統(tǒng)只在較小規(guī)模下實(shí)現(xiàn)，并將機(jī)器故障的處理細(xì)節(jié)交給了程序開發(fā)者。

Bulk Synchronous Programming和一些MPI源于提供了更高層次的抽象使它更易于讓開發(fā)者編寫并行程序。這些系統(tǒng)和MapReduce的一個(gè)關(guān)鍵不同點(diǎn)是MapReduce開發(fā)了一個(gè)有限的程序模型來自動的并行執(zhí)行用戶的程序，并提供了透明的容錯(cuò)機(jī)制。

我們的位置優(yōu)化機(jī)制的靈感來自于移動磁盤技術(shù)，計(jì)算用于處理靠近本地磁盤的數(shù)據(jù)，減少數(shù)據(jù)在I/O子系統(tǒng)或網(wǎng)絡(luò)上傳輸?shù)拇螖?shù)。我們的系統(tǒng)運(yùn)行在掛載幾個(gè)磁盤的普通機(jī)器上，而不是在磁盤處理器上運(yùn)行，但是一般方法是類似的。

我們的備用任務(wù)機(jī)制與Charlotte系統(tǒng)中采用的eager調(diào)度機(jī)制類似。簡單的Eager調(diào)度機(jī)制有一個(gè)缺點(diǎn)，如果一個(gè)給定的任務(wù)造成反復(fù)的失敗，整個(gè)計(jì)算將以失敗告終。我們通過跳過損壞計(jì)算路的機(jī)制，解決了這個(gè)問題的一些情況。

MapReduce實(shí)現(xiàn)依賴了內(nèi)部集群管理系統(tǒng)，它負(fù)責(zé)在一個(gè)大規(guī)模的共享機(jī)器集合中分發(fā)和運(yùn)行用戶的任務(wù)。盡管不是本篇文章的焦點(diǎn)，但是集群管理系統(tǒng)在本質(zhì)上與像Condor的其它系統(tǒng)類似。

排序功能是MapReduce庫的一部分，與NOW-Sort中的操作類似。源機(jī)器（map工作進(jìn)程）將將要排序的數(shù)據(jù)分區(qū)，并將其發(fā)送給R個(gè)Reduce工作進(jìn)程中的一個(gè)。每個(gè)reduce工作進(jìn)程在本地對這些數(shù)據(jù)進(jìn)行排序（如果可能的話就在內(nèi)存中進(jìn)行）。當(dāng)然NOW-Sort沒有使MapReduce庫能夠廣泛使用的用戶定義的Map和Reduce函數(shù)。

River提供了一個(gè)編程模型，處理進(jìn)程通過在分布式隊(duì)列上發(fā)送數(shù)據(jù)來進(jìn)行通信。像MapReduce一樣，即使在不均勻的硬件或系統(tǒng)顛簸的情況下，River系統(tǒng)依然試圖提供較好的平均性能。River系統(tǒng)通過小心的磁盤和網(wǎng)絡(luò)傳輸調(diào)度來平衡完成時(shí)間。通過限制編程模型，MapReduce框架能夠?qū)栴}分解成很多細(xì)顆粒的任務(wù)，這些任務(wù)在可用的工作進(jìn)程上動態(tài)的調(diào)度，以至于越快的工作進(jìn)程處理越多的任務(wù)。這個(gè)受限制的編程模型也允許我們在工作將要結(jié)束時(shí)調(diào)度冗余的任務(wù)進(jìn)行處理，這樣可以減少不均勻情況下的完成時(shí)間。

BAD-FS與MapReduce有完全不同的編程模型，不像MapReduce，它是用于在廣域網(wǎng)下執(zhí)行工作的。然而，它們有兩個(gè)基本相似點(diǎn)。（1）兩個(gè)系統(tǒng)都使用了重新執(zhí)行的方式來處理因故障而丟失的數(shù)據(jù)。（2）兩個(gè)系統(tǒng)都本地有限調(diào)度原則來減少網(wǎng)絡(luò)鏈路上發(fā)送數(shù)據(jù)的次數(shù)。

TASCC是一個(gè)用于簡化結(jié)構(gòu)的高可用性的網(wǎng)絡(luò)服務(wù)。像MapReduce一樣，它依靠重新執(zhí)行作為一個(gè)容錯(cuò)機(jī)制。

八、??????? 總結(jié)

MapReduce編程模型已經(jīng)成功的應(yīng)用在Google內(nèi)部的許多不同的產(chǎn)品上。我們將這個(gè)成功歸功于幾個(gè)原因。第一，模型很易用，即使對那些沒有并行計(jì)算和分布式系統(tǒng)經(jīng)驗(yàn)的開發(fā)者，因?yàn)樗[藏了并行處理、容錯(cuò)、本地優(yōu)化和負(fù)載均衡這些處理過程。第二，各種各樣的問題都能用MapReduce計(jì)算簡單的表示出來，例如，MapReduce被Google網(wǎng)頁搜索服務(wù)用于生成數(shù)據(jù)、排序、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)和許多其它系統(tǒng)。第三，我們已經(jīng)實(shí)現(xiàn)了擴(kuò)展到由數(shù)千臺機(jī)器組成的大規(guī)模集群上使用的MapReduce。這個(gè)實(shí)現(xiàn)能夠有效的利用這些機(jī)器自由，因此適合在Google內(nèi)部遇到的很多海量計(jì)算問題。

我們從這項(xiàng)工作中學(xué)到了幾樣?xùn)|西。第一，限制程序模型使得并行計(jì)算和分布式計(jì)算變得容易，也容易實(shí)現(xiàn)這樣的計(jì)算容錯(cuò)。第二，網(wǎng)絡(luò)帶寬是一個(gè)稀有的資源，因此我們系統(tǒng)中的很多優(yōu)化的目標(biāo)都是為了減少數(shù)據(jù)在網(wǎng)絡(luò)上的傳輸次數(shù)：位置優(yōu)化允許我們從本地磁盤讀取數(shù)據(jù)，并將中間數(shù)據(jù)的一個(gè)拷貝寫入到本地磁盤，以此來節(jié)省網(wǎng)絡(luò)帶寬的使用。第三，冗余執(zhí)行能夠用于減少允許速度慢的機(jī)器所造成的影響，并且能夠處理機(jī)器故障和數(shù)據(jù)丟失。

分類:?Google,?web技術(shù)

轉(zhuǎn)載于:https://www.cnblogs.com/guoyongrong/p/3700971.html

總結(jié)

以上是生活随笔為你收集整理的转：Google论文之三----MapReduce的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。