MapReduce

MapReduce是Google提出的一個軟件架構，用於大規模數據集的並行運算。概念「Map（映射）」和「Reduce（歸約）」，及他們的主要思想，都是從函數式編程語言借鑑的，還有從矢量編程語言借來的特性。

當前的軟件實現是指定一個「Map」（映射）函數，用來把一組鍵值對映射成一組新的鍵值對，指定並發的「Reduce」（歸約）函數，用來保證所有映射的鍵值對中的每一個共享相同的鍵組。

映射和歸約

簡單來說，一個映射函數就是對一些獨立元素組成的概念上的列表（例如，一個測試成績的列表）的每一個元素進行指定的操作（比如，有人發現所有學生的成績都被高估了一分，他可以定義一個「減一」的映射函數，用來修正這個錯誤。）。事實上，每個元素都是被獨立操作的，而原始列表沒有被更改，因為這裡創建了一個新的列表來保存新的答案。這就是說，Map操作是可以高度並行的，這對高性能要求的應用以及並行計算領域的需求非常有用。

而歸約操作指的是對一個列表的元素進行適當的合併（繼續看前面的例子，如果有人想知道班級的平均分該怎麼做？他可以定義一個歸約函數，通過讓列表中的奇數（odd）或偶數（even）元素跟自己的相鄰的元素相加的方式把列表減半，如此遞歸運算直到列表只剩下一個元素，然後用這個元素除以人數，就得到了平均分）。雖然他不如映射函數那麼並行，但是因為歸約總是有一個簡單的答案，大規模的運算相對獨立，所以歸約函數在高度並行環境下也很有用。

分布和可靠性

MapReduce通過把對數據集的大規模操作分發給網絡上的每個節點實現可靠性；每個節點會周期性的把完成的工作和狀態的更新報告回來。如果一個節點保持沉默超過一個預設的時間間隔，主節點（類同Google檔案系統中的主服務器）記錄下這個節點狀態為死亡，並把分配給這個節點的數據發到別的節點。每個操作使用命名文件的不可分割操作以確保不會發生並行線程間的衝突；當文件被改名的時候，系統可能會把他們複製到任務名以外的另一個名字上去。（避免副作用）。

歸約操作工作方式很類似，但是由於歸約操作在並行能力較差，主節點會儘量把歸約操作調度在一個節點上，或者離需要操作的數據儘可能近的節點上了；這個特性可以滿足Google的需求，因為他們有足夠的帶寬，他們的內部網絡沒有那麼多的機器。

其他實現

• Hadoop－Apache軟件基金會的開放源碼項目，提供與MapReduce檔案系統類似的功能。

外部連結

• Interpreting the Data: Parallel Analysis with Sawzall- a paper on an internal tool at Google, Sawzall, which acts as an interface to MapReduce, intended to make MapReduce much easier to use.
• Discussion （頁面存檔備份，存於網際網路檔案館） on Lambda the Ultimate.