MapReduce海量數(shù)據(jù)并行處理ch.03

Ch.3.GoogleMapReduce基本構(gòu)架南京大學(xué)計算機科學(xué)與技術(shù)系主講人：黃宜華2011年春季學(xué)期MapReduce海量數(shù)據(jù)并行處理鳴謝：本課程得到Google公司(北京）中國大學(xué)合作部精品課程計劃資助Ch.3.

GoogleMapReduce基本構(gòu)架1.MapReduce的基本模型和處理思想2.GoogleMapReduce的基本工作原理3.分布式文件系統(tǒng)GFS的基本工作原理4.分布式結(jié)構(gòu)化數(shù)據(jù)表BigTable三個層面上的基本構(gòu)思如何對付大數(shù)據(jù)處理：分而治之

對相互間不具有計算依賴關(guān)系的大數(shù)據(jù)，實現(xiàn)并行最自然的辦法就是采取分而治之的策略上升到抽象模型：Mapper與Reducer

MPI等并行計算方法缺少高層并行編程模型，為了克服這一缺陷，MapReduce借鑒了Lisp函數(shù)式語言中的思想，用Map和Reduce兩個函數(shù)提供了高層的并行編程抽象模型上升到構(gòu)架：統(tǒng)一構(gòu)架，為程序員隱藏系統(tǒng)層細節(jié)

MPI等并行計算方法缺少統(tǒng)一的計算框架支持，程序員需要考慮數(shù)據(jù)存儲、劃分、分發(fā)、結(jié)果收集、錯誤恢復(fù)等諸多細節(jié)；為此，MapReduce設(shè)計并提供了統(tǒng)一的計算框架，為程序員隱藏了絕大多數(shù)系統(tǒng)層面的處理細節(jié)1.MapReduce的基本模型和處理思想大數(shù)據(jù)分而治之

MapReduce的基本模型和處理思想大數(shù)據(jù)計算任務(wù)子任務(wù)子任務(wù)子任務(wù)子任務(wù)……任務(wù)劃分計算結(jié)果結(jié)果合并建立Map和Reduce抽象模型典型的流式大數(shù)據(jù)問題的特征大量數(shù)據(jù)記錄/元素進行重復(fù)處理對每個數(shù)據(jù)記錄/元素作感興趣的處理、獲取感興趣的中間結(jié)果信息排序和整理中間結(jié)果以利后續(xù)處理收集整理中間結(jié)果產(chǎn)生最終結(jié)果輸出MapReduce的基本模型與處理思想MapReduce關(guān)鍵思想：為大數(shù)據(jù)處理過程中的兩個主要處理階段

提煉為一種抽象的操作機制建立Map和Reduce抽象模型借鑒函數(shù)式程序設(shè)計語言Lisp中的思想，定義了Map和Reduce兩個抽象的操作函數(shù)：map:(k1;v1)

[(k2;v2)]reduce:

(k2;[v2])

[(k3;v3)]特點：描述了對一組數(shù)據(jù)處理的兩個階段的抽象操作僅僅描述了需要做什么，不需要關(guān)注怎么做MapReduce的基本模型與處理思想上升到構(gòu)架--自動并行化并隱藏低層細節(jié)海量數(shù)據(jù)存儲……數(shù)據(jù)劃分MapMapMapMap初始kv鍵值對初始kv鍵值對初始kv鍵值對初始kv鍵值對中間結(jié)果(k1,val)(k2,val)(k3,val)(k1,val)(k3,val)(k2,val)(k3,val)(k1,val)(k2,val)(k3,val)Barrier：AggregationandShuffleReduceReduceReduce(k1,values)(k2,values)(k3,values)計算結(jié)果(K1,val)(K2,val)(K3,val)MapReduce的基本模型與處理思想Barrier(good,1)(good,1)(good,2)(good,1)PartitionerPartitionerPartitionerPartitioner(is,1)(is,1)(is,1)(has,1)(weather,1)(weather,1)(weather,1)(the,1)(today,1)(today,1)上升到構(gòu)架--自動并行化并隱藏低層細節(jié)海量數(shù)據(jù)存儲計算結(jié)果……數(shù)據(jù)劃分Map初始kv鍵值對初始kv鍵值對初始kv鍵值對初始kv鍵值對MapMapMap中間結(jié)果(the,1)(weather,1)(is,1)(good,1)CombinerCombinerCombinerCombiner(the,1)(weather,1)(is,1)(good,1)(today,1)(is,1)(good,1)(good,1)(weather,1)(is,1)(good,1)(today,1)(has,1)(good,1)(weather,1)(today,1)(is,1)(good,1)(good,2)(weather,1)(is,1)(today,1)(has,1)(good,1)(weather,1)ReduceReduceReduce(good,5)(is,3)(has,1)(weather,3)(the,1)(today,2)Combiner和PartitionerMapReduce的基本模型與處理思想GoogleMapReduce并行處理的基本過程

2.GoogleMapReduce的基本工作原理CitefromDeanandGhemawat(OSDI2004)1.有一個待處理的大數(shù)據(jù)，被劃分為大小相同的數(shù)據(jù)塊(如64MB),及與此相應(yīng)的用戶作業(yè)程序2.系統(tǒng)中有一個負責(zé)調(diào)度的主節(jié)點(Master),以及數(shù)據(jù)Map和Reduce工作節(jié)點(Worker)GoogleMapReduce并行處理的基本過程

GoogleMapReduce的基本工作原理CitefromDeanandGhemawat(OSDI2004)3.用戶作業(yè)程序提交給主節(jié)點4.主節(jié)點為作業(yè)程序?qū)ふ液团鋫淇捎玫腗ap節(jié)點，并將程序傳送給map節(jié)點5.主節(jié)點也為作業(yè)程序?qū)ふ液团鋫淇捎玫腞educe節(jié)點，并將程序傳送給Reduce節(jié)點GoogleMapReduce并行處理的基本過程

GoogleMapReduce的基本工作原理CitefromDeanandGhemawat(OSDI2004)6.主節(jié)點啟動每個Map節(jié)點執(zhí)行程序，每個map節(jié)點盡可能讀取本地或本機架的數(shù)據(jù)進行計算7.每個Map節(jié)點處理讀取的數(shù)據(jù)塊,并做一些數(shù)據(jù)整理工作(combining,sorting等)并將中間結(jié)果存放在本地；同時通知主節(jié)點計算任務(wù)完成并告知中間結(jié)果數(shù)據(jù)存儲位置GoogleMapReduce并行處理的基本過程

GoogleMapReduce的基本工作原理CitefromDeanandGhemawat(OSDI2004)8.主節(jié)點等所有Map節(jié)點計算完成后，開始啟動Reduce節(jié)點運行；Reduce節(jié)點從主節(jié)點所掌握的中間結(jié)果數(shù)據(jù)位置信息，遠程讀取這些數(shù)據(jù)9.Reduce節(jié)點計算結(jié)果匯總輸出到一個結(jié)果文件即獲得整個處理結(jié)果GoogleMapReduce并行處理的基本過程

GoogleMapReduce的基本工作原理CitefromDeanandGhemawat(OSDI2004)完整計算過程GoogleMapReduce的基本工作原理失效處理主節(jié)點失效主節(jié)點中會周期性地設(shè)置檢查點(checkpoint)，檢查整個計算作業(yè)的執(zhí)行情況，一旦某個任務(wù)失效，可以從最近有效的檢查點開始重新執(zhí)行，避免從頭開始計算的時間浪費。工作節(jié)點失效工作節(jié)點失效是很普遍發(fā)生的，主節(jié)點會周期性地給工作節(jié)點發(fā)送檢測命令，如果工作節(jié)點沒有回應(yīng)，這認為該工作節(jié)點失效，主節(jié)點將終止該工作節(jié)點的任務(wù)并把失效的任務(wù)重新調(diào)度到其它工作節(jié)點上重新執(zhí)行

GoogleMapReduce的基本工作原理帶寬優(yōu)化問題

大量的鍵值對數(shù)據(jù)在傳送給Reduce節(jié)點時會引起較大的通信帶寬開銷。解決方案每個Map節(jié)點處理完成的中間鍵值隊將由combiner做一個合并壓縮，即把那些鍵名相同的鍵值對歸并為一個鍵名下的一組數(shù)值。(good,1)(weather,1)(is,1)(good,1)(good,2)(weather,1)(is,1)combiner

GoogleMapReduce的基本工作原理計算優(yōu)化問題Reduce節(jié)點必須要等到所有Map節(jié)點計算計算才能開始執(zhí)行，因此，如果有一個計算量大、或者由于某個問題導(dǎo)致很慢結(jié)束的Map節(jié)點，則會成為嚴重的“拖后腿者”。解決方案把一個Map計算任務(wù)讓多個Map節(jié)點同時做，取最快完成者的計算結(jié)果。根據(jù)Google的測試，使用了這個冗余Map節(jié)點計算方法以后，計算任務(wù)性能提高40%多！

GoogleMapReduce的基本工作原理用數(shù)據(jù)分區(qū)解決數(shù)據(jù)相關(guān)性問題問題

一個Reduce節(jié)點上的計算數(shù)據(jù)可能會來自多個Map節(jié)點，因此，為了在進入Reduce節(jié)點計算之前，需要把屬于一個Reduce節(jié)點的數(shù)據(jù)歸并到一起。解決方案在Map階段進行了Combining以后，可以根據(jù)一定的策略對Map輸出的中間結(jié)果進行分區(qū)(partitioning)，這樣既可解決以上數(shù)據(jù)相關(guān)性問題避免Reduce計算過程中的數(shù)據(jù)通信。例如：有一個巨大的數(shù)組,其最終結(jié)果需要排序,每個Map節(jié)點數(shù)據(jù)處理好后,為了避免在每個Reduce節(jié)點本地排序完成后還需要進行全局排序,我們可以使用一個分區(qū)策略如:(d%R),d為數(shù)據(jù)大小，R為Reduce節(jié)點的個數(shù)，則可根據(jù)數(shù)據(jù)的大小將其劃分到指定數(shù)據(jù)范圍的Reduce節(jié)點上,每個Reduce將本地數(shù)據(jù)拍好序后即為最終結(jié)果基本問題海量數(shù)據(jù)怎么存儲？數(shù)據(jù)存儲可靠性怎么解決？當前主流的分布文件系統(tǒng)有：RedHat的GFSIBM的GPFSSun的Lustre等主要用于對硬件設(shè)施要求很高的高性能計算或大型數(shù)據(jù)中心；價格昂貴且缺少完整的數(shù)據(jù)存儲容錯解決方案如Lustre只對元數(shù)據(jù)管理提供容錯處理，但對于具體的分布存儲節(jié)點，可靠性完全依賴于這些分布節(jié)點采用RAID或存儲區(qū)域網(wǎng)(SAN)技術(shù)提供容錯，一旦分布節(jié)點失效，數(shù)據(jù)就無法恢復(fù)。3.MapReduce分布式文件系統(tǒng)GFS的工作原理GoogleGFS的基本設(shè)計原則GoogleGFS是一個基于分布式集群的大型分布式文件系統(tǒng)，為MapReduce計算框架提供低層數(shù)據(jù)存儲和數(shù)據(jù)可靠性支撐；GFS是一個構(gòu)建在分布節(jié)點本地文件系統(tǒng)之上的一個邏輯上文件系統(tǒng)，它將數(shù)據(jù)存儲在物理上分布的每個節(jié)點上，但通過GFS將整個數(shù)據(jù)形成一個邏輯上整體的文件。MapReduce分布式文件系統(tǒng)GFS的工作原理……GoogleGFSGoogleMapReduceMapReduceApplicationsGoogleGFS的基本設(shè)計原則廉價本地磁盤分布存儲

各節(jié)點本地分布式存儲數(shù)據(jù)，優(yōu)點是不需要采用價格較貴的集中式磁盤陣列，容量可隨節(jié)點數(shù)增加自動增加多數(shù)據(jù)自動備份解決可靠性

采用廉價的普通磁盤，把磁盤數(shù)據(jù)出錯視為常態(tài)，用自動多數(shù)據(jù)備份存儲解決數(shù)據(jù)存儲可靠性問題為上層的MapReduce計算框架提供支撐GFS作為向上層MapReduce執(zhí)行框架的底層數(shù)據(jù)存儲支撐，負責(zé)處理所有的數(shù)據(jù)自動存儲和容錯處理，因而上層框架不需要考慮低層的數(shù)據(jù)存儲和數(shù)據(jù)容錯問題MapReduce分布式文件系統(tǒng)GFS的工作原理GoogleGFS的基本構(gòu)架和工作原理

MapReduce分布式文件系統(tǒng)GFS的工作原理CitefromGhemawatetal.(SOSP2003)GFSMasterChunkServerGoogleGFS的基本構(gòu)架和工作原理GFSMasterMaster上保存了GFS文件系統(tǒng)的三種元數(shù)據(jù)

：命名空間(NameSpace),即整個分布式文件系統(tǒng)的目錄結(jié)構(gòu)

Chunk與文件名的映射表Chunk副本的位置信息，每一個Chunk默認有3個副本MapReduce分布式文件系統(tǒng)GFS的工作原理GFSMaster前兩種元數(shù)據(jù)可通過操作日志提供容錯處理能力；第3個元數(shù)據(jù)直接保存在ChunkServer上，Master啟動或ChunkServer注冊時自動完成在ChunkServer上元數(shù)據(jù)的生成；因此，當Master失效時，只要ChunkServer數(shù)據(jù)保存完好，可迅速恢復(fù)Master上的元數(shù)據(jù)。GoogleGFS的基本構(gòu)架和工作原理GFSChunkServer即用來保存大量實際數(shù)據(jù)的數(shù)據(jù)服務(wù)器。GFS中每個數(shù)據(jù)塊劃分缺省為64MB每個數(shù)據(jù)塊會分別在3個(缺省情況下)不同的地方復(fù)制副本；對每一個數(shù)據(jù)塊，僅當3個副本都更新成功時，才認為數(shù)據(jù)保存成功。MapReduce分布式文件系統(tǒng)GFS的工作原理當某個副本失效時，Master會自動將正確的副本數(shù)據(jù)進行復(fù)制以保證足夠的副本數(shù)GFS上存儲的數(shù)據(jù)塊副本，在物理上以一個本地的Linux操作系統(tǒng)的文件形式存儲，每一個數(shù)據(jù)塊再劃分為64KB的子塊，每個子快有一個32位的校驗和，讀數(shù)據(jù)時會檢查校驗和以保證使用為失效的數(shù)據(jù)。ChunkServerGoogleGFS的基本構(gòu)架和工作原理數(shù)據(jù)訪問工作過程MapReduce分布式文件系統(tǒng)GFS的工作原理1.在程序運行前，數(shù)據(jù)已經(jīng)存儲在GFS文件系統(tǒng)中；程序?qū)嵭袝r應(yīng)用程序會告訴GFSServer所要訪問的文件名或者數(shù)據(jù)塊索引是什么GoogleGFS的基本構(gòu)架和工作原理數(shù)據(jù)訪問工作過程MapReduce分布式文件系統(tǒng)GFS的工作原理2.GFSServer根據(jù)文件名會數(shù)據(jù)塊索引在其文件目錄空間中查找和定位該文件或數(shù)據(jù)塊，并找數(shù)據(jù)塊在具體哪些ChunkServer上；將這些位置信息回送給應(yīng)用程序GoogleGFS的基本構(gòu)架和工作原理數(shù)據(jù)訪問工作過程MapReduce分布式文件系統(tǒng)GFS的工作原理3.應(yīng)用程序根據(jù)GFSServer返回的具體Chunk數(shù)據(jù)塊位置信息，直接訪問相應(yīng)的ChunkServerGoogleGFS的基本構(gòu)架和工作原理數(shù)據(jù)訪問工作過程MapReduce分布式文件系統(tǒng)GFS的工作原理4.應(yīng)用程序根據(jù)GFSServer返回的具體Chunk數(shù)據(jù)塊位置信息直接讀取指定位置的數(shù)據(jù)進行計算處理GoogleGFS的基本構(gòu)架和工作原理數(shù)據(jù)訪問工作過程MapReduce分布式文件系統(tǒng)GFS的工作原理特點：應(yīng)用程序訪問具體數(shù)據(jù)時部需要經(jīng)過GFSMaster，因此，避免了Master成為訪問瓶頸并發(fā)訪問：由于一個大數(shù)據(jù)會存儲在不同的ChunkServer中，應(yīng)用程序可實現(xiàn)并發(fā)訪問GoogleGFS的基本構(gòu)架和工作原理GFS的系統(tǒng)管理技術(shù)大規(guī)模集群安裝技術(shù)：如何在一個成千上萬個節(jié)點的集群上迅速部署GFS，升級管理和維護等故障檢測技術(shù)：GFS是構(gòu)建在不可靠的廉價計算機之上的文件系統(tǒng)，節(jié)點數(shù)多，故障頻繁，如何快速檢測、定位、恢復(fù)或隔離故障節(jié)點節(jié)點動態(tài)加入技術(shù)：當新的節(jié)點加入時，需要能自動安裝和部署GFS節(jié)能技術(shù)：服務(wù)器的耗電成本大于購買成本，Google為每個節(jié)點服務(wù)器配置了蓄電池替代UPS，大大節(jié)省了能耗。MapReduce分布式文件系統(tǒng)GFS的工作原理BigTable的基本作用和設(shè)計思想

GFS是一個文件系統(tǒng)，難以提供對結(jié)構(gòu)化數(shù)據(jù)的存儲和訪問管理。為此，Google在GFS之上又設(shè)計了一個結(jié)構(gòu)化數(shù)據(jù)存儲和訪問管理系統(tǒng)—BigTable，為應(yīng)用程序提供比單純的文件系統(tǒng)更方便、更高層的數(shù)據(jù)操作能力Google的很多數(shù)據(jù)，包括Web索引、衛(wèi)星圖像數(shù)據(jù)、地圖數(shù)據(jù)等都以結(jié)構(gòu)化形式存放在BigTable中BigTable提供了一定粒度的結(jié)構(gòu)化數(shù)據(jù)操作能力，主要解決一些大型媒體數(shù)據(jù)（Web文檔、圖片等）的結(jié)構(gòu)化存儲問題。但與傳統(tǒng)的關(guān)系數(shù)據(jù)庫相比，其結(jié)構(gòu)化粒度沒有那么高，也沒有事務(wù)處理等能力，因此，它并不是真正意義上的數(shù)據(jù)庫。4.分布式結(jié)構(gòu)化數(shù)據(jù)表BigTableBigTable設(shè)計動機和目標主要動機需要存儲多種數(shù)據(jù) Google提供的服務(wù)很多，序處理的數(shù)據(jù)類型也很多，如URL,網(wǎng)頁,圖片,地圖數(shù)據(jù),email,用戶的個性化設(shè)置等海量的服務(wù)請求Google是目前世界上最繁忙的系統(tǒng)，因此，需要有高性能的請求和數(shù)據(jù)處理能力商用數(shù)據(jù)庫無法適用

在如此龐大的分布集群上難以有效部署商用數(shù)據(jù)庫系統(tǒng)，且其難以承受如此巨量的數(shù)據(jù)存儲和操作需求分布式結(jié)構(gòu)化數(shù)據(jù)表BigTableBigTable設(shè)計動機和目標主要設(shè)計目標廣泛的適用性:為一系列服務(wù)和應(yīng)用而設(shè)計的數(shù)據(jù)存儲系統(tǒng),可滿足對不同類型數(shù)據(jù)的存儲和操作需求很強的可擴展性:根據(jù)需要可隨時自動加入或撤銷服務(wù)器節(jié)點高吞吐量數(shù)據(jù)訪問:提供P級數(shù)據(jù)存儲能力，每秒數(shù)百萬次的訪問請求高可用性和容錯性:保證系統(tǒng)在各種情況下度能正常運轉(zhuǎn)，服務(wù)不中斷自動管理能力：自動加入和撤銷服務(wù)器，自動負載平衡簡單性：系統(tǒng)設(shè)計盡量簡單以減少復(fù)雜性和出錯率分布式結(jié)構(gòu)化數(shù)據(jù)表BigTableBigTable數(shù)據(jù)模型BigTable主要是一個分布式多維表，表中的數(shù)據(jù)通過：一個行關(guān)鍵字(rowkey)一個列關(guān)鍵字(columnkey)一個時間戳(timestamp)進行索引和查詢定位的。BigTable對存儲在表中的數(shù)據(jù)不做任何解釋，一律視為字符串，具體數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)有用戶自行定義。BigTable查詢模型

(row:string,column:string,time:int64)結(jié)果數(shù)據(jù)字符串支持查詢、插入和刪除操作分布式結(jié)構(gòu)化數(shù)據(jù)表BigTableBigTable數(shù)據(jù)模型BigTable數(shù)據(jù)存儲格式行(Row):大小不超過64KB的任意字符串。表中的數(shù)據(jù)都是根據(jù)行關(guān)鍵字進行排序的。n.www就是一個行關(guān)鍵字，指明一行存儲數(shù)據(jù)。URL地址倒排好處是：1)同一地址的網(wǎng)頁將被存儲在表中連續(xù)的位置,便于查找；2)倒排便于數(shù)據(jù)壓縮,可大幅提高數(shù)據(jù)壓縮率子表(Tablet)：一個大表可能太大，不利于存儲管理，將在水平方向上被分為多個子表分布式結(jié)構(gòu)化數(shù)據(jù)表BigTableBigTable數(shù)據(jù)模型BigTable數(shù)據(jù)存儲格式列(Column):BigTable將列關(guān)鍵字組織成為“列族”(columnfamily),每個族中的數(shù)據(jù)屬于同一類別,如anchor時一個列族，其下可有不同的表示一個個超鏈的列關(guān)鍵字。一個列族下的數(shù)據(jù)會被壓縮在一起存放。因此,一個列關(guān)鍵字可表示為:

族名：列名(family:qualifier)content、anchor都是族名；而和my.look.ca則是anchor族中的列名。分布式結(jié)構(gòu)化數(shù)據(jù)表BigTableBigTable數(shù)據(jù)模型BigTable數(shù)據(jù)存儲格式時間戳(timestamp):很多時候同一個URL的網(wǎng)頁會不斷更新，而Google需要保存不同時間的網(wǎng)頁數(shù)據(jù)，因此需要使用時間戳來加以區(qū)分。為了簡化不同版本的數(shù)據(jù)管理，BigTable提供給了兩種設(shè)置：保留最近的n個版本數(shù)據(jù)保留限定時間內(nèi)的所有不同版本數(shù)據(jù)分布式結(jié)構(gòu)化數(shù)據(jù)表BigTableBigTable基本構(gòu)架分布式結(jié)構(gòu)化數(shù)據(jù)表BigTableBigTable主服務(wù)器BigTable客戶端BigTable客戶端程序庫BigTable子表服務(wù)器BigTable子表服務(wù)器BigTable子表服務(wù)器BigTable子表服務(wù)器……執(zhí)行元數(shù)據(jù)操作和負載平衡數(shù)據(jù)存儲和訪問操作數(shù)據(jù)存儲和訪問操作數(shù)據(jù)存儲和訪問操作數(shù)據(jù)存儲和訪問操作GFSChubby服務(wù)器（分布式鎖服務(wù)）GoogleWorkQueue負責(zé)故障監(jiān)控和處理子表數(shù)據(jù)的存儲及日志元數(shù)據(jù)存儲及主服務(wù)器選擇BigTable基本構(gòu)架主服務(wù)器新子表分配：當一個新子表產(chǎn)

生時，主服務(wù)器通過加載命令

將其分配給一個空間足夠大的

子表服務(wù)；創(chuàng)建新表、表合并

及較大子表的分裂都會產(chǎn)生新

的子表。子表監(jiān)控：通過Chubby完成。所有子表服務(wù)器基本信息被保存在Chubby中的服務(wù)器目錄中主服務(wù)器檢測這個目錄可獲取最新子表服務(wù)器的狀態(tài)信息。當子表服務(wù)器出現(xiàn)故障，主服務(wù)器將終止該子表服務(wù)器，并將其上的全部子表數(shù)據(jù)移動到其它子表服務(wù)器。負債均衡：當主服務(wù)器發(fā)現(xiàn)某個子表服務(wù)器負載過重時，將對自動對其進行負載均衡操作。分布式結(jié)構(gòu)化數(shù)據(jù)表BigTable主服務(wù)器新子表分配子表服務(wù)器間的負載均衡子表服務(wù)器狀態(tài)監(jiān)控BigTable基本構(gòu)架子表服務(wù)器BigTable中的數(shù)據(jù)都以子表形式保存在子表服務(wù)器上，客戶端程序也直接和子表服務(wù)器通信。分配：當一個新子表產(chǎn)子表服務(wù)器的主要問題