【Coursera课程笔记】Web智能和大数据Week3_MapReduce
本文目的
到今天為止，Coursera上的課程Web Intelligence and Big Data[5]已經(jīng)上到Week 3（從0開始計數(shù)，實際上是4周）。前幾周講了一些機(jī)器學(xué)習(xí)的算法，如LHS，PageRank，樸素貝葉斯分類器等。但是光有這些算法還不夠，特別是在當(dāng)前這種海量數(shù)據(jù)（Big Data）盛行的年代。所以，Week 3就聊到了一種通用的大數(shù)據(jù)處理解決方法?——Map Reduce(后面簡稱MR)。此方法最初來自Google的一篇論文[1]，現(xiàn)在用來指代一種編程方式，主要作用與大規(guī)模數(shù)據(jù)集（通常在1T以上）的并行計算（很多算法都可以用MR方式實現(xiàn)）。本周課程主要內(nèi)容介紹了MR的編程模型（結(jié)合Mincemeat[2]和Octopy[3]），運作原理和計算效率。在這里簡單記錄本周內(nèi)容，作為備忘，對后面的工作會有幫助。
?
MapReduce編程方式
MR是一種編程模式。基于這種編程模式，可以有多種實現(xiàn)，鼎鼎大名的Hadoop就是其中之一。在MR的世界中，你只需要實現(xiàn)兩個方法：map和reduce，剩下的所有事情交給MR框架，比如消息處理，中間數(shù)據(jù)存儲，數(shù)據(jù)合并，容錯等。
?
上千個廉價PC機(jī)并行處理，難免會出現(xiàn)服務(wù)器故障，至少出現(xiàn)一臺服務(wù)器出錯的概率為1-Pk，也就意味著隨著機(jī)器數(shù)量K的增加，概率會趨近于1
?
Map函數(shù)的輸入可以是任意序列，但輸出必須是一個鍵值對{K,V}，這一點很重要，因為MR框架會根據(jù)K，將不同K對應(yīng)的V合并成一個列表，得到{K，V–List}，然后將其作為reduce函數(shù)的輸入，reduce的輸出可以是任意數(shù)據(jù)。舉個例子，有下列map和輸出：
???????? map1?–> {‘one’,1}, {‘two’,1}, {‘three’,1}
???????? map2--?–> {‘two’,1}, {‘world,1}
???????? map3--?–>{‘three,1}
那么經(jīng)過合并后，得到中結(jié)果：
??????? {‘one’, [1]}, {‘two’, [1,1]}, {‘three’, [1,1]}, {‘world’, [1]}
最后，MR框架會均勻的將上面的鍵值對分發(fā)給不同的Reduce函數(shù)。
?
由于Hadoop的環(huán)境搭建相對困難，如果想體驗MR的編程方式，可以使用輕量級的MR框架Mincemeat[2]（需要注意，在自定義map和reduce函數(shù)中，如果要引用外部函數(shù)或?qū)ο?#xff0c;需要在函數(shù)定義中import，否則會報錯）或Octopy[3]。
?
Mincemeat代碼學(xué)習(xí)
Mincemeat的源代碼十分小，去掉注釋，只有不到350行（是不是有點震精！）。但是麻雀雖小五臟俱全，具有MR的基本特性：
l??并行計算
l??容錯
l??安全
?
Mincemeat運行原理
Mincemeat主要分兩塊：Server和Client。Server只有一個進(jìn)程，用于調(diào)度，確保安全和執(zhí)行容錯的邏輯。Client就是真正做計算的進(jìn)程（其他資料也稱為Worker進(jìn)程）。Mincemeat的網(wǎng)絡(luò)通訊（Server與Client之間）采用的是Python內(nèi)置的異步數(shù)據(jù)通訊框架asynchat（Python對本地Select和Poll的封裝）。異步框架相對于多線程有個優(yōu)點，不用處理線程間數(shù)據(jù)同步。這一點很重要，因為Mincemeat主要處理大數(shù)據(jù)并行計算，這樣可以省去不少數(shù)據(jù)同步的開銷。
Server啟動后會監(jiān)聽端口11235，等待處理數(shù)據(jù)的Client進(jìn)程。一旦有Client主動與Server連接，Server會與Client進(jìn)行一些交互，大致如下，
1.??????鑒權(quán)?根據(jù)預(yù)先設(shè)定的密碼，確保次client的“合法性”
2.??????傳遞方法?由于map，reduce和collect（可選）方法只在Server端定義，所以Server會將這些方法傳遞給Client。數(shù)據(jù)傳遞通過Python內(nèi)置的marshal模塊，對函數(shù)定義進(jìn)行編碼和解碼。
3.? ? ?Map階段?Server會傳遞部分原始數(shù)據(jù)給Client并等待其處理結(jié)果。這里Mincemeat引入了collect環(huán)節(jié)，可以理解為一個mini reduce過程，其輸入是一個局部的｛K, V-List｝，該數(shù)據(jù)從當(dāng)前Map處理的原始數(shù)據(jù)計算得到。
4.??????Reduce階段?server會將map階段的結(jié)果融合，然后將每一個｛K，V -list｝作為此階段的輸入
5.? ? ??結(jié)束?Server會將所有Reduce返回的結(jié)果合并，返回最后結(jié)果
?
Tips：Client可以在計算的任何時候（map階段或reduce階段均可以）加入計算，比如一開始只有1個Work計算，發(fā)現(xiàn)時間仍然很久，那么可以在其它計算機(jī)上啟動client連接server，一起參與計算。或者，如果本機(jī)有多核，也可以同時啟動多個進(jìn)程，最大限度的利用多核計算能力。
?
Mincemeat有Client容錯能力。重源代碼中，不難發(fā)現(xiàn)在map階段（reduce階段類似），Mincemeat會標(biāo)記每個Client處理的數(shù)據(jù)，標(biāo)記使用原始輸入的key。那么，Mincemeat就可以追蹤每一塊數(shù)據(jù)處理的狀態(tài)，比如某個服務(wù)器宕機(jī)了，那么它當(dāng)前處理的數(shù)據(jù)必然無法正確返回給Server，Server會在后面的某個時候?qū)⑼瑯拥臄?shù)據(jù)分給其他的Client。但是沒有Server容錯，所以一旦Server掛掉，整個計算無法完成。
?
Mincemeat的優(yōu)點和不足
個人能認(rèn)為，Mincemeat適合MR學(xué)習(xí)和科學(xué)研究。如果使用在商業(yè)環(huán)境下會有下面的不足：1）沒有Server容錯，不穩(wěn)定。2）計算結(jié)果放在內(nèi)存中，所以一旦輸出結(jié)果超過內(nèi)存限制，那么Mincemeat無能為力。3）缺少自動化部署和執(zhí)行client很局限，目前只能手動添加client，而且每個client的狀態(tài)也不能事實顯示。
雖然這樣，我覺得Mincemeat還是很優(yōu)秀的：1）比起同類的Octopy而言，效率要高很多；2）科研環(huán)境中，如果只做一兩次MR并行計算，跑跑數(shù)據(jù)，寫論文，整幾臺服務(wù)器，用Mincemeat跑跑成本還是很低的。3）簡單，門檻低，為后面使用Hadoop等商業(yè)的MR框架打下基礎(chǔ)。
?
MapReduce效率
MR框架會生成許多中間結(jié)果，這些中間結(jié)果的量級往往和輸入數(shù)據(jù)相當(dāng)，所以MR框架往往與分布式文件系統(tǒng)（DFS）是一對好基友。HDFS就是構(gòu)建在Hadoop框架之上的分布式文件系統(tǒng)。這里，想用一種直觀的方法討論一下MapReduce的計算效率。
假設(shè)需要處理的數(shù)據(jù)量D，MR產(chǎn)生的中間結(jié)果為σD，σ是一個系數(shù)。ωD為單機(jī)處理D所需要做的計算量。P為MR框架可以并行的個數(shù)，那么效率公式如下：
其中c是常量，MR的工作量等于每個處理器需要處理的實際工作量，在加上需要傳輸?shù)闹虚g結(jié)果。可以看到，MR的工作效率與處理器的數(shù)目（map+reduce的數(shù)目）沒有關(guān)系，只與
σ有關(guān)，也就是與中間數(shù)據(jù)的比例有關(guān)。在使用MR框架計算時，需要盡可能的減少σ，提高M(jìn)R的工作效率。
?
?
希望這篇文章對你理解MR有幫助！
?
?
參考資料
[1]???????MapReduce Simplified Data Processing on Large Clusters
[2]???????Mincemeat Project on Github
[3]???????Octopy: Easy MapReduce for Python
[4]???????mincemeat.py-最精簡的MapReduce引擎實現(xiàn)
[5]???????Coursera : Web Intelligence and Big Data
?
聲明：如有轉(zhuǎn)載本博文章，請注明出處。您的支持是我的動力！文章部分內(nèi)容來自互聯(lián)網(wǎng)，本人不負(fù)任何法律責(zé)任。 本文轉(zhuǎn)自bourneli博客園博客，原文鏈接：http://www.cnblogs.com/bourneli/archive/2013/04/20/3033325.html，如需轉(zhuǎn)載請自行聯(lián)系原作者總結(jié)
以上是生活随笔為你收集整理的【Coursera课程笔记】Web智能和大数据Week3_MapReduce的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
