（只有文字沒有圖，圖請參考http://research.google.com/archive/mapreduce.html）

MapReduce: 1種簡化的大范圍集群數據處理法

翻譯：風里來雨里去

原文：MapReduce: Simplified Data Processing on Large Clusters

作者：JeffreyDean and Sanjay Ghemawat

轉載請保存以上信息

摘要

MapReduct是1個用于處理與生成大型數據集的編程模型及相干實現。用戶分別指定1個map函數與1個reduce函數，由map函數處理1個輸入鍵值對，生成若干中間鍵值對，再由reduce函數合并具有相同鍵的中間值。這1模型可以用于表述許多真實世界的問題。

采取這類函數式風格編寫的程序能自動地并行運轉在便宜計算機構成的大范圍集群中。運行系統管理著輸入數據的拆分、橫跨多機的程序調度、硬件故障的處理，和多機間的通訊。這樣1來，就算是沒有任何并行計算開發經驗的程序員都能輕易地利用1個大型散布式系統的資源。

我們的MapReduce實現是運行于由便宜計算機構成的大范圍集群之上，具有很高的伸縮性，1個典型的MapReduce操作常常需要處理數千臺計算機上的TB級數據。程序員們認為這1系統易于使用，目前他們已實現了數百個MapReduce程序，而且每天都要在Google內部的集群上運行1000多個MapReduce作業。

1 簡介

在過去的5年中，本文作者與許多Google同事曾編寫了數百個專門用處的程序，這些程序都是對爬蟲取回的網頁、web要求日志等容量巨大的原始數據進行處理，計算出各種不同的衍生數據，例如反向索引、各種情勢的網頁結構圖、各網站的網頁總數、指定日期的頻繁查詢集，等等。這些程序的算法常常很簡單，但由于輸入數據量太大，為了要在可以接受的時間內完成，我們不能不將它們放到數千臺計算機上去運行。而為了處理并行化、數據分發、硬件故障等困難，又不能不在本來簡單的程序中加入大量復雜的代碼。

為解決這1困難，我們設計了1個新模型，利用運行庫隱藏并行化、故障處理、數據分發和負載均衡等復雜細節，程序員只需表達真正想要的計算邏輯便可。我們從Lips等函數式語言的map與reduce原語中遭到啟發，發現之前所寫的程序大都具有1個共性：對輸入的“記錄”履行1個map操作，得出若干中間鍵值對，然后處理中間值，對鍵相同的中間值履行1個reduce操作，對衍生出的數據加以合并。利用這類由用戶指定map/reduce操作的模型，很容易實現并行化，而且可以使用重新運行作為容錯的主要手段。

這1成果的主要貢獻是提供了1個簡單而強大的接口，可幫助實現大范圍計算的自動并行化，同時還提供了該接口的1個實現，可在由便宜計算機構成的大范圍集群上到達很高的性能。

本文的第2節講述了MapReduce的基本編程模型，并給出了1些例子。第3節介紹了1個專為我們的集群環境度身訂造的MapReduce實現。第4節介紹了1些我們認為有用的優化技術。第5節利用幾個不同的作業，對我們的MapReduce實現進行了性能評測。第6節介紹了MapReduce在Google內部的使用情況，和我們利用它重寫索引編制系統的1些經驗。第7節討論了1些相干的成果。

2 編程模型

某1計算，獲得若干輸入鍵值對，生成若干輸出鍵值對。MapReduce的用戶可以通過兩個函數表達這1計算：Map與Reduce。

Map是由用戶編寫，它獲得1個輸入鍵值對，生成若干中間鍵值對。MapReduce將所有具有相同鍵I的中間值編為1組，交給Reduce函數。

Reduce函數一樣是由用戶編寫，它接受I及I對應的所有值，將它們合并為較小的集合。1次Reduce調用常常只生成0到1個值。在將中間值傳遞給reduce函數時，系統采取了迭代方式，從而得以處理那些由于數據過量而沒法放入內存的情況。

2.1 示例

現在，假定需要統計某1批文檔中各個單詞出現的次數。用戶可能會寫出這樣的代碼：

map(String key, String value):

//key: document name

//value: document contents

foreach word w in value:

EmitIntermediate(w, “1”);

reduce(String key, Iterator values):

//key: a word

//values: a list of counts

intresult = 0;

foreach v in values:

result += ParseInt(v);

Emit(AsString(result));

map函數輸出各單詞及出現次數（本例中為1）。reduce函數將指訂單詞的次數累加起來。

用戶還需編寫1些代碼，將輸入輸出文件的名稱及1些可選參數填入mapreducespecification對象，然后將它作為參數，調用MapReduce函數。系統會將用戶代碼鏈接到MapReduce庫（以C++實現）上。附錄A提供了本例的完全代碼。

2.2 類型

上1節的偽代碼中，輸入輸出均為字符串。但在概念上，用戶提供的map和reduce函數應具有以下相應類型：

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

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

也就是說，輸入鍵值與輸出鍵值分屬不同域。而中間鍵值與輸出鍵值屬于相同域。

在我們的實現中，map/reduce函數的輸入與輸出均采取字符串，而字符串與相應類型間的轉換交由用戶代碼負責。

2.3 更多示例

以下是1些很容易采取MapReduce模型的小例子。

散布式grep：如果map函數匹配到指定的模式，即輸出1行。reduce函數是1個恒等函數，直接將中間數據復制為輸出數據。

URL訪問頻率統計：map函數處理web要求日志，輸出

include”mapreduce/mapreduce.h”

// User’smap function

classWordCounter : public Mapper {

public:

virtual void Map(constMapInput& input) {

const string& text =input.value();

const int n = text.size();

for (int i = 0; i < n; ) {

// Skip past leading whitespace

while ((i < n) &&isspace(text[i]))

i++;

// Find word end

int start = i;

while ((i < n) && !isspace(text[i]))

i++;

if (start < i)

Emit(text.substr(start,i-start),”1”);

}

}

};

REGISTER_MAPPER(WordCounter);

// User’sreduce function

classAdder : public Reducer {

virtual void Reduce(ReduceInput*input) {

// Iterate over all entries withthe

// same key and add the values

int64 value = 0;

while (!input->done()) {

value +=StringToInt(input->value());

input->NextValue();

}

// Emit sum for input->key()

Emit(IntToString(value));

}

};

REGISTER_REDUCER(Adder);

intmain(int argc, char** argv) {

ParseCommandLineFlags(argc, argv);

MapReduceSpecification spec;

// Store list of input files into”spec”

for (int i = 1; i < argc; i++){

MapReduceInput* input =spec.add_input();

input->set_format(“text”);

input->set_filepattern(argv[i]);

input->set_mapper_class(“WordCounter”);

}

// Specify the output files:

// /gfs/test/freq-00000-of-00100

// /gfs/test/freq-00001-of-00100

// …

MapReduceOutput* out =spec.output();

out->set_filebase(“/gfs/test/freq”);

out->set_num_tasks(100);

out->set_format(“text”);

out->set_reducer_class(“Adder”);

// Optional: do partial sumswithin map

// tasks to save network bandwidth

out->set_combiner_class(“Adder”);

// Tuning parameters: use at most2000

// machines and 100 MB of memoryper task

spec.set_machines(2000);

spec.set_map_megabytes(100);

spec.set_reduce_megabytes(100);

// Now run it

MapReduceResult result;

if (!MapReduce(spec, &result))abort();

// Done: ‘result’ structurecontains info

// about counters, time taken,number of

// machines used, etc.

return 0;

}