【Coursera課程筆記】Web智能和大資料Week3_MapReduce

本文目的

到今天為止，Coursera上的課程Web Intelligence and Big Data[5]已經上到Week 3（從0開始計數，實際上是4周）。前幾周講了一些機器學習的算法，如LHS，PageRank，樸素貝葉斯分類器等。但是光有這些算法還不夠，特别是在目前這種海量資料（Big Data）盛行的年代。是以，Week 3就聊到了一種通用的大資料處了解決方法 ——Map Reduce(後面簡稱MR)。此方法最初來自Google的一篇論文[1]，現在用來指代一種程式設計方式，主要作用與大規模資料集（通常在1T以上）的并行計算（很多算法都可以用MR方式實作）。本周課程主要内容介紹了MR的程式設計模型（結合Mincemeat[2]和Octopy[3]），運作原理和計算效率。在這裡簡單記錄本周内容，作為備忘，對後面的工作會有幫助。

MapReduce程式設計方式

MR是一種程式設計模式。基于這種程式設計模式，可以有多種實作，鼎鼎大名的Hadoop就是其中之一。在MR的世界中，你隻需要實作兩個方法：map和reduce，剩下的所有事情交給MR架構，比如消息處理，中間資料存儲，資料合并，容錯等。

上千個廉價PC機并行處理，難免會出現伺服器故障，至少出現一台伺服器出錯的機率為1-Pk，也就意味着随着機器數量K的增加，機率會趨近于1

Map函數的輸入可以是任意序列，但輸出必須是一個鍵值對{K,V}，這一點很重要，因為MR架構會根據K，将不同K對應的V合并成一個清單，得到{K，V–List}，然後将其作為reduce函數的輸入，reduce的輸出可以是任意資料。舉個例子，有下列map和輸出：

         map1 –> {‘one’,1}, {‘two’,1}, {‘three’,1}

         map2­­ –> {‘two’,1}, {‘world,1}

         map3­­ –>{‘three,1}

那麼經過合并後，得到中結果：

        {‘one’, [1]}, {‘two’, [1,1]}, {‘three’, [1,1]}, {‘world’, [1]}

最後，MR架構會均勻的将上面的鍵值對分發給不同的Reduce函數。

由于Hadoop的環境搭建相對困難，如果想體驗MR的程式設計方式，可以使用輕量級的MR架構Mincemeat[2]（需要注意，在自定義map和reduce函數中，如果要引用外部函數或對象，需要在函數定義中import，否則會報錯）或Octopy[3]。

Mincemeat代碼學習

Mincemeat的源代碼十分小，去掉注釋，隻有不到350行（是不是有點震精！）。但是麻雀雖小五髒俱全，具有MR的基本特性：

l  并行計算

l  容錯

l  安全

Mincemeat運作原理

Mincemeat主要分兩塊：Server和Client。Server隻有一個程序，用于排程，確定安全和執行容錯的邏輯。Client就是真正做計算的程序（其他資料也稱為Worker程序）。Mincemeat的網絡通訊（Server與Client之間）采用的是Python内置的異步資料通訊架構asynchat（Python對本地Select和Poll的封裝）。異步架構相對于多線程有個優點，不用處理線程間資料同步。這一點很重要，因為Mincemeat主要處理大資料并行計算，這樣可以省去不少資料同步的開銷。

Server啟動後會監聽端口11235，等待處理資料的Client程序。一旦有Client主動與Server連接配接，Server會與Client進行一些互動，大緻如下，

1.      鑒權 根據預先設定的密碼，確定次client的“合法性”

2.      傳遞方法 由于map，reduce和collect（可選）方法隻在Server端定義，是以Server會将這些方法傳遞給Client。資料傳遞通過Python内置的marshal子產品，對函數定義進行編碼和解碼。

3.     Map階段 Server會傳遞部分原始資料給Client并等待其處理結果。這裡Mincemeat引入了collect環節，可以了解為一個mini reduce過程，其輸入是一個局部的｛K, V-List｝，該資料從目前Map處理的原始資料計算得到。

4.      Reduce階段 server會将map階段的結果融合，然後将每一個｛K，V -list｝作為此階段的輸入

5.      結束 Server會将所有Reduce傳回的結果合并，傳回最後結果

Tips：Client可以在計算的任何時候（map階段或reduce階段均可以）加入計算，比如一開始隻有1個Work計算，發現時間仍然很久，那麼可以在其它計算機上啟動client連接配接server，一起參與計算。或者，如果本機有多核，也可以同時啟動多個程序，最大限度的利用多核計算能力。

Mincemeat有Client容錯能力。重源代碼中，不難發現在map階段（reduce階段類似），Mincemeat會标記每個Client處理的資料，标記使用原始輸入的key。那麼，Mincemeat就可以追蹤每一塊資料處理的狀态，比如某個伺服器當機了，那麼它目前處理的資料必然無法正确傳回給Server，Server會在後面的某個時候将同樣的資料分給其他的Client。但是沒有Server容錯，是以一旦Server挂掉，整個計算無法完成。

Mincemeat的優點和不足

個人能認為，Mincemeat适合MR學習和科學研究。如果使用在商業環境下會有下面的不足：1）沒有Server容錯，不穩定。2）計算結果放在記憶體中，是以一旦輸出結果超過記憶體限制，那麼Mincemeat無能為力。3）缺少自動化部署和執行client很局限，目前隻能手動添加client，而且每個client的狀态也不能事實顯示。

雖然這樣，我覺得Mincemeat還是很優秀的：1）比起同類的Octopy而言，效率要高很多；2）科研環境中，如果隻做一兩次MR并行計算，跑跑資料，寫論文，整幾台伺服器，用Mincemeat跑跑成本還是很低的。3）簡單，門檻低，為後面使用Hadoop等商業的MR架構打下基礎。

MapReduce效率

MR架構會生成許多中間結果，這些中間結果的量級往往和輸入資料相當，是以MR架構往往與分布式檔案系統（DFS）是一對好基友。HDFS就是建構在Hadoop架構之上的分布式檔案系統。這裡，想用一種直覺的方法讨論一下MapReduce的計算效率。

假設需要處理的資料量D，MR産生的中間結果為σD，σ是一個系數。ωD為單機處理D所需要做的計算量。P為MR架構可以并行的個數，那麼效率公式如下：

其中c是常量，MR的工作量等于每個處理器需要處理的實際工作量，在加上需要傳輸的中間結果。可以看到，MR的工作效率與處理器的數目（map+reduce的數目）沒有關系，隻與

σ有關，也就是與中間資料的比例有關。在使用MR架構計算時，需要盡可能的減少σ，提高MR的工作效率。

希望這篇文章對你了解MR有幫助！

參考資料

<b>聲明：如有轉載本博文章，請注明出處。您的支援是我的動力！文章部分内容來自網際網路，本人不負任何法律責任。</b>

本文轉自bourneli部落格園部落格，原文連結：http://www.cnblogs.com/bourneli/archive/2013/04/20/3033325.html，如需轉載請自行聯系原作者