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