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.