1. 介紹
MapReduce是google發(fā)明的一種編程模型。在這種編程模型下，用戶通過定義一個map函數(shù)和一個reduce函數(shù)來解決問題。map函數(shù)對用戶輸入的鍵/值對（key/value pair）進行處理（處理時可能只有值這一項有用），生成一系列新的鍵/值對作為中間結(jié)果；系統(tǒng)（
MapReduce的實現(xiàn)）對map函數(shù)生成的鍵/值對進行處理，將同屬于一個鍵（key）的值（value）組合在一起，生成鍵/值列表（（key/list of values） pair）對；reduce函數(shù)將鍵/值列表對作為輸入，對同屬于一個鍵的值列表進行處理，生成最終處理結(jié)果輸出。
如果一個問題可以通過
MapReduce編程模型來表達和解決，就可以通過
MapReduce系統(tǒng)自動獲得并行執(zhí)行能力。程序員不需要有并行程序設計的經(jīng)驗，只需要定義map和reduce函數(shù)。
2. 例子
設想對一堆文檔進行每個單詞出現(xiàn)次數(shù)進行統(tǒng)計的例子。用戶會定義類似下面的map和reduce函數(shù)：
map(String key, String value):
//key: document name
//value: document contents
for each word w in value:
EmitIntermediate(w, "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));
假如輸入是兩篇文檔：
A--"
MapReduce is a programming model"
B--"
MapReduce is easy to use"
map過程是將map分別作用于兩篇文檔，這樣就可以兩篇文檔并行處理，產(chǎn)生輸出是：
(
MapReduce, 1), (is, 1), (a, 1), (programming, 1), (model, 1), (
MapReduce, 1), (is, 1), (easy, 1), (to, 1), (use, 1)。
系統(tǒng)對map的輸出結(jié)果進行處理，生成中間結(jié)果，作為reduce的輸入， 中間結(jié)果為：
(
MapReduce, [1,1]), (is, [1,1]), (a, [1]), (programming, [1]), (model, [1]), (easy, [1]), (to, [1]), (use, [1])。
reduce過程是將reduce函數(shù)分別作用于上面八個鍵/值列表對，這樣就可以八個鍵/值列表對并行處理，產(chǎn)生的輸出是：
(
MapReduce, 2), (is, 2), (a, 1), (programming, 1), (model, 1), (easy, 1), (to, 1), (use, 1)。
這樣，每個單詞出現(xiàn)的頻率就統(tǒng)計出來了。
3. 實現(xiàn)
Google的
MapReduce實現(xiàn)，運行在他們一向引以為傲的數(shù)以千計的commodity machines組成的
linux cluster上面，使用了master/slaves結(jié)構(gòu)，master進行任務分配，slave執(zhí)行具體的任務。
在
MapReduce的具體實現(xiàn)中，并不是簡單的將n個文檔作為n個map任務并行處理，而是將輸入文檔集合按字節(jié)數(shù)（比如64M）打包，每個包中的數(shù)據(jù)，作為一個map任務并行處理，這樣，一個大文件，就可能被分為多個包分別進行處理。也不是將r個鍵/值列表對作為r個reduce任務并行處理，而是通過一個哈希函數(shù)將所有的 key分組，同一個組中的鍵/值列表對在同一個reduce任務中處理（仍然是分別處理）。這樣就可以控制map和reduce的任務數(shù)量。
Google的
MapReduce實現(xiàn)，大量使用了臨時文件。假如有n個map任務，r個reduce任務，每個map任務，將自己的輸出按照key對于哈希函數(shù)的哈希值進行分組（共r 組），同一分組中的所有鍵/值對排序后寫入一個臨時文件中。這時保證了同一個文件中的所有鍵（key）是有序的。每個reduce任務執(zhí)行時，將所有 map任務產(chǎn)生的屬于自己的那個臨時文件（共n個文件）讀入，歸并排序后將結(jié)果送給reduce函數(shù)處理。每個reduce任務產(chǎn)生一個最終的文件作為輸出。這樣，就需要一個分布式的文件系統(tǒng)作為底層支持。Google使用的是Google File System(
GFS)。
4. 總結(jié)
限制了編程模型可以使并行計算十分簡單易用，并且系統(tǒng)結(jié)構(gòu)簡單，易于實現(xiàn)。在這種模型下，
MapReduce系統(tǒng)框架隱藏了并行處理，容錯，負載均衡等細節(jié)問題，使沒有并行處理和分布系統(tǒng)經(jīng)驗的程序員可以使用并行系統(tǒng)解決問題。
這種限制了的編程模型仍然具有很強的表達能力，可以處理信息檢索領域的許多問題，比如Distributed Grep, Count of URL Access Frequency, Reverse Web-Link Graph, Term-Vector per Host, Inverted Index, Word Count。
5. 更多參考
[1] Google關于MapReduce的論文：Dean, Jeff and Ghemawat, Sanjay. MapReduce: Simplified Data Processing on Large Clusters http://labs.google.com/papers/mapreduce-osdi04.pdf
[2] 另一篇關于MapReduce的論文：Lammal, Ralf. Google's MapReduce Programming Model Revisited. http://www.cs.vu.nl/~ralf/MapReduce/paper.pdf
[3] MapReduce和GFS的一個java平臺的開源實現(xiàn)，是Nutch項目的一個副產(chǎn)品：http://lucene.apache.org/hadoop/
[4] Google上一篇關于MapReduce和并行計算的介紹文章：Introduction to Parallel Programming and MapReduce. http://code.google.com/edu/parallel/mapreduce-tutorial.html
轉(zhuǎn)自:
MapReduce 簡介