從分治算法說(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)也就自然而然了观蓄。
