數據分布式了，計算也得跟上!
1.前情提要
經過一番努力，張大胖和Bill成功地實現了一個分布式的文件系統：HDFS。
（參見《HDFS的誕生》）。
這個系統可以把大文件分成一個個片段，分散地存儲在各個服務器上，每個片段還額外有2個或多個備份。
雖然把文件分了片，但在客戶端軟件看來，仍然是對一個文件進行操作， 并不知道HDFS在背后搞的“伎倆”。
于是張大胖便把海量的Web日志文件存儲到了HDFS當中。
2.并行計算
張大胖決定先使用HDFS完成一個小目標： 統計每個URL被訪問了多少次。
剛一開始，就遇到了棘手的問題：數據量太大，如果只有一臺機器讀出所有文件，在同一臺機器上進行處理，還是慢得要死。
師傅Bill說：“我們在編程中有個非常重要的思想就是‘Divide and Conquer’，現在就可以用到這里來了。”
“分而治之？ ” 張大胖說，“我們不是已經把文件分而治之，變成分片，放到不同機器上了嗎？”
“那只是數據，現在我們讓計算程序也分布式，并且要盡可能地讓計算靠近數據，降低網絡流量的開銷！比如你的小目標，是為了統計URL的訪問次數，我們就把這個計算程序發到每個分片所在的機器上，然后在每個機器上并行地做計算， 像這樣：“
“雖然是并行計算， 但是計算出來的結果還是雜亂無章啊，有什么用？”
“你想想，要是把他們按URL分下組呢？” Bill 說。
（注：正式的術語不叫group by ,叫shuffle。）
“奧，明白，這么做以后，數據之間互相獨立， 又可以并行計算了！”
張大胖接著Bill的圖繼續往下畫：
“對，這樣一來我們的計算也變成分布式的了，并且每個程序都比較簡單， 程序1的職責是：把該分片中的URL給提取出來，記一個數。 程序2的職責是累計每個URL的訪問量。 ” Bill 說道。
3.深入討論
“有意思，看來保持程序的并行執行是關鍵，我注意到一個現象，那就是程序1和程序2都不維護內部狀態，他們就像一個函數，根據輸入進行計算，輸出結果，就這么簡單。”
“ 只有這樣，才有***的靈活性嘛，程序1的各個副本之間不互相依賴， 程序2也會如此， 所以我們才能把程序1和程序2部署到任意一臺機器上去運行。” Bill說。
“還有， 程序1的輸出為什么把每個URL訪問量都記為1呢？我們為什么不能把屬于同一個URL的訪問量在那個節點上先做個求和呢？”
“對于我們這個簡單的情況，是可以先求和，然后發給第二個程序繼續統計，也沒有什么錯誤， 但是對于其他情況，例如求平均數，那就不能先做平均了，得留給第二個程序去做，不然就錯了。”
張大胖心里盤算了一下，假設有三個數字，a= 20,b=10,c = 30, 他們三個的平均數是20 ，但是如果先計算a+b的平均數，再和c 進行平均，即((a+b)/2 + c)/2，結果是22.5，就和之前不一樣了。
“你說過分布式很麻煩，我想到一個問題，如果某個程序沒運行完就死翹翹了，或者那個程序所在的機器down掉了，怎么辦呢？”
“魔鬼都是在細節當中，一遇到異常分支，我們的程序就變得異常復雜。 很明顯，我們得跟蹤每個程序的狀態，如果發現它不可用了，就得在另外一個機器上重新運行它。 我們甚至可以故意多開幾個程序，讓他們競爭，誰運行得最快，就以誰的結果為準。”
“唉，這么多事情，看來又得弄個框架來處理了！” 張大胖感慨道。
“那是自然，什么是框架？ 框架自然是把基礎設施做好，把重復的工作都做了，讓用戶寫的程序越簡單越好，我們的框架會把程序1和程序2分布到各個機器上并行運行，還會監控他們的狀態。 還有那個所謂的分組操作，也得我們處理，所以這必然是個框架，我想可以把它叫做MapReduce。”
4.MapReduce
“MapReduce？ 就是你上次給我說的那個東西？ ”
“對啊， 如果我們把程序1稱為Mapper， 把程序2稱為Reducer，那合起來不就是MapReduce 了。 ” Bill笑著說道。
“怎么會起了這么一個古怪的名字呢？” 張大胖撇撇嘴。
“Map 和 Reduce最早是函數式編程中的概念，所謂map ，就是這個樣子： ”
張大胖說：“不就是把一個函數施加到一組數據上，把它變成另外一組數據嘛！”
“是啊，map 在廣義上來講，就是數據的變換，把一個數據變成另外一個， 回到我們的例子，我們的程序1接收的輸入其實就是一行行的日志記錄，對每一行日志，程序1從中提取URL，變換成另外一個結構:（URL, 1）， 輸出給后續處理。所以也是一種map操作。”
“那reduce 呢？”
“reduce 就是給定一個函數和初始值，每次對列表中的一個元素調用該函數，不斷地“折疊”一個列表，最終把它變成一個值，以最簡單的求和為例，如果初始值為0 ， 列表是[1,2,3,4]，計算過程如下：
“明白了，思想雖然很簡單， 但應用到我們的HDFS當中，讓程序并行化運行， 威力巨大?。?rdquo;
【本文為51CTO專欄作者“劉欣”的原創稿件，轉載請通過作者微信公眾號coderising獲取授權】
