1、大數據培訓講義大數據培訓講義2013-6Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 目錄目錄大數據起源Hadoop1.0Hadoop2.0商用環境Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. 大數據起源大數據起源-Google-Google三篇三篇Google MapReduceGoogle MapReduceGoogleGoogle分布式分布式文件系統文件系統GFSGFSGoolgeGoolge分布式結構分布式結構化數據表化數據表BigTableBigTa

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

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

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

5、tial and Proprietary BOCO Inter-Telecom Co.,Ltd. 上升到構架上升到構架-自動并行化并隱藏低層細節自動并行化并隱藏低層細節海量數據存儲海量數據存儲數據劃分MapMapMapMap初始初始kv鍵值對鍵值對初始初始kv鍵值對鍵值對初始初始kv鍵值對鍵值對初始初始kv鍵值對鍵值對中 間 結 果(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)計算結果計算結果(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)上升到構

7、架上升到構架-自動并行化并隱藏低層細節自動并行化并隱藏低層細節海量數據存儲計算結果計算結果數據劃分Map初始初始kv鍵值對鍵值對初始初始kv鍵值對鍵值對初始初始kv鍵值對鍵值對初始初始kv鍵值對鍵值對MapMapMap中間結果中間結果(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.有一個待處理的大數據，被劃分為大小相同的數據塊(如64MB),及與此相應的用戶作業程序2.系統中有一個負責調度的主節點(Master),以及數據Map和Reduce工作節點(Worker)Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Google MapReduce并行處理的基本過程并行處理的基本過程 3.用戶作業程序提交給主節點4.主節點為作業程序尋找和配備可用的Map節點，并將程序傳送給map節點 5.主節點也為作業程序尋找和配備可用的Reduce節點，并將程序傳送給Reduce節點 Confidential and

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

39、很多數據，包括Web索引、衛星圖像數據、地圖數據等都以結構化形式存放在BigTable中 BigTable提供了一定粒度的結構化數據操作能力，主要解決一些大型媒體數據（Web文檔、圖片等）的結構化存儲問題。但與傳統的關系數據庫相比，其結構化粒度沒有那么高，也沒有事務處理等能力，因此，它并不是真正意義上的數據庫。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable設計動機和目標設計動機和目標主要動機需要存儲多種數據Google提供的服務很多，序處理的數據類型也很多，如URL,網頁,圖片,地圖數據,email,用戶的個性

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

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

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

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

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

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

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

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

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

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

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

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

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

53、cIlroys方式，這種方式在一個很大的掃描窗口里對常見的長字符串進行壓縮；第二遍是采用快速壓縮算法，即在一個16KB的小掃描窗口中尋找重復數據。兩個壓縮的算法都很快，在現在的機器上，壓縮的速率達到100-200MB/s，解壓的速率達到400-1000MB/s。Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. BigTable基本構架基本構架優化lBloom filter 一個讀操作必須讀取構成Tablet狀態的所有SSTable的數據。如果這些SSTable不在內存中，那么就需要多次訪問硬盤。我們通過允許客戶程序對特定局部性群組

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

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

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

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

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

59、據塊位置HDFS NameNodeDataNode數據DataNode數據DataNode數據Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Hadoop MapReduce基本構架與工作過程基本構架與工作過程對等于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數據存儲與計算節點構架Confidential and Proprietary BOCO Inter-Telecom Co.,Ltd. Hadoop 1.0Hadoop 1.0X86 PC集群本機硬盤本機硬盤本機硬盤本機硬盤本機硬盤本機硬盤數據節點Datanod