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

大數(shù)據(jù)培訓(xùn)講義2013-6目錄大數(shù)據(jù)起源Hadoop1.0Hadoop2.0商用環(huán)境大數(shù)據(jù)起源-Google三篇GoogleMapReduceGoogle分布式文件系統(tǒng)GFSGoolge分布式結(jié)構(gòu)化數(shù)據(jù)表BigTable三個(gè)層面上的基本構(gòu)思如何對(duì)付大數(shù)據(jù)處理：分而治之

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

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

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

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

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

[(k2;v2)]reduce:

(k2;[v2])

[(k3;v3)]特點(diǎn)：描述了對(duì)一組數(shù)據(jù)處理的兩個(gè)階段的抽象操作GoogleMapReduce的基本模型和處理思想上升到構(gòu)架--自動(dòng)并行化并隱藏低層細(xì)節(jié)海量數(shù)據(jù)存儲(chǔ)……數(shù)據(jù)劃分MapMapMapMap初始kv鍵值對(duì)初始kv鍵值對(duì)初始kv鍵值對(duì)初始kv鍵值對(duì)中間結(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)計(jì)算結(jié)果(K1,val)(K2,val)(K3,val)GoogleMapReduce的基本模型和處理思想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)架--自動(dòng)并行化并隱藏低層細(xì)節(jié)海量數(shù)據(jù)存儲(chǔ)計(jì)算結(jié)果……數(shù)據(jù)劃分Map初始kv鍵值對(duì)初始kv鍵值對(duì)初始kv鍵值對(duì)初始kv鍵值對(duì)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和PartitionerGoogleMapReduce的基本模型和處理思想GoogleMapReduce并行處理的基本過程

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

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

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

8.主節(jié)點(diǎn)等所有Map節(jié)點(diǎn)計(jì)算完成后，開始啟動(dòng)Reduce節(jié)點(diǎn)運(yùn)行；Reduce節(jié)點(diǎn)從主節(jié)點(diǎn)所掌握的中間結(jié)果數(shù)據(jù)位置信息，遠(yuǎn)程讀取這些數(shù)據(jù)9.Reduce節(jié)點(diǎn)計(jì)算結(jié)果匯總輸出到一個(gè)結(jié)果文件即獲得整個(gè)處理結(jié)果GoogleMapReduce的基本模型和處理思想GoogleMapReduce并行處理的基本過程

完整計(jì)算過程GoogleMapReduce的基本模型和處理思想存儲(chǔ)位置的計(jì)算策略策略

MapReduce的master在調(diào)度Map任務(wù)時(shí)會(huì)考慮輸入文件的位置信息，盡量將一個(gè)Map任務(wù)調(diào)度在包含相關(guān)輸入數(shù)據(jù)拷貝的機(jī)器上執(zhí)行；如果上述努力失敗了，master將嘗試在保存有輸入數(shù)據(jù)拷貝的機(jī)器附近的機(jī)器上執(zhí)行Map任務(wù)(例如，分配到一個(gè)和包含輸入數(shù)據(jù)的機(jī)器在一個(gè)switch里的worker機(jī)器上執(zhí)行)。當(dāng)在一個(gè)足夠大的cluster集群上運(yùn)行大型MapReduce操作的時(shí)候，大部分的輸入數(shù)據(jù)都能從本地機(jī)器讀取，因此消耗非常少的網(wǎng)絡(luò)帶寬。。GoogleMapReduce的基本模型和處理思想失效處理主節(jié)點(diǎn)失效主節(jié)點(diǎn)中會(huì)周期性地設(shè)置檢查點(diǎn)(checkpoint)，檢查整個(gè)計(jì)算作業(yè)的執(zhí)行情況，一旦某個(gè)任務(wù)失效，可以從最近有效的檢查點(diǎn)開始重新執(zhí)行，避免從頭開始計(jì)算的時(shí)間浪費(fèi)。工作節(jié)點(diǎn)失效工作節(jié)點(diǎn)失效是很普遍發(fā)生的，主節(jié)點(diǎn)會(huì)周期性地給工作節(jié)點(diǎn)發(fā)送檢測(cè)命令，如果工作節(jié)點(diǎn)沒有回應(yīng)，這認(rèn)為該工作節(jié)點(diǎn)失效，主節(jié)點(diǎn)將終止該工作節(jié)點(diǎn)的任務(wù)并把失效的任務(wù)重新調(diào)度到其它工作節(jié)點(diǎn)上重新執(zhí)行GoogleMapReduce的基本模型和處理思想CounterMapReduce庫(kù)使用計(jì)數(shù)器統(tǒng)計(jì)不同事件發(fā)生次數(shù)。比如，用戶可能想統(tǒng)計(jì)已經(jīng)處理了多少個(gè)單詞、已經(jīng)索引的多少篇文檔。這些計(jì)數(shù)器的值周期性的從各個(gè)單獨(dú)的worker機(jī)器上傳遞給master（附加在ping的應(yīng)答包中傳遞）。master把執(zhí)行成功的Map和Reduce任務(wù)的計(jì)數(shù)器值進(jìn)行累計(jì)，當(dāng)MapReduce操作完成之后，返回給用戶代碼GoogleMapReduce的基本模型和處理思想

帶寬優(yōu)化問題

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

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

用數(shù)據(jù)分區(qū)解決數(shù)據(jù)相關(guān)性問題問題

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

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

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

Citefrom

Ghemawatetal.(SOSP2003)GFSMasterChunkServerGoogleGFS文件系統(tǒng)GoogleGFS的工作原理GFSMasterMaster上保存了GFS文件系統(tǒng)的三種元數(shù)據(jù)

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

Chunk與文件名的映射表Chunk副本的位置信息，每一個(gè)Chunk默認(rèn)有3個(gè)副本GFSMaster前兩種元數(shù)據(jù)可通過操作日志提供容錯(cuò)處理能力；第3個(gè)元數(shù)據(jù)直接保存在ChunkServer上，Master啟動(dòng)或ChunkServer注冊(cè)時(shí)自動(dòng)完成在ChunkServer上元數(shù)據(jù)的生成；因此，當(dāng)Master失效時(shí)，只要ChunkServer數(shù)據(jù)保存完好，可迅速恢復(fù)Master上的元數(shù)據(jù)。GoogleGFS文件系統(tǒng)GoogleGFS的工作原理GFSChunkServer即用來保存大量實(shí)際數(shù)據(jù)的數(shù)據(jù)服務(wù)器。GFS中每個(gè)數(shù)據(jù)塊劃分缺省為64MB每個(gè)數(shù)據(jù)塊會(huì)分別在3個(gè)(缺省情況下)不同的地方復(fù)制副本；對(duì)每一個(gè)數(shù)據(jù)塊，僅當(dāng)3個(gè)副本都更新成功時(shí)，才認(rèn)為數(shù)據(jù)保存成功。當(dāng)某個(gè)副本失效時(shí)，Master會(huì)自動(dòng)將正確的副本數(shù)據(jù)進(jìn)行復(fù)制以保證足夠的副本數(shù)GFS上存儲(chǔ)的數(shù)據(jù)塊副本，在物理上以一個(gè)本地的Linux操作系統(tǒng)的文件形式存儲(chǔ)，每一個(gè)數(shù)據(jù)塊再劃分為64KB的子塊，每個(gè)子快有一個(gè)32位的校驗(yàn)和，讀數(shù)據(jù)時(shí)會(huì)檢查校驗(yàn)和以保證使用為失效的數(shù)據(jù)。ChunkServerGoogleGFS文件系統(tǒng)GoogleGFS的工作原理Chunk位置信息Master服務(wù)器并不保存持久化保存哪個(gè)Chunk服務(wù)器存有指定Chunk的副本的信息。Master服務(wù)器只是在啟動(dòng)的時(shí)候輪詢Chunk服務(wù)器以獲取這些信息。Master服務(wù)器能夠保證它持有的信息始終是最新的，因?yàn)樗刂屏怂械腃hunk位置的分配，而且通過周期性的心跳信息監(jiān)控Chunk服務(wù)器的狀態(tài)。ChunkServerGoogleGFS文件系統(tǒng)GoogleGFS的工作原理數(shù)據(jù)訪問工作過程1.在程序運(yùn)行前，數(shù)據(jù)已經(jīng)存儲(chǔ)在GFS文件系統(tǒng)中；程序?qū)嵭袝r(shí)應(yīng)用程序會(huì)告訴GFSServer所要訪問的文件名或者數(shù)據(jù)塊索引是什么GoogleGFS文件系統(tǒng)GoogleGFS的工作原理數(shù)據(jù)訪問工作過程2.GFSServer根據(jù)文件名會(huì)數(shù)據(jù)塊索引在其文件目錄空間中查找和定位該文件或數(shù)據(jù)塊，并找數(shù)據(jù)塊在具體哪些ChunkServer上；將這些位置信息回送給應(yīng)用程序GoogleGFS文件系統(tǒng)GoogleGFS的工作原理數(shù)據(jù)訪問工作過程3.應(yīng)用程序根據(jù)GFSServer返回的具體Chunk數(shù)據(jù)塊位置信息，直接訪問相應(yīng)的ChunkServerGoogleGFS文件系統(tǒng)GoogleGFS的工作原理數(shù)據(jù)訪問工作過程4.應(yīng)用程序根據(jù)GFSServer返回的具體Chunk數(shù)據(jù)塊位置信息直接讀取指定位置的數(shù)據(jù)進(jìn)行計(jì)算處理GoogleGFS文件系統(tǒng)GoogleGFS的工作原理數(shù)據(jù)訪問工作過程特點(diǎn)：應(yīng)用程序訪問具體數(shù)據(jù)時(shí)部需要經(jīng)過GFSMaster，因此，避免了Master成為訪問瓶頸并發(fā)訪問：由于一個(gè)大數(shù)據(jù)會(huì)存儲(chǔ)在不同的ChunkServer中，應(yīng)用程序可實(shí)現(xiàn)并發(fā)訪問GoogleGFS文件系統(tǒng)GoogleGFS的工作原理GFS租約機(jī)制設(shè)計(jì)租約機(jī)制的目的是為了最小化Master節(jié)點(diǎn)的管理負(fù)擔(dān)。租約的初始超時(shí)設(shè)置為60秒。不過，只要Chunk被修改了，主Chunk就可以申請(qǐng)更長(zhǎng)的租期，通常會(huì)得到Master節(jié)點(diǎn)的確認(rèn)并收到租約延長(zhǎng)的時(shí)間。這些租約延長(zhǎng)請(qǐng)求和批準(zhǔn)的信息通常都是附加在Master節(jié)點(diǎn)和Chunk服務(wù)器之間的心跳消息中來傳遞。GoogleGFS文件系統(tǒng)GoogleGFS的工作原理數(shù)據(jù)流為了提高網(wǎng)絡(luò)效率，GFS采取了把數(shù)據(jù)流和控制流分開的措施。在控制流從客戶機(jī)到主Chunk、然后再到所有二級(jí)副本的同時(shí)，數(shù)據(jù)以管道的方式，順序的沿著一個(gè)精心選擇的Chunk服務(wù)器鏈推送。我們的目標(biāo)是充分利用每臺(tái)機(jī)器的帶寬，避免網(wǎng)絡(luò)瓶頸和高延時(shí)的連接，最小化推送所有數(shù)據(jù)的延時(shí)。GoogleGFS文件系統(tǒng)GoogleGFS的工作原理數(shù)據(jù)完整性

GFS把每個(gè)Chunk都分成64KB大小的塊。每個(gè)塊都對(duì)應(yīng)一個(gè)32位的Checksum。和其它元數(shù)據(jù)一樣，Checksum與其它的用戶數(shù)據(jù)是分開的，并且保存在內(nèi)存和硬盤上，同時(shí)也記錄操作日志。對(duì)于讀操作來說，在把數(shù)據(jù)返回給客戶端或者其它的Chunk服務(wù)器之前，Chunk服務(wù)器會(huì)校驗(yàn)讀取操作涉及的范圍內(nèi)的塊的Checksum。因此Chunk服務(wù)器不會(huì)把錯(cuò)誤數(shù)據(jù)傳遞到其它的機(jī)器上。如果發(fā)生某個(gè)塊的Checksum不正確，Chunk服務(wù)器返回給請(qǐng)求者一個(gè)錯(cuò)誤信息，并且通知Master服務(wù)器這個(gè)錯(cuò)誤。作為回應(yīng)，請(qǐng)求者應(yīng)當(dāng)從其它副本讀取數(shù)據(jù)，Master服務(wù)器也會(huì)從其它副本克隆數(shù)據(jù)進(jìn)行恢復(fù)。當(dāng)一個(gè)新的副本就緒后，Master服務(wù)器通知副本錯(cuò)誤的Chunk服務(wù)器刪掉錯(cuò)誤的副本。GoogleGFS文件系統(tǒng)GoogleGFS的工作原理Chunk副本的3種機(jī)制創(chuàng)建：當(dāng)Master節(jié)點(diǎn)創(chuàng)建一個(gè)Chunk時(shí)，它會(huì)選擇在哪里放置初始的空的副本。Master節(jié)點(diǎn)會(huì)考慮幾個(gè)因素。（1）GFS希望在低于平均硬盤使用率的Chunk服務(wù)器上存儲(chǔ)新的副本。這樣的做法最終能夠平衡Chunk服務(wù)器之間的硬盤使用率。（2）GFS希望限制在每個(gè)Chunk服務(wù)器上”最近”的Chunk創(chuàng)建操作的次數(shù)。雖然創(chuàng)建操作本身是廉價(jià)的，但是創(chuàng)建操作也意味著隨之會(huì)有大量的寫入數(shù)據(jù)的操作，因?yàn)镃hunk在Writer真正寫入數(shù)據(jù)的時(shí)候才被創(chuàng)建，而在我們的”追加一次，讀取多次”的工作模式下，Chunk一旦寫入成功之后就會(huì)變?yōu)橹蛔x的了。（3）GFS希望把Chunk的副本分布在多個(gè)機(jī)架之間。GoogleGFS文件系統(tǒng)GoogleGFS的工作原理Chunk副本的3種機(jī)制重新復(fù)制：當(dāng)Chunk的有效副本數(shù)量少于用戶指定的復(fù)制因數(shù)的時(shí)候，Master節(jié)點(diǎn)會(huì)重新復(fù)制它。這可能是由幾個(gè)原因引起的：一個(gè)Chunk服務(wù)器不可用了，Chunk服務(wù)器報(bào)告它所存儲(chǔ)的一個(gè)副本損壞了，Chunk服務(wù)器的一個(gè)磁盤因?yàn)殄e(cuò)誤不可用了，或者Chunk副本的復(fù)制因數(shù)提高了。每個(gè)需要被重新復(fù)制的Chunk都會(huì)根據(jù)幾個(gè)因素進(jìn)行排序。一個(gè)因素是Chunk現(xiàn)有副本數(shù)量和復(fù)制因數(shù)相差多少。例如，丟失兩個(gè)副本的Chunk比丟失一個(gè)副本的Chunk有更高的優(yōu)先級(jí)。另外，GFS優(yōu)先重新復(fù)制活躍（live）文件的Chunk而不是最近剛被刪除的文件的Chunk。最后，為了最小化失效的Chunk對(duì)正在運(yùn)行的應(yīng)用程序的影響，我們提高會(huì)阻塞客戶機(jī)程序處理流程的Chunk的優(yōu)先級(jí)。Master節(jié)點(diǎn)選擇優(yōu)先級(jí)最高的Chunk，然后命令某個(gè)Chunk服務(wù)器直接從可用的副本”克隆”一個(gè)副本出來。選擇新副本的位置的策略和創(chuàng)建時(shí)類似：平衡硬盤使用率、限制同一臺(tái)Chunk服務(wù)器上的正在進(jìn)行的克隆操作的數(shù)量、在機(jī)架間分布副本。為了防止克隆產(chǎn)生的網(wǎng)絡(luò)流量大大超過客戶機(jī)的流量，Master節(jié)點(diǎn)對(duì)整個(gè)集群和每個(gè)Chunk服務(wù)器上的同時(shí)進(jìn)行的克隆操作的數(shù)量都進(jìn)行了限制。另外，Chunk服務(wù)器通過調(diào)節(jié)它對(duì)源Chunk服務(wù)器讀請(qǐng)求的頻率來限制它用于克隆操作的帶寬。GoogleGFS文件系統(tǒng)GoogleGFS的工作原理Chunk副本的3種機(jī)制重新負(fù)載均衡：最后，Master服務(wù)器周期性地對(duì)副本進(jìn)行重新負(fù)載均衡：它檢查當(dāng)前的副本分布情況，然后移動(dòng)副本以便更好的利用硬盤空間、更有效的進(jìn)行負(fù)載均衡。而且在這個(gè)過程中，Master服務(wù)器逐漸的填滿一個(gè)新的Chunk服務(wù)器，而不是在短時(shí)間內(nèi)用新的Chunk填滿它，以至于過載。新副本的存儲(chǔ)位置選擇策略和上面討論的相同。另外，Master節(jié)點(diǎn)必須選擇哪個(gè)副本要被移走。通常情況，Master節(jié)點(diǎn)移走那些剩余空間低于平均值的Chunk服務(wù)器上的副本，從而平衡系統(tǒng)整體的硬盤使用率。GoogleGFS文件系統(tǒng)GoogleGFS的工作原理過期失效的副本檢測(cè)當(dāng)Chunk服務(wù)器失效時(shí)，Chunk的副本有可能因錯(cuò)失了一些修改操作而過期失效。Master節(jié)點(diǎn)保存了每個(gè)Chunk的版本號(hào)，用來區(qū)分當(dāng)前的副本和過期副本。無論何時(shí)，只要Master節(jié)點(diǎn)和Chunk簽訂一個(gè)新的租約，它就增加Chunk的版本號(hào)，然后通知最新的副本。Master節(jié)點(diǎn)和這些副本都把新的版本號(hào)記錄在它們持久化存儲(chǔ)的狀態(tài)信息中。這個(gè)動(dòng)作發(fā)生在任何客戶機(jī)得到通知以前，因此也是對(duì)這個(gè)Chunk開始寫之前。如果某個(gè)副本所在的Chunk服務(wù)器正好處于失效狀態(tài)，那么副本的版本號(hào)就不會(huì)被增加。Master節(jié)點(diǎn)在這個(gè)Chunk服務(wù)器重新啟動(dòng)，并且向Master節(jié)點(diǎn)報(bào)告它擁有的Chunk的集合以及相應(yīng)的版本號(hào)的時(shí)候，就會(huì)檢測(cè)出它包含過期的Chunk。如果Master節(jié)點(diǎn)看到一個(gè)比它記錄的版本號(hào)更高的版本號(hào)，Master節(jié)點(diǎn)會(huì)認(rèn)為它和Chunk服務(wù)器簽訂租約的操作失敗了，因此會(huì)選擇更高的版本號(hào)作為當(dāng)前的版本號(hào)。Master節(jié)點(diǎn)在例行的垃圾回收過程中移除所有的過期失效副本。在此之前，Master節(jié)點(diǎn)在回復(fù)客戶機(jī)的Chunk信息請(qǐng)求的時(shí)候，簡(jiǎn)單的認(rèn)為那些過期的塊根本就不存在。另外一重保障措施是，Master節(jié)點(diǎn)在通知客戶機(jī)哪個(gè)Chunk服務(wù)器持有租約、或者指示Chunk服務(wù)器從哪個(gè)Chunk服務(wù)器進(jìn)行克隆時(shí)，消息中都附帶了Chunk的版本號(hào)?？蛻魴C(jī)或者Chunk服務(wù)器在執(zhí)行操作時(shí)都會(huì)驗(yàn)證版本號(hào)以確?？偸窃L問當(dāng)前版本的數(shù)據(jù)。GoogleGFS文件系統(tǒng)GoogleGFS的基本構(gòu)架和工作原理GFS的系統(tǒng)管理技術(shù)大規(guī)模集群安裝技術(shù)：如何在一個(gè)成千上萬(wàn)個(gè)節(jié)點(diǎn)的集群上迅速部署GFS，升級(jí)管理和維護(hù)等故障檢測(cè)技術(shù)：GFS是構(gòu)建在不可靠的廉價(jià)計(jì)算機(jī)之上的文件系統(tǒng)，節(jié)點(diǎn)數(shù)多，故障頻繁，如何快速檢測(cè)、定位、恢復(fù)或隔離故障節(jié)點(diǎn)節(jié)點(diǎn)動(dòng)態(tài)加入技術(shù)：當(dāng)新的節(jié)點(diǎn)加入時(shí)，需要能自動(dòng)安裝和部署GFS節(jié)能技術(shù)：服務(wù)器的耗電成本大于購(gòu)買成本，Google為每個(gè)節(jié)點(diǎn)服務(wù)器配置了蓄電池替代UPS，大大節(jié)省了能耗。GoogleGFS文件系統(tǒng)目錄GoogleMapReduceGoogle分布式文件系統(tǒng)GFSGoogle分布式結(jié)構(gòu)化數(shù)據(jù)表BigTableBigTable的基本作用和設(shè)計(jì)思想

GFS是一個(gè)文件系統(tǒng)，難以提供對(duì)結(jié)構(gòu)化數(shù)據(jù)的存儲(chǔ)和訪問管理。為此，Google在GFS之上又設(shè)計(jì)了一個(gè)結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)和訪問管理系統(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)化存儲(chǔ)問題。但與傳統(tǒng)的關(guān)系數(shù)據(jù)庫(kù)相比，其結(jié)構(gòu)化粒度沒有那么高，也沒有事務(wù)處理等能力，因此，它并不是真正意義上的數(shù)據(jù)庫(kù)。GoogleBigTableBigTable設(shè)計(jì)動(dòng)機(jī)和目標(biāo)主要?jiǎng)訖C(jī)需要存儲(chǔ)多種數(shù)據(jù) Google提供的服務(wù)很多，序處理的數(shù)據(jù)類型也很多，如URL,網(wǎng)頁(yè),圖片,地圖數(shù)據(jù),email,用戶的個(gè)性化設(shè)置等海量的服務(wù)請(qǐng)求Google是目前世界上最繁忙的系統(tǒng)，因此，需要有高性能的請(qǐng)求和數(shù)據(jù)處理能力商用數(shù)據(jù)庫(kù)無法適用

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

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

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

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

將其分配給一個(gè)空間足夠大的

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

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

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

SSTable是BigTable內(nèi)部的基本存儲(chǔ)結(jié)構(gòu)，以GFS文件形式存儲(chǔ)在GFS文件系統(tǒng)中。一個(gè)SSTable實(shí)際上對(duì)應(yīng)于GFS中的一個(gè)64MB的數(shù)據(jù)塊(Chunk)SSTable中的數(shù)據(jù)進(jìn)一步劃分為64KB的子塊，因此一個(gè)SSTable可以有多達(dá)1千個(gè)這樣的子塊。為了維護(hù)這些子塊的位置信息，需要使用一個(gè)Index索引。Index64Kblock64Kblock64KblockSSTableGoogleBigTableBigTable基本構(gòu)架子表服務(wù)器子表數(shù)據(jù)格式

概念上子表是整個(gè)大表的多行數(shù)據(jù)劃分后構(gòu)成。而一個(gè)子表服務(wù)器上的子表將進(jìn)一步由很多個(gè)SSTAble構(gòu)成，每個(gè)SSTable構(gòu)成最終的在底層GFS中的存儲(chǔ)單位。Index64Kblock64Kblock64KblockSSTableIndex64Kblock64Kblock64KblockSSTableTabletStart:aardvarkEnd:appleGoogleBigTableBigTable基本構(gòu)架子表服務(wù)器子表數(shù)據(jù)格式

一個(gè)SSTable還可以為不同的子表所共享，以避免同樣數(shù)據(jù)的重復(fù)存儲(chǔ)。

SSTableSSTableSSTableSSTableTabletaardvarkappleTabletapple_two_EboatGoogleBigTableBigTable基本構(gòu)架子表服務(wù)器子表尋址子表地址以3級(jí)B+樹形式進(jìn)行索引；首先從Chubby

服務(wù)器中取得根子表，由根子表找到二級(jí)索引

指標(biāo)，最后獲取最終的SSTable的位置

GoogleBigTableBigTable基本構(gòu)架子表服務(wù)器MinorCompaction隨著寫操作的執(zhí)行，memtable的大小不斷增加。當(dāng)memtable的尺寸到達(dá)一個(gè)門限值的時(shí)候，這個(gè)memtable就會(huì)被凍結(jié)，然后創(chuàng)建一個(gè)新的memtable；被凍結(jié)住memtable會(huì)被轉(zhuǎn)換成SSTable，然后寫入GFS。GoogleBigTableBigTable基本構(gòu)架子表服務(wù)器MergingCompaction每一次MinorCompaction都會(huì)創(chuàng)建一個(gè)新的SSTable。通過定期在后臺(tái)執(zhí)行MergingCompaction過程合并文件，限制這類文件的數(shù)量。MergingCompaction過程讀取一些SSTable和memtable的內(nèi)容，合并成一個(gè)新的SSTable。MajorCompaction

MajorCompaction過程生成的SSTable不包含已經(jīng)刪除的信息或數(shù)據(jù)。Bigtable循環(huán)掃描它所有的Tablet，并且定期對(duì)它們執(zhí)行MajorCompaction。MajorCompaction機(jī)制允許Bigtable回收已經(jīng)刪除的數(shù)據(jù)占有的資源，并且確保BigTable能及時(shí)清除已經(jīng)刪除的數(shù)據(jù)。GoogleBigTableBigTable基本構(gòu)架優(yōu)化壓縮每個(gè)SSTable的塊（塊的大小由局部性群組的優(yōu)化參數(shù)定）都使用用戶指定的壓縮格式來壓縮。雖然分塊壓縮浪費(fèi)了少量空間（相比于對(duì)整個(gè)SSTable進(jìn)行壓縮，分塊壓縮壓縮率較低），但是，在只讀取SSTable的一小部分?jǐn)?shù)據(jù)的時(shí)候就不必解壓整個(gè)文件了。使用了“兩遍”的、可定制的壓縮方式。第一遍采用BentleyandMcIlroy’s方式，這種方式在一個(gè)很大的掃描窗口里對(duì)常見的長(zhǎng)字符串進(jìn)行壓縮；第二遍是采用快速壓縮算法，即在一個(gè)16KB的小掃描窗口中尋找重復(fù)數(shù)據(jù)。兩個(gè)壓縮的算法都很快，在現(xiàn)在的機(jī)器上，壓縮的速率達(dá)到100-200MB/s，解壓的速率達(dá)到400-1000MB/s。GoogleBigTableBigTable基本構(gòu)架優(yōu)化Bloomfilter一個(gè)讀操作必須讀取構(gòu)成Tablet狀態(tài)的所有SSTable的數(shù)據(jù)。如果這些SSTable不在內(nèi)存中，那么就需要多次訪問硬盤。我們通過允許客戶程序?qū)μ囟ň植啃匀航M的SSTable指定Bloom過濾器，來減少硬盤訪問的次數(shù)。我們可以使用Bloom過濾器查詢一個(gè)SSTable是否包含了特定行和列的數(shù)據(jù)。對(duì)于某些特定應(yīng)用程序，我們只付出了少量的、用于存儲(chǔ)Bloom過濾器的內(nèi)存的代價(jià)，就換來了讀操作顯著減少的磁盤訪問的次數(shù)。使用Bloom過濾器也隱式的達(dá)到了當(dāng)應(yīng)用程序訪問不存在的行或列時(shí)，大多數(shù)時(shí)候我們都不需要訪問硬盤的目的。GoogleBigTableBigTable基本構(gòu)架Bloomfilter原理如需要判斷一個(gè)元素是不是在一個(gè)集合中，我們通常做法是把所有元素保存下來，然后通過比較知道它是不是在集合內(nèi)，鏈表、樹都是基于這種思路，當(dāng)集合內(nèi)元素個(gè)數(shù)的變大，我們需要的空間和時(shí)間都線性變大，檢索速度也越來越慢。Bloomfilter采用的是哈希函數(shù)的方法，將一個(gè)元素映射到一個(gè)m長(zhǎng)度的陣列上的一個(gè)點(diǎn)，當(dāng)這個(gè)點(diǎn)是1時(shí)，那么這個(gè)元素在集合內(nèi)，反之則不在集合內(nèi)。這個(gè)方法的缺點(diǎn)就是當(dāng)檢測(cè)的元素很多的時(shí)候可能有沖突，解決方法就是使用k個(gè)哈希函數(shù)對(duì)應(yīng)k個(gè)點(diǎn)，如果所有點(diǎn)都是1的話，那么元素在集合內(nèi)，如果有0的話，元素則不在集合內(nèi)。初始狀態(tài)時(shí)，BloomFilter是一個(gè)包含m位的位數(shù)組，每一位都置為0。GoogleBigTableBigTable基本構(gòu)架Bloomfilter為了表達(dá)S={x1,x2,…,xn}這樣一個(gè)n個(gè)元素的集合，BloomFilter使用k個(gè)相互獨(dú)立的哈希函數(shù)（HashFunction），它們分別將集合中的每個(gè)元素映射到{1,…,m}的范圍中。對(duì)任意一個(gè)元素x，第i個(gè)哈希函數(shù)映射的位置hi(x)就會(huì)被置為1（1≤i≤k）。注意，如果一個(gè)位置多次被置為1，那么只有第一次會(huì)起作用，后面幾次將沒有任何效果。在下圖中，k=3，且有兩個(gè)哈希函數(shù)選中同一個(gè)位置（從左邊數(shù)第五位）。在判斷y是否屬于這個(gè)集合時(shí)，我們對(duì)y應(yīng)用k次哈希函數(shù)，如果所有hi(y)的位置都是1（1≤i≤k），那么我們就認(rèn)為y是集合中的元素，否則就認(rèn)為y不是集合中的元素。下圖中y1就不是集合中的元素。y2或者屬于這個(gè)集合，或者剛好是一個(gè)falsepositive。GoogleBigTable目錄大數(shù)據(jù)起源Hadoop1.0Hadoop2.0商用環(huán)境hadoopHadoop是一個(gè)開源的軟件框架，它支持?jǐn)?shù)據(jù)密集型的分布式應(yīng)用，許可授權(quán)隸屬于Apachev2license.可以在成千上萬(wàn)臺(tái)獨(dú)立的計(jì)算機(jī)上運(yùn)行。Hadoop源自于Google的MapReduce和GoogleFileSystem(GFS)兩篇論文?，F(xiàn)在通常認(rèn)為完整的ApacheHadoop‘平臺(tái)’由Hadoop內(nèi)核、MapReduce和HDFS組成，以及若干相關(guān)的項(xiàng)目——包括ApacheHive、ApacheHbase等等Hadoop介紹

HDFS基本構(gòu)架對(duì)等于GFS

Master對(duì)等于GFS

ChunkServer應(yīng)用程序HDFS客戶端文件名或數(shù)據(jù)塊號(hào)數(shù)據(jù)塊號(hào)，數(shù)據(jù)塊位置HDFSNameNodeDataNode數(shù)據(jù)DataNode數(shù)據(jù)DataNode數(shù)據(jù)Hadoop的分布式文件系統(tǒng)HDFSHadoopMapReduce基本構(gòu)架與工作過程2.Hadoop

MapReduce的基本工作原理對(duì)等于GoogleMapReduce中的Master對(duì)等于GoogleMapReduce中的WorkerdatanodedaemonLinuxfilesystem…tasktrackerslavenodedatanodedaemonLinuxfilesystem…tasktrackerslavenodedatanodedaemonLinuxfilesystem…tasktrackerslavenodenamenodenamenodedaemonjobsubmissionnodejobtrackerHadoop介紹

HadoopMapReduce和HDFS數(shù)據(jù)存儲(chǔ)與計(jì)算節(jié)點(diǎn)構(gòu)架Hadoop1.0X86PC集群本機(jī)硬盤本機(jī)硬盤本機(jī)硬盤本機(jī)硬盤本機(jī)硬盤本機(jī)硬盤數(shù)據(jù)節(jié)點(diǎn)Datanode數(shù)據(jù)節(jié)點(diǎn)Datanode數(shù)據(jù)節(jié)點(diǎn)Datanode數(shù)據(jù)節(jié)點(diǎn)Datanode數(shù)據(jù)節(jié)點(diǎn)Datanode管理節(jié)點(diǎn)Datanode備份管理節(jié)點(diǎn)Datanode萬(wàn)兆交換萬(wàn)兆交換數(shù)據(jù)查詢（Hbase）運(yùn)算與處理（Map-Reduce)數(shù)據(jù)提取（HIVE）ETLOozieTaskTracker(MapTask)TaskTracker(MapTask)中間結(jié)果中間結(jié)果TaskTracker(ReduceTask)輸出數(shù)據(jù)JobTracker任務(wù)調(diào)度任務(wù)調(diào)度狀態(tài)監(jiān)控狀態(tài)監(jiān)控任務(wù)管理調(diào)度管理Hadoop處理層-設(shè)備及拓?fù)涮幚韺?軟件技術(shù)架構(gòu)SQL-Script列式存儲(chǔ)Hive架構(gòu)轉(zhuǎn)化為Map-Reduce程序列式索引Hadoop1.0架構(gòu)下的混搭處理中心X86PC集群本機(jī)硬盤本機(jī)硬盤本機(jī)硬盤本機(jī)硬盤本機(jī)硬盤本機(jī)硬盤數(shù)據(jù)節(jié)點(diǎn)Datanode數(shù)據(jù)節(jié)點(diǎn)Datanode數(shù)據(jù)節(jié)點(diǎn)Datanode數(shù)據(jù)節(jié)點(diǎn)Datanode數(shù)據(jù)節(jié)點(diǎn)Datanode管理節(jié)點(diǎn)Namenode備份管理節(jié)點(diǎn)Namenode萬(wàn)兆交換萬(wàn)兆交換數(shù)據(jù)查詢（Hbase）運(yùn)算與處理（Map-Reduce)數(shù)據(jù)提?。℉IVE）ETL數(shù)據(jù)存儲(chǔ)：磁盤陣列數(shù)據(jù)計(jì)算：

數(shù)據(jù)服務(wù)器HadoopRDB&內(nèi)存庫(kù)RDB內(nèi)存數(shù)據(jù)庫(kù)處理層-設(shè)備及拓?fù)涮幚韺?軟件技術(shù)架構(gòu)。主ID，億級(jí)查詢，毫秒級(jí)。次級(jí)索引查詢，秒級(jí)。外部提供noSql查詢方式。使用CoprocessorMR程序，滿足臨時(shí)性分析。。億級(jí)數(shù)據(jù)，支持秒級(jí)查詢。支持SQL方式提取數(shù)據(jù)。支持?jǐn)?shù)據(jù)匯總，數(shù)據(jù)提取的快速開發(fā)。通過MR開發(fā)，滿足絕大部分?jǐn)?shù)據(jù)處理需求。支持十億級(jí)，百億級(jí)的數(shù)據(jù)分析與開發(fā)。結(jié)合Mahout，滿足對(duì)大數(shù)據(jù)的分析需求。通過結(jié)合文本處理技術(shù)，滿足非結(jié)構(gòu)化文本數(shù)據(jù)需求。OLTP及數(shù)據(jù)量較小的OLAP管理節(jié)點(diǎn)備份保證安全數(shù)據(jù)冗余參數(shù)設(shè)置，保障基礎(chǔ)數(shù)據(jù)安全實(shí)時(shí)數(shù)據(jù)查詢（Impala）。Jdbc/ODBC列式存儲(chǔ)HRegion-Server混搭架構(gòu)解決各類數(shù)據(jù)訪問需求基礎(chǔ)存儲(chǔ)（HDFS）滿足萬(wàn)分之一秒訪問并行查詢調(diào)度查詢優(yōu)化器本機(jī)硬盤本機(jī)硬盤MPP萬(wàn)兆交換ODSLinux：FSDW&DMDB-File。Jdbc/ODBC。支持SQL方式提取數(shù)據(jù)。支持關(guān)聯(lián)性查詢。對(duì)內(nèi)存有效利用。對(duì)網(wǎng)絡(luò)帶寬有依賴Hbase&HiveHBase原理復(fù)雜查詢和二級(jí)索引HBase與Hive集成HBase簡(jiǎn)介HBase是分布式的、面向列的開源數(shù)據(jù)庫(kù)HBase是GoogleBigtable的開源實(shí)現(xiàn)底層基于Hadoop，HDFS為HBase提供高可靠性的底層存儲(chǔ)支持，MapReduce為HBase提供高性能的計(jì)算能力Zookeeper為HBase提供了穩(wěn)定服務(wù)和failover機(jī)制HBase簡(jiǎn)介HBase中有兩張?zhí)厥獾腡able，-ROOT-和.META..META.：記錄了用戶表的Region信息，.META.可以有多個(gè)regoin-ROOT-：記錄了.META.表的Region信息，-ROOT-只有一個(gè)region?Zookeeper中記錄了-ROOT-表的locationClient訪問用戶數(shù)據(jù)之前需要首先訪問zookeeper，然后訪問-ROOT-表，接著訪問.META.表，最后才能找到用戶數(shù)據(jù)的位置去訪問，中間需要多次網(wǎng)絡(luò)操作，不過client端會(huì)做cache緩存。ZookeeperQuorum中除了存儲(chǔ)了-ROOT-表的地址和HMaster的地址，HRegionServer也會(huì)把自己以Ephemeral方式注冊(cè)到Zookeeper中，使得HMaster可以隨時(shí)感知到各個(gè)HRegionServer的健康狀態(tài)。HMaster沒有單點(diǎn)問題，HBase中可以啟動(dòng)多個(gè)HMaster，通過Zookeeper的MasterElection機(jī)制保證總有一個(gè)Master運(yùn)行當(dāng)HRegionServer意外終止后，HMaster會(huì)通過Zookeeper感知到HBase數(shù)據(jù)模型RowKeycontentsanchorCMy.look.caTimestampvalueTimestampvalueTimestampvalueCn.wwwt3<html>…t8CNNt9CNN.comt5<html>…t6<html>…RowKey：table主鍵，HBase中記錄按照RowKey排序Timestamp：時(shí)間戳，HBase可以保存多版本的數(shù)據(jù)ColumnFamily，列簇，HBase中的集中存儲(chǔ)單元ColumnQualifier，與ColumnFamily一起標(biāo)記某一列HFile結(jié)構(gòu)名稱字節(jié)數(shù)說明keyLength4表示Key所占的總字節(jié)數(shù)valueLength4表示Value所占的總字節(jié)數(shù)rowLength2表示rowKey所占的字節(jié)數(shù)rowrowLength數(shù)據(jù)的rowKeycolumnFamilyLength1表示列族名稱所占的字節(jié)數(shù)columnFamilycolumnFamilyLength列族名稱columnQualifier

列名與columnFamily一起標(biāo)記唯一列timestamp8時(shí)間戳type1Key類型，比如是新增(Put)，還是刪除(Delete)valuevalueLength列值KeyValue結(jié)構(gòu)說明Hfile結(jié)構(gòu)：KeyValue結(jié)構(gòu)：列存儲(chǔ)RowKey基本信息成績(jī)名字性別語(yǔ)文數(shù)學(xué)TimestampvalueTimestampvalueTimestampvalueTimestampvalue小明keyt1小明t2男t580t990t483t893t385t795文件1文件21724小明key4成績(jī)語(yǔ)文t5180HBase系統(tǒng)架構(gòu)Client通過zookeeper與master通信進(jìn)行管理類操作client與regionserver通信進(jìn)行數(shù)據(jù)讀寫操作存儲(chǔ)-ROOT-表地址存儲(chǔ)HMaster的地址協(xié)調(diào)多個(gè)HMaster防止單點(diǎn)問題管理用戶對(duì)表的操作調(diào)整Region分布，負(fù)載均衡管理Regionsplit后的region重分布RegionServer宕機(jī)后region的遷移工作響應(yīng)用戶的I/O請(qǐng)求，向HDFS中讀寫文件HBase數(shù)據(jù)訪問流程clientzookeeper關(guān)鍵文件：/hbase/hbaseid

集群ID，跟存儲(chǔ)在HDFS上的hbase.id文件中的一致/hbase/master服務(wù)器名稱/hbase/root-region-server持有-ROOT-表regions的regionserver的服務(wù)器名稱-ROOT-表記錄.META.的Region信息，該region永遠(yuǎn)不split，只會(huì)有一個(gè)Region。表數(shù)據(jù)結(jié)構(gòu)：rowkey：

存儲(chǔ).META.的region的名稱columnFamily：共一個(gè)，為“info”columnQualifier共三個(gè)包含：regioninfo：保存region的信息，包括name、startkey、 endkey等信息server：該region所在RegionServerserverstartcord：region所在RegionServer啟動(dòng)時(shí)間RowKeyinforegioninfoserverserverstartcord.META.,,1NAME=>'.META.,,1',STARTKEY=>'',ENDKEY=>'',ENCODED=>1028785192,}cloud204:600201371430827702UserTable,100,1371430844857.de0b50NAME=>UserTable,100,1371430844857.de0b50',STARTKEY=>‘100',ENDKEY=>‘200',ENCODED=>de0b50,}cloud199:600201371430844857.META.表記錄用戶表的Region信息：表數(shù)據(jù)結(jié)構(gòu)與-ROOT-相似：rowkey：

存儲(chǔ)用戶表的region的名稱columnFamily：共一個(gè)，為“info”columnQualifier共三個(gè)包含：regioninfo：保存region的信息，包括name、startkey、 endkey等信息server：該region所在RegionServerserverstartcord：region所在RegionServer啟動(dòng)時(shí)間HRegionServer結(jié)構(gòu)每個(gè)HRegion對(duì)應(yīng)Table中的Region，由多個(gè)HStore組成HBase中的集中的存儲(chǔ)單元，對(duì)應(yīng)Table中的ColumnFamily，由MemStore和StoreFile組成HRegionServer：包含多個(gè)HRegionHRegionServer結(jié)構(gòu)Region合并和分割HStore存儲(chǔ)是HBase存儲(chǔ)的核心了，其中由兩部分組成，一部分是MemStore，一部分是StoreFiles。1.MemStore是SortedMemoryBuffer，用戶寫入的數(shù)據(jù)首先會(huì)放入MemStore，當(dāng)MemStore滿了以后會(huì)Flush成一個(gè)StoreFile（底層實(shí)現(xiàn)是HFile）.2.當(dāng)StoreFile文件數(shù)量增長(zhǎng)到一定閾值，會(huì)觸發(fā)Compact合并操作，將多個(gè)StoreFiles合并成一個(gè)StoreFile，合并過程中會(huì)進(jìn)行版本合并和數(shù)據(jù)刪除，因此可以看出HBase其實(shí)只有增加數(shù)據(jù)，所有的更新和刪除操作都是在后續(xù)的compact過程中進(jìn)行的，這使得用戶的寫操作只要進(jìn)入內(nèi)存中就可以立即返回，保證了HBaseI/O的高性能。3.當(dāng)StoreFilesCompact后，會(huì)逐步形成越來越大的StoreFile，當(dāng)單個(gè)StoreFile大小超過一定閾值后，會(huì)觸發(fā)Split操作，同時(shí)把當(dāng)前RegionSplit成2個(gè)Region，父Region會(huì)下線，新Split出的2個(gè)孩子Region會(huì)被HMaster分配到相應(yīng)的HRegionServer上，使得原先1個(gè)Region的壓力得以分流到2個(gè)Region上。HStore中數(shù)據(jù)寫入流程PUTFlushCompactSplitClient端PUT數(shù)據(jù)數(shù)據(jù)寫入MemStore中MemStore寫滿后執(zhí)行flush數(shù)據(jù)被flush為StoreFileStoreFile數(shù)量增長(zhǎng)到閥值，觸發(fā)Compact操作多個(gè)StoreFile合并成一個(gè)StoreFile版本合并，數(shù)據(jù)刪除Region大小達(dá)到閥值，執(zhí)行Split操作一個(gè)Region會(huì)Split成成兩個(gè)Master上線新的兩個(gè)Region舊的Region下線HBaseCoprocessorHBaseCoprocessor實(shí)現(xiàn)目的：HBase0.92版本新增加特性，為了解決如下問題HBase無法輕易建立“二級(jí)索引”執(zhí)行求和、計(jì)數(shù)、排序等操作比較困難，必須通過mapreduce實(shí)現(xiàn)，對(duì)于簡(jiǎn)單的統(tǒng)計(jì)或聚合計(jì)算時(shí)，可能會(huì)因?yàn)榫W(wǎng)絡(luò)開銷大而帶來性能問題靈感來源：靈感來源于bigtable的協(xié)處理器，包含如下特性每個(gè)表服務(wù)器的任意子表都可以運(yùn)行代碼客戶端能夠直接訪問數(shù)據(jù)表的行，多行讀寫會(huì)自動(dòng)分片成多個(gè)并行的RPC調(diào)用提供接口：RegionObserver：提供客戶端的數(shù)據(jù)操縱事件鉤子：Get、Put、Delete、Scan等WALObserver：提供WAL相關(guān)操作鉤子MasterObserver：提供DDL-類型的操作鉤子。如創(chuàng)建、刪除、修改數(shù)據(jù)表等Endpoint：終端是動(dòng)態(tài)RPC插件的接口，它的實(shí)現(xiàn)代碼被安裝在服務(wù)器端，能夠通過HBaseRPC調(diào)用喚醒應(yīng)用范圍：通過使用RegionObserver接口可以實(shí)現(xiàn)二級(jí)索引的創(chuàng)建和維護(hù)通過使用Endpoint接口，在對(duì)數(shù)據(jù)進(jìn)行簡(jiǎn)單排序和sum，count等統(tǒng)計(jì)操作時(shí)，能夠極大提高性能RegionObserver工作原理RegionObserver提供客戶端的數(shù)據(jù)操縱事件鉤子，Get、Put、Delete、Scan，使用此功能能夠解決主表以及多個(gè)索引表之間數(shù)據(jù)一致性的問題CoprocessorEndpoint2.客戶端通過調(diào)用count方法查詢，等待查詢結(jié)果1.操作region上數(shù)據(jù)的代碼，需要先安裝到服務(wù)器端，客戶端通過接口調(diào)用3.HBase通過RPC喚醒安裝在服務(wù)器端的實(shí)現(xiàn)代碼（CountProtocol），等待執(zhí)行結(jié)果返回，然后通過callback回調(diào)匯聚函數(shù)4.匯聚每個(gè)region上的返回?cái)?shù)據(jù)，更新最終結(jié)果5.返回最終查詢結(jié)果目錄HBase原理復(fù)雜查詢和二級(jí)索引HBase與Hive集成HBase二級(jí)索引HBase二級(jí)索引HBase索引需求：HBase只支持針對(duì)與主鍵key的高性能查詢HBase本身不支持快速的復(fù)雜查詢和join索引的實(shí)現(xiàn)目標(biāo)：高性能的數(shù)據(jù)檢索數(shù)據(jù)的低冗余數(shù)據(jù)的一致性索引的實(shí)現(xiàn)方式：基于表的索引，多個(gè)索引時(shí)每個(gè)索引建一個(gè)表或者建組合索引基于列的索引，所有索引存單張表，每個(gè)索引字段為一個(gè)列簇第三方工具框架：ITHbase，HBase索引的事務(wù)行解決方案，0.92版本以后的HBase已經(jīng)可以通過Coprocessor實(shí)現(xiàn)其功能Lily，基于HBase和SOLR實(shí)現(xiàn)，能夠提供快速的檢索和模糊查詢表索引實(shí)現(xiàn)原理發(fā)揮HBase基于主鍵查詢效率高的特點(diǎn)，添加索引表，把基于索引字段的查詢轉(zhuǎn)換為基于HBase主鍵的查詢業(yè)務(wù)表key101101…………key102102…………key103103…………

基于column1字段的查詢先查Index表Index表101key101102key102103key103rowkeycolumn1column2……表索引的使用和維護(hù)索引表的維護(hù)索引表的使用

CoprocessorUserTableIndexTablePut/DeletepostPut/postDeleteRegionServer通過開發(fā)基于Coprocessor的RegionObserver接口的程序?qū)崿F(xiàn)對(duì)索引表的維護(hù)

CoprocessorUserTableIndexTableScanCoprocessorHMaster

perScan判斷查詢是否走索引

通過索引獲取原表數(shù)據(jù)

不走索引，直接scantable通過Coprocessor的perScan判斷是否是scan索引字段如果走索引，通過IndexTable查到UserTable的key，再去UserTable中查詢ValueHBase組合索引支持更靈活的查詢，對(duì)每個(gè)索引都可以進(jìn)行范圍查詢和等于匹配key……key……key……業(yè)務(wù)表MsisdnIndex表TimeIndex表CellIndex表key……key……key……業(yè)務(wù)表msisdn+cell+timekey組合索引表數(shù)據(jù)冗余較多數(shù)據(jù)一致性維護(hù)更復(fù)雜、數(shù)據(jù)導(dǎo)入速度更慢查詢是需要做多個(gè)表的查詢以及數(shù)據(jù)合并，會(huì)影響查詢效率數(shù)據(jù)的冗余較少查詢效率更高數(shù)據(jù)一致性維護(hù)較容易只支持索引最后一個(gè)字段的范圍查詢，其他索引字段只能等于匹配組合索引多個(gè)索引表HBase列索引將ColumnFamily做為index，多個(gè)index值散落到Qualifier，多個(gè)column值依據(jù)version排列查詢時(shí)，先找到該table索引所在位置，再選擇使用哪一個(gè)索引，再根據(jù)該索引字段的值查出主表的rowkeyrowkeycolumn1column2101102103你好再見table

Akey101key102key103key101key103key102tableB……tableC……tableAkey101101……key102102……key103103……rowkeycolumn1column2……你好你好再見

索引表的columnFamily值為column1，表示是針對(duì)column1的索引

該條數(shù)據(jù)的rowkey為tableA，表示是針對(duì)tableA的索引

column2列數(shù)據(jù)的值為“你好”的有多條數(shù)據(jù)，用HBase的多個(gè)版本號(hào)標(biāo)識(shí)表索引和列索引比較列索引表索引檢索性能需要三次scan只需要一次scan存儲(chǔ)空間在沒有組合索引時(shí)，存儲(chǔ)較節(jié)省在沒有組合索引時(shí)，存儲(chǔ)較節(jié)省事務(wù)容易比較困難，需要使用Coprocessor來保證Join性能較差，只有在建立組合條件Qualifier的時(shí)候性能會(huì)有所改善性能較差，只有在建立組合表索引的時(shí)候性能會(huì)有所改善統(tǒng)計(jì)符合條件的結(jié)果集全表掃描符合條件的結(jié)果集全表掃描其他問題同一個(gè)row里每個(gè)qualifier的version是有大小限制的，version的count總數(shù)需要額外做處理獲取，單個(gè)row數(shù)據(jù)超過split大小時(shí)，會(huì)導(dǎo)致不能compaction或compactionLily簡(jiǎn)介L(zhǎng)ily是一個(gè)HBase和SOLR實(shí)現(xiàn)的數(shù)據(jù)倉(cāng)庫(kù)提供強(qiáng)大的搜索能力，包括全表檢索和模糊查詢?yōu)槿乃饕峁┓?wù)，LilyNode插入內(nèi)容會(huì)同步輸出到SOLRNode，SOLR自己生成全文索引存儲(chǔ)HBase的數(shù)據(jù)，直接供Client使用通過HBase存儲(chǔ)Client寫入的數(shù)據(jù)每個(gè)LilyNode用Zookeeper來發(fā)布自己的存在，Client可以從Zookeeper獲取當(dāng)前有多少個(gè)LilyNode在提供服務(wù)LilyNode架構(gòu)Repository:這個(gè)是Client操作的入口，Client使用基于Avro的協(xié)議操作Repository，在Repository中操作HBase、添加SecondaryIndex信息。WAL：保證Index信息和原始信息的最終一致性。MessageQueue:實(shí)現(xiàn)任務(wù)的異步完成，用HBase里面的一個(gè)Table來實(shí)現(xiàn)。Indexer:Indexer的主要功能是同步SOLR，進(jìn)而實(shí)現(xiàn)全文索引。LinkIndex：根據(jù)Index來查找具體類容的模塊，Repository和Indexer都會(huì)用到。目錄HBase原理復(fù)雜查詢和二級(jí)索引HBase與Hive集成HBase與Hive整合原理使用hive和hbase對(duì)外的接口可以實(shí)現(xiàn)它們之間的整合Hive+HBase的導(dǎo)入和查詢數(shù)據(jù)導(dǎo)入數(shù)據(jù)查詢導(dǎo)入數(shù)據(jù)時(shí)通過HBase端put進(jìn)行通過hive外部表的方式創(chuàng)建表，存儲(chǔ)方式指定為HBaseStorageHandlerHBase整合Hive后，即可以通過Hive的Sql進(jìn)行查詢，也可以通過HBase的API進(jìn)行Scan和get查詢HDFSHBASEHiveputHFilehive-hbase-handler

HDFSHBASEHivescan/getHFilehive-hbase-handler

HivesqlHive與Hive+HBase比較HiveHive+HBaseHBase數(shù)據(jù)存儲(chǔ)Hive基于HDFS存儲(chǔ)基于HBase的HFile基于HFile數(shù)據(jù)導(dǎo)入1.內(nèi)部表通過load或insert兩種方式導(dǎo)入2.外部表直接添加HDFS到hive的鏈接1.內(nèi)部表需要先load進(jìn)hive，再insert到HBase2.外部表先put進(jìn)HBase，再添加到hive的鏈接調(diào)用put接口或者通過MapReduce生成HFile導(dǎo)入性能外部表只添加鏈接，快內(nèi)部表需要對(duì)數(shù)據(jù)進(jìn)行處理，稍慢內(nèi)部表需要先導(dǎo)入hive再insert進(jìn)HBase，慢外部表put進(jìn)HBase,稍快比hive導(dǎo)入慢查詢性能HiveSQL會(huì)轉(zhuǎn)換為MapReduce執(zhí)行，比原生MapReduce稍慢比hive直接從HDFS查詢慢基于key的查詢很快復(fù)雜查詢走M(jìn)apReduce查詢實(shí)現(xiàn)Hive提供了sql，實(shí)現(xiàn)查詢方便通過Hive提供了sql，實(shí)現(xiàn)方便必須通過API接口通過程序?qū)崿F(xiàn)查詢目錄大數(shù)據(jù)起源Hadoop1.0Hadoop2.0商用環(huán)境目前的大數(shù)據(jù)技術(shù)架構(gòu)：ClouderaManagerCluustermanager&monitoringMahoutMachineLearningHiveBatchqueryHBaseNosqlkvstoreImpalaRealTime

queryOozieWorkflowtoolsMapReduceDataprocessingHDFSDataStorageSqoopImport&ExportofRelationaldatabaseFlumeImport&ExportofDataflowsZookeeperClustercoodination目前的大數(shù)據(jù)架構(gòu)目前的大數(shù)據(jù)技術(shù)架構(gòu)的不足：缺少真正意義上的流式場(chǎng)景的