大數(shù)據(jù)培訓講義

1、大數(shù)據(jù)培訓講義大數(shù)據(jù)培訓講義2013-6Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 目錄目錄大數(shù)據(jù)起源Hadoop1.0Hadoop2.0商用環(huán)境Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 大數(shù)據(jù)起源大數(shù)據(jù)起源-Google-Google三篇三篇Google MapReduceGoogle MapReduceGoogleGoogle分布式分布式文件系統(tǒng)文件系統(tǒng)GFSGFSGoolgeGoolge分布式結(jié)構(gòu)分布式結(jié)構(gòu)化數(shù)據(jù)表化數(shù)據(jù)表BigTableBigTa

2、bleConfidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 三個層面上的基本構(gòu)思如何對付大數(shù)據(jù)處理：分而治之對相互間不具有計算依賴關系的大數(shù)據(jù)，實現(xiàn)并行最自然的辦法就是采取分而治之的策略上升到抽象模型：Mapper與ReducerMPI等并行計算方法缺少高層并行編程模型，為了克服這一缺陷，MapReduce借鑒了Lisp函數(shù)式語言中的思想，用Map和Reduce兩個函數(shù)提供了高層的并行編程抽象模型上升到構(gòu)架：統(tǒng)一構(gòu)架，為程序員隱藏系統(tǒng)層細節(jié)MPI等并行計算方法缺少統(tǒng)一的計算框架支持，程序員需要考慮數(shù)據(jù)存儲、劃分、分發(fā)、結(jié)果收集、錯誤恢

3、復等諸多細節(jié)；為此，MapReduce設計并提供了統(tǒng)一的計算框架，為程序員隱藏了絕大多數(shù)系統(tǒng)層面的處理細節(jié)Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 大數(shù)據(jù)分而治之大數(shù)據(jù)分而治之 大數(shù)據(jù)計算任務子任務子任務子任務子任務任務劃分計算結(jié)果結(jié)果合并Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 建立建立Map和和Reduce抽象模型抽象模型典型的流式大數(shù)據(jù)問題的特征 大量數(shù)據(jù)記錄/元素進行重復處理 對每個數(shù)據(jù)記錄/元素作感興趣的處理、獲取感興趣的中間結(jié)果信息 排序和

4、整理中間結(jié)果以利后續(xù)處理 收集整理中間結(jié)果 產(chǎn)生最終結(jié)果輸出MapReduce關鍵思想：為大數(shù)據(jù)處理過程中的兩個主要處理階段 提煉為一種抽象的操作機制Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 建立建立Map和和Reduce抽象模型抽象模型 借鑒函數(shù)式程序設計語言Lisp中的思想，定義了Map和Reduce兩個抽象的操作函數(shù)：map: (k1; v1) (k2; v2)reduce: (k2; v2) (k3; v3)特點：特點：描述了對一組數(shù)據(jù)處理的兩個階段的抽象操作描述了對一組數(shù)據(jù)處理的兩個階段的抽象操作Confiden

5、tial and Proprietary BOCO Inter-Telecom Co.,Ltd. 上升到構(gòu)架上升到構(gòu)架-自動并行化并隱藏低層細節(jié)自動并行化并隱藏低層細節(jié)海量數(shù)據(jù)存儲海量數(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：Aggregation and ShuffleReduceReduceReduce(k1,

6、values)(k2,values)(k3,values)計算結(jié)果計算結(jié)果(K1,val)(K2,val)(K3,val)Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 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)

7、架上升到構(gòu)架-自動并行化并隱藏低層細節(jié)自動并行化并隱藏低層細節(jié)海量數(shù)據(jù)存儲計算結(jié)果計算結(jié)果數(shù)據(jù)劃分Map初始初始kv鍵值對鍵值對初始初始kv鍵值對鍵值對初始初始kv鍵值對鍵值對初始初始kv鍵值對鍵值對MapMapMap中間結(jié)果中間結(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,

8、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和PartitionerConfidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google MapReduce并行處理的基本過程并行處理的基本過程

9、 1.有一個待處理的大數(shù)據(jù)，被劃分為大小相同的數(shù)據(jù)塊(如64MB),及與此相應的用戶作業(yè)程序2.系統(tǒng)中有一個負責調(diào)度的主節(jié)點(Master),以及數(shù)據(jù)Map和Reduce工作節(jié)點(Worker)Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google MapReduce并行處理的基本過程并行處理的基本過程 3.用戶作業(yè)程序提交給主節(jié)點4.主節(jié)點為作業(yè)程序?qū)ふ液团鋫淇捎玫腗ap節(jié)點，并將程序傳送給map節(jié)點 5.主節(jié)點也為作業(yè)程序?qū)ふ液团鋫淇捎玫腞educe節(jié)點，并將程序傳送給Reduce節(jié)點 Confidential and

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

11、 8.主節(jié)點等所有Map節(jié)點計算完成后，開始啟動Reduce節(jié)點運行；Reduce節(jié)點從主節(jié)點所掌握的中間結(jié)果數(shù)據(jù)位置信息，遠程讀取這些數(shù)據(jù)9.Reduce節(jié)點計算結(jié)果匯總輸出到一個結(jié)果文件即獲得整個處理結(jié)果Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google MapReduce并行處理的基本過程并行處理的基本過程 完整計算過程Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 存儲位置的計算策略存儲位置的計算策略策略 MapReduce的master在調(diào)度M

12、ap任務時會考慮輸入文件的位置信息，盡量將一個Map任務調(diào)度在包含相關輸入數(shù)據(jù)拷貝的機器上執(zhí)行；如果上述努力失敗了，master將嘗試在保存有輸入數(shù)據(jù)拷貝的機器附近的機器上執(zhí)行Map任務(例如，分配到一個和包含輸入數(shù)據(jù)的機器在一個switch里的worker機器上執(zhí)行)。當在一個足夠大的cluster集群上運行大型MapReduce操作的時候，大部分的輸入數(shù)據(jù)都能從本地機器讀取，因此消耗非常少的網(wǎng)絡帶寬。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 失效處理失效處理主節(jié)點失效 主節(jié)點中會周期性地設置檢查點(checkpoint

13、)，檢查整個計算作業(yè)的執(zhí)行情況，一旦某個任務失效，可以從最近有效的檢查點開始重新執(zhí)行，避免從頭開始計算的時間浪費。工作節(jié)點失效 工作節(jié)點失效是很普遍發(fā)生的，主節(jié)點會周期性地給工作節(jié)點發(fā)送檢測命令，如果工作節(jié)點沒有回應，這認為該工作節(jié)點失效，主節(jié)點將終止該工作節(jié)點的任務并把失效的任務重新調(diào)度到其它工作節(jié)點上重新執(zhí)行Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. CounterCounter MapReduce庫使用計數(shù)器統(tǒng)計不同事件發(fā)生次數(shù)。比如，用戶可能想統(tǒng)計已經(jīng)處理了多少個單詞、已經(jīng)索引的多少篇文檔。 這些計數(shù)器的值周期性的從

14、各個單獨的worker機器上傳遞給master（附加在ping的應答包中傳遞）。master把執(zhí)行成功的Map和Reduce任務的計數(shù)器值進行累計，當MapReduce操作完成之后，返回給用戶代碼Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 帶寬優(yōu)化帶寬優(yōu)化問題 大量的鍵值對數(shù)據(jù)在傳送給Reduce節(jié)點時會引起較大的通信帶寬開銷。解決方案 每個Map節(jié)點處理完成的中間鍵值隊將由combiner做一個合并壓縮，即把那些鍵名相同的鍵值對歸并為一個鍵名下的一組數(shù)值。(good, 1)(weather, 1)(is, 1)(good,

15、 1)(good, 2)(weather, 1)(is, 1)combinerConfidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 計算優(yōu)化計算優(yōu)化問題 Reduce節(jié)點必須要等到所有Map節(jié)點計算計算才能開始執(zhí)行，因此，如果有一個計算量大、或者由于某個問題導致很慢結(jié)束的Map節(jié)點，則會成為嚴重的“拖后腿者”。解決方案 把一個Map計算任務讓多個Map節(jié)點同時做，取最快完成者的計算結(jié)果。根據(jù)Google的測試，使用了這個冗余Map節(jié)點計算方法以后，計算任務性能提高40%多！Confidential and Proprietary BO

16、CO Inter-Telecom Co.,Ltd. 用數(shù)據(jù)分區(qū)解決數(shù)據(jù)相關性問題用數(shù)據(jù)分區(qū)解決數(shù)據(jù)相關性問題問題 一個Reduce節(jié)點上的計算數(shù)據(jù)可能會來自多個Map節(jié)點，因此，為了在進入Reduce節(jié)點計算之前，需要把屬于一個Reduce節(jié)點的數(shù)據(jù)歸并到一起。解決方案 在Map階段進行了Combining以后，可以根據(jù)一定的策略對Map輸出的中間結(jié)果進行分區(qū)(partitioning)，這樣既可解決以上數(shù)據(jù)相關性問題避免Reduce計算過程中的數(shù)據(jù)通信。例如：有一個巨大的數(shù)組,其最終結(jié)果需要排序,每個Map節(jié)點數(shù)據(jù)處理好后,為了避免在每個Reduce節(jié)點本地排序完成后還需要進行全局排序,我們

17、可以使用一個分區(qū)策略如:(d%R),d為數(shù)據(jù)大小，R為Reduce節(jié)點的個數(shù)，則可根據(jù)數(shù)據(jù)的大小將其劃分到指定數(shù)據(jù)范圍的Reduce節(jié)點上,每個Reduce將本地數(shù)據(jù)拍好序后即為最終結(jié)果Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 目錄目錄Google MapReduceGoogle MapReduce的基本工作原理的基本工作原理分布式文件系統(tǒng)分布式文件系統(tǒng)GFSGFS的基本工作原理的基本工作原理分布式結(jié)構(gòu)化數(shù)據(jù)表分布式結(jié)構(gòu)化數(shù)據(jù)表BigTableBigTableConfidential and Proprietary BOC

18、O Inter-Telecom Co.,Ltd. 基本問題基本問題海量數(shù)據(jù)怎么存儲？數(shù)據(jù)存儲可靠性怎么解決？當前主流的分布文件系統(tǒng)有： RedHat的GFS IBM的GPFS Sun的Lustre等主要用于對硬件設施要求很高的高性能計算或大型數(shù)據(jù)中心；價格昂貴且缺少完整的數(shù)據(jù)存儲容錯解決方案如Lustre只對元數(shù)據(jù)管理提供容錯處理，但對于具體的分布存儲節(jié)點，可靠性完全依賴于這些分布節(jié)點采用RAID或存儲區(qū)域網(wǎng)(SAN)技術提供容錯，一旦分布節(jié)點失效，數(shù)據(jù)就無法恢復。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google G

19、FS的的基本設計原則基本設計原則 Google GFS是一個基于分布式集群的大型分布式文件系統(tǒng)，為MapReduce計算框架提供低層數(shù)據(jù)存儲和數(shù)據(jù)可靠性支撐； GFS是一個構(gòu)建在分布節(jié)點本地文件系統(tǒng)之上的一個邏輯上文件系統(tǒng)，它將數(shù)據(jù)存儲在物理上分布的每個節(jié)點上，但通過GFS將整個數(shù)據(jù)形成一個邏輯上整體的文件。Google GFSGoogle MapReduceMapReduce ApplicationsConfidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google GFS的的基本設計原則基本設計原則 廉價本地磁盤分布存儲 各節(jié)點本

20、地分布式存儲數(shù)據(jù)，優(yōu)點是不需要采用價格較貴的集中式磁盤陣列，容量可隨節(jié)點數(shù)增加自動增加 多數(shù)據(jù)自動備份解決可靠性 采用廉價的普通磁盤，把磁盤數(shù)據(jù)出錯視為常態(tài)，用自動多數(shù)據(jù)備份存儲解決數(shù)據(jù)存儲可靠性問題 為上層的MapReduce計算框架提供支撐 GFS作為向上層MapReduce執(zhí)行框架的底層數(shù)據(jù)存儲支撐，負責處理所有的數(shù)據(jù)自動存儲和容錯處理，因而上層框架不需要考慮低層的數(shù)據(jù)存儲和數(shù)據(jù)容錯問題Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google GFS的基本構(gòu)架和工作原理的基本構(gòu)架和工作原理 Cite from Ghem

21、awat et al. (SOSP 2003)GFS MasterChunkServerConfidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google GFS的工作原理的工作原理GFS MasterMaster上保存了GFS文件系統(tǒng)的三種元數(shù)據(jù) ： 命名空間(Name Space),即整個 分布式文件系統(tǒng)的目錄結(jié)構(gòu) Chunk與文件名的映射表 Chunk副本的位置信息，每一個Chunk默認有3個副本GFS Master前兩種元數(shù)據(jù)可通過操作日志提供容錯處理能力；第3個元數(shù)據(jù)直接保存在ChunkServer上， Master 啟動或

22、Chunk Server注冊時自動完成在Chunk Server上元數(shù)據(jù)的生成；因此，當Master失效時，只要ChunkServer數(shù)據(jù)保存完好，可迅速恢復Master上的元數(shù)據(jù)。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google GFS的工作原理的工作原理GFS ChunkServer 即用來保存大量實際數(shù)據(jù)的數(shù)據(jù)服務器。 GFS中每個數(shù)據(jù)塊劃分缺省為64MB 每個數(shù)據(jù)塊會分別在3個(缺省情況下)不同的地方復制副本； 對每一個數(shù)據(jù)塊，僅當3個副本都更新成功時，才認為數(shù)據(jù)保存成功。當某個副本失效時，Master會自動

23、將正確的副本數(shù)據(jù)進行復制以保證足夠的副本數(shù) GFS上存儲的數(shù)據(jù)塊副本，在物理上以一個本地的Linux操作系統(tǒng)的文件形式存儲，每一個數(shù)據(jù)塊再劃分為64KB的子塊，每個子快有一個32位的校驗和，讀數(shù)據(jù)時會檢查校驗和以保證使用為失效的數(shù)據(jù)。ChunkServerConfidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google GFS的工作原理的工作原理Chunk位置信息位置信息 Master服務器并不保存持久化保存哪個Chunk服務器存有指定Chunk的副本的信息。Master服務器只是在啟動的時候輪詢Chunk服務器以獲取這些信息。Ma

24、ster服務器能夠保證它持有的信息始終是最新的，因 為它控制了所有的Chunk位置的分配，而且通過周期性的心跳信息監(jiān)控Chunk服務器的狀態(tài)。ChunkServerConfidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google GFS的工作原理的工作原理數(shù)據(jù)訪問工作過程1.在程序運行前，數(shù)據(jù)已經(jīng)存儲在GFS文件系統(tǒng)中；程序?qū)嵭袝r應用程序會告訴GFS Server所要訪問的文件名或者數(shù)據(jù)塊索引是什么Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google GFS的

25、工作原理的工作原理數(shù)據(jù)訪問工作過程2.GFS Server根據(jù)文件名會數(shù)據(jù)塊索引在其文件目錄空間中查找和定位該文件或數(shù)據(jù)塊，并找數(shù)據(jù)塊在具體哪些ChunkServer上；將這些位置信息回送給應用程序Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google GFS的工作原理的工作原理數(shù)據(jù)訪問工作過程3.應用程序根據(jù)GFSServer返回的具體Chunk數(shù)據(jù)塊位置信息，直接訪問相應的Chunk ServerConfidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Googl

26、e GFS的工作原理的工作原理數(shù)據(jù)訪問工作過程4.應用程序根據(jù)GFSServer返回的具體Chunk數(shù)據(jù)塊位置信息直接讀取指定位置的數(shù)據(jù)進行計算處理Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google GFS的工作原理的工作原理數(shù)據(jù)訪問工作過程特點：應用程序訪問具體數(shù)據(jù)時部需要經(jīng)過GFS Master，因此，避免了Master成為訪問瓶頸并發(fā)訪問：由于一個大數(shù)據(jù)會存儲在不同的ChunkServer中，應用程序可實現(xiàn)并發(fā)訪問Confidential and Proprietary BOCO Inter-Telecom Co

27、.,Ltd. Google GFS的工作原理的工作原理GFS租約租約機制機制 設計租約機制的目的是為了最小化Master節(jié)點的管理負擔。租約的初始超時設置為60秒。不過，只要Chunk被修改了，主Chunk就可以申請更長的租期，通常會得到Master節(jié)點的確認并收到租約延長的時間。這些租約延長請求和批準的信息通常都是附加在Master節(jié)點和Chunk服務器之間的心跳消息中來傳遞。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google GFS的工作原理的工作原理數(shù)據(jù)流數(shù)據(jù)流 為了提高網(wǎng)絡效率，GFS采取了把數(shù)據(jù)流和控制流分開

28、的措施。在控制流從客戶機到主Chunk、然后再到 所有二級副本的同時，數(shù)據(jù)以管道的方式，順序的沿著一個精心選擇的Chunk服務器鏈推送。我們的目標是充分利用每臺機器的帶寬，避免網(wǎng)絡瓶頸和高延時的連接，最小化推送所有數(shù)據(jù)的延時。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google GFS的工作原理的工作原理數(shù)據(jù)完整性數(shù)據(jù)完整性 GFS把每個Chunk都分成64KB大小的塊。每個塊都對應一個32位的Checksum。和其它元數(shù)據(jù)一樣，Checksum與其它的用戶數(shù)據(jù)是分開的，并且保存在內(nèi)存和硬盤上，同時也記錄操作日志。對于讀

29、操作來說，在把數(shù)據(jù)返回給客戶端或者其它的Chunk服務器之前，Chunk服務器會校驗讀取操作涉及的范圍內(nèi)的塊的Checksum。因此Chunk服務器不會把錯誤數(shù)據(jù)傳遞到其它的機器上。如果發(fā)生某個塊的Checksum不正確，Chunk服務器返回給請求者一個錯誤信息，并且通知Master服務器這個錯誤。作為回應，請求者應當從其它副本讀取數(shù)據(jù)，Master服務器也會從其它副本克隆數(shù)據(jù)進行恢復。當一個新的副本就緒后，Master服務器通知副本錯誤的Chunk服務器刪掉錯誤的副本。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Googl

30、e GFS的工作原理的工作原理Chunk副本的副本的3種機制種機制 創(chuàng)建： 當Master節(jié)點創(chuàng)建一個Chunk時，它會選擇在哪里放置初始的空的副本。Master節(jié)點會考慮幾個因素。（1）GFS希望在低于平均硬盤使用率的Chunk服務器上存儲新的副本。這樣的做法最終能夠平衡Chunk服務器之間的硬盤使用率。（2）GFS希望限制在每個Chunk服務器上”最近”的Chunk創(chuàng)建操作的次數(shù)。雖然創(chuàng)建操作本身是廉價的，但是創(chuàng)建操作也意味著隨之會有大量的寫入數(shù)據(jù)的操作，因為Chunk在Writer真正寫入數(shù)據(jù)的時候才被創(chuàng)建，而在我們的”追加一次，讀取多次”的工作模式下，Chunk一旦寫入成功之后就會變?yōu)?/p>

31、只讀的了。（3）GFS希望把Chunk的副本分布在多個機架之間。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google GFS的工作原理的工作原理Chunk副本的副本的3種機制種機制 重新復制： 當Chunk的有效副本數(shù)量少于用戶指定的復制因數(shù)的時候，Master節(jié)點會重新復制它。這可能是由幾個原因引起的：一個Chunk服務器不可用了，Chunk服務器報告它所存儲的一個副本損壞了，Chunk服務器的一個磁盤因為錯誤不可用了，或者Chunk副本的復制因數(shù)提高了。每個需要被重新復制的Chunk都會根據(jù)幾個因素進行排序。一個因素

32、是Chunk現(xiàn)有副本數(shù)量和復制因數(shù)相差多少。例如，丟失兩個副本的Chunk比丟失一個副本的Chunk有更高的優(yōu)先級。另外，GFS優(yōu)先重新復制活躍（live）文件的Chunk而不是最近剛被刪除的文件的Chunk。最后，為了最小化失效的Chunk對正在運行的應用程序的影響，我們提高會阻塞客戶機程序處理流程的Chunk的優(yōu)先級。 Master節(jié)點選擇優(yōu)先級最高的Chunk，然后命令某個Chunk服務器直接從可用的副本”克隆”一個副本出來。選擇新副本的位置的策略和創(chuàng)建時類似：平衡硬盤使用率、限制同一臺Chunk服務器上的正在進行的克隆操作的數(shù)量、在機架間分布副本。為了防止克隆產(chǎn)生的網(wǎng)絡流量大大超過客戶

33、機的流量，Master節(jié)點對整個集群和每個Chunk服務器上的同時進行的克隆操作的數(shù)量都進行了限制。另外，Chunk服務器通過調(diào)節(jié)它對源Chunk服務器讀請求的頻率來限制它用于克隆操作的帶寬。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google GFS的工作原理的工作原理Chunk副本的副本的3種機制種機制 重新負載均衡： 最后，Master服務器周期性地對副本進行重新負載均衡：它檢查當前的副本分布情況，然后移動副本以便更好的利用硬盤空間、更有效的進行負載均衡。而且在這個過程中，Master服務器逐漸的填滿一個新的Chu

34、nk服務器，而不是在短時間內(nèi)用新的Chunk填滿它，以至于過載。新副本的存儲位置選擇策略和上面討論的相同。另外，Master節(jié)點必須選擇哪個副本要被移走。通常情況，Master節(jié)點移走那些剩余空間低于平均值的Chunk服務器上的副本，從而平衡系統(tǒng)整體的硬盤使用率。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google GFS的工作原理的工作原理 過期過期失效的副本失效的副本檢測檢測 當Chunk服務器失效時，Chunk的副本有可能因錯失了一些修改操作而過期失效。Master節(jié)點保存了每個Chunk的版本號，用來區(qū)分當前的副

35、本和過期副本。無論何時，只要Master節(jié)點和Chunk簽訂一個新的租約，它就增加Chunk的版本號，然后通知最新的副本。Master節(jié)點和這些副本都把新的版本號記錄在它們持久化存儲的狀態(tài)信息中。這個動作發(fā)生在任何客戶機得到通知以前，因此也是對這個Chunk開始寫之前。如果某個副本所在的Chunk服務器正好處于失效狀態(tài)，那么副本的版本號就不會被增加。Master節(jié)點在這個Chunk服務器重新啟動，并且向Master節(jié)點報告它擁有的Chunk的集合以及相應的版本號的時候，就會檢測出它包含過期的Chunk。如果Master節(jié)點看到一個比它記錄的版本號更高的版本號，Master節(jié)點會認為它和Chun

36、k服務器簽訂租約的操作失敗了，因此會選擇更高的版本號作為當前的版本號。 Master節(jié)點在例行的垃圾回收過程中移除所有的過期失效副本。在此之前，Master節(jié)點在回復客戶機的Chunk信息請求的時候，簡單的認為那些過期的塊根本就不存在。另外一重保障措施是，Master節(jié)點在通知客戶機哪個Chunk服務器持有租約、或者指示Chunk服務器從哪個Chunk服務器進行克隆時，消息中都附帶了Chunk的版本號?？蛻魴C或者Chunk服務器在執(zhí)行操作時都會驗證版本號以確?？偸窃L問當前版本的數(shù)據(jù)。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd.

37、 Google GFS的基本構(gòu)架和工作原理的基本構(gòu)架和工作原理GFS的系統(tǒng)管理技術 大規(guī)模集群安裝技術：如何在一個成千上萬個節(jié)點的集群上迅速部署GFS，升級管理和維護等 故障檢測技術：GFS是構(gòu)建在不可靠的廉價計算機之上的文件系統(tǒng)，節(jié)點數(shù)多，故障頻繁，如何快速檢測、定位、恢復或隔離故障節(jié)點 節(jié)點動態(tài)加入技術：當新的節(jié)點加入時，需要能自動安裝和部署GFS 節(jié)能技術：服務器的耗電成本大于購買成本，Google為每個節(jié)點服務器配置了蓄電池替代UPS，大大節(jié)省了能耗。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 目錄目錄Google

38、MapReduceGoogle MapReduceGoogleGoogle分布式分布式文件系統(tǒng)文件系統(tǒng)GFSGFSGoogleGoogle分布式結(jié)構(gòu)分布式結(jié)構(gòu)化數(shù)據(jù)表化數(shù)據(jù)表BigTableBigTableConfidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable的基本作用和設計思想的基本作用和設計思想 GFS是一個文件系統(tǒng)，難以提供對結(jié)構(gòu)化數(shù)據(jù)的存儲和訪問管理。為此，Google在GFS之上又設計了一個結(jié)構(gòu)化數(shù)據(jù)存儲和訪問管理系統(tǒng)BigTable，為應用程序提供比單純的文件系統(tǒng)更方便、更高層的數(shù)據(jù)操作能力 Google的

39、很多數(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)的關系數(shù)據(jù)庫相比，其結(jié)構(gòu)化粒度沒有那么高，也沒有事務處理等能力，因此，它并不是真正意義上的數(shù)據(jù)庫。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable設計動機和目標設計動機和目標主要動機需要存儲多種數(shù)據(jù)Google提供的服務很多，序處理的數(shù)據(jù)類型也很多，如URL,網(wǎng)頁,圖片,地圖數(shù)據(jù),email,用戶的個性

40、化設置等海量的服務請求 Google是目前世界上最繁忙的系統(tǒng)，因此，需要有高性能的請求和數(shù)據(jù)處理能力商用數(shù)據(jù)庫無法適用 在如此龐大的分布集群上難以有效部署商用數(shù)據(jù)庫系統(tǒng)，且其難以承受如此巨量的數(shù)據(jù)存儲和操作需求Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable設計動機和目標設計動機和目標主要設計目標廣泛的適用性:為一系列服務和應用而設計的數(shù)據(jù)存儲系統(tǒng),可滿足對不同類型數(shù)據(jù)的存儲和操作需求很強的可擴展性:根據(jù)需要可隨時自動加入或撤銷服務器節(jié)點高吞吐量數(shù)據(jù)訪問:提供P級數(shù)據(jù)存儲能力，每秒數(shù)百萬次的訪問請求高可用性和容錯

41、性:保證系統(tǒng)在各種情況下度能正常運轉(zhuǎn)，服務不中斷自動管理能力：自動加入和撤銷服務器，自動負載平衡簡單性：系統(tǒng)設計盡量簡單以減少復雜性和出錯率Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable數(shù)據(jù)模型數(shù)據(jù)模型lBigTable主要是一個分布式多維表，表中的數(shù)據(jù)通過：l一個行關鍵字(row key)l一個列關鍵字(column key)l一個時間戳(time stamp) 進行索引和查詢定位的。lBigTable對存儲在表中的數(shù)據(jù)不做任何解釋，一律視為字符串，具體數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)有用戶自行定義。lBigTable查詢模型

42、 (row:string, column:string,time:int64) 結(jié)果數(shù)據(jù)字符串l支持查詢、插入和刪除操作Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable數(shù)據(jù)模型數(shù)據(jù)模型BigTable數(shù)據(jù)存儲格式l行(Row):大小不超過64KB的任意字符串。表中的數(shù)據(jù)都是根據(jù)行關鍵字進行排序的。 n.www就是一個行關鍵字，指明一行存儲數(shù)據(jù)。URL地址倒排好處是：1)同一地址的網(wǎng)頁將被存儲在表中連續(xù)的位置,便于查找；2)倒排便于數(shù)據(jù)壓縮,可大幅提高數(shù)據(jù)壓縮率l子表(Tablet)：一個大表可能太大，不利于存儲管

43、理，將在水平方向上被分為多個子表Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable數(shù)據(jù)模型數(shù)據(jù)模型BigTable數(shù)據(jù)存儲格式l列(Column): BigTable將列關鍵字組織成為“列族”(column family),每個族中的數(shù)據(jù)屬于同一類別,如anchor時一個列族，其下可有不同的表示一個個超鏈的列關鍵字。一個列族下的數(shù)據(jù)會被壓縮在一起存放。因此,一個列關鍵字可表示為: 族名：列名(family:qualifier) content、anchor都是族名；而和my.look.ca則是anchor族中的列名

44、。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable數(shù)據(jù)模型數(shù)據(jù)模型BigTable數(shù)據(jù)存儲格式l時間戳(time stamp): 很多時候同一個URL的網(wǎng)頁會不斷更新，而Google需要保存不同時間的網(wǎng)頁數(shù)據(jù)，因此需要使用時間戳來加以區(qū)分。l為了簡化不同版本的數(shù)據(jù)管理，BigTable提供給了兩種設置：l保留最近的n個版本數(shù)據(jù)l保留限定時間內(nèi)的所有不同版本數(shù)據(jù)Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable基本構(gòu)架基本構(gòu)架BigTa

45、ble主服務器BigTable客戶端BigTable客戶端程序庫BigTable子表服務器BigTable子表服務器BigTable子表服務器BigTable子表服務器執(zhí)行元數(shù)據(jù)操作和負載平衡數(shù)據(jù)存儲和訪問操作數(shù)據(jù)存儲和訪問操作數(shù)據(jù)存儲和訪問操作數(shù)據(jù)存儲和訪問操作GFSChubby服務器（分布式鎖服務）GoogleWorkQueue負責故障監(jiān)控和處理子表數(shù)據(jù)的存儲及日志元數(shù)據(jù)存儲及主服務器選擇Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable基本構(gòu)架基本構(gòu)架主服務器l新子表分配：當一個新子表產(chǎn) 生時，主服務器通過加

46、載命令 將其分配給一個空間足夠大的 子表服務；創(chuàng)建新表、表合并 及較大子表的分裂都會產(chǎn)生新 的子表。l子表監(jiān)控：通過Chubby完成。所有子表服務器基本信息被保存在Chubby中的服務器目錄中主服務器檢測這個目錄可獲取最新子表服務器的狀態(tài)信息。當子表服務器出現(xiàn)故障，主服務器將終止該子表服務器，并將其上的全部子表數(shù)據(jù)移動到其它子表服務器。l負債均衡：當主服務器發(fā)現(xiàn)某個子表服務器負載過重時，將對自動對其進行負載均衡操作。主服務器新子表分配子表服務器間的負載均衡子表服務器狀態(tài)監(jiān)控Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigT

47、able基本構(gòu)架基本構(gòu)架子表服務器BigTable中的數(shù)據(jù)都以子表形式保存在子表服務器上，客戶端程序也直接和子表服務器通信。分配：當一個新子表產(chǎn)子表服務器的主要問題包括子表的定位、分配、及子表數(shù)據(jù)的最終存儲。l子表的基本存儲結(jié)構(gòu)SSTable SSTable是BigTable內(nèi)部的基本存儲結(jié)構(gòu)，以GFS文件形式存儲在GFS文件系統(tǒng)中。一個SSTable實際上對應于GFS中的一個64MB的數(shù)據(jù)塊(Chunk) SSTable中的數(shù)據(jù)進一步劃分為64KB的子塊，因此一個SSTable可以有多達1千個這樣的子塊。為了維護這些子塊的位置信息，需要使用一個Index索引。Index64K block64

48、K block64K blockSSTableConfidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable基本構(gòu)架基本構(gòu)架子表服務器l子表數(shù)據(jù)格式 概念上子表是整個大表的多行數(shù)據(jù)劃分后構(gòu)成。而一個子表服務器上的子表將進一步由很多個SSTAble構(gòu)成，每個SSTable構(gòu)成最終的在底層GFS中的存儲單位。Index64K block64K block64K blockSSTableIndex64K block64K block64K blockSSTableTabletStart:aardvarkEnd:appleConfid

49、ential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable基本構(gòu)架基本構(gòu)架子表服務器l子表數(shù)據(jù)格式 一個SSTable還可以為不同的子表所共享，以避免同樣數(shù)據(jù)的重復存儲。 SSTableSSTableSSTableSSTableTabletaardvarkappleTabletapple_two_EboatConfidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable基本構(gòu)架基本構(gòu)架子表服務器l子表尋址 子表地址以3級B+樹形式進行索引；首先從Chubby 服務器中取

50、得根子表，由根子表找到二級索引 指標，最后獲取最終的 SSTable的位置 Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable基本構(gòu)架基本構(gòu)架子表服務器lMinor Compaction 隨著寫操作的執(zhí)行，memtable的大小不斷增加。當memtable的尺寸到達一個門限值的時候，這個memtable就會被凍結(jié)，然后創(chuàng)建一個新的memtable；被凍結(jié)住memtable會被轉(zhuǎn)換成SSTable，然后寫入GFS。Confidential and Proprietary BOCO Inter-Telecom Co.,

51、Ltd. BigTable基本構(gòu)架基本構(gòu)架子表服務器lMerging Compaction 每一次Minor Compaction都會創(chuàng)建一個新的SSTable。通過定期在后臺執(zhí)行Merging Compaction過程合并文件，限制這類文件的數(shù)量。Merging Compaction過程讀取一些SSTable和memtable的內(nèi)容，合并成一個新的SSTable。lMajor Compaction Major Compaction過程生成的SSTable不包含已經(jīng)刪除的信息或數(shù)據(jù)。Bigtable循環(huán)掃描它所有的Tablet，并且定期對它們執(zhí)行Major Compaction。Major C

52、ompaction機制允許Bigtable回收已經(jīng)刪除的數(shù)據(jù)占有的資源，并且確保BigTable能及時清除已經(jīng)刪除的數(shù)據(jù)。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable基本構(gòu)架基本構(gòu)架優(yōu)化l壓縮 每個SSTable的塊（塊的大小由局部性群組的優(yōu)化參數(shù)定）都使用用戶指定的壓縮格式來壓縮。雖然分塊 壓縮浪費了少量空間（相比于對整個SSTable進行壓縮，分塊壓縮壓縮率較低），但是，在只讀取SSTable的一小部分數(shù)據(jù)的時候就不必解壓整個文件了。使用了“兩遍”的、可定制的壓縮方式。第一遍采用Bentley and M

53、cIlroys方式，這種方式在一個很大的掃描窗口里對常見的長字符串進行壓縮；第二遍是采用快速壓縮算法，即在一個16KB的小掃描窗口中尋找重復數(shù)據(jù)。兩個壓縮的算法都很快，在現(xiàn)在的機器上，壓縮的速率達到100-200MB/s，解壓的速率達到400-1000MB/s。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable基本構(gòu)架基本構(gòu)架優(yōu)化lBloom filter 一個讀操作必須讀取構(gòu)成Tablet狀態(tài)的所有SSTable的數(shù)據(jù)。如果這些SSTable不在內(nèi)存中，那么就需要多次訪問硬盤。我們通過允許客戶程序?qū)μ囟ň植啃匀航M

54、的SSTable指定Bloom過濾器，來減少硬盤訪問的次數(shù)。我們可以使用Bloom過濾器查詢一個SSTable是否包含了特定行和列的數(shù)據(jù)。對于某些特定應用程序，我們只付出了少量的、用于存儲Bloom過濾器的內(nèi)存的代價，就換來了讀操作顯著減少的磁盤訪問的次數(shù)。使用Bloom過濾器也隱式的達到了當應用程序訪問不存在的行或列時，大多數(shù)時候我們都不需要訪問硬盤的目的。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable基本構(gòu)架基本構(gòu)架Bloom filterl原理如需要判斷一個元素是不是在一個集合中，我們通常做法是把所有元素

55、保存下來，然后通過比較知道它是不是在集合內(nèi)，鏈表、樹都是基于這種思路，當集合內(nèi)元素個數(shù)的變大，我們需要的空間和時間都線性變大，檢索速度也越來越慢。 Bloom filter 采用的是哈希函數(shù)的方法，將一個元素映射到一個 m 長度的陣列上的一個點，當這個點是 1 時，那么這個元素在集合內(nèi)，反之則不在集合內(nèi)。這個方法的缺點就是當檢測的元素很多的時候可能有沖突，解決方法就是使用 k 個哈希 函數(shù)對應 k 個點，如果所有點都是 1 的話，那么元素在集合內(nèi)，如果有 0 的話，元素則不在集合內(nèi)。初始狀態(tài)時，Bloom Filter是一個包含m位的位數(shù)組，每一位都置為0。Confidential and P

56、roprietary BOCO Inter-Telecom Co.,Ltd. BigTable基本構(gòu)架基本構(gòu)架Bloom filter為了表達S=x1, x2,xn這樣一個n個元素的集合，Bloom Filter使用k個相互獨立的哈希函數(shù)（Hash Function），它們分別將集合中的每個元素映射到1,m的范圍中。對任意一個元素x，第i個哈希函數(shù)映射的位置hi(x)就會被置為1（1ik）。注意，如果一個位置多次被置為1，那么只有第一次會起作用，后面幾次將沒有任何效果。在下圖中，k=3，且有兩個哈希函數(shù)選中同一個位置（從左邊數(shù)第五位）。在判斷y是否屬于這個集合時，我們對y應用k次哈希函數(shù)，如果

57、所有hi(y)的位置都是1（1ik），那么我們就認為y是集合中的元素，否則就認為y不是集合中的元素。下圖中y1就不是集合中的元素。y2或者屬于這個集合，或者剛好是一個false positive。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 目錄目錄大數(shù)據(jù)起源Hadoop1.0Hadoop2.0商用環(huán)境Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. hadoopHadoop是一個開源的軟件框架，它支持數(shù)據(jù)密集型的分布式應用，許可授權隸屬于Apache v2 li

58、cense.可以在成千上萬臺獨立的計算機上運行。Hadoop源自于Google的MapReduce 和 Google File System (GFS) 兩篇論文?，F(xiàn)在通常認為完整的Apache Hadoop平臺由Hadoop內(nèi)核、MapReduce 和HDFS組成，以及若干相關的項目包括Apache Hive 、Apache Hbase等等Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. HDFS基本構(gòu)架基本構(gòu)架對等于GFS Master對等于GFS ChunkServer應用程序HDFS客戶端客戶端文件名或數(shù)據(jù)塊號數(shù)據(jù)塊號，數(shù)

59、據(jù)塊位置HDFS NameNodeDataNode數(shù)據(jù)DataNode數(shù)據(jù)DataNode數(shù)據(jù)Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Hadoop MapReduce基本構(gòu)架與工作過程基本構(gòu)架與工作過程對等于Google MapReduce 中的Master對等于Google MapReduce 中的WorkerConfidential and Proprietary BOCO Inter-Telecom Co.,Ltd. datanode daemonLinux file systemtasktrackerslave

60、nodedatanode daemonLinux file systemtasktrackerslave nodedatanode daemonLinux file systemtasktrackerslave nodenamenodenamenode daemonjob submission nodejobtrackerHadoop MapReduce和和HDFS數(shù)據(jù)存儲與計算節(jié)點構(gòu)架Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Hadoop 1.0Hadoop 1.0X86 PC集群本機硬盤本機硬盤本機硬盤本機硬盤本機硬盤本機硬盤數(shù)據(jù)節(jié)點Datanod