MapReduce是Google提出的一個編程框架，用於大規模海量數據處理，其主要思想就是分治（divide and conquer）。我們希望程序有並行處理能力，於是就可以使用多台機器同時處理加快速度。

然而，怎樣分派任務給不同的計算機？如果任務單元的數量大於可執行任務的計算機的數量怎麼辦？計算需要使用到一些中間結果怎樣處理？如果某些計算機在處理任務時中途死掉了呢？怎樣才能知道任務已經處理完畢？問題主要來自於任務處理節點的交流（比如狀態信息），以及對共享資源（數據）的訪問。要解決這些棘手的問題，我們需要有一套完整的同步機制：同步鎖信號量、條件變量（等待、通告、廣播）等等。

現有的一些編程模型有共享內存（pthread）、消息傳遞（MPI）等，架構的設計模式有主從式（Master-Slaves）、生產者消費者流式（Producer-consumer flows）等。Map Reduce結合了函數式編程語言的思想，使用key-value對作為輸入和輸出。開發者只需要實現map(key, value)和reduce(key, value)兩個功能。map()會產生中間結果作為輸出，而這正是reduce()的輸入。中間結果經過reduce()產生最終結果。類似以下模型：

map (in_key, in_value) ->
(out_key, intermediate_value) list

reduce (out_key, intermediate_value list) ->
out_value list

具體的原理可以參看Google發表的關於MapReduce的論文。從應用開發的角度，本站的MapReduce分類下有一些python示例，可以作為初步入門學習。最簡單的方法就是利用管道來進行代碼測試，例如：

./mapper.py < input.txt | sort | ./reducer.py

或者也可以自己搭個虛擬機在Hadoop裡面跑跑，企業級的實際應用可以前往Amazon AWS EMR。

向想深入學習MapReduce分布式程序設計的同學推薦這本書：Data-Intensive Text Processing with MapReduce。如果所在學校購買了數據庫，應該可以直接下載電子版閱讀。書是馬里蘭大學一個華人教授寫的，這教授很牛B，簡直就是算法帝啊……語言方面通俗易懂，像我這種英語爛人都毫無障礙。重點看2、3、4章，講得深入淺出，從最基本的word count程序開始，各種版本的word count寫法以及如何逐步的優化。書里還講到了MapReduce在搜索引擎中的應用。之前還順帶介紹了distributed system的一些基礎，例如GFS以及開源實現HDFS。後面的Graph還有EM算法什麼的比較高深了，我還沒看。。。

現在突然感到有點絕望了，自己對分布式系統架構雲計算什麼的還是蠻有興趣，最後卻發現基礎性工作全是大公司做出來的。因為他們才有最迫切的需求，看看那些論文作者不是google就是yahoo，國內的taobao也在這方面有些貢獻。在實驗室完全沒有那種億萬級別的環境，如何做simulation呢？或者，根本就沒有人帶我入門。。。

科研是條清苦路。