[[221573]]

1.前情提要

經(jīng)過一番努力，張大胖和Bill成功地實(shí)現(xiàn)了一個(gè)分布式的文件系統(tǒng)：HDFS。

（參見《HDFS的誕生》）。

這個(gè)系統(tǒng)可以把大文件分成一個(gè)個(gè)片段，分散地存儲(chǔ)在各個(gè)服務(wù)器上，每個(gè)片段還額外有2個(gè)或多個(gè)備份。

雖然把文件分了片，但在客戶端軟件看來，仍然是對(duì)一個(gè)文件進(jìn)行操作， 并不知道HDFS在背后搞的“伎倆”。

于是張大胖便把海量的Web日志文件存儲(chǔ)到了HDFS當(dāng)中。

2.并行計(jì)算

張大胖決定先使用HDFS完成一個(gè)小目標(biāo)： 統(tǒng)計(jì)每個(gè)URL被訪問了多少次。

剛一開始，就遇到了棘手的問題：數(shù)據(jù)量太大，如果只有一臺(tái)機(jī)器讀出所有文件，在同一臺(tái)機(jī)器上進(jìn)行處理，還是慢得要死。

師傅Bill說：“我們?cè)诰幊讨杏袀€(gè)非常重要的思想就是‘Divide and Conquer’，現(xiàn)在就可以用到這里來了。”

“分而治之？ ” 張大胖說，“我們不是已經(jīng)把文件分而治之，變成分片，放到不同機(jī)器上了嗎？”

“那只是數(shù)據(jù)，現(xiàn)在我們讓計(jì)算程序也分布式，并且要盡可能地讓計(jì)算靠近數(shù)據(jù)，降低網(wǎng)絡(luò)流量的開銷！比如你的小目標(biāo)，是為了統(tǒng)計(jì)URL的訪問次數(shù)，我們就把這個(gè)計(jì)算程序發(fā)到每個(gè)分片所在的機(jī)器上，然后在每個(gè)機(jī)器上并行地做計(jì)算， 像這樣：“

“雖然是并行計(jì)算， 但是計(jì)算出來的結(jié)果還是雜亂無章啊，有什么用？”

“你想想，要是把他們按URL分下組呢？” Bill 說。

（注：正式的術(shù)語(yǔ)不叫g(shù)roup by ,叫shuffle。）

“奧，明白，這么做以后，數(shù)據(jù)之間互相獨(dú)立， 又可以并行計(jì)算了！”

張大胖接著Bill的圖繼續(xù)往下畫：

“對(duì)，這樣一來我們的計(jì)算也變成分布式的了，并且每個(gè)程序都比較簡(jiǎn)單， 程序1的職責(zé)是：把該分片中的URL給提取出來，記一個(gè)數(shù)。 程序2的職責(zé)是累計(jì)每個(gè)URL的訪問量。 ” Bill 說道。

3.深入討論

“有意思，看來保持程序的并行執(zhí)行是關(guān)鍵，我注意到一個(gè)現(xiàn)象，那就是程序1和程序2都不維護(hù)內(nèi)部狀態(tài)，他們就像一個(gè)函數(shù)，根據(jù)輸入進(jìn)行計(jì)算，輸出結(jié)果，就這么簡(jiǎn)單。”

“ 只有這樣，才有***的靈活性嘛，程序1的各個(gè)副本之間不互相依賴， 程序2也會(huì)如此， 所以我們才能把程序1和程序2部署到任意一臺(tái)機(jī)器上去運(yùn)行。” Bill說。

“還有， 程序1的輸出為什么把每個(gè)URL訪問量都記為1呢？我們?yōu)槭裁床荒馨褜儆谕粋€(gè)URL的訪問量在那個(gè)節(jié)點(diǎn)上先做個(gè)求和呢？”

“對(duì)于我們這個(gè)簡(jiǎn)單的情況，是可以先求和，然后發(fā)給第二個(gè)程序繼續(xù)統(tǒng)計(jì)，也沒有什么錯(cuò)誤， 但是對(duì)于其他情況，例如求平均數(shù)，那就不能先做平均了，得留給第二個(gè)程序去做，不然就錯(cuò)了。”

張大胖心里盤算了一下，假設(shè)有三個(gè)數(shù)字，a= 20,b=10,c = 30,  他們?nèi)齻€(gè)的平均數(shù)是20 ，但是如果先計(jì)算a+b的平均數(shù)，再和c 進(jìn)行平均，即((a+b)/2 + c)/2，結(jié)果是22.5，就和之前不一樣了。

“你說過分布式很麻煩，我想到一個(gè)問題，如果某個(gè)程序沒運(yùn)行完就死翹翹了，或者那個(gè)程序所在的機(jī)器down掉了，怎么辦呢？”

“魔鬼都是在細(xì)節(jié)當(dāng)中，一遇到異常分支，我們的程序就變得異常復(fù)雜。 很明顯，我們得跟蹤每個(gè)程序的狀態(tài)，如果發(fā)現(xiàn)它不可用了，就得在另外一個(gè)機(jī)器上重新運(yùn)行它。 我們甚至可以故意多開幾個(gè)程序，讓他們競(jìng)爭(zhēng)，誰(shuí)運(yùn)行得最快，就以誰(shuí)的結(jié)果為準(zhǔn)。”

“唉，這么多事情，看來又得弄個(gè)框架來處理了！” 張大胖感慨道。

“那是自然，什么是框架？ 框架自然是把基礎(chǔ)設(shè)施做好，把重復(fù)的工作都做了，讓用戶寫的程序越簡(jiǎn)單越好，我們的框架會(huì)把程序1和程序2分布到各個(gè)機(jī)器上并行運(yùn)行，還會(huì)監(jiān)控他們的狀態(tài)。 還有那個(gè)所謂的分組操作，也得我們處理，所以這必然是個(gè)框架，我想可以把它叫做MapReduce。”

4.MapReduce

“MapReduce？ 就是你上次給我說的那個(gè)東西？ ”

“對(duì)啊， 如果我們把程序1稱為Mapper， 把程序2稱為Reducer，那合起來不就是MapReduce 了。 ” Bill笑著說道。

“怎么會(huì)起了這么一個(gè)古怪的名字呢？” 張大胖撇撇嘴。

“Map 和 Reduce最早是函數(shù)式編程中的概念，所謂map ，就是這個(gè)樣子： ”

張大胖說：“不就是把一個(gè)函數(shù)施加到一組數(shù)據(jù)上，把它變成另外一組數(shù)據(jù)嘛！”

“是啊，map 在廣義上來講，就是數(shù)據(jù)的變換，把一個(gè)數(shù)據(jù)變成另外一個(gè)， 回到我們的例子，我們的程序1接收的輸入其實(shí)就是一行行的日志記錄，對(duì)每一行日志，程序1從中提取URL，變換成另外一個(gè)結(jié)構(gòu):（URL, 1）， 輸出給后續(xù)處理。所以也是一種map操作。”

“那reduce 呢？”

“reduce 就是給定一個(gè)函數(shù)和初始值，每次對(duì)列表中的一個(gè)元素調(diào)用該函數(shù)，不斷地“折疊”一個(gè)列表，最終把它變成一個(gè)值，以最簡(jiǎn)單的求和為例，如果初始值為0 ， 列表是[1,2,3,4]，計(jì)算過程如下：

“明白了，思想雖然很簡(jiǎn)單， 但應(yīng)用到我們的HDFS當(dāng)中，讓程序并行化運(yùn)行， 威力巨大??！”

【本文為51CTO專欄作者“劉欣”的原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)通過作者微信公眾號(hào)coderising獲取授權(quán)】

戳這里，看該作者更多好文