用 MapReduce 處理大量工作

MapReduce是一種簡單的程式模型，只要知道map和reduce程式，系統會幫忙將map用在原始資料上，整理岀中繼資料，然後用reduce程式收斂這些中繼資料。

程式結構

Map是一個從 (key, list(value)) 對應到 list(key', value') 的函數。簡單說，對map輸入一列資料，map會將資料做一些前處理，然後把一個 key 跟每一筆資料配對。Map是使用者自己寫的程式。

Reduce是一個從 list(key', value') 對應到 list(value'') 的函數。簡單說，reduce是彙總函數，將許多 value' 收合為一個value'' 。 Key' 的存在，可能是用於樣式比對或額外附加資訊的需要。最後的結果仍是 list(value'') 是方便與其他 reduce 程式的輸出再做合併。

系統組成

系統使用相當多的工作單元分別消化map和reduce工作。工作單元可以分佈在許多台電腦中，並且工作單元彼此不共享記憶體資料。Map或reduce做完之後，將資料儲存在檔案系統中。只有一種特殊的工作單元稱為master，負責監看所有map和reduce工作單元的活動情況，並負責派遣map或reduce工作。

分散處理：Map和reduce工作單元各別處理自己的一段資料，做完時，將資料儲存在自己所在電腦的檔案系統，並將完成訊息和檔案位置資訊傳給master工作單元。Master工作單元可以再將中繼檔案或結果檔案的位置資訊傳給下一個map或reduce工作單元，指派下一階段的工作。

檔案儲存：檔案從來不整合成一個大檔案，而是以許多小檔案的形式存在許多台電腦中。電腦彼此之間不交換檔案流，節省網路頻寬。

容錯處理：如果有一些工作單元或電腦不活動並且沒有回應，master工作單元將已經指派去那些電腦的工作重新指派給其他工作單元。要重做工作的原因是，不回應的工作單元造成它所在的電腦檔案無法讀取。重做無效的工作最有容錯的保障。

實作案例

Google MapReduce是C/C++寫的。Hadoop是用Java實作的MapReduce平台，從其中擴充出HadoopDB和Hive等資料庫系統。CouchDB是用到MapReduce方法處理索引的文件式資料庫，用Erlang實作。Disco是Nokia開發的開源MapReduce平台，用Erlang實作，使用者必須用Python寫程式。

1. MapReduce, Wikipedia, http://en.wikipedia.org/wiki/MapReduce.

2. Jeffrey Dean and Sanjay Ghemawat, MapReduce: Simplified Data Processing on Large Clusters, Proceedings of 6th Symposium on Operating Systems Design and Implementation, 2004.