云計算及應(yīng)用課件：分布式數(shù)據(jù)處理MapReduce

分布式數(shù)據(jù)處理MapReduce

產(chǎn)生背景

編程模型實現(xiàn)機(jī)制案例分析MapReduce

一種處理海量數(shù)據(jù)的并行編程模式，用于大規(guī)模數(shù)據(jù)集（通常大于1TB）的并行運(yùn)算。

“Map（映射）”、“Reduce（化簡）”的概念和主要思想，都是從函數(shù)式編程語言和矢量編程語言借鑒適合非結(jié)構(gòu)化和結(jié)構(gòu)化的海量數(shù)據(jù)的搜索、挖掘、分析與機(jī)器智能學(xué)習(xí)等

Google擁有海量數(shù)據(jù)，并且需要快速處理Google全球Web數(shù)據(jù)郵件數(shù)據(jù)地圖數(shù)據(jù)衛(wèi)星照片……

計算問題簡單，但求解困難

待處理數(shù)據(jù)量巨大（PB級），只有分布在成百上千個節(jié)點上并行計算才能在可接受的時間內(nèi)完成

如何進(jìn)行并行分布式計算？

如何分發(fā)待處理數(shù)據(jù)？

如何處理分布式計算中的錯誤？簡單的問題，計算并不簡單！JefferyDean設(shè)計一個新的抽象模型，封裝并行處理、容錯處理、本地化計算、負(fù)載均衡的細(xì)節(jié)，還提供了一個簡單而強(qiáng)大的接口這就是MapReduceGoogleMapReduce架構(gòu)設(shè)計師JeffreyDean分布式數(shù)據(jù)處理MapReduce

產(chǎn)生背景

編程模型實現(xiàn)機(jī)制案例分析MapReduce運(yùn)行模型

Map函數(shù)——對一部分原始數(shù)據(jù)進(jìn)行指定的操作。每個Map操作都針對不同的原始數(shù)據(jù)，因此Map與Map之間是互相獨(dú)立的，這使得它們可以充分并行化Reduce操作——對每個Map所產(chǎn)生的一部分中間結(jié)果進(jìn)行合并操作，每個Reduce所處理的Map中間結(jié)果是互不交叉的，所有Reduce產(chǎn)生的最終結(jié)果經(jīng)過簡單連接就形成了完整的結(jié)果集Map:(in_key,in_value)

{(keyj,valuej)|j=1…k}Reduce:(key,[value1,…,valuem])(key,final_value)

開發(fā)者需編寫兩個主要函數(shù)

Map輸入?yún)?shù)：in_key和in_value，它指明了Map需要處理的原始數(shù)據(jù)Map輸出結(jié)果：一組<key,value>對，這是經(jīng)過Map操作后所產(chǎn)生的中間結(jié)果

Map:(in_key,in_value)

{(keyj,valuej)|j=1…k}Reduce:(key,[value1,…,valuem])(key,final_value)

開發(fā)者需編寫兩個主要函數(shù)

Reduce輸入?yún)?shù)：（key,[value1,…,valuem]）Reduce工作：對這些對應(yīng)相同key的value值進(jìn)行歸并處理Reduce輸出結(jié)果：（key,final_value），所有Reduce的結(jié)果并在一起就是最終結(jié)果Map的輸入?yún)?shù)指明了需要處理哪部分?jǐn)?shù)據(jù)，以“<在文本中的起始位置，需要處理的數(shù)據(jù)長度>”表示，經(jīng)過Map處理，形成一批中間結(jié)果“<單詞，出現(xiàn)次數(shù)>”。而Reduce函數(shù)處理中間結(jié)果，將相同單詞出現(xiàn)的次數(shù)進(jìn)行累加，得到每個單詞總的出現(xiàn)次數(shù)

怎么用MapReduce計算一個大型文本文件中各單詞出現(xiàn)次數(shù)？分布式數(shù)據(jù)處理MapReduce

產(chǎn)生背景

編程模型實現(xiàn)機(jī)制案例分析MapReduce操作執(zhí)行流程圖

操作過程（1）輸入文件分成M塊，每塊大概16M～64MB（可以通過參數(shù)決定），接著在集群的機(jī)器上執(zhí)行分派處理程序

（2）M個Map任務(wù)和R個Reduce任務(wù)需要分派，Master選擇空閑Worker來分配這些Map或Reduce任務(wù)（3）Worker讀取并處理相關(guān)輸入塊，Map函數(shù)產(chǎn)生的中間結(jié)果<key,value>對暫時緩沖到內(nèi)存（4）中間結(jié)果定時寫到本地硬盤，分區(qū)函數(shù)將其分成R個區(qū)。中間結(jié)果在本地硬盤的位置信息將被發(fā)送回Master，然后Master負(fù)責(zé)把這些位置信息傳送給ReduceWorker操作過程（5）當(dāng)Master通知執(zhí)行Reduce的Worker關(guān)于中間<key,value>對的位置時，它調(diào)用遠(yuǎn)程過程，從MapWorker的本地硬盤上讀取緩沖的中間數(shù)據(jù)。當(dāng)ReduceWorker讀到所有的中間數(shù)據(jù)，它就使用中間key進(jìn)行排序，這樣可使相同key的值都在一起（6）ReduceWorker根據(jù)每一個唯一中間key來遍歷所有的排序后的中間數(shù)據(jù)，并且把key和相關(guān)的中間結(jié)果值集合傳遞給用戶定義的Reduce函數(shù)。Reduce函數(shù)的結(jié)果寫到一個最終的輸出文件

（7）當(dāng)所有的Map任務(wù)和Reduce任務(wù)都完成的時候，Master激活用戶程序。此時MapReduce返回用戶程序的調(diào)用點MapReduce容錯

Master周期性地給Worker發(fā)送ping命令，若沒有應(yīng)答，則認(rèn)為Worker失效，終止其任務(wù)調(diào)度，把該任務(wù)調(diào)度到其他Worker上重新執(zhí)行Master會周期性地設(shè)置檢查點（checkpoint），并導(dǎo)出Master的數(shù)據(jù)。一旦某個任務(wù)失效，系統(tǒng)就從最近的一個檢查點恢復(fù)并重新執(zhí)行MapReduce容錯分布式數(shù)據(jù)處理MapReduce

產(chǎn)生背景

編程模型實現(xiàn)機(jī)制案例分析假設(shè)有一批海量的數(shù)據(jù)，每個數(shù)據(jù)都是由26個字母組成的字符串，原始的數(shù)據(jù)集合是完全無序的，怎樣通過MapReduce完成排序工作，使其有序（字典序）呢？排序通常用于衡量分布式數(shù)據(jù)處理框架的數(shù)據(jù)處理能力

對原始的數(shù)據(jù)進(jìn)行分割（Split），得到N個不同的數(shù)據(jù)分塊每一個數(shù)據(jù)分塊都啟動一個Map進(jìn)行處理。采用桶排序的方法，每個