1. 介紹
MapReduce是google發明的一種編程模型。在這種編程模型下，用戶通過定義一個map函數和一個reduce函數來解決問題。map函數對用戶輸入的鍵/值對（key/value pair）進行處理（處理時可能只有值這一項有用），生成一系列新的鍵/值對作為中間結果；系統（
MapReduce的實現）對map函數生成的鍵/值對進行處理，將同屬于一個鍵（key）的值（value）組合在一起，生成鍵/值列表（（key/list of values） pair）對；reduce函數將鍵/值列表對作為輸入，對同屬于一個鍵的值列表進行處理，生成最終處理結果輸出。
如果一個問題可以通過
MapReduce編程模型來表達和解決，就可以通過
MapReduce系統自動獲得并行執行能力。程序員不需要有并行程序設計的經驗，只需要定義map和reduce函數。
2. 例子
設想對一堆文檔進行每個單詞出現次數進行統計的例子。用戶會定義類似下面的map和reduce函數：
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分別作用于兩篇文檔，這樣就可以兩篇文檔并行處理，產生輸出是：
(
MapReduce, 1), (is, 1), (a, 1), (programming, 1), (model, 1), (
MapReduce, 1), (is, 1), (easy, 1), (to, 1), (use, 1)。
系統對map的輸出結果進行處理，生成中間結果，作為reduce的輸入， 中間結果為：
(
MapReduce, [1,1]), (is, [1,1]), (a, [1]), (programming, [1]), (model, [1]), (easy, [1]), (to, [1]), (use, [1])。
reduce過程是將reduce函數分別作用于上面八個鍵/值列表對，這樣就可以八個鍵/值列表對并行處理，產生的輸出是：
(
MapReduce, 2), (is, 2), (a, 1), (programming, 1), (model, 1), (easy, 1), (to, 1), (use, 1)。
這樣，每個單詞出現的頻率就統計出來了。
3. 實現
Google的
MapReduce實現，運行在他們一向引以為傲的數以千計的commodity machines組成的
linux cluster上面，使用了master/slaves結構，master進行任務分配，slave執行具體的任務。
在
MapReduce的具體實現中，并不是簡單的將n個文檔作為n個map任務并行處理，而是將輸入文檔集合按字節數（比如64M）打包，每個包中的數據，作為一個map任務并行處理，這樣，一個大文件，就可能被分為多個包分別進行處理。也不是將r個鍵/值列表對作為r個reduce任務并行處理，而是通過一個哈希函數將所有的 key分組，同一個組中的鍵/值列表對在同一個reduce任務中處理（仍然是分別處理）。這樣就可以控制map和reduce的任務數量。
Google的
MapReduce實現，大量使用了臨時文件。假如有n個map任務，r個reduce任務，每個map任務，將自己的輸出按照key對于哈希函數的哈希值進行分組（共r 組），同一分組中的所有鍵/值對排序后寫入一個臨時文件中。這時保證了同一個文件中的所有鍵（key）是有序的。每個reduce任務執行時，將所有 map任務產生的屬于自己的那個臨時文件（共n個文件）讀入，歸并排序后將結果送給reduce函數處理。每個reduce任務產生一個最終的文件作為輸出。這樣，就需要一個分布式的文件系統作為底層支持。Google使用的是Google File System(
GFS)。
4. 總結
限制了編程模型可以使并行計算十分簡單易用，并且系統結構簡單，易于實現。在這種模型下，
MapReduce系統框架隱藏了并行處理，容錯，負載均衡等細節問題，使沒有并行處理和分布系統經驗的程序員可以使用并行系統解決問題。
這種限制了的編程模型仍然具有很強的表達能力，可以處理信息檢索領域的許多問題，比如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平臺的開源實現，是Nutch項目的一個副產品：http://lucene.apache.org/hadoop/
[4] Google上一篇關于MapReduce和并行計算的介紹文章：Introduction to Parallel Programming and MapReduce. http://code.google.com/edu/parallel/mapreduce-tutorial.html
轉自:
MapReduce 簡介