Mapreduce實(shí)驗(yàn)報(bào)告

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

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

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

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

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

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

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

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

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

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

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

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

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