MapReduce簡介

MapReduce是Google開發的C++程式設計工具，用于大規模資料集（大于1TB）的并行運算。概念"Map（映射）"和"Reduce（化簡）"，和他們的主要思想，都是從函數式程式設計語言裡借來的，還有從矢量程式設計語言裡借來的特性。[1]

目前的軟體實作是指定一個Map（映射）函數，用來把一組鍵值對映射成一組新的鍵值對，指定并發的Reduce（化簡）函數，用來保證所有映射的鍵值對中的每一個共享相同的鍵組。

映射和化簡

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

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

分布和可靠性

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

化簡操作工作方式很類似，但是由于化簡操作在并行能力較差，主節點會盡量把化簡操作排程在一個節點上，或者離需要操作的資料盡可能進的節點上了；這個特性可以滿足Google的需求，因為他們有足夠的帶寬，他們的内部網絡沒有那麼多的機器。

用途

在Google，MapReduce用在非常廣泛的應用程式中，包括“分布grep，分布排序，web連接配接圖反轉，每台機器的詞矢量，web通路日志分析，反向索引建構，文檔聚類,機器學習，基于統計的機器翻譯...”值得注意的是，MapReduce實作以後，它被用來重新生成Google的整個索引，并取代老的ad hoc程式去更新索引。

MapReduce會生成大量的臨時檔案，為了提高效率，它利用Google檔案系統來管理和通路這些檔案。

其他實作

Nutch項目開發了一個實驗性的MapReduce的實作[2]。

參考

* Dean, Jeffrey & Ghemawat, Sanjay (2004)."MapReduce:大規模叢集上的簡單資料處理方式" 2005年4月6日。

 "我們的靈感來自lisp和其他函數式程式設計語言中的古老的映射和化簡操作." -"MapReduce:大規模叢集上的簡單資料處理方式"

本文轉自Phinecos(洞庭散人)部落格園部落格，原文連結：http://www.cnblogs.com/phinecos/archive/2007/10/27/939740.html，如需轉載請自行聯系原作者