從分治演算法說起 要說 MapReduce 就不得不說分治演算法，而分治演算法其實說白了，就是四個字 分而治之 。其實就是將一個複雜的問題分解成多組相同或類似的子問題，對這些子問題再分，然後再分。直到最後的子問題可以簡單得求解。 要具體介紹分治演算法，那就不得不說一個很經典的排序演算法 歸併排序。這裡不說它的 ...
從分治演算法說起
要說 MapReduce 就不得不說分治演算法，而分治演算法其實說白了，就是四個字 分而治之 。其實就是將一個複雜的問題分解成多組相同或類似的子問題，對這些子問題再分，然後再分。直到最後的子問題可以簡單得求解。
要具體介紹分治演算法，那就不得不說一個很經典的排序演算法 -- 歸併排序。這裡不說它的具體演算法代碼，只說明它的主要思想。而歸併排序的思想正是分治思想。
歸併排序採用遞歸的方式，每次都將一個數組分解成更小的兩個數組，再對這兩個數組進行排序，不斷遞歸下去。直到分解成最簡單形式的兩個數組的時候，再將這一個個分解後的數組進行合併。這就是歸併排序。
下麵有一個取自百度百科的具體例子可以看看：
我們可以看到，初始的數組是：{10，4，6，3，8，2，5，7}
第一次分解後，變成兩個數組：{10，4，6，3}，{8，2，5，7}
分解到最後為 5 個數組：{10}，{4，6}，{3，8}，{2，5}，{7}
然後分別合併併排序，最後排序完成：{2，3，4，5，6，7，8，10}
上述的例子這是比較簡單的情況，那麼我們想想看，當這個數組很大的時候又該怎麼辦呢？比如這個數組達到 100 GB大小，那麼在一臺機器上肯定是無法實現或是效率較為低下的。
那一臺機器不行，那我們可以拆分到多台機器中去嘛。剛好使用分治演算法將一個任務可以拆分成多個小任務，並且這多個小任務間不會相互干擾，可以獨立計算。那麼我們可以拆分這個數組，將這個數組拆分成 20 個塊，每個的大小為 5 GB。然後將這每個 5 GB的塊分散到各個不同的機器中去運行，最後再將處理的結果返回，讓中央機器再進行一次完整的排序，這樣無疑速度上會提升很多。
上述這個過程就是 MapReduce 的大致原理了。
函數式的 MapReduce
Map 和 Reduce 其實是函數式編程中的兩個語義。Map 和迴圈 for 類似，只不過它有返回值。比如對一個 List 進行 Map 操作，它就會遍歷 List 中的所有元素，然後根據每個元素處理後的結果返回一個新的值。下麵這個例子就是利用 map 函數，將 List 中每個元素從 Int 類型 轉換為 String 類型。
val a:List[Int] = List(1,2,3,4)
val b:List[String] = a.map(num => (num.toString))
而 Reduce 在函數式編程的作用則是進行數據歸約。Reduce 方法需要傳入兩個參數，然後會遞歸得對每一個參數執行運算。還是用一個例子來說明：
val list:List[Int] = List(1,2,3,4,5)
//運算順序是：1-2 = -1; -1-3 = -4; -4-4 = -8; -8-5 = -13;
//所以結果等於 -13
list.reduce(_ - _)談談 Hadoop 的 MapReduce
Hadoop MapReduce 和函數式中的 Map Reduce 還是比較類似的，只是它是一種編程模型。我們來看看 WordCount 的例子就明白了。
在這個 wordcount 程式中，MapReduce 會對輸入先進行切分，這一步其實就是分治中分的過程。切分後不同部分就會讓不同的機器去執行 Map 操作。而後便是 Shuffle，這一階段會將不相同的單詞加到一起，最後再進行 Reduce 。
這個 WordCount 程式是官方提供的一個簡易的 Demo，更複雜的任務需要自己分解成 MapReduce 模型的代碼然後執行。
所謂 MapReduce 的意思是任何的事情只要都嚴格遵循 Map Shuffle Reduce 三個階段就好。其中Shuffle是系統自己提供的而Map和Reduce則用戶需要寫代碼。
當碰到一個任務的時候，我們需要將它解析成 Map Reduce 的處理方式然後編寫 MapReduce 代碼來實現。我看過一個比喻很貼切，MapReduce 這個東西這就像是說我們有一把大砍刀，一個錘子。世界上的萬事萬物都可以先砍幾刀再錘幾下，就能搞定。至於刀怎麼砍，錘子怎麼錘，那就算個人的手藝了。
從模型的角度來看，MapReduce 是比較粗糙的，無論什麼方法都只能用 Map Reduce 的方式來運行，而這種方式無疑不是萬能的，很多應用場景都很難解決。而從做資料庫的角度來看，這無非也就是一個 select + groupBy() 。這也就是為什麼有了後面 Spark 基於 DAG 的 RDD 概念的崛起。
這裡不得不多說一句，Hadoop 的文件系統 Hdfs 才是 MapReduce 的基礎，因為 Map Reduce 最實質的支撐其實就是這個 Hdfs 。沒有它， Map Reduce 不過是空中閣樓。你看，在 MapReduce 式微的今天，Hdfs 還不是活得好好的，Spark 或是 Hive 這些工具也都是以它為基礎。不得不說，Hdfs 才牛逼啊。
為什麼會出現 MapReduce
好了，接下來我們來探究一下為什麼會出現 MapReduce 這個東西。
MapReduce 在 Google 最大的應用是做網頁的索引。大家都知道 Google 是做搜索引擎起家的，而搜索引擎的基本原理就是索引，就是爬去互聯網上的網頁，然後對建立 單詞->文檔 的索引。這樣什麼搜索關鍵字，才能找出對應網頁。這也是為什麼 Google 會以 WordCount 作為 MapReduce 的例子。
既然明白搜索引擎的原理，那應該就明白自 2000 年來互聯網爆發的年代，單台機器肯定是不夠存儲大量的索引的，所以就有了分散式存儲，Google 內部用的叫 Gfs，Hadoop Hdfs 其實可以說是山寨 Gfs 來的。而在 Gfs 的基礎上，MapReduce 的出現也就自然而然了。
