[[221573]]

1.前情提要

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

（參見《HDFS的誕生》）。

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

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

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

2.并行計算

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

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

師傅Bill說：“我們在編程中有個非常重要的思想就是‘Divide and Conquer’，現(xiàn)在就可以用到這里來了。”

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

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

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

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

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

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

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

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

3.深入討論

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

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

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

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

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

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

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

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

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

4.MapReduce

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

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

“怎么會起了這么一個古怪的名字呢？” 張大胖撇撇嘴。

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

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

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

“那reduce 呢？”

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

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

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

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