孫子兵法．謀攻篇：「凡用兵之法：十則圍之，五則攻之，倍則分之。」

這句話的意思是，當我們的兵力大過敵人兵力十倍，就用包圍攻擊來殲滅對方。反過來說，當對方的兵力大過我們，就想辦法分開他們而各自擊破。雖然我的翻譯不是很好，但是老祖宗的智慧，就是 computer science 中，一個非常著名的演算法 divide and conquer。

我們會用到雲端運算，要處理的資料一定是非比尋常的大，大多數的這類的分散式演算法本質上都和 divide and conquer 接近。我們這邊要介紹的 framework，就是 Google 所提的 MapReduce。

以下的圖，就是一個簡化過的 MapReduce 的 work flow。一般來說，它分成四個階段:

hadoop-2

1) Input

雖然原始的資料量太大，但是我們有很多個 node 可以來運算。所以將原始的資料切成若干等份的 block，並往下一個階段送。

2) Map

對傳過來的 block 中的每一個元素，進行 Map function 的運算成為中繼資料。然後將中繼資料往下一個階段送。

3) Reduce

對傳過來的中繼資料，以及前一個 reduce 的結果，進行 Reduce function 的運算。然後將運算結果往下一個階段送。Reduce 和 Map 不同，它有兩個 input。

4) Output

將運算結果寫進檔案系統，完成運算。

這個 design pattern 就是這麼簡單，不知不覺得用上 MapReduce。當然，Map 和 Reduce 的數目，與可以運算的 Node，都是影響效能的關鍵，這個我們容後再講。目前我們所要知道的，就是如何把問題轉化成 MapReduce 的解法，一旦可以套用，那問題幾乎是解了一半了，剩下的就是動手 coding 而己。

我再舉另一些例子。如何從某個電子書中找到最常用到的單字? 這個問題是不是有點像在用 google search 時，出現的關鍵字自動補齊功能 (search autocomplete) 呢? 只是問題簡化過而己。我們來看看這個問題怎麼用 MapReduce。

1) Input

電子書以章為單位，分別送給每一個 Map。

2) Map

Map 找出該章裡所有的單字，接著送給 Reduce。

3) Reduce

Reduce 對上一個 Reduce 排序好的結果，加上對應的 Map 送過來的單字，兩者再排序之後送給下一個 Reduce。

4) Output

最後一個 Reduce 處理完之後，就是最終的單字排序名單。

大家可以多想一些例子來練習這樣的 work flow。

雖然概念上是這樣，但是實際上的作法大家都略有差異。下一篇就是針對 Hadoop 的 MapReduce 來作說明。

Popularity: 9% [?]