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