Mapreduce實驗報告

1、Mapreduce實驗報告前言和簡介 MapReduce是Google提出的一種編程模型，在這個模型的支持下可以實現(xiàn)大規(guī)模并行化計算。在Mapreduce框架下一個計算機群通過統(tǒng)一的任務(wù)調(diào)度將一個巨型任務(wù)分成許多部分，分別解決然后合并得到最終結(jié)果。Mapreduce可以讓程序員以簡單的程序來解決實際問題，而隱藏了諸如分布、工作調(diào)度、容錯、機器間通信，使得大規(guī)模任務(wù)簡單而迅速地完成。一 Mapreduce的基本原理1. 核心思想?！癉ivide and Conquer”是Mapreduce的核心思想。面對一個規(guī)模龐大的問題，要處理是以TB計的數(shù)據(jù)，Mapreduce采用“輸入

2、”-“分解”-“解決”-“聚合”-“輸出結(jié)果”的基本過程。2. 基本原理Map和Reduce是兩個核心操作，用戶定義的map函數(shù)接收被切割過的原始的key/value對集并且計算出一個中間key/value對集。Mapreduce庫函數(shù)將所有的具有相同key值的value聚合在一起交給用戶定義的reduce函數(shù)處理。reduce函數(shù)將同一key值的所有value合并成得到輸出文件。在整個過程中，Mapreduce庫函數(shù)負(fù)責(zé)原始數(shù)據(jù)的切割，中間key/value對集的聚合，以及任務(wù)的調(diào)度，容錯、通信控制等基礎(chǔ)工作。而用戶定義的map和reduce函數(shù)則根據(jù)實際問題確定具體操作。二 框架的基本結(jié)構(gòu)

3、和執(zhí)行流程 基本結(jié)構(gòu) Mapreduce框架的主要程序分為三種即Master，Map和Reduce。1. Master：主要功能有兩個，任務(wù)的分割和任務(wù)的調(diào)度。Master把輸入文件切成許多個split，每個split文件一般為幾十M。Master同時還要調(diào)度任務(wù)監(jiān)視各個map worker和reduce worker的工作狀態(tài)，以做出相應(yīng)的安排。Master還要監(jiān)視各個子任務(wù)的完成進(jìn)展情況。Master用到的數(shù)據(jù)結(jié)構(gòu)Struct Split /文件切割后的信息struct MapSTATE /記錄各個map任務(wù)的情況。struct ReduceSTATER /各個reduce任務(wù)的情況。Ty

4、pe Map=0，Reduce=0 /記錄map任務(wù)和reduce任務(wù)的完成個數(shù)。MapWorkerSTATE ReduceWorkerSTATE /各個工作機器的忙閑狀態(tài)(string input) /輸入文件切割JobAssign（） /工作任務(wù)分配2. Map：主要功能是讀取經(jīng)過切割split文件形成一個map任務(wù)，分析map任務(wù)，得到中間結(jié)構(gòu)并且將同一類型的中間文件存放在同一個區(qū)域內(nèi)等待特定的reduce程序讀取。3. Reduce：不同的Reduce讀取各個Map得到的特定的中間文件，將所有相同的中間文件整合成最后的輸出文件。任務(wù)執(zhí)行基本流程基本流程圖見下一頁首先輸入收據(jù)文件被Map

5、reduce庫函數(shù)分割成M個split集。用戶定義的程序被拷貝到機群中，其中一個是master，其它的都是worker。M個map任務(wù)和R個reduce任務(wù)將被分配。Master負(fù)責(zé)調(diào)度任務(wù)和過程監(jiān)視。隨時檢測worker的工作狀況，任務(wù)的完成進(jìn)度。Map worker每完成一個子任務(wù)向master報告。一個被分配了map任務(wù)的worker讀取一個split集，該worker從這個split集中分析出key/value對，然后有map函數(shù)來處理這些key/value對并得到中間key/value對，這些key/value對將最終存放在map worker的本地硬盤上。每完成一個任務(wù)報告mast

6、er。中間key/value對被存在本地硬盤的R個不同的區(qū)域中，由于可能的key值很可能不止R個，故必須利用一個分割函數(shù)來劃分中間文件，常用的是散列的方法（如hash(key) mod R）。保證key值相同的key/value對被存放同一區(qū)域中，并且將位置報告給master。如果同一個key的中間文件多而小可以考慮用cmobine函數(shù)在本地進(jìn)行合并。當(dāng)所有的split都被分析完成之后，reduce worker開始工作，每個reduce根據(jù)master的安排和信息指示利用機群的內(nèi)部文件系統(tǒng)讀取map worker本地磁盤中特定位置的中間文件。Reduce開始聚合中間文件，得到自己的輸出文件。

7、在聚合的過程中由于有很多key值，一般將用到排序。Reduce worker完成自己的工作后向master報告。輸入文件 控制Split0 split1 split2 . split n MasterMapWorkerrMapWorkerrMap Worker 分析key/value對 分區(qū)寫入磁盤 讀取ReduceWorkerReduceWorkerrReduceWorkerr輸出文件輸出文件輸出文件 *單向箭頭表示控制，雙向箭頭表示控制和反饋*某些操作中Mapworker硬盤上的key/value在被Reducerworker讀取之前可以有combine操作，將相同key的value合并以

8、減少讀取次數(shù)*分散的輸出文件也可以合并成一個輸出文件而對于有些操作如求最大值則必須合并輸出文件才能得到最終結(jié)果三 一些操作的偽碼1. 查找查找文件存在機群的存儲機器上，可以查找其中若干個單詞的出現(xiàn)位置。Master 根據(jù)文件的大小將文件切成合適的分?jǐn)?shù)，切割信息（如起始位置，終止位置，切片長度等）存儲在master上。 Map根據(jù)master 的切割信息讀取各小規(guī)模文件，分析文件內(nèi)容，每遇到一個要查找的單詞形成一個key/value，這里的key是待查找的單詞，value是單詞的位置，周期性地更新中間文件。Reduce讀取每一個map worker同一個區(qū)域中的所有中間文件將所有具有相同key值

9、也就是同一個單詞的文件合并，將所有的位置匯總成一個輸出文件。Map(String key,String value)  /key:文檔的名字 /value:文檔的內(nèi)容String word；Struct position；While（?。?/讀取整個文件 word=WordRead（key）； /讀取文件中的單詞position=PositionRead（key）；/單詞位置讀取 EmitIntermediate，position）/形成中間文件Reduce(String key,String value)/key:中間文件名即待查單詞 /value:單詞位置列表

10、For every key readed Emit（value ，position（key）；/每讀到一個單詞將其位置寫入其位置列表2. 詞頻統(tǒng)計被統(tǒng)計的的文件被切割后，map讀取切割文件，統(tǒng)計該文件中的單詞數(shù)目，形成中間文件，reduce讀取相同單詞的中間文件，合并得到單詞總數(shù)。由于單詞很多，而reduce worker有限，故應(yīng)在map中用散列的方法將不同單詞的中間文件映射到不同的區(qū)域，同一單詞的中間文件必須保證存放在同一區(qū)域。Map（string key，string value）/Key：文件名/value：文件內(nèi)容String Word；While（?。￤ord = WordRead

11、（key）；EmitIntermediate，1）；形成中間文件Reduce（string key，string value）/Key：文件名及單詞名/value：單詞計數(shù)列表Int Result=0；String word；While（！）Word = WordRead（key）；If （Word in vlaue）Result+； /單詞累加（result）； /將結(jié)果寫入文件3. 反向鏈接輸入文件包括所有的URL及其鏈接信息?？梢钥紤]將同一個源URL的信息切割成一個文件。Map讀取切割文件，將每個被鏈接的URL生成中間文件，key是被鏈接的URL，value是源URL。Reduce讀取所

12、有中間文件同一被鏈接URL的中間文件合并，得到反鏈接表。Map（string key，string value）/Key：文件名/value：文件內(nèi)容String URLlinked; /被鏈接URLWhile（?。︰RLRead（URLlinked）；EmitIntermediate）；形成中間文件Reduce（string key，string value）/Key：文件名/value：反向鏈接列表For every key readed Emit（value，sourceURL(key)）；/每讀到一個中間文件將其源URL存放到源URL列表4. 倒排索引根反向鏈接向類似，搜索輸入文件中的

13、某些單詞，將所有包含特定單詞的文件的ID形成一個索引列表。map函數(shù)分析每個文檔,然后產(chǎn)生一個(詞,文檔號)對的序列.reduce函數(shù)接受一個給定詞的所有對,排序相應(yīng)的文檔ID,并且產(chǎn)生一個(詞,文檔ID列表)對.所有的輸出對集形成一個的倒排索引。Map（string key，string value）/Key：文件名/value：文件內(nèi)容String Word；While（?。￤ord = WordRead（key）；EmitIntermediate，F(xiàn)ileID）；形成中間文件Reduce（string key，string value）/Key：文件名/value：源文件列表For ev

14、ery key readed Emit（value，fileID(key)）；/每讀到一個中間文件將其源文件的ID存放到源文件列表四 總結(jié)和評價 Mapreduce的原理很簡單，通過對任務(wù)劃分和分而治之的方法，使得大型問題得到迅速地解決。Mapreduce的關(guān)鍵貢獻(xiàn)是各種實際問題抽象的解決過程抽象成map（映射）和reduce（化簡）兩個主要過程，著使得程序員在解決實際問題事只要分析什么map過程什么是reduce過程，它們的key/value對分別是什么。而不用去關(guān)心mapreduce庫函數(shù)做的復(fù)雜的底層工作。Mapreduce 是典型的以空間的消耗換取時間的節(jié)省的例子。為解決一個問題可能要動用很多臺機器。在機器間的信息傳遞和信息延遲都會影響問題解決的速度和效果。這里有幾個關(guān)鍵：一是機群內(nèi)部使用的文件存儲系統(tǒng)要能高效地工作，google 使用的分布式文件系統(tǒng)GFS能達(dá)到這個要求。然后是機群中的網(wǎng)絡(luò)通信，網(wǎng)絡(luò)帶寬和網(wǎng)絡(luò)通信質(zhì)量決定的信息傳遞的延遲，當(dāng)大量的文件被通過網(wǎng)絡(luò)遠(yuǎn)程讀取時，網(wǎng)絡(luò)可能會成為問題解決速度的瓶頸。另外，一個高效的調(diào)度和容錯機制是非常關(guān)鍵的。Master必須能及時地了解全局的運行情況并采取相應(yīng)的措施。采取什么的方式和策略進(jìn)行控制和反饋，將很大程度上影響任務(wù)完成的速度和質(zhì)量。在分布式