Google MapReduce到底解決什麼問題？

很多時候，定義清楚問題比解決問題更難。

什麼是MapReduce？

它不是一個産品，而是一種解決問題的思路，它有多個工程實作，Google在論文中也給出了它自己的工程架構實作。

MapReduce這個程式設計模型解決什麼問題？

能夠用分治法解決的問題，例如：

• 網頁抓取
• 日志處理
• 索引倒排
• 查詢請求彙總
• …

畫外音：能夠發現，現實中有許多基于分治的應用需求。

為什麼是Google，發明了這個模型？

Google網頁抓取，分析，倒排的多個應用場景，當時的技術體系，解決不了Google大資料量高并發量的需求，Google被迫進行技術創新，思考出了這個模型。

畫外音：誰痛誰想辦法。

為什麼MapReduce對“能夠用分治法解決的問題”特别有效？

分治法，是将一個大規模的問題，分解成多個小規模的問題(分)，多個小規模問題解決，再統籌小問題的解(合)，就能夠解決大規模的問題。

分治法詳見《​​分治法與減治法​​》

Google MapReduce為什麼能夠成功？

Google為了友善使用者使用系統，提供給了使用者很少的接口，去解決複雜的問題。

(1) Map函數接口：處理一個基于key/value(後簡稱kv)的成對(pair)資料集合，同時也輸出基于kv的資料集合；

(2) Reduce函數接口：用來合并Map輸出的kv資料集合；

畫外音：MapReduce系統架構，能在大規模普通PC叢集上實作并行處理，和GFS等典型的網際網路架構類似。

使用者僅僅關注少量接口，不用關心并行、容錯、資料分布、負載均衡等細節，又能夠解決很多實際的問題，還有這等好事！

能不能舉一個例子，說明下MapReduce的Map函數與Reduce函數是如何解決實際問題的？

舉例：假設要統計大量文檔中單詞出現的個數。

Map

輸入KV：pair(文檔名稱，文檔内容)

輸出KV：pair(單詞，1)

畫外音：一個單詞出現一次，就輸出一個1。

Reduce

輸入KV：pair(單詞，1)

輸入KV：pair(單詞，總計數)

以下是一段僞代碼，

Map(list<pair($doc_name, $doc_content)>){

    foreach(pair in list)

        foreach($word in $doc_content)

            echo pair($word, 1); // 輸出list<k,v>

}

畫外音：如果有多個Map程序，輸入可以是一個pair，不是一個list。

Reduce(list<pair($word, $count)>){// 大量(單詞,1)

    map<string,int> result;

        result[$word] += $count;

    foreach($keyin result)

        echo pair($key, result[$key]); // 輸出list<k,v>

畫外音：即使有多個Reduce程序，輸入也是list<pair>，因為它的輸入是Map的輸出。

最早在單機的體系下計算，輸入資料量巨大的時候，處理很慢。如何能夠在短時間内完成處理，很容易想到的思路是，将這些計算分布在成百上千的主機上，但此時，會遇到各種複雜的問題，例如：

• 并行計算
• 資料分發
• 錯誤處理
• 叢集通訊

這些綜合到一起，就成為了一個困難的問題，這也是Google MapReduce工程架構要解決的問題