1、MapReduce: 超大機(jī)群上的簡單數(shù)據(jù)處理摘要MapReduce是一個編程模型，和處理，產(chǎn)生大數(shù)據(jù)集的相關(guān)實(shí)現(xiàn)。用戶指定 一個map函數(shù)處理一個key/value對，從而產(chǎn)生中間的key/value對集。然后再指 定一個reduce函數(shù)合并所有的具有相同中間 key的中間value。下面將列舉許多 可以用這個模型來表示的現(xiàn)實(shí)世界的工作。以這種方式寫的程序能自動的在大規(guī)模的普通機(jī)器上實(shí)現(xiàn)并行化。 這個運(yùn)行時系統(tǒng)關(guān)心這些細(xì)節(jié):分割輸入數(shù)據(jù)，在機(jī)群上的調(diào)度，機(jī)器的錯誤處理，管理機(jī)器之間必要的通信。這樣就可以讓那些沒有并行分布式處理系統(tǒng)經(jīng)驗(yàn)的程序員利用大量分布式系統(tǒng)的資源。我們的MapReduce

2、 實(shí)現(xiàn)運(yùn)行在規(guī)模可以靈活調(diào)整的由普通機(jī)器組成的機(jī)群上，一個典型的MapReduce計(jì)算處理幾千臺機(jī)器上的以 TB計(jì)算的數(shù)據(jù)。程序 員發(fā)現(xiàn)這個系統(tǒng)非常好用 : 已經(jīng)實(shí)現(xiàn)了數(shù)以百計(jì)的 MapReduce 程序，每天在 Google的機(jī)群上都有1000多個MapReduce程序在執(zhí)行。1. 介紹在過去的 5 年里，作者和 Google 的許多人已經(jīng)實(shí)現(xiàn)了數(shù)以百計(jì)的為專門目的而寫的計(jì)算來處理大量的原始數(shù)據(jù)， 比如， 爬行的文檔， Web 請求日志， 等等。為了計(jì)算各種類型的派生數(shù)據(jù)， 比如， 倒排索引， Web 文檔的圖結(jié)構(gòu)的各種表示，每個主機(jī)上爬行的頁面數(shù)量的概要， 每天被請求數(shù)量最多的集合， 等等

3、。 很多這樣的計(jì)算在概念上很容易理解。 然而， 輸入的數(shù)據(jù)量很大， 并且只有計(jì)算被分布在成百上千的機(jī)器上才能在可以接受的時間內(nèi)完成。怎樣并行計(jì)算，分發(fā)數(shù)據(jù)，處理錯誤， 所有這些問題綜合在一起， 使得原本很簡介的計(jì)算， 因?yàn)橐罅康膹?fù) 雜代碼來處理這些問題，而變得讓人難以處理。作為對這個復(fù)雜性的回應(yīng)， 我們設(shè)計(jì)一個新的抽象模型， 它讓我們表示我們將要執(zhí)行的簡單計(jì)算，而隱藏并行化，容錯，數(shù)據(jù)分布，負(fù)載均衡的那些雜亂的細(xì)節(jié)， 在一個庫里。 我們的抽象模型的靈感來自 Lisp 和許多其他函數(shù)語言的 map 和 reduce 的原始表示。我們認(rèn)識到我們的許多計(jì)算都包含這樣的操作:在我們輸 入數(shù)據(jù)的邏輯記

4、錄上應(yīng)用 map操作，來計(jì)算出一個中間key/value對集，在所有 具有相同key的value上應(yīng)用reduce操作，來適當(dāng)?shù)暮喜⑴缮臄?shù)據(jù)。功能模型 的使用，再結(jié)合用戶指定的 map和reduce操作，讓我們可以非常容易的實(shí)現(xiàn)大 規(guī)模并行化計(jì)算，和使用再次執(zhí)行作為初級機(jī)制來實(shí)現(xiàn)容錯。這個工作的主要貢獻(xiàn)是通過簡單有力的接口來實(shí)現(xiàn)自動的并行化和大規(guī)模分布式計(jì)算，結(jié)合這個接口的實(shí)現(xiàn)來在大量普通的 PC 機(jī)上實(shí)現(xiàn)高性能計(jì)算。第二部分描述基本的編程模型， 并且給一些例子。 第三部分描述符合我們的基于集群的計(jì)算環(huán)境的 MapReduce 的接口的實(shí)現(xiàn)。第四部分描述我們覺得編程模型中一些有用的技巧。第五

5、部分對于各種不同的任務(wù)，測量我們實(shí)現(xiàn)的性能。第六部分探究在Google內(nèi)部使用MapReduce作為基礎(chǔ)來重寫我們的索引系統(tǒng)產(chǎn) 品。第七部分討論相關(guān)的，和未來的工作。2. 編程模型計(jì)算利用一個輸入 key/value 對集，來產(chǎn)生一個輸出 key/value 對集。MapReduce庫的用戶用兩個函數(shù)表達(dá)這個計(jì)算：map和reduce用戶自定義的map函數(shù)，接受一個輸入對，然后產(chǎn)生一個中間 key/value對 集。MapReduce庫把所有具有相同中間key I的中間value聚合在一起，然后把 它們傳遞給reduce 函數(shù)。用戶自定義的reduce函數(shù)，接受一個中間key I和相關(guān)的一個v

6、alue集。它 合并這些value,形成一個比較小的value集。一般的，每次reduce調(diào)用只產(chǎn)生0 或1個輸出value。通過一個迭代器把中間value提供給用戶自定義的reduce函 數(shù)。這樣可以使我們根據(jù)內(nèi)存來控制 value 列表的大小。2.1 實(shí)例考慮這個問題:計(jì)算在一個大的文檔集合中每個詞出現(xiàn)的次數(shù)。用戶將寫和下面類似的偽代碼:map(String key， String value):key:文檔的名字/value:文檔的內(nèi)容for each word w in value:EmitIntermediate（w， 1）;reduce（String key， Iterator v

7、alues）:/key:一個詞/values:一個計(jì)數(shù)列表int result=0;for each v in values:result+=ParseInt（v）;Emit（AsString（resut）;map 函數(shù)產(chǎn)生每個詞和這個詞的出現(xiàn)次數(shù)（在這個簡單的例子里就是1）。reduce函數(shù)把產(chǎn)生的每一個特定的詞的計(jì)數(shù)加在一起。另外，用戶用輸入輸出文件的名字和可選的調(diào)節(jié)參數(shù)來填充一個mapreduce規(guī)范對象。用戶然后調(diào)用 MapReduce 函數(shù)，并把規(guī)范對象傳遞給它。用戶的代碼和MapReduce庫鏈接在一起（用C+實(shí)現(xiàn)）。附錄A包含這個實(shí)例的全部文本。2.2 類型即使前面的偽代碼寫成了

8、字符串輸入和輸出的 term 格式，但是概念上用戶寫的map和reduce函數(shù)有關(guān)聯(lián)的類型：map（k1， v1） -list（k2 ， v2）reduce（k2， list（v2） -list（v2）例如，輸入的 key， value 和輸出的 key， value 的域不同。此外，中間key，value和輸出key, values的域相同。我們的C+實(shí)現(xiàn)傳遞字符用來和用戶自定義的函數(shù)交互，并把它留給用戶的 代碼，來在字符串和適當(dāng)?shù)念愋烷g進(jìn)行轉(zhuǎn)換。2.3 更多實(shí)例這里有一些讓人感興趣的簡單程序，可以容易的用MapReduce計(jì)算來表示。分布式的 Grep（UNIX 工具程序， 可做文件內(nèi)的字

9、符串查找）:如果輸入行匹配給定的樣式，map函數(shù)就輸出這一行。reduce函數(shù)就是把中間數(shù)據(jù)復(fù)制到輸出。計(jì)算 URL 訪問頻率 :map 函數(shù)處理 web 頁面請求的記錄，輸出 （URL ， 1）。reduce函數(shù)把相同URL的value都加起來，產(chǎn)生一個（URL,記錄總數(shù)）的對。倒轉(zhuǎn)網(wǎng)絡(luò)鏈接圖 :map 函數(shù)為每個鏈接輸出（目標(biāo)，源）對，一個URL 叫做目標(biāo)，包含這個URL 的頁面叫做源。reduce 函數(shù)根據(jù)給定的相關(guān)目標(biāo)URLs 連接所有的源 URLs 形成一個列表，產(chǎn)生（ 目標(biāo)，源列表）對。每個主機(jī)的術(shù)語向量:一個術(shù)語向量用一個（詞， 頻率 ） 列表來概述出現(xiàn)在一個文檔或一個文檔集中的

10、最重要的一些詞。 map 函數(shù)為每一個輸入文檔產(chǎn)生一個（主機(jī)名，術(shù)語向量）對（主機(jī)名來自文檔的URL）。reduce函數(shù)接收給定主機(jī)的所有文檔的術(shù)語向量。 它把這些術(shù)語向量加在一起， 丟棄低頻的術(shù)語， 然后產(chǎn)生一個最終的（主機(jī)名，術(shù)語向量）對。倒排索引 :map 函數(shù)分析每個文檔，然后產(chǎn)生一個（詞，文檔號）對的序列。reduce函數(shù)接受一個給定詞的所有對，排序相應(yīng)的文檔IDs,并且產(chǎn)生一個（詞,文檔 ID 列表 ）對。 所有的輸出對集形成一個簡單的倒排索引。 它可以簡單的增加 跟蹤詞位置的計(jì)算。分布式排序：map函數(shù)從每個記錄提取key,并且產(chǎn)生一個（key, record）對。 reduce

11、函數(shù)不改變?nèi)魏蔚膶Α＿@個計(jì)算依賴分割工具（在4.1描述）和排序?qū)傩裕ㄔ?4.2描述 ）。3. 實(shí)現(xiàn)MapReduce接口可能有許多不同的實(shí)現(xiàn)。根據(jù)環(huán)境進(jìn)行正確的選擇。例如，一個實(shí)現(xiàn)對一個共享內(nèi)存較小的機(jī)器是合適的，另外的適合一個大NUMA 的多處理器的機(jī)器，而有的適合一個更大的網(wǎng)絡(luò)機(jī)器的集合。這部分描述一個在Google廣泛使用的計(jì)算環(huán)境的實(shí)現(xiàn)：用交換機(jī)連接的普通 PC機(jī)的大機(jī)群。我們的環(huán)境是：1. Linux 操作系統(tǒng)，雙處理器， 24GB 內(nèi)存的機(jī)器。2. 普通的網(wǎng)絡(luò)硬件，每個機(jī)器的帶寬或者是百兆或者千兆，但是平均小于全部帶寬的一半。3. 因?yàn)橐粋€機(jī)群包含成百上千的機(jī)器，所有機(jī)器會經(jīng)常出現(xiàn)

12、問題。4. 存儲用直接連到每個機(jī)器上的廉價IDE 硬盤。一個從內(nèi)部文件系統(tǒng)發(fā)展起來的分布式文件系統(tǒng)被用來管理存儲在這些磁盤上的數(shù)據(jù)。 文件系統(tǒng)用復(fù)制的 方式在不可靠的硬件上來保證可靠性和有效性。5. 用戶提交工作給調(diào)度系統(tǒng)。每個工作包含一個任務(wù)集，每個工作被調(diào)度者映射到機(jī)群中一個可用的機(jī)器集上。3.1 執(zhí)行預(yù)覽通過自動分割輸入數(shù)據(jù)成一個有M 個 split 的集， map 調(diào)用被分布到多臺機(jī)器上。輸入的 split 能夠在不同的機(jī)器上被并行處理。通過用分割函數(shù)分割中間key,來形成R個片（例如，hash（key） mod R）, reduce調(diào)用被分布到多臺機(jī)器上。分割數(shù)量（R）和分割函數(shù)由用

13、戶來指定。圖1顯示了我們實(shí)現(xiàn)的 MapReduce操作的全部流程。當(dāng)用戶的程序調(diào)用 MapReduce 的函數(shù)的時候，將發(fā)生下面的一系列動作（下面的數(shù)字和圖 1 中的數(shù)字標(biāo)簽相對應(yīng) ）:1 .在用戶程序里的MapReduce庫首先分割輸入文件成 M個片，每個片 的大小一般從16到64MB（用戶可以通過可選的參數(shù)來控制）。然后在機(jī)群中開 始大量的拷貝程序。2 .這些程序拷貝中的一個是 master,其他的都是由master分配任務(wù) 的workero有M個map任務(wù)和R個reduce任務(wù)將被分配。管理者分配一個 map 任務(wù)或reduce任務(wù)給一個空閑的 worker。3。一個被分配了map 任務(wù)

14、的 worker 讀取相關(guān)輸入 split 的內(nèi)容。它從輸入數(shù)據(jù)中分析出key/value對，然后把key/value對傳遞給用戶自定義的 map函數(shù)。 由map函數(shù)產(chǎn)生的中間key/value對被緩存在內(nèi)存中。4。 緩存在內(nèi)存中的 key/value 對被周期性的寫入到本地磁盤上， 通過分割函數(shù)把它們寫入 R 個區(qū)域。在本地磁盤上的緩存對的位置被傳送給master， master負(fù)責(zé)把這些位置傳送給reduce worker。5。當(dāng)一個reduce worker得到master的位置通知的時候，它使用遠(yuǎn)程過程調(diào) 用來從map worker的磁盤上讀取緩存的數(shù)據(jù)。當(dāng)reduce worker讀

15、取了所有的中 間數(shù)據(jù)后，它通過排序使具有相同 key 的內(nèi)容聚合在一起。因?yàn)樵S多不同的 key 映射到相同的 reduce 任務(wù)，所以排序是必須的。如果中間數(shù)據(jù)比內(nèi)存還大，那 么還需要一個外部排序。6。reduce worker迭代排過序的中間數(shù)據(jù)，對于遇到的每一個唯一的 中間key,它把key和相關(guān)的中間value集傳遞給用戶自定義的reduce函數(shù)。reduce 函數(shù)的輸出被添加到這個reduce 分割的最終的輸出文件中。7。當(dāng)所有的map和reduce任務(wù)都完成了，管理者喚醒用戶程序。在這個時 候，在用戶程序里的MapReduce調(diào)用返回到用戶代碼。在成功完成之后， mapreduce

16、執(zhí)行的輸出存放在R 個輸出文件中（每一個reduce任務(wù)產(chǎn)生一個由用戶指定名字的文件）。一般，用戶不需要合并這 R個輸 出 文 件 成 一 個 文 件 - 他 們 經(jīng) 常 把 這 些 文 件 當(dāng) 作 一 個 輸 入 傳 遞 給 其 他 的 MapReduce調(diào)用，或者在可以處理多個分割文件的分布式應(yīng)用中使用他們。3。2master數(shù)據(jù)結(jié)構(gòu)master保持一些數(shù)據(jù)結(jié)構(gòu)。它為每一個map和reduced務(wù)存儲它們的狀態(tài)（空 閑，工作中，完成），和 worker 機(jī)器 （非空閑任務(wù)的機(jī)器）的標(biāo)識。master就像一個管道，通過它，中間文件區(qū)域的位置從 map任務(wù)傳遞到reduce 任務(wù)。因此，對于每

17、個完成的 map任務(wù)，master存儲由map任務(wù)產(chǎn)生的R個中 間文件區(qū)域的大小和位置。當(dāng) map 任務(wù)完成的時候，位置和大小的更新信息被 接受。這些信息被逐步增加的傳遞給那些正在工作的reduce任務(wù)。3。 3 容錯因?yàn)镸apReduce庫被設(shè)計(jì)用來使用成百上千的機(jī)器來幫助處理非常大規(guī)模 的數(shù)據(jù)，所以這個庫必須要能很好的處理機(jī)器故障。worker 故障master周期性的ping每個worker。如果master在一個確定的時間段內(nèi)沒有收到 worker 返回的信息，那么它將把這個worker 標(biāo)記成失效。因?yàn)槊恳粋€由這個失效的worker完成的map任務(wù)被重新設(shè)置成它初始的空閑狀態(tài)，所以它

18、可以 被安排給其他的workero同樣的，每一個在失敗的 worker上正在運(yùn)行的map或 reduce任務(wù)，也被重新設(shè)置成空閑狀態(tài)，并且將被重新調(diào)度。在一個失敗機(jī)器上已經(jīng)完成的 map 任務(wù)將被再次執(zhí)行，因?yàn)樗妮敵龃鎯υ谒拇疟P上，所以不可訪問。已經(jīng)完成的 reduce 任務(wù)將不會再次執(zhí)行，因?yàn)?它的輸出存儲在全局文件系統(tǒng)中。當(dāng)一個map任務(wù)首先被worker A執(zhí)行之后，又被B執(zhí)行了（因?yàn)锳失效了）， 重新執(zhí)行這個情況被通知給所有執(zhí)行 reduce任務(wù)的worker。任何還沒有從A讀 數(shù)據(jù)的reduce任務(wù)將從worker B讀取數(shù)據(jù)。MapReduce可以處理大規(guī)模 worker失敗的

19、情況。例如，在一個 MapReduce操作期間，在正在運(yùn)行的機(jī)群上進(jìn)行網(wǎng)絡(luò)維護(hù)引起80 臺機(jī)器在幾分鐘內(nèi)不可訪問了，MapReduce master只是簡單的再次執(zhí)行已經(jīng)被不可訪問的worker完成的工作，繼續(xù)執(zhí)行，最終完成這個 MapReduce操作。master失敗可以很容易的讓管理者周期的寫入上面描述的數(shù)據(jù)結(jié)構(gòu)的checkpoints。 如果這個master任務(wù)失效了，可以從上次最后一個checkpoint開始啟動另一個master 進(jìn)程。然而，因?yàn)橹挥幸粋€ master,所以它的失敗是比較麻煩的，因此我們現(xiàn)在 的實(shí)現(xiàn)是，如果master失敗，就中止MapReduce計(jì)算。客戶可以檢查這

20、個狀態(tài)， 并且可以根據(jù)需要重新執(zhí)行MapReduce操作。在錯誤面前的處理機(jī)制當(dāng)用戶提供的map和reduce操作對它的輸出值是確定的函數(shù)時，我們的分 布式實(shí)現(xiàn)產(chǎn)生，和全部程序沒有錯誤的順序執(zhí)行一樣，相同的輸出。我們依賴對map和reduce任務(wù)的輸出進(jìn)行原子提交來完成這個性質(zhì)。每個工作中的任務(wù)把它的輸出寫到私有臨時文件中。一個reduce 任務(wù)產(chǎn)生一個這樣的文件，而一個map任務(wù)產(chǎn)生R個這樣的文件(一個reduce任務(wù)對應(yīng)一個文件)。 當(dāng)一個map任務(wù)完成白時候，worker發(fā)送一個消息給 master,在這個消息中包 含這R個臨時文件的名字。如果 master從一個已經(jīng)完成的map任務(wù)再次

21、收到一 個完成的消息，它將忽略這個消息。否則，它在master 的數(shù)據(jù)結(jié)構(gòu)里記錄這R個文件的名字。當(dāng)一個reduce任務(wù)完成的時候，這個reduce worker原子的把臨時文件重命名成最終的輸出文件。如果相同的 reduce 任務(wù)在多個機(jī)器上執(zhí)行，多個重命名調(diào)用將被執(zhí)行， 并產(chǎn)生相同的輸出文件。 我們依賴由底層文件系統(tǒng)提供的原子重命名操作來保證，最終的文件系統(tǒng)狀態(tài)僅僅包含一個reduce任務(wù)產(chǎn)生的數(shù)據(jù)。我們的map和reduce操作大部分都是確定的，并且我們的處理機(jī)制等價于一個順序的執(zhí)行的這個事實(shí)， 使得程序員可以很容易的理解程序的行為。 當(dāng) map 或/和reduce操作是不確定的時候，我

22、們提供雖然比較弱但是合理的處理機(jī)制。當(dāng)在一個非確定操作的前面，一個reduce任務(wù)R1的輸出等價于一個非確定順序 程序執(zhí)行產(chǎn)生的輸出。然而，一個不同的reduce任務(wù)R2的輸出也許符合一個不 同的非確定順序程序執(zhí)行產(chǎn)生的輸出?？紤]map任務(wù)M和reduce任務(wù)R1, R2的情況。我們設(shè)定e(Ri)為已經(jīng)提交 的Ri的執(zhí)行（有且僅有一個這樣的執(zhí)行）。這個比較弱的語義出現(xiàn)，因?yàn)?e（R1）也 許已經(jīng)讀取了由M的執(zhí)行產(chǎn)生的輸出，而e（R2）也許已經(jīng)讀取了由M的不同執(zhí) 行產(chǎn)生的輸出。3。 4 存儲位置在我們的計(jì)算機(jī)環(huán)境里， 網(wǎng)絡(luò)帶寬是一個相當(dāng)缺乏的資源。 我們利用把輸入數(shù)據(jù)（由GFS管理）存儲在機(jī)器的

23、本地磁盤上來保存網(wǎng)絡(luò)帶寬。GFS把每個文件分 成 64MB 的一些塊，然后每個塊的幾個拷貝存儲在不同的機(jī)器上（一般是3 個拷貝）。MapReduce的master考慮輸入文件的位置信息，并且努力在一個包含相關(guān) 輸入數(shù)據(jù)的機(jī)器上安排一個map 任務(wù)。如果這樣做失敗了，它嘗試在那個任務(wù)的輸入數(shù)據(jù)的附近安排一個map 任務(wù) （例如，分配到一個和包含輸入數(shù)據(jù)塊在一個switch里的worker機(jī)器上執(zhí)行）。當(dāng)運(yùn)行巨大的MapReduce操作在一個機(jī)群中 的一部分機(jī)器上的時候，大部分輸入數(shù)據(jù)在本地被讀取，從而不消耗網(wǎng)絡(luò)帶寬。4。 5 任務(wù)粒度象上面描述的那樣，我們細(xì)分map 階段成 M 個片，reduc

24、e 階段成R 個片。M 和 R 應(yīng)當(dāng)比 worker 機(jī)器的數(shù)量大許多。 每個 worker 執(zhí)行許多不同的工作來提高動態(tài)負(fù)載均衡，也可以加速從一個worker 失效中的恢復(fù)，這個機(jī)器上的許多已經(jīng)完成的map任務(wù)可以被分配到所有其他的 worker機(jī)器上。在我們的實(shí)現(xiàn)里，M和R的范圍是有大小限制的，因?yàn)閙aster必須做O（M+R）次調(diào)度， 并且保存 O（M*R） 個狀態(tài)在內(nèi)存中。（這個因素使用的內(nèi)存是很少的，在O（M*R）個狀態(tài)片里，大約每個 map任務(wù)/reduce任務(wù)對使用一個字節(jié)的數(shù)據(jù)）。此外，R經(jīng)常被用戶限制，因?yàn)槊恳粋€reduce任務(wù)最終都是一個獨(dú)立的輸出文件。 實(shí)際上， 我們傾向

25、于選擇M ， 以便每一個單獨(dú)的任務(wù)大概都是16 到 64MB的輸入數(shù)據(jù)（以便上面描述的位置優(yōu)化是最有效的）， 我們把 R 設(shè)置成我們希望使用的worker機(jī)器數(shù)量的小倍數(shù)。我們經(jīng)常執(zhí)行MapReduce計(jì)算，在M=200000, R=5000,使用2000臺工作者機(jī)器的情況下。5。 6 備用任務(wù)一個落后者是延長MapReduce操作時間的原因之一：一個機(jī)器花費(fèi)一個異乎 尋常地的長時間來完成最后的一些 map或reduce任務(wù)中的一個。有很多原因可 能產(chǎn)生落后者。 例如， 一個有壞磁盤的機(jī)器經(jīng)常發(fā)生可以糾正的錯誤， 這樣就使讀性能從 30MB/s 降低到 3MB/s 。機(jī)群調(diào)度系統(tǒng)也許已經(jīng)安排其

26、他的任務(wù)在這個機(jī)器上，由于計(jì)算要使用 CPU,內(nèi)存，本地磁盤，網(wǎng)絡(luò)帶寬的原因，引起它執(zhí) 行MapReduce代碼很慢。我們最近遇到的一個問題是，一個在機(jī)器初始化時的 Bug 引起處理器緩存的失效:在一個被影響的機(jī)器上的計(jì)算性能有上百倍的影響。我們有一個一般的機(jī)制來減輕這個落后者的問題。當(dāng)一個 MapReduce操作 將要完成的時候，master調(diào)度備用進(jìn)程來執(zhí)行那些剩下的還在執(zhí)行的任務(wù)。無論是原來的還是備用的執(zhí)行完成了， 工作都被標(biāo)記成完成。 我們已經(jīng)調(diào)整了這個機(jī) 制， 通常只會占用多幾個百分點(diǎn)的機(jī)器資源。 我們發(fā)現(xiàn)這可以顯著的減少完成大 規(guī)模MapReduce操作的時間。作為一個例子，將要在

27、 5。3描述的排序程序，在 關(guān)閉掉備用任務(wù)的情況下，要比有備用任務(wù)的情況下多花44%的時間。4 技巧盡管簡單的 map 和 reduce 函數(shù)的功能對于大多數(shù)需求是足夠的了，但是我 們開發(fā)了一些有用的擴(kuò)充。這些將在這個部分描述。4。 1 分割函數(shù)MapReduce用戶指定reduce任務(wù)和reduce任務(wù)需要的輸出文件的數(shù)量。在 中間 key 上使用分割函數(shù)， 使數(shù)據(jù)分割后通過這些任務(wù)。 一個缺省的分割函數(shù)使 用hash方法(例如，hash(key) mod Rb這個導(dǎo)致非常平衡的分割。然后，有的時 候，使用其他的 key 分割函數(shù)來分割數(shù)據(jù)有非常有用的。例如，有時候，輸出的 key 是 UR

28、Ls ，并且我們希望每個主機(jī)的所有條目保持在同一個輸出文件中。為了支持像這樣的情況，MapReduce庫的用戶可以提供專門的分割函數(shù)。例如，使 用hash(Hostname(urlkey) mod R祚為分割函數(shù)，使所有來自同一個主機(jī)的 URLs 保存在同一個輸出文件中。4。 2 順序保證我們保證在一個給定的分割里面，中間key/value對以key遞增的順序處理。這個順序保證可以使每個分割產(chǎn)出一個有序的輸出文件， 當(dāng)輸出文件的格式需要支持有效率的隨機(jī)訪問 key 的時候， 或者對輸出數(shù)據(jù)集再作排序的時候， 就很容4。 3combiner 函數(shù)在某些情況下， 允許中間結(jié)果key 重復(fù)會占據(jù)相當(dāng)

29、的比重， 并且用戶定義的reduce函數(shù)滿足結(jié)合律和交換律。一個很好的例子就是在 2。 1 部分的詞統(tǒng)計(jì)程序。因 為詞頻率傾向于一個zipf 分布 （齊夫分布）， 每個 map 任務(wù)將產(chǎn)生成百上千個這樣的記錄the, 1。所有的這些計(jì)數(shù)將通過網(wǎng)絡(luò)被傳輸?shù)揭粋€單獨(dú)的reduce任務(wù)，然后由 reduce 函數(shù)加在一起產(chǎn)生一個數(shù)字。我們允許用戶指定一個可選的combiner 函數(shù)，先在本地進(jìn)行合并一下，然后再通過網(wǎng)絡(luò)發(fā)送。在每一個執(zhí)行map任務(wù)的機(jī)器上combiner函數(shù)被執(zhí)行。一般的，相同的代 碼被用在combiner和reduce函數(shù)。在combiner和reduce函數(shù)之間唯一的區(qū)別是 Ma

30、pReduce庫怎樣控制函數(shù)的輸出。reduce函數(shù)的輸出被保存最終輸出文件里。 combiner函數(shù)的輸出被寫到中間文件里，然后被發(fā)送給 reduce任務(wù)。部分使用combiner可以顯著的提高一些MapReduce操作的速度。附錄A包 含一個使用 combiner 函數(shù)的例子。4。 4 輸入輸出類型MapReduce庫支持以幾種不同的格式讀取輸入數(shù)據(jù)。例如，文本模式輸入把 每一行看作是一個key/value對。key是文件的偏移量，value是那一行的內(nèi)容。 其他普通的支持格式以 key 的順序存儲key/value 對序列。每一個輸入類型的實(shí)現(xiàn)知道怎樣把輸入分割成對每個單獨(dú)的 map 任

31、務(wù)來說是有意義的（例如，文本模式的范圍分割確保僅僅在每行的邊界進(jìn)行范圍分割） 。雖然許多用戶僅僅使用很少的預(yù)定意輸入類型的一個，但是用戶可以通過提供一個簡單的reader接口來支 持一個新的輸入類型。一個reader不必要從文件里讀數(shù)據(jù)。例如，我們可以很容易的定義它從數(shù)據(jù) 庫里讀記錄，或從內(nèi)存中的數(shù)據(jù)結(jié)構(gòu)讀取。4。 5 副作用有的時候，MapReduce的用戶發(fā)現(xiàn)在map操作或/和reduce操作時產(chǎn)生輔助 文件作為一個附加的輸出是很方便的。 我們依靠應(yīng)用程序?qū)憗硎惯@個副作用成為 原子的。一般的，應(yīng)用程序?qū)懸粋€臨時文件，然后一旦這個文件全部產(chǎn)生完，就 自動的被重命名。對于單個任務(wù)產(chǎn)生的多個輸出

32、文件來說， 我們沒有提供其上的兩階段提交的 原子操作支持。 因此， 一個產(chǎn)生需要交叉文件連接的多個輸出文件的任務(wù)， 應(yīng)該 使確定性的任務(wù)。不過這個限制在實(shí)際的工作中并不是一個問題。4。 6 跳過錯誤記錄有的時候因?yàn)橛脩舻拇a里有 bug,導(dǎo)致在某一個記錄上 map或reduce函 數(shù)突然crash掉。這樣的bug使得MapReduce操作不能完成。雖然一般是修復(fù)這 個bug,但是有時候這是不現(xiàn)實(shí)的；也許這個bug是在源代碼不可得到的第三方庫 里。 有的時候也可以忽略一些記錄， 例如， 當(dāng)在一個大的數(shù)據(jù)集上進(jìn)行統(tǒng)計(jì)分析。我們提供一個可選的執(zhí)行模式，在這個模式下，MapReduce庫檢測那些記錄引

33、起 的crash,然后跳過那些記錄，來繼續(xù)執(zhí)行程序。每個 worker 程序安裝一個信號處理器來獲取內(nèi)存段異常和總線錯誤。在調(diào)用一個用戶自定義的map或reduce操作之前，MapReduce庫把記錄的序列號存 儲在一個全局變量里。 如果用戶代碼產(chǎn)生一個信號， 那個信號處理器就會發(fā)送一個包含序號的last gasp”UDP包給MapReduce的masters當(dāng)master不止一次看到 同一個記錄的時候，它就會指出，當(dāng)相關(guān)的map或reduce任務(wù)再次執(zhí)行的時候， 這個記錄應(yīng)當(dāng)被跳過。4。 7 本地執(zhí)行調(diào)試在 map 或 reduce 函數(shù)中問題是很困難的，因?yàn)閷?shí)際的計(jì)算發(fā)生在一個分布式的系統(tǒng)

34、中，經(jīng)常是有一個master 動態(tài)的分配工作給幾千臺機(jī)器。為了簡化調(diào)試和測試，我們開發(fā)了一個可替換的實(shí)現(xiàn)，這個實(shí)現(xiàn)在本地執(zhí)行所有的MapReduce操作。用戶可以控制執(zhí)行，這樣計(jì)算可以限制到特定的 map任務(wù)上。用戶以一個標(biāo)志調(diào)用他們的程序， 然后可以容易的使用他們認(rèn)為好用的任何調(diào)試和測試工具（例如，gdb）。4。 8 狀態(tài)信息master運(yùn)行一個HTTP服務(wù)器，并且可以輸出一組狀況頁來供人們使用。狀態(tài)頁顯示計(jì)算進(jìn)度，象多少個任務(wù)已經(jīng)完成，多少個還在運(yùn)行，輸入的字節(jié)數(shù)，中間數(shù)據(jù)字節(jié)數(shù)，輸出字節(jié)數(shù)，處理百分比，等等。這個頁也包含到標(biāo)準(zhǔn)錯誤的鏈接， 和由每個任務(wù)產(chǎn)生的標(biāo)準(zhǔn)輸出的鏈接。 用戶可以根據(jù)

35、這些數(shù)據(jù)預(yù)測計(jì)算需要花費(fèi)的時間， 和是否需要更多的資源。 當(dāng)計(jì)算比預(yù)期的要慢很多的時候， 這些 頁面也可以被用來判斷是不是這樣。此外， 最上面的狀態(tài)頁顯示已經(jīng)有多少個工作者失敗了， 和當(dāng)它們失敗的時候，那個map和reduce任務(wù)正在運(yùn)行。當(dāng)試圖診斷在用戶代碼里的bug時，這個信息也是有用的。6。 9 計(jì)數(shù)器MapReduce庫提供一個計(jì)數(shù)器工具,來計(jì)算各種事件的發(fā)生次數(shù)。例如,用 戶代碼想要計(jì)算所有處理的詞的個數(shù)，或者被索引的德文文檔的數(shù)量。為了使用這個工具，用戶代碼創(chuàng)建一個命名的計(jì)數(shù)器對象，然后在map 或/和 reduce 函數(shù)里適當(dāng)?shù)脑黾佑?jì)數(shù)器。例如:Counter * upperca

36、se;uppercase=GetCounter(uppercase);map(String name， String contents):for each word w in contents:if(IsCapitalized(w):uppercase-Increment();EmitIntermediate(w， 1);來自不同worker機(jī)器上的計(jì)數(shù)器值被周期性的傳送給 master ping回應(yīng)里) master把來自成功的 map和reduce任務(wù)的計(jì)數(shù)器值加起來，在 MapReduce操作 完成的時候，把它返回給用戶代碼。當(dāng)前計(jì)數(shù)器的值也被顯示在master 狀態(tài)頁里， 以便人們可以

37、查看實(shí)際的計(jì)算進(jìn)度。 當(dāng)計(jì)算計(jì)數(shù)器值的時候消除重復(fù)執(zhí)行的影響，避免數(shù)據(jù)的累加。(在備用任務(wù)的使用，和由于出錯的重新執(zhí)行，可以產(chǎn)生重復(fù)執(zhí)行)有些計(jì)數(shù)器值被MapReduce庫自動的維護(hù)，比如，被處理的輸入 key/value 對的數(shù)量，和被產(chǎn)生的輸出 key/value 對的數(shù)量。用戶發(fā)現(xiàn)計(jì)數(shù)器工具對于檢查MapReduce操作的完整性很有用。例如，在一些MapReduce操作中，用戶代碼也許想要確保輸出對的數(shù)量完全等于輸入對 的數(shù)量， 或者處理過的德文文檔的數(shù)量是在全部被處理的文檔數(shù)量中屬于合理的范圍。5 性能在本節(jié)，我們用在一個大型集群上運(yùn)行的兩個計(jì)算來衡量MapReduce 的性能。一個計(jì)

38、算用來在一個大概1TB 的數(shù)據(jù)中查找特定的匹配串。另一個計(jì)算排序大概 1TB 的數(shù)據(jù)。這兩個程序代表了 MapReduce 的用戶實(shí)現(xiàn)的真實(shí)的程序的一個大子集。一類是， 把數(shù)據(jù)從一種表示轉(zhuǎn)化到另一種表示。 另一類是， 從一個大的數(shù)據(jù)集中提 取少量的關(guān)心的數(shù)據(jù)。5。 1 機(jī)群配置所有的程序在包含大概1800 臺機(jī)器的機(jī)群上執(zhí)行。機(jī)器的配置是:2 個 2G的 Intel Xeon 超線程處理器， 4GB 內(nèi)存， 兩個 160GB IDE 磁盤， 一個千兆網(wǎng)卡。這些機(jī)器部署在一個由兩層的， 樹形交換網(wǎng)絡(luò)中， 在根節(jié)點(diǎn)上大概有100 到 2000G的帶寬。所有這些機(jī)器都有相同的部署（對等部署） ，因此

39、任意兩點(diǎn)之間的來回時間小于 1 毫秒。在 4GB 的內(nèi)存里，大概有1-1。 5GB 被用來運(yùn)行在機(jī)群中其他的任務(wù)。這個程序是在周末的下午開始執(zhí)行的，這個時候 CPU,磁盤，網(wǎng)絡(luò)基本上是空閑 的。5。 2Grep這個Grep程序掃描大概10A10個，每個100字節(jié)的記錄，查找比較少的 3 字符的查找串（這個查找串出現(xiàn)在92337個記錄中）。 輸入數(shù)據(jù)被分割成大概64MB的片 （M=15000） ，全部的輸出存放在一個文件中 （R=1）。圖 2 顯示計(jì)算過程隨時間變化的情況。 Y 軸表示輸入數(shù)據(jù)被掃描的速度。 隨 著更多的機(jī)群被分配給這個 MapReduce計(jì)算，速度在逐步的提高，當(dāng)有1764個

40、worker的時候這個速度達(dá)到最高的30GB/s。當(dāng)map任務(wù)完成的時候，速度開始 下降， 在計(jì)算開始后 80 秒， 輸入的速度降到0。 這個計(jì)算持續(xù)的時間大概是150秒。 這包括了前面大概一分鐘的啟動時間。 啟動時間用來把程序傳播到所有的機(jī) 器上,等待GFS打開1000個輸入文件，得到必要的位置優(yōu)化信息。5。 3 排序這個sort程序排序10A10個記錄，每個記錄100個字節(jié)（大概1TB的數(shù)據(jù)）。 這個程序是模仿TeraSort 的。這個排序程序只包含不到 50 行的用戶代碼。其中有3 行 map 函數(shù)用來從文 本行提取10字節(jié)的排序key,并且產(chǎn)生一個由這個key和原始文本行組成的中 問k

41、ey/value對。我們使用一個內(nèi)置的Identity函數(shù)作為reduce操作。這個函數(shù) 直接把中間key/value對作為輸出的key/value對。最終的排序輸出寫到一個2路 復(fù)制的GFS文件中（也就是，程序的輸出會寫2TB的數(shù)據(jù)）。象以前一樣，輸入數(shù)據(jù)被分割成 64MB的片（M=15000）。我們把排序后的輸 出寫到4000個文件中（R=4000）。分區(qū)函數(shù)使用key的原始字節(jié)來把數(shù)據(jù)分區(qū)到 R 個小片中。我們以這個基準(zhǔn)的分割函數(shù)，知道 key 的分布情況。在一般的排序程序中，我們會增加一個預(yù)處理的 MapReduce操作，這個操作用于采樣 key的情況，并 且用這個采樣的 key 的分

42、布情況來計(jì)算對最終排序處理的分割點(diǎn)。圖3（a）顯示這個排序程序的正常執(zhí)行情況。左上圖顯示輸入數(shù)據(jù)的讀取速度。 這個速度最高到達(dá)13GB/S,并且在不到200秒所有map任務(wù)完成之后迅速滑落 到0o注意到這個輸入速度小于 Grep。這是因?yàn)檫@個排序 map任務(wù)花費(fèi)大概一 半的時間和帶寬，來把中間數(shù)據(jù)寫到本地硬盤中。而Grep 相關(guān)的中間數(shù)據(jù)可以忽略不計(jì)。左中圖顯示數(shù)據(jù)通過網(wǎng)絡(luò)從 map任務(wù)傳輸給reduce任務(wù)的速度。當(dāng)?shù)谝粋€ map任務(wù)完成后，這個排序過程就開始了。圖示上的第一個高峰是啟動了第一批 大概1700個reduce任務(wù)（整個MapReduce任務(wù)被分配到1700臺機(jī)器上，每個機(jī) 器一

43、次只執(zhí)行一個reduce任務(wù)）。大概開始計(jì)算后的300秒，第一批reduce任務(wù) 中的一些完成了，我們開始執(zhí)行剩下的 reduce 任務(wù)。全部的排序過程持續(xù)了大 概 600 秒的時間。左下圖顯示排序后的數(shù)據(jù)被 reduce 任務(wù)寫入最終文件的速度。因?yàn)闄C(jī)器忙于排序中間數(shù)據(jù)， 所以在第一個排序階段的結(jié)束和寫階段的開始有一個延遲。 寫 的速度大概是2-4GB/S。大概開始計(jì)算后的850秒寫過程結(jié)束。包括前面的啟動 過程，全部的計(jì)算任務(wù)持續(xù)的891秒。這個和TeraSort benchmark最高紀(jì)錄1057 秒差不多。需要注意的事情是:因此位置優(yōu)化的原因，很多數(shù)據(jù)都是從本地磁盤讀取的而沒有通過我們

44、有限帶寬的網(wǎng)絡(luò)，所以輸入速度比排序速度和輸出速度都要快。排序速度比輸出速度快的原因是輸出階段寫兩個排序后數(shù)據(jù)的拷貝（我們寫兩個副本的原因是為了可靠性和可用性） 。我們寫兩份的原因是因?yàn)榈讓游募到y(tǒng)的可靠性和可用性的要求。如果底層文件系統(tǒng)用類似容錯編碼（erasure coding珀方式，而不采用復(fù)制寫的方式，在寫盤階段可以降低網(wǎng)絡(luò)帶寬的要求。5。 4 備用任務(wù)的影響在圖3（b）中，顯示我們不用備用任務(wù)的排序程序的執(zhí)行情況。 除了它有一個 很長的幾乎沒有寫動作發(fā)生的尾巴外，執(zhí)行流程和圖 3（a）相似。在960秒后，只 有5個reduce任務(wù)沒有完成。然而，就是這最后幾個落后者知道 300秒后才完

45、 成。全部的計(jì)算任務(wù)執(zhí)行了 1283 秒，多花了44%的時間。7。 5 機(jī)器失效在圖3（c）中，顯示我們有意的在排序程序計(jì)算過程中停止1746臺worker中的 200 臺機(jī)器上的程序的情況。 底層機(jī)群調(diào)度者在這些機(jī)器上馬上重新開始新的worker 程序 （因?yàn)閮H僅程序被停止，而機(jī)器仍然在正常運(yùn)行）。因?yàn)橐呀?jīng)完成的 map 工作丟失了 （由于相關(guān)的 map worker 被殺掉了） ，需要重新再作，所以worker死掉會導(dǎo)致一個負(fù)數(shù)的輸入速率。相關(guān) map任務(wù)的重新 執(zhí)行很快就重新執(zhí)行了。 整個計(jì)算過程在933 秒內(nèi)完成， 包括了前邊的啟動時間（只比正常執(zhí)行時間多了5%的時間）。6 經(jīng)驗(yàn)我們在

46、2003年的2月寫了 MapReduce庫的第一個版本，并且在2003年的8 月做了顯著的增強(qiáng)， 包括位置優(yōu)化， worker 機(jī)器間任務(wù)執(zhí)行的動態(tài)負(fù)載均衡， 等 等。從那個時候起，我們驚奇的發(fā)現(xiàn)MapReduce 函數(shù)庫廣泛用于我們?nèi)粘Ｌ幚淼膯栴}。它現(xiàn)在在Google 內(nèi)部各個領(lǐng)域內(nèi)廣泛應(yīng)用，包括:大規(guī)模機(jī)器學(xué)習(xí)問題Google News和Froogle產(chǎn)品的機(jī)器問題。提取數(shù)據(jù)產(chǎn)生一個流行查詢的報(bào)告（例如，Google Zeitgeist）。為新的試驗(yàn)和產(chǎn)品提取網(wǎng)頁的屬性（例如，從一個web 頁的大集合中提取位置信息 用在位置查詢 ） 。大規(guī)模的圖計(jì)算。圖4顯示了我們主要的源代碼管理系統(tǒng)中，

47、隨著時間推移，MapReduce程序的顯著增加， 從 2003 年早先時候的 0 個增長到 2004 年 9 月份的差不多 900 個不同的程序。MapReduce之所以這樣的成功，是因?yàn)樗軌蛟诓坏桨胄r時間內(nèi)寫出一個簡單的能夠應(yīng)用于上千臺機(jī)器的大規(guī)模并發(fā)程序， 并且極大的提高了開發(fā)和原形設(shè)計(jì)的周期效率。并且，他可以讓一個完全沒有分布式和/ 或并行系統(tǒng)經(jīng)驗(yàn)的程序員，能夠很容易的利用大量的資源。在每一個任務(wù)結(jié)束的時候，MapReduce 函數(shù)庫記錄使用的計(jì)算資源的統(tǒng)計(jì)信息。在圖 1 里，我們列出了 2004 年 8 月份在 Google 運(yùn)行的一些 MapReduce 的 工作的統(tǒng)計(jì)信息。6

48、。 1 大規(guī)模索引到目前為止， 最成功的 MapReduce 的應(yīng)用就是重寫了 Google web 搜索服務(wù)所使用到的 index 系統(tǒng)。索引系統(tǒng)處理爬蟲系統(tǒng)抓回來的超大量的文檔集，這些文檔集保存在GFS 文件里。這些文檔的原始內(nèi)容的大小，超過了20TB 。索引程序是通過一系列的，大概5 到 10 次 MapReduce 操作來建立索引。通過利用MapReduce睛換掉上一個版本的特別設(shè)計(jì)白分布處理的索引程序版本）有這樣一些好處 :索引的代碼簡單，量少，容易理解，因?yàn)槿蒎e，分布式，并行處理都隱藏在MapReduce庫中了。例如，當(dāng)使用 MapReduce函數(shù)庫的時候，計(jì)算的代碼行數(shù)從原來的3

49、800行C+代碼一下減少到大概700行代碼。MapReduce的函數(shù)庫的性能已經(jīng)非常好，所以我們可以把概念上不相關(guān)的計(jì)算步驟分開處理， 而不是混在一起以期減少在數(shù)據(jù)上的處理。 這使得改變索引過程很容易。例如，我們對老索引系統(tǒng)的一個小更改可能要好幾個月的時間，但是在新系統(tǒng)內(nèi)，只需要花幾天時間就可以了。索引系統(tǒng)的操作更容易了，這是因?yàn)闄C(jī)器的失效，速度慢的機(jī)器，以及網(wǎng)絡(luò)失效都已經(jīng)由 MapReduce 自己解決了，而不需要操作人員的交互。另外，我們可以簡單的通過對索引系統(tǒng)增加機(jī)器的方式提高處理性能。7 相關(guān)工作很多系統(tǒng)都提供了嚴(yán)格的設(shè)計(jì)模式， 并且通過對編程的嚴(yán)格限制來實(shí)現(xiàn)自動的并行計(jì)算。例如，一個

50、結(jié)合函數(shù)可以通過N 個元素的數(shù)組的前綴在N 個處理器上使用并行前綴計(jì)算在log N的時間內(nèi)計(jì)算完。MapReduce是基于我們的大型現(xiàn)實(shí)計(jì)算的經(jīng)驗(yàn)， 對這些模型的一個簡化和精煉。 并且， 我們還提供了基于上千臺處理器的容錯實(shí)現(xiàn)。 而大部分并發(fā)處理系統(tǒng)都只在小規(guī)模的尺度上實(shí)現(xiàn)， 并且 機(jī)器的容錯還是程序員來控制的。Bulk Synchronous Programming 以及一些 MPI primitives 提供了更高級別的抽象，可以更容易寫出并行處理的程序。這些系統(tǒng)和 MapReduce 系統(tǒng)的不同之處在，MapReduce利用嚴(yán)格的編程模式自動實(shí)現(xiàn)用戶程序的并發(fā)處理，并且提供了透明的容錯處

51、理。我們本地的優(yōu)化策略是受active disks等技術(shù)的啟發(fā)，在active disks中，計(jì) 算任務(wù)是盡量推送到靠近本地磁盤的處理單元上， 這樣就減少了通過I/O 子系統(tǒng)或網(wǎng)絡(luò)的數(shù)據(jù)量。 我們在少量磁盤直接連接到普通處理機(jī)運(yùn)行， 來代替直接連接 到磁盤控制器的處理機(jī)上，但是一般的步驟是相似的。我們的備用任務(wù)的機(jī)制和在 Charlotte 系統(tǒng)上的積極調(diào)度機(jī)制相似。這個簡單的積極調(diào)度的一個缺陷是， 如果一個任務(wù)引起了一個重復(fù)性的失敗， 那個整個計(jì)算將無法完成。 我們通過在故障情況下跳過故障記錄的機(jī)制， 在某種程度上解決了這個問題。MapReduce 實(shí)現(xiàn)依賴一個內(nèi)置的機(jī)群管理系統(tǒng)來在一個大規(guī)

52、模共享機(jī)器組上分布和運(yùn)行用戶任務(wù)。 雖然這個不是本論文的重點(diǎn)， 但是集群管理系統(tǒng)在理念 上和 Condor 等其他系統(tǒng)是一樣的。在 MapReduce 庫中的排序工具在操作上和 NOW-Sort 相似。源機(jī)器（mapworker）分割將要被排序的數(shù)據(jù)，然后把它發(fā)送到R個reduce worker中的一個上。 每個reduce worker來本地排序它的數(shù)據(jù)（如果可能，就在內(nèi)存中）。當(dāng)然，NOW-Sort 沒有用戶自定義的map 和 reduce 函數(shù)，使得我們的庫可以廣泛的應(yīng)用。River 提供一個編程模型，在這個模型下，處理進(jìn)程可以靠在分布式的隊(duì)列上發(fā)送數(shù)據(jù)進(jìn)行彼此通訊。和MapReduce

53、一樣，River系統(tǒng)嘗試提供對不同應(yīng)用有近似平均的性能，即使在不對等的硬件環(huán)境下或者在系統(tǒng)顛簸的情況下也能提供近似平均的性。River 是通過精心調(diào)度硬盤和網(wǎng)絡(luò)的通訊，來平衡任務(wù)的完成時間。 MapReduce 不和它不同。利用嚴(yán)格編程模型， MapReduce 構(gòu)架來把問題分割成大量的任務(wù)。這些任務(wù)被自動的在可用的 worker 上調(diào)度，以便速度快的worker 可以處理更多的任務(wù)。 這個嚴(yán)格編程模型也讓我們可以在工作快要結(jié)束的時候安排冗余的執(zhí)行，來在非一致處理的情況減少完成時間（比如，在有慢機(jī)或者阻塞的 worker 的時候 )BAD-FS 是一個很 MapReduce 完全不同的編程模型

54、，它的目標(biāo)是在一個廣闊的網(wǎng)絡(luò)上執(zhí)行工作。然而，它們有兩個基本原理是相同的。 (1)這兩個系統(tǒng)使用冗余的執(zhí)行來從由失效引起的數(shù)據(jù)丟失中恢復(fù)。(2)這兩個系統(tǒng)使用本地化調(diào)度策略，來減少通過擁擠的網(wǎng)絡(luò)連接發(fā)送的數(shù)據(jù)數(shù)量。TACC 是一個被設(shè)計(jì)用來簡化高有效性網(wǎng)絡(luò)服務(wù)結(jié)構(gòu)的系統(tǒng)。 和 MapReduce 一樣，它通過再次執(zhí)行來實(shí)現(xiàn)容錯。8 結(jié)束語MapReduce編程模型已經(jīng)在Google成功的用在不同的目的。我們把這個成 功歸于以下幾個原因 :第一，這個模型使用簡單，甚至對沒有并行和分布式經(jīng)驗(yàn) 的程序員也是如此，因?yàn)樗[藏了并行化，容錯，位置優(yōu)化和負(fù)載均衡的細(xì)節(jié)。第二，大量不同的問題可以用 MapReduce計(jì)算來表達(dá)。例如，MapReduce被用 來，為Google的產(chǎn)品web搜索服務(wù)，排序，數(shù)據(jù)挖掘，機(jī)器學(xué)習(xí)，和其他許多 系統(tǒng)， 產(chǎn)生數(shù)據(jù)。 第三， 我們已經(jīng)在一個好幾千臺計(jì)算機(jī)的大型集群上開發(fā)實(shí)現(xiàn) 了這個MapReduce。 這個實(shí)現(xiàn)使得對于這些機(jī)器資源的利用非常簡單， 因此也適用于解決Google遇到的其他很多需要大量計(jì)算的問題。從這個工作中我們也學(xué)習(xí)到了一些東西。 首先， 嚴(yán)格的編程模型使得并行化和分布式計(jì)算簡單， 并且也易于構(gòu)造這