云計算（典藏版）課件 第2章 Google云計算原理與應(yīng)用

第二章Google云計算原理與應(yīng)用of311高級人工智能人才培養(yǎng)叢書2.1Google文件系統(tǒng)GFS2.2分布式數(shù)據(jù)處理MapReduce2.3分布式鎖服務(wù)Chubby2.4分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable2.5分布式存儲系統(tǒng)Megastore2.6

大規(guī)模分布式系統(tǒng)的監(jiān)控基礎(chǔ)架構(gòu)Dapper2.7海量數(shù)據(jù)的交互式分析工具Dremel2.8內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDrill2.9Google應(yīng)用程序引擎全球最大搜索引擎、GoogleMaps、GoogleEarth、Gmail、YouTube等。這些應(yīng)用的共性在于數(shù)據(jù)量巨大，且要面向全球用戶提供實時服務(wù)。2.1Google文件系統(tǒng)GFS2.1.1系統(tǒng)架構(gòu)2.1.2容錯機(jī)制2.1.3系統(tǒng)管理技術(shù)GFS的系統(tǒng)架構(gòu)應(yīng)用程序GFS客戶端(文件名，Chunk索引)(Chunk句柄Chunk位置)GFS主服務(wù)器文件命名空間/foo/barChunk2ef0向數(shù)據(jù)塊服務(wù)器發(fā)出指令數(shù)據(jù)塊服務(wù)器狀態(tài)GFS數(shù)據(jù)塊服務(wù)器Linux文件系統(tǒng)GFS數(shù)據(jù)塊服務(wù)器Linux文件系統(tǒng)……(Chunk句柄，字節(jié)范圍)Chunk數(shù)據(jù)…標(biāo)注：數(shù)據(jù)信息控制信息42.1Google文件系統(tǒng)GFS《云計算》第三版配套PPT課件GFS將整個系統(tǒng)節(jié)點(diǎn)分為三類角色Client（客戶端）Master（主服務(wù)器）ChunkServer（數(shù)據(jù)塊服務(wù)器）Client是GFS提供給應(yīng)用程序的訪問接口，以庫文件的形式提供Master是GFS的管理節(jié)點(diǎn)，負(fù)責(zé)整個文件系統(tǒng)的管理ChunkServer負(fù)責(zé)具體的存儲工作系統(tǒng)節(jié)點(diǎn)GFS52.1Google文件系統(tǒng)GFS《云計算》第三版配套PPT課件GFS的實現(xiàn)機(jī)制客戶端首先訪問Master節(jié)點(diǎn)，獲取交互的ChunkServer信息，然后訪問這些ChunkServer，完成數(shù)據(jù)存取工作。這種設(shè)計方法實現(xiàn)了控制流和數(shù)據(jù)流的分離。Client與Master之間只有控制流，而無數(shù)據(jù)流，極大地降低了Master的負(fù)載。Client與ChunkServer之間直接傳輸數(shù)據(jù)流，同時由于文件被分成多個Chunk進(jìn)行分布式存儲，Client可以同時訪問多個ChunkServer，從而使得整個系統(tǒng)的I/O高度并行，系統(tǒng)整體性能得到提高。62.1Google文件系統(tǒng)GFS《云計算》第三版配套PPT課件GFS的特點(diǎn)1采用中心服務(wù)器模式可以方便地增加ChunkServerMaster掌握系統(tǒng)內(nèi)所有ChunkServer的情況，方便進(jìn)行負(fù)載均衡不存在元數(shù)據(jù)的一致性問題72.1Google文件系統(tǒng)GFS《云計算》第三版配套PPT課件GFS的特點(diǎn)2不緩存數(shù)據(jù)文件操作大部分是流式讀寫，不存在大量重復(fù)讀寫，使用Cache對性能提高不大ChunkServer上數(shù)據(jù)存取使用本地文件系統(tǒng)從可行性看，Cache與實際數(shù)據(jù)的一致性維護(hù)也極其復(fù)雜82.1Google文件系統(tǒng)GFS《云計算》第三版配套PPT課件GFS的特點(diǎn)3在用戶態(tài)下實現(xiàn)利用POSIX編程接口存取數(shù)據(jù)降低了實現(xiàn)難度，提高通用性POSIX接口提供功能更豐富用戶態(tài)下有多種調(diào)試工具M(jìn)aster和ChunkServer都以進(jìn)程方式運(yùn)行，單個進(jìn)程不影響整個操作系統(tǒng)GFS和操作系統(tǒng)運(yùn)行在不同的空間，兩者耦合性降低92.1Google文件系統(tǒng)GFS《云計算》第三版配套PPT課件2.1Google文件系統(tǒng)GFS2.1.1系統(tǒng)架構(gòu)2.1.2容錯機(jī)制2.1.3系統(tǒng)管理技術(shù)Master容錯為了防止Master徹底死機(jī)的情況，GFS還提供了Master遠(yuǎn)程的實時備份Master命名空間（NameSpace），也就是整個文件系統(tǒng)的目錄結(jié)構(gòu)。Chunk與文件名的映射表。Chunk副本的位置信息，每一個Chunk默認(rèn)有三個副本。日志直接保存在各個ChunkServer上當(dāng)Master發(fā)生故障時，在磁盤數(shù)據(jù)保存完好的情況下，可以迅速恢復(fù)以上元數(shù)據(jù)112.1Google文件系統(tǒng)GFS《云計算》第三版配套PPT課件ChunkServer容錯GFS采用副本的方式實現(xiàn)ChunkServer的容錯每一個Chunk有多個存儲副本（默認(rèn)為三個）對于每一個Chunk，必須將所有的副本全部寫入成功，才視為成功寫入相關(guān)的副本出現(xiàn)丟失或不可恢復(fù)等情況，Master自動將該副本復(fù)制到其他ChunkServerGFS中的每一個文件被劃分成多個Chunk，Chunk的默認(rèn)大小是64MB每一個Chunk以Block為單位進(jìn)行劃分，大小為64KB，每一個Block對應(yīng)一個32bit的校驗和122.1Google文件系統(tǒng)GFS《云計算》第三版配套PPT課件2.1Google文件系統(tǒng)GFS2.1.1系統(tǒng)架構(gòu)2.1.2容錯機(jī)制2.1.3系統(tǒng)管理技術(shù)系統(tǒng)管理技術(shù)系統(tǒng)管理技術(shù)大規(guī)模集群安裝技術(shù)故障檢測技術(shù)節(jié)點(diǎn)動態(tài)加入技術(shù)節(jié)能技術(shù)GFS集群中通常有非常多的節(jié)點(diǎn)，需要相應(yīng)的技術(shù)支撐GFS構(gòu)建在不可靠廉價計算機(jī)之上的文件系統(tǒng)，由于節(jié)點(diǎn)數(shù)目眾多，故障發(fā)生十分頻繁新的ChunkServer加入時，只需裸機(jī)加入，大大減少GFS維護(hù)工作量Google采用了多種機(jī)制降低服務(wù)器能耗，如采用蓄電池代替昂貴的UPS142.1Google文件系統(tǒng)GFS《云計算》第三版配套PPT課件第二章Google云計算原理與應(yīng)用of3115高級人工智能人才培養(yǎng)叢書2.1Google文件系統(tǒng)GFS2.2分布式數(shù)據(jù)處理MapReduce2.3分布式鎖服務(wù)Chubby2.4分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable2.5分布式存儲系統(tǒng)Megastore2.6

大規(guī)模分布式系統(tǒng)的監(jiān)控基礎(chǔ)架構(gòu)Dapper2.7海量數(shù)據(jù)的交互式分析工具Dremel2.8內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDrill2.9Google應(yīng)用程序引擎2.2分布式數(shù)據(jù)處理MapReduce2.2.1產(chǎn)生背景2.2.2編程模型2.2.3實現(xiàn)機(jī)制2.2.4案例分析產(chǎn)生背景GoogleMapReduce架構(gòu)設(shè)計師JeffreyDeanJefferyDean設(shè)計一個新的抽象模型，封裝并行處理、容錯處理、本地化計算、負(fù)載均衡的細(xì)節(jié)，還提供了一個簡單而強(qiáng)大的接口。這就是MapReduce172.2分布式數(shù)據(jù)處理MapReduce《云計算》第三版配套PPT課件MapReduce這種并行編程模式思想最早是在1995年提出的。與傳統(tǒng)的分布式程序設(shè)計相比，MapReduce封裝了并行處理、容錯處理、本地化計算、負(fù)載均衡等細(xì)節(jié)，還提供了一個簡單而強(qiáng)大的接口。MapReduce把對數(shù)據(jù)集的大規(guī)模操作，分發(fā)給一個主節(jié)點(diǎn)管理下的各分節(jié)點(diǎn)共同完成，通過這種方式實現(xiàn)任務(wù)的可靠執(zhí)行與容錯機(jī)制。產(chǎn)生背景182.2分布式數(shù)據(jù)處理MapReduce《云計算》第三版配套PPT課件2.2分布式數(shù)據(jù)處理MapReduce2.2.1產(chǎn)生背景2.2.2編程模型2.2.3實現(xiàn)機(jī)制2.2.4案例分析編程模型MapMapMapReduceReduce原始數(shù)據(jù)1原始數(shù)據(jù)2原始數(shù)據(jù)M…結(jié)果1結(jié)果R…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é)果集.202.2分布式數(shù)據(jù)處理MapReduce《云計算》第三版配套PPT課件編程模型Map:(in_key,in_value)

{(keyj,valuej)|j=1…k}Reduce:(key,[value1,…,valuem])(key,final_value)Map輸入?yún)?shù)：in_key和in_value，它指明了Map需要處理的原始數(shù)據(jù)Map輸出結(jié)果：一組<key,value>對，這是經(jīng)過Map操作后所產(chǎn)生的中間結(jié)果

Reduce輸入?yún)?shù)：（key,[value1,…,valuem]）Reduce工作：對這些對應(yīng)相同key的value值進(jìn)行歸并處理Reduce輸出結(jié)果：（key,final_value），所有Reduce的結(jié)果并在一起就是最終結(jié)果212.2分布式數(shù)據(jù)處理MapReduce《云計算》第三版配套PPT課件2.2分布式數(shù)據(jù)處理MapReduce2.2.1產(chǎn)生背景2.2.2編程模型2.2.3實現(xiàn)機(jī)制2.2.4案例分析實現(xiàn)機(jī)制232.2分布式數(shù)據(jù)處理MapReduce《云計算》第三版配套PPT課件實現(xiàn)機(jī)制（1）MapReduce函數(shù)首先把輸入文件分成M塊（2）分派的執(zhí)行程序中有一個主控程序Master（3）一個被分配了Map任務(wù)的Worker讀取并處理相關(guān)的輸入塊（4）這些緩沖到內(nèi)存的中間結(jié)果將被定時寫到本地硬盤，這些數(shù)據(jù)通過分區(qū)函數(shù)分成R個區(qū)（5）當(dāng)Master通知執(zhí)行Reduce的Worker關(guān)于中間<key,value>對的位置時，它調(diào)用遠(yuǎn)程過程，從MapWorker的本地硬盤上讀取緩沖的中間數(shù)據(jù)（6）ReduceWorker根據(jù)每一個唯一中間key來遍歷所有的排序后的中間數(shù)據(jù)，并且把key和相關(guān)的中間結(jié)果值集合傳遞給用戶定義的Reduce函數(shù)（7）當(dāng)所有的Map任務(wù)和Reduce任務(wù)都完成的時候，Master激活用戶程序242.2分布式數(shù)據(jù)處理MapReduce《云計算》第三版配套PPT課件容錯機(jī)制由于MapReduce在成百上千臺機(jī)器上處理海量數(shù)據(jù)，所以容錯機(jī)制是不可或缺的?？偟膩碚f，MapReduce通過重新執(zhí)行失效的地方來實現(xiàn)容錯。Master失效Worker失效Master會周期性地設(shè)置檢查點(diǎn)（checkpoint），并導(dǎo)出Master的數(shù)據(jù)。一旦某個任務(wù)失效，系統(tǒng)就從最近的一個檢查點(diǎn)恢復(fù)并重新執(zhí)行。由于只有一個Master在運(yùn)行，如果Master失效了，則只能終止整個MapReduce程序的運(yùn)行并重新開始。Master會周期性地給Worker發(fā)送ping命令，如果沒有Worker的應(yīng)答，則Master認(rèn)為Worker失效，終止對這個Worker的任務(wù)調(diào)度，把失效Worker的任務(wù)調(diào)度到其他Worker上重新執(zhí)行。252.2分布式數(shù)據(jù)處理MapReduce《云計算》第三版配套PPT課件2.2分布式數(shù)據(jù)處理MapReduce2.2.1產(chǎn)生背景2.2.2編程模型2.2.3實現(xiàn)機(jī)制2.2.4案例分析怎樣通過MapReduce完成排序工作，使其有序（字典序）呢？第一個步驟對原始的數(shù)據(jù)進(jìn)行分割（Split），得到N個不同的數(shù)據(jù)分塊。282.2分布式數(shù)據(jù)處理MapReduce第二個步驟對每一個數(shù)據(jù)分塊都啟動一個Map進(jìn)行處理。采用桶排序的方法，每個Map中按照首字母將字符串分配到26個不同的桶中。292.2分布式數(shù)據(jù)處理MapReduce第三個步驟對于Map之后得到的中間結(jié)果，啟動26個Reduce。按照首字母將Map中不同桶中的字符串集合放置到相應(yīng)的Reduce中進(jìn)行處理。302.2分布式數(shù)據(jù)處理MapReduce本章未完待續(xù)第二章Google云計算原理與應(yīng)用of3132高級人工智能人才培養(yǎng)叢書2.1Google文件系統(tǒng)GFS2.2分布式數(shù)據(jù)處理MapReduce2.3分布式鎖服務(wù)Chubby2.4分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable2.5分布式存儲系統(tǒng)Megastore2.6

大規(guī)模分布式系統(tǒng)的監(jiān)控基礎(chǔ)架構(gòu)Dapper2.7海量數(shù)據(jù)的交互式分析工具Dremel2.8內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDrill2.9Google應(yīng)用程序引擎初步了解ChubbyChubby是Google設(shè)計的提供粗粒度鎖服務(wù)的一個文件系統(tǒng)，它基于松耦合分布式系統(tǒng)，解決了分布的一致性問題。通過使用Chubby的鎖服務(wù)，用戶可以確保數(shù)據(jù)操作過程中的一致性Chubby作為一個穩(wěn)定的存儲系統(tǒng)存儲包括元數(shù)據(jù)在內(nèi)的小數(shù)據(jù)Google內(nèi)部還使用Chubby進(jìn)行名字服務(wù)（NameServer）332.3分布式鎖服務(wù)Chubby《云計算》第三版配套PPT課件2.3分布式鎖服務(wù)Chubby2.3.1Paxos算法2.3.2Chubby系統(tǒng)設(shè)計2.3.3Chubby中的Paxos2.3.4Chubby文件系統(tǒng)2.3.5通信協(xié)議2.3.6正確性與性能Paxos算法proposersacceptorslearners提出決議批準(zhǔn)決議獲取并使用已經(jīng)通過的決議三個節(jié)點(diǎn)決議只有在被proposers提出后才能批準(zhǔn)每次只批準(zhǔn)一個決議只有決議確定被批準(zhǔn)后learners才能獲取這個決議三個條件352.3分布式鎖服務(wù)Chubby《云計算》第三版配套PPT課件系統(tǒng)的約束條件p1：每個acceptor只接受它得到的第一個決議。p2：一旦某個決議得到通過，之后通過的決議必須和該決議保持一致。p2a：一旦某個決議v得到通過，之后任何acceptor再批準(zhǔn)的決議必須是v。p2b：一旦某個決議v得到通過，之后任何proposer再提出的決議必須是v。p2c：如果一個編號為n的提案具有值v，那么存在一個“多數(shù)派”，要么它們中沒有誰批準(zhǔn)過編號小于n的任何提案，要么它們進(jìn)行的最近一次批準(zhǔn)具有值v。為了保證決議的唯一性，acceptors也要滿足一個約束條件：當(dāng)且僅當(dāng)acceptors沒有收到編號大于n的請求時，acceptors才批準(zhǔn)編號為n的提案。362.3分布式鎖服務(wù)Chubby《云計算》第三版配套PPT課件37一個決議分為兩個階段準(zhǔn)備階段12批準(zhǔn)階段proposers選擇一個提案并將它的編號設(shè)為n將它發(fā)送給acceptors中的一個“多數(shù)派”acceptors收到后，如果提案的編號大于它已經(jīng)回復(fù)的所有消息，則acceptors將自己上次的批準(zhǔn)回復(fù)給proposers，并不再批準(zhǔn)小于n的提案。當(dāng)proposers接收到acceptors中的這個“多數(shù)派”的回復(fù)后，就向回復(fù)請求的acceptors發(fā)送accept請求，在符合acceptors一方的約束條件下，acceptors收到accept請求后即批準(zhǔn)這個請求。2.3分布式鎖服務(wù)Chubby《云計算》第三版配套PPT課件2.3分布式鎖服務(wù)Chubby2.3.1Paxos算法2.3.2Chubby系統(tǒng)設(shè)計2.3.3Chubby中的Paxos2.3.4Chubby文件系統(tǒng)2.3.5通信協(xié)議2.3.6正確性與性能54639Chubby的設(shè)計目標(biāo)主要有以下幾點(diǎn)高可用性和高可靠性213高擴(kuò)展性支持粗粒度的建議性鎖服務(wù)服務(wù)信息的直接存儲支持通報機(jī)制支持緩存機(jī)制2.3分布式鎖服務(wù)Chubby《云計算》第三版配套PPT課件客戶端應(yīng)用程序客戶端應(yīng)用程序Chubby程序率Chubby程序率…遠(yuǎn)程過程調(diào)用Chubby單元的五個服務(wù)器主服務(wù)器客戶端進(jìn)程40Chubby的基本架構(gòu)在客戶這一端每個客戶應(yīng)用程序都有一個Chubby程序庫（ChubbyLibrary），客戶端的所有應(yīng)用都是通過調(diào)用這個庫中的相關(guān)函數(shù)來完成的。服務(wù)器一端稱為Chubby單元，一般是由五個稱為副本（Replica）的服務(wù)器組成的，這五個副本在配置上完全一致，并且在系統(tǒng)剛開始時處于對等地位。客戶端服務(wù)器端2.3分布式鎖服務(wù)Chubby《云計算》第三版配套PPT課件2.3分布式鎖服務(wù)Chubby2.3.1Paxos算法2.3.2Chubby系統(tǒng)設(shè)計2.3.3Chubby中的Paxos2.3.4Chubby文件系統(tǒng)2.3.5通信協(xié)議2.3.6正確性與性能副本網(wǎng)絡(luò)Chubby客戶端網(wǎng)絡(luò)Chubby協(xié)議快照互換（Sanpshotexchange）Paxos協(xié)議本地文件系統(tǒng)日志文件I/O快照容錯的日志（Fault-tolerantLog）容錯的數(shù)據(jù)庫（Fault-tolerantDB）ChubbyRPC42單個Chubby副本結(jié)構(gòu)文件傳輸2.3分布式鎖服務(wù)Chubby《云計算》第三版配套PPT課件副本1副本2副本3值值值響應(yīng)響應(yīng)響應(yīng)值提交客戶端應(yīng)用程序Paxos構(gòu)架Paxos協(xié)議43容錯日志的API2.3分布式鎖服務(wù)Chubby《云計算》第三版配套PPT課件2.3分布式鎖服務(wù)Chubby2.3.1Paxos算法2.3.2Chubby系統(tǒng)設(shè)計2.3.3Chubby中的Paxos2.3.4Chubby文件系統(tǒng)2.3.5通信協(xié)議2.3.6正確性與性能45單調(diào)遞增的64位編號實例號InstanceNumber新節(jié)點(diǎn)實例號必定大于舊節(jié)點(diǎn)的實例號。1鎖生成號LockGenerationNumber鎖被用戶持有時該號增加。內(nèi)容生成號ContentGenerationNumber文件內(nèi)容修改時該號增加。23ACL生成號ACLGenerationNumberACL名被覆寫時該號增加。42.3分布式鎖服務(wù)Chubby《云計算》第三版配套PPT課件

函數(shù)名稱

作

用Open()打開某個文件或者目錄來創(chuàng)建句柄Close()關(guān)閉打開的句柄，后續(xù)的任何操作都將中止Poison()中止當(dāng)前未完成及后續(xù)的操作，但不關(guān)閉句柄GetContentsAndStat()返回文件內(nèi)容及元數(shù)據(jù)GetStat()只返回文件元數(shù)據(jù)ReadDir()返回子目錄名稱及其元數(shù)據(jù)SetContents()向文件中寫入內(nèi)容SetACL()設(shè)置ACL名稱Delete()如果該節(jié)點(diǎn)沒有子節(jié)點(diǎn)的話則執(zhí)行刪除操作Acquire()獲取鎖Release()釋放鎖GetSequencer()返回一個sequencerSetSequencer()將sequencer和某個句柄進(jìn)行關(guān)聯(lián)CheckSequencer()檢查某個sequencer是否有效46常用的句柄函數(shù)及作用2.3分布式鎖服務(wù)Chubby2.3分布式鎖服務(wù)Chubby2.3.1Paxos算法2.3.2Chubby系統(tǒng)設(shè)計2.3.3Chubby中的Paxos2.3.4Chubby文件系統(tǒng)2.3.5通信協(xié)議2.3.6正確性與性能48Chubby客戶端與服務(wù)器端的通信過程2.3分布式鎖服務(wù)Chubby49可能出現(xiàn)的兩種故障2.3分布式鎖服務(wù)Chubby客戶端租約過期主服務(wù)器出錯122.3分布式鎖服務(wù)Chubby2.3.1Paxos算法2.3.2Chubby系統(tǒng)設(shè)計2.3.3Chubby中的Paxos2.3.4Chubby文件系統(tǒng)2.3.5通信協(xié)議2.3.6正確性與性能51一致性2.3分布式鎖服務(wù)Chubby正確性與性能每個Chubby單元是由五個副本組成的，這五個副本中需要選舉產(chǎn)生一個主服務(wù)器，這種選舉本質(zhì)上就是一個一致性問題安全性采用的是ACL形式的安全保障措施。只要不被覆寫，子節(jié)點(diǎn)都是直接繼承父節(jié)點(diǎn)的ACL名性能優(yōu)化提高主服務(wù)器默認(rèn)的租約期、使用協(xié)議轉(zhuǎn)換服務(wù)將Chubby協(xié)議轉(zhuǎn)換成較簡單的協(xié)議、客戶端一致性緩存等52Chubby的ACL機(jī)制2.3分布式鎖服務(wù)Chubby用戶chinacloud提出向文件CLOUD中寫入內(nèi)容的請求。CLOUD首先讀取自身的寫ACL名fun，接著在fun中查到了chinacloud這一行記錄，于是返回信息允許chinacloud對文件進(jìn)行寫操作，此時chinacloud才被允許向CLOUD寫入內(nèi)容。其他的操作和寫操作類似。第二章Google云計算原理與應(yīng)用of3153高級人工智能人才培養(yǎng)叢書2.1Google文件系統(tǒng)GFS2.2分布式數(shù)據(jù)處理MapReduce2.3分布式鎖服務(wù)Chubby2.4分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable2.5分布式存儲系統(tǒng)Megastore2.6

大規(guī)模分布式系統(tǒng)的監(jiān)控基礎(chǔ)架構(gòu)Dapper2.7海量數(shù)據(jù)的交互式分析工具Dremel2.8內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDrill2.9Google應(yīng)用程序引擎2.4分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable2.4.1設(shè)計動機(jī)與目標(biāo)2.4.2數(shù)據(jù)模型2.4.3系統(tǒng)架構(gòu)2.4.4主服務(wù)器2.4.5子表服務(wù)器2.4.6性能優(yōu)化552.4分布式結(jié)構(gòu)化數(shù)據(jù)表BigtableBigtable的設(shè)計動機(jī)123需要存儲的數(shù)據(jù)種類繁多海量的服務(wù)請求商用數(shù)據(jù)庫

無法滿足需求包括URL、網(wǎng)頁內(nèi)容、用戶的個性化設(shè)置在內(nèi)的數(shù)據(jù)都是Google需要經(jīng)常處理的Google運(yùn)行著目前世界上最繁忙的系統(tǒng)，它每時每刻處理的客戶服務(wù)請求數(shù)量是普通的系統(tǒng)根本無法承受的一方面現(xiàn)有商用數(shù)據(jù)庫的設(shè)計著眼點(diǎn)在于其通用性。另一方面對于底層系統(tǒng)的完全掌控會給后期的系統(tǒng)維護(hù)、升級帶來極大的便利562.4分布式結(jié)構(gòu)化數(shù)據(jù)表BigtableBigtable應(yīng)達(dá)到的基本目標(biāo)廣泛的適用性很強(qiáng)的可擴(kuò)展性高可用性簡單性Bigtable是為了滿足一系列Google產(chǎn)品而并非特定產(chǎn)品的存儲要求。根據(jù)需要隨時可以加入或撤銷服務(wù)器確保幾乎所有的情況下系統(tǒng)都可用底層系統(tǒng)的簡單性既可以減少系統(tǒng)出錯的概率，也為上層應(yīng)用的開發(fā)帶來便利2.4分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable2.4.1設(shè)計動機(jī)與目標(biāo)2.4.2數(shù)據(jù)模型2.4.3系統(tǒng)架構(gòu)2.4.4主服務(wù)器2.4.5子表服務(wù)器2.4.6性能優(yōu)化58Bigtable數(shù)據(jù)的存儲格式2.4分布式結(jié)構(gòu)化數(shù)據(jù)表BigtableBigtable是一個分布式多維映射表，表中的數(shù)據(jù)通過一個行關(guān)鍵字（RowKey）、一個列關(guān)鍵字（ColumnKey）以及一個時間戳（TimeStamp）進(jìn)行索引Bigtable的存儲邏輯可以表示為：(row:string,column:string,time:int64)→string592.4分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable行列時間戳Bigtable的行關(guān)鍵字可以是任意的字符串，但是大小不能夠超過64KB表中數(shù)據(jù)都是根據(jù)行關(guān)鍵字進(jìn)行排序的，排序使用的是詞典序同一地址域的網(wǎng)頁會被存儲在表中的連續(xù)位置倒排便于數(shù)據(jù)壓縮，可以大幅提高壓縮率將其組織成所謂的列族（ColumnFamily）族名必須有意義，限定詞則可以任意選定組織的數(shù)據(jù)結(jié)構(gòu)清晰明了，含義也很清楚族同時也是Bigtable中訪問控制（AccessControl）的基本單元Bigtable中的時間戳是64位整型數(shù)，具體的賦值方式可以用戶自行定義Google的很多服務(wù)比如網(wǎng)頁檢索和用戶的個性化設(shè)置等都需要保存不同時間的數(shù)據(jù)，這些不同的數(shù)據(jù)版本必須通過時間戳來區(qū)分。2.4分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable2.4.1設(shè)計動機(jī)與目標(biāo)2.4.2數(shù)據(jù)模型2.4.3系統(tǒng)架構(gòu)2.4.4主服務(wù)器2.4.5子表服務(wù)器2.4.6性能優(yōu)化61Bigtable基本架構(gòu)2.4分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable622.4分布式結(jié)構(gòu)化數(shù)據(jù)表BigtableBigtable中Chubby的主要作用作用一選取并保證同一時間內(nèi)只有一個主服務(wù)器（MasterServer）。獲取子表的位置信息。保存Bigtable的模式信息及訪問控制列表。作用二作用三2.4分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable2.4.1設(shè)計動機(jī)與目標(biāo)2.4.2數(shù)據(jù)模型2.4.3系統(tǒng)架構(gòu)2.4.4主服務(wù)器2.4.5子表服務(wù)器2.4.6性能優(yōu)化642.4分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable主服務(wù)器新子表分配子表服務(wù)器狀態(tài)監(jiān)控子服務(wù)器之間的負(fù)載均衡當(dāng)一個新的子表產(chǎn)生時，主服務(wù)器通過一個加載命令將其分配給一個空間足夠的子表服務(wù)器。創(chuàng)建新表、表合并以及較大子表的分裂都會產(chǎn)生一個或多個新子表。分割完成之后子服務(wù)器需要向主服務(wù)發(fā)出一個通知。主服務(wù)器必須對子表服務(wù)器的狀態(tài)進(jìn)行監(jiān)控，以便及時檢測到服務(wù)器的加入或撤銷652.4分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable從Chubby中獲取一個獨(dú)占鎖，確保同一時間只有一個主服務(wù)器Bigtable中Chubby的主要作用掃描服務(wù)器目錄，發(fā)現(xiàn)目前活躍的子表服務(wù)器與所有的活躍子表服務(wù)器取得聯(lián)系以便了解所有子表的分配情況通過掃描元數(shù)據(jù)表（MetadataTable），發(fā)現(xiàn)未分配的子表并將其分配到合適的子表服務(wù)器步驟1

步驟3

步驟2

步驟42.4分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable2.4.1設(shè)計動機(jī)與目標(biāo)2.4.2數(shù)據(jù)模型2.4.3系統(tǒng)架構(gòu)2.4.4主服務(wù)器2.4.5子表服務(wù)器2.4.6性能優(yōu)化6764KB塊64KB塊…SSTable索引SSTable格式的基本示意2.4分布式結(jié)構(gòu)化數(shù)據(jù)表BigtableSSTable是Google為Bigtable設(shè)計的內(nèi)部數(shù)據(jù)存儲格式。所有的SSTable文件都存儲在GFS上，用戶可以通過鍵來查詢相應(yīng)的值。68子表實際組成日志64KB塊64KB塊…SSTable索引64KB塊64KB塊…SSTable索引…2.4分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable不同子表的SSTable可以共享每個子表服務(wù)器上僅保存一個日志文件Bigtable規(guī)定將日志的內(nèi)容按照鍵值進(jìn)行排序每個子表服務(wù)器上保存的子表數(shù)量可以從幾十到上千不等，通常情況下是100個左右69Chubby文件根子表（元數(shù)據(jù)表中第一條記錄）………………用戶表1用戶表N其他元數(shù)據(jù)子表······子表地址組成2.4分布式結(jié)構(gòu)化數(shù)據(jù)表BigtableBigtable系統(tǒng)的內(nèi)部采用的是一種類似B+樹的三層查詢體系……···70Bigtable數(shù)據(jù)存儲及讀/寫操作2.4分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable較新的數(shù)據(jù)存儲在內(nèi)存中一個稱為內(nèi)存表（Memtable）的有序緩沖里，較早的數(shù)據(jù)則以SSTable格式保存在GFS中。讀和寫操作有很大的差異性71三種形式壓縮之間的關(guān)系2.4分布式結(jié)構(gòu)化數(shù)據(jù)表BigtableSSTableSSTable內(nèi)存表SSTable內(nèi)存表內(nèi)存表次壓縮次壓縮SSTableSSTable合并壓縮SSTable主壓縮………………2.4分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable2.4.1設(shè)計動機(jī)與目標(biāo)2.4.2數(shù)據(jù)模型2.4.3系統(tǒng)架構(gòu)2.4.4主服務(wù)器2.4.5子表服務(wù)器2.4.6性能優(yōu)化73局部性群組2.4分布式結(jié)構(gòu)化數(shù)據(jù)表BigtableBigtable允許用戶將原本并不存儲在一起的數(shù)據(jù)以列族為單位，根據(jù)需要組織在一個單獨(dú)的SSTable中，以構(gòu)成一個局部性群組。用戶可以只看自己感興趣的內(nèi)容。對于一些較小的且會被經(jīng)常讀取的局部性群組，明顯地改善讀取效率。742.4分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable壓縮12利用Bentley&McIlroy方式（BMDiff）在大的掃描窗口將常見的長串進(jìn)行壓縮采取Zippy技術(shù)進(jìn)行快速壓縮，它在一個16KB大小的掃描窗口內(nèi)尋找重復(fù)數(shù)據(jù)，這個過程非常快壓縮可以有效地節(jié)省空間，Bigtable中的壓縮被應(yīng)用于很多場合。首先壓縮可以被用在構(gòu)成局部性群組的SSTable中，可以選擇是否對個人的局部性群組的SSTable進(jìn)行壓縮。752.4分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable布隆過濾器Bigtable向用戶提供了一種稱為布隆過濾器的數(shù)學(xué)工具。布隆過濾器是巴頓?布隆在1970年提出的，實際上它是一個很長的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)，在讀操作中確定子表的位置時非常有用。布隆過濾器的速度快，省空間不會將一個存在的子表判定為不存在在某些情況下它會將不存在的子表判斷為存在缺點(diǎn)優(yōu)點(diǎn)本章未完待續(xù)第二章Google云計算原理與應(yīng)用of3177高級人工智能人才培養(yǎng)叢書2.1Google文件系統(tǒng)GFS2.2分布式數(shù)據(jù)處理MapReduce2.3分布式鎖服務(wù)Chubby2.4分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable2.5分布式存儲系統(tǒng)Megastore2.6

大規(guī)模分布式系統(tǒng)的監(jiān)控基礎(chǔ)架構(gòu)Dapper2.7海量數(shù)據(jù)的交互式分析工具Dremel2.8內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDrill2.9Google應(yīng)用程序引擎2.5分布式存儲系統(tǒng)Megastore2.5.1設(shè)計目標(biāo)及方案選擇2.5.2Megastore數(shù)據(jù)模型2.5.3Megastore中的事務(wù)及并發(fā)控制2.5.4Megastore基本架構(gòu)2.5.5核心技術(shù)——復(fù)制2.5.6產(chǎn)品性能及控制措施針對可用性的要求，實現(xiàn)了一個同步的、容錯的、適合遠(yuǎn)距離傳輸?shù)膹?fù)制機(jī)制。針對可擴(kuò)展性的要求，將整個大的數(shù)據(jù)分割成很多小的數(shù)據(jù)分區(qū)，每個數(shù)據(jù)分區(qū)連同它自身的日志存放在NoSQL數(shù)據(jù)庫中，具體來說就是存放在Bigtable中。設(shè)計目標(biāo)及方案選擇2.5分布式存儲系統(tǒng)Megastore設(shè)計一種介于傳統(tǒng)的關(guān)系型數(shù)據(jù)庫和NoSQL之間的存儲技術(shù)，盡可能達(dá)到高可用性和高可擴(kuò)展性的統(tǒng)一。方法一設(shè)計目標(biāo)方法二79《云計算》第三版配套PPT課件數(shù)據(jù)的分區(qū)和復(fù)制2.5分布式存儲系統(tǒng)Megastore在Megastore中，這些小的數(shù)據(jù)分區(qū)被稱為實體組集（EntityGroups）。每個實體組集包含若干的實體組（EntityGroup，相當(dāng)于分區(qū)中表的概念）。一個實體組中包含很多的實體（Entity，相當(dāng)于表中記錄的概念）。80《云計算》第三版配套PPT課件2.5分布式存儲系統(tǒng)Megastore2.5.1設(shè)計目標(biāo)及方案選擇2.5.2Megastore數(shù)據(jù)模型2.5.3Megastore中的事務(wù)及并發(fā)控制2.5.4Megastore基本架構(gòu)2.5.5核心技術(shù)——復(fù)制2.5.6產(chǎn)品性能及控制措施822.5分布式存儲系統(tǒng)Megastore傳統(tǒng)的關(guān)系型數(shù)據(jù)庫不合適的三個原因傳統(tǒng)的關(guān)系型數(shù)據(jù)庫是通過連接（Join）來滿足用戶的需求的，但是就Megastore而言，這種數(shù)據(jù)模型是不合適的，主要有以下三個原因：原因1對于高負(fù)載的交互式應(yīng)用來說，可預(yù)期的性能提升要比使用一種代價高昂的查詢語言所帶來的好處多原因2Megastore所面對的應(yīng)用是讀遠(yuǎn)多于寫，因此好的選擇是將讀操作所需要做的工作盡可能地轉(zhuǎn)移到寫操作上原因3在Bigtable這樣的鍵/值存儲系統(tǒng)中存儲和查詢級聯(lián)數(shù)據(jù)（HierarchicalData）是很方便的《云計算》第三版配套PPT課件Megastore數(shù)據(jù)模型怎么設(shè)計？842.5分布式存儲系統(tǒng)Megastore細(xì)粒度控制的數(shù)據(jù)模型和模式語言同關(guān)系型數(shù)據(jù)庫一樣，Megastore的數(shù)據(jù)模型是在模式（schema）中定義的且是強(qiáng)類型的（stronglytyped）每個模式都由一系列的表（tables）構(gòu)成，表又包含有一系列的實體（entities），每實體中包含一系列屬性（properties）屬性是命名的且具有類型，這些類型包括字符型（strings）、數(shù)字類型（numbers）或者Google的ProtocolBuffers。Google團(tuán)隊設(shè)計的Megastore數(shù)據(jù)模型《云計算》第三版配套PPT課件852.5分布式存儲系統(tǒng)Megastore照片共享服務(wù)數(shù)據(jù)模型實例表Photo就是一個子表，因為它聲明了一個外鍵User則是一個根表一個Megastore實例中可以有若干個不同的根表，表示不同類型的實體組集三種不同屬性設(shè)置，既有必須的（如user_id），也有可選的（如thumbnail_url）Photo中的可重復(fù)類型的tag屬性《云計算》第三版配套PPT課件862.5分布式存儲系統(tǒng)MegastoreMegastore索引局部索引定義在單個實體組中，作用域僅限于單個實體組（如PhotosByTime）可以橫跨多個實體組集進(jìn)行數(shù)據(jù)讀取操作（如PhotosByTag）全局索引主要兩類額外索引STORING子句（STORINGClause）可重復(fù)的索引（RepeatedIndexes）內(nèi)聯(lián)索引（InlineIndexes）《云計算》第三版配套PPT課件872.5分布式存儲系統(tǒng)MegastoreBigtable中存儲情況行鍵（RowKey）UPhoto.timePhoto.tagPhoto._url101John101,50012:30:01Dinner,Paris…101,50212:15:22Betty,Paris…102MaryBigtable的列名實際上是表名和屬性名結(jié)合在一起得到，不同表中實體可存儲在同一個Bigtable行中《云計算》第三版配套PPT課件2.5分布式存儲系統(tǒng)Megastore2.5.1設(shè)計目標(biāo)及方案選擇2.5.2Megastore數(shù)據(jù)模型2.5.3Megastore中的事務(wù)及并發(fā)控制2.5.4Megastore基本架構(gòu)2.5.5核心技術(shù)——復(fù)制2.5.6產(chǎn)品性能及控制措施89Megastore提供的三種讀currentsnapshotinconsistent總是在單個實體組中完成總是在單個實體組中完成系統(tǒng)取出已知的最后一個完整提交的事務(wù)的時間戳，接著從這個位置讀數(shù)據(jù)忽略日志的狀態(tài)直接讀取最新的值2.5分布式存儲系統(tǒng)Megastore《云計算》第三版配套PPT課件90完整的事務(wù)周期讀應(yīng)用邏輯提交生效清除獲取最后一次提交的事務(wù)的時間戳和日志位置從Bigtable讀取且聚集數(shù)據(jù)到日志入口使用Paxos達(dá)到一致，將個入口追加到日志將數(shù)據(jù)更新到Bigtable中的實體和索引清理不再需要的數(shù)據(jù)2.5分布式存儲系統(tǒng)Megastore《云計算》第三版配套PPT課件912.5分布式存儲系統(tǒng)MegastoreMegastore中的事務(wù)機(jī)制《云計算》第三版配套PPT課件2.5分布式存儲系統(tǒng)Megastore2.5.1設(shè)計目標(biāo)及方案選擇2.5.2Megastore數(shù)據(jù)模型2.5.3Megastore中的事務(wù)及并發(fā)控制2.5.4Megastore基本架構(gòu)2.5.5核心技術(shù)——復(fù)制2.5.6產(chǎn)品性能及控制措施932.5分布式存儲系統(tǒng)MegastoreMegastore基本架構(gòu)完整副本（FullReplica）見證者副本（WitnessReplica）只讀副本（Read-onlyReplica）在Megastore中共有三種副本《云計算》第三版配套PPT課件942.5分布式存儲系統(tǒng)Megastore快速讀與快速寫快速讀快速寫利用本地讀取實現(xiàn)快速讀，帶來更好的用戶體驗及更低的延遲關(guān)鍵是保證選擇的副本上數(shù)據(jù)是最新的協(xié)調(diào)者是一個服務(wù)，該服務(wù)分布在每個副本的數(shù)據(jù)中心里面。它的主要作用就是跟蹤一個實體組集合協(xié)調(diào)者的狀態(tài)是由寫算法來保證如果一次寫成功，那么下一次寫的時候就跳過準(zhǔn)備過程，直接進(jìn)入接受階段Megastore沒有使用專門的主服務(wù)器，而是使用leadersleader主要是來裁決哪個寫入的值可以獲取0號提議客戶端、網(wǎng)絡(luò)及Bigtable的故障都會導(dǎo)致一個寫操作處于不確定的狀態(tài)《云計算》第三版配套PPT課件2.5分布式存儲系統(tǒng)Megastore2.5.1設(shè)計目標(biāo)及方案選擇2.5.2Megastore數(shù)據(jù)模型2.5.3Megastore中的事務(wù)及并發(fā)控制2.5.4Megastore基本架構(gòu)2.5.5核心技術(shù)——復(fù)制2.5.6產(chǎn)品性能及控制措施962.5分布式存儲系統(tǒng)Megastore復(fù)制的日志每個副本都存有記錄所有更新的數(shù)據(jù)。Megastore允許副本不按順序接受日志，這些日志將獨(dú)立的存儲在Bigtable中。預(yù)寫式日志《云計算》第三版配套PPT課件972.5分布式存儲系統(tǒng)Megastore數(shù)據(jù)讀取本地查詢發(fā)現(xiàn)位置追趕驗證查詢數(shù)據(jù)《云計算》第三版配套PPT課件982.5分布式存儲系統(tǒng)Megastore數(shù)據(jù)寫入接受leader準(zhǔn)備接受失效生效《云計算》第三版配套PPT課件992.5分布式存儲系統(tǒng)Megastore協(xié)調(diào)者的可用性協(xié)調(diào)者在系統(tǒng)中是比較重要的——協(xié)調(diào)者的進(jìn)程運(yùn)行在每個數(shù)據(jù)中心。每次的寫操作中都要涉及協(xié)調(diào)者，因此協(xié)調(diào)者的故障將會導(dǎo)致系統(tǒng)的不可用Megastore使用了Chubby鎖服務(wù)，為了處理請求，一個協(xié)調(diào)者必須持有多數(shù)鎖。一旦因為出現(xiàn)問題導(dǎo)致它丟失了大部分鎖，協(xié)調(diào)者就會恢復(fù)到一個默認(rèn)保守狀態(tài)除了可用性問題，對于協(xié)調(diào)者的讀寫協(xié)議必須滿足一系列的競爭條件《云計算》第三版配套PPT課件2.5分布式存儲系統(tǒng)Megastore2.5.1設(shè)計目標(biāo)及方案選擇2.5.2Megastore數(shù)據(jù)模型2.5.3Megastore中的事務(wù)及并發(fā)控制2.5.4Megastore基本架構(gòu)2.5.5核心技術(shù)——復(fù)制2.5.6產(chǎn)品性能及控制措施1012.5分布式存儲系統(tǒng)Megastore可用性的分布情況Megastore在Google中已經(jīng)部署和使用了若干年，有超過100個產(chǎn)品使用Megastore作為其存儲系統(tǒng)從圖中可以看出，絕大多數(shù)產(chǎn)品具有極高的可用性（>99.999%）。這表明Megastore系統(tǒng)的設(shè)計是非常成功的，基本達(dá)到了預(yù)期目標(biāo)《云計算》第三版配套PPT課件102產(chǎn)品延遲情況的分布2.5分布式存儲系統(tǒng)Megastore應(yīng)用程序的平均讀取延遲在萬分之一毫秒之內(nèi)，平均寫入延遲在100至400毫秒之間避免Megastore的性能下降，可采取以下三種應(yīng)對方法：（1）重新選擇路由使客戶端繞開出現(xiàn)問題的副本（2）將出現(xiàn)問題副本上的協(xié)調(diào)者禁用，確保問題的影響降至最小。（3）禁用整個副本《云計算》第三版配套PPT課件2.6

大規(guī)模分布式系統(tǒng)的監(jiān)控基礎(chǔ)架構(gòu)Dapper第二章Google云計算原理與應(yīng)用of31103高級人工智能人才培養(yǎng)叢書2.1Google文件系統(tǒng)GFS2.2分布式數(shù)據(jù)處理MapReduce2.3分布式鎖服務(wù)Chubby2.4分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable2.5分布式存儲系統(tǒng)Megastore2.7海量數(shù)據(jù)的交互式分析工具Dremel2.8內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDrill2.9Google應(yīng)用程序引擎2.6大規(guī)模分布式系統(tǒng)的監(jiān)控

基礎(chǔ)架構(gòu)Dapper2.6.1基本設(shè)計目標(biāo)2.6.2Dapper監(jiān)控系統(tǒng)簡介2.6.3關(guān)鍵性技術(shù)2.6.4常用Dapper工具2.6.5Dapper使用經(jīng)驗在我們看來很簡單的一次搜索實際上涉及了眾多Google后臺子系統(tǒng)，這些子系統(tǒng)的運(yùn)行狀態(tài)都需要進(jìn)行監(jiān)控用戶的平均每一次前臺搜索會導(dǎo)致Google的后臺發(fā)生1011次的處理1062.6大規(guī)模分布式系統(tǒng)的監(jiān)控基礎(chǔ)架構(gòu)Dapper兩個基本要求設(shè)計出的監(jiān)控系統(tǒng)應(yīng)當(dāng)能夠?qū)ΡM可能多的Google服務(wù)進(jìn)行監(jiān)控Google的服務(wù)是全天候的，如果不能對Google的后臺同樣進(jìn)行全天候的監(jiān)控很可能會錯過某些無法再現(xiàn)的關(guān)鍵性故障監(jiān)控系統(tǒng)設(shè)計兩個基本要求1.廣泛可部署性（UbiquitousDeployment）2.不間斷的監(jiān)控《云計算》第三版配套PPT課件1072.6大規(guī)模分布式系統(tǒng)的監(jiān)控基礎(chǔ)架構(gòu)Dapper三個基本設(shè)計目標(biāo)低開銷這個是廣泛可部署性的必然要求。監(jiān)控系統(tǒng)的開銷越低，對于原系統(tǒng)的影響就越小，系統(tǒng)的開發(fā)人員也就越愿意接受這個監(jiān)控系統(tǒng)。對應(yīng)用層透明監(jiān)控系統(tǒng)對程序員應(yīng)當(dāng)是不可見的。如果監(jiān)控系統(tǒng)的使用需要程序開發(fā)人員對其底層的一些細(xì)節(jié)進(jìn)行調(diào)整才能正常工作的話，這個監(jiān)控系統(tǒng)肯定不是一個完善的監(jiān)控系統(tǒng)?？蓴U(kuò)展性Google的服務(wù)增長速度是驚人的，設(shè)計出的系統(tǒng)至少在未來幾年里要能夠滿足Google服務(wù)和集群的需求?！对朴嬎恪返谌媾涮譖PT課件2.6大規(guī)模分布式系統(tǒng)的監(jiān)控

基礎(chǔ)架構(gòu)Dapper2.6.1基本設(shè)計目標(biāo)2.6.2Dapper監(jiān)控系統(tǒng)簡介2.6.3關(guān)鍵性技術(shù)2.6.4常用Dapper工具2.6.5Dapper使用經(jīng)驗1092.6大規(guī)模分布式系統(tǒng)的監(jiān)控基礎(chǔ)架構(gòu)DapperDapper監(jiān)控系統(tǒng)的基本概念典型分布式系統(tǒng)的請求及應(yīng)答過程用戶ABCDE請求X應(yīng)答XRPC1中間層RPC2前端后臺RPC4RPC3在監(jiān)控系統(tǒng)中記錄下所有這些消息不難，如何將這些消息記錄同特定的請求（本例中的X）關(guān)聯(lián)起來才是分布式監(jiān)控系統(tǒng)設(shè)計中需要解決的關(guān)鍵性問題之一。《云計算》第三版配套PPT課件1102.6大規(guī)模分布式系統(tǒng)的監(jiān)控基礎(chǔ)架構(gòu)DapperDapper監(jiān)控系統(tǒng)的三個基本概念監(jiān)控樹（TraceTree）區(qū)間（Span）注釋（Annotation）一個同特定事件相關(guān)的所有消息區(qū)間實際上就是一條記錄注釋主要用來輔助推斷區(qū)間關(guān)系，也可以包含一些自定義的內(nèi)容《云計算》第三版配套PPT課件1112.6大規(guī)模分布式系統(tǒng)的監(jiān)控基礎(chǔ)架構(gòu)Dapper區(qū)間Helper.Call的詳細(xì)信息區(qū)間包含了來自客戶端的注釋信息：“<Start>”、“ClientSend”、“ClientRecv”和“<End>”，也包含了來自服務(wù)器端的注釋信息：“ServerRecv”、“foo”和“ServerSend”《云計算》第三版配套PPT課件1122.6大規(guī)模分布式系統(tǒng)的監(jiān)控基礎(chǔ)架構(gòu)Dapper監(jiān)控信息的匯總（1）將區(qū)間的數(shù)據(jù)寫入到本地的日志文件（2）所有機(jī)器上的本地日志文件匯集（3）匯集后的數(shù)據(jù)寫入到Bigtable存儲庫中《云計算》第三版配套PPT課件2.6大規(guī)模分布式系統(tǒng)的監(jiān)控

基礎(chǔ)架構(gòu)Dapper2.6.1基本設(shè)計目標(biāo)2.6.2Dapper監(jiān)控系統(tǒng)簡介2.6.3關(guān)鍵性技術(shù)2.6.4常用Dapper工具2.6.5Dapper使用經(jīng)驗1142.6大規(guī)模分布式系統(tǒng)的監(jiān)控基礎(chǔ)架構(gòu)Dapper輕量級核心功能庫最關(guān)鍵的代碼基礎(chǔ)是基本RPC、線程和控制流函數(shù)庫的實現(xiàn)主要功能是實現(xiàn)區(qū)間創(chuàng)建、抽樣和在本地磁盤上記錄日志。將復(fù)雜的功能實現(xiàn)限制在一個輕量級的核心功能庫中保證了Dapper的監(jiān)控過程基本對應(yīng)用層透明。小規(guī)模庫通用線程（UbiquitousThreading）控制流（ControlFlow）RPC代碼庫（RPCLibraryCode）《云計算》第三版配套PPT課件1152.6大規(guī)模分布式系統(tǒng)的監(jiān)控基礎(chǔ)架構(gòu)Dapper二次抽樣技術(shù)利用二次抽樣技術(shù)成功地解決了低開銷及廣泛可部署性的問題。第一次抽樣第二次抽樣實踐中，設(shè)計人員發(fā)現(xiàn)當(dāng)抽樣率低至1/1024時也能夠產(chǎn)生足夠多的有效監(jiān)控數(shù)據(jù)，即在1024個請求中抽取1個進(jìn)行監(jiān)控也是可行的，從而可以捕獲有效數(shù)據(jù)發(fā)生在數(shù)據(jù)寫入Bigtable前，具體方法是將監(jiān)控id散列成一個標(biāo)量z（0≤z≤1），如果某個區(qū)間的z小于事先定義好的匯總抽樣系數(shù)，則保留這個區(qū)間并將它寫入Bigtable，否則丟棄《云計算》第三版配套PPT課件2.6大規(guī)模分布式系統(tǒng)的監(jiān)控

基礎(chǔ)架構(gòu)Dapper2.6.1基本設(shè)計目標(biāo)2.6.2Dapper監(jiān)控系統(tǒng)簡介2.6.3關(guān)鍵性技術(shù)2.6.4常用Dapper工具2.6.5Dapper使用經(jīng)驗1172.6大規(guī)模分布式系統(tǒng)的監(jiān)控基礎(chǔ)架構(gòu)DapperDapper存儲APIDapper的“存儲API”簡稱為DAPI，提供了對分散在區(qū)域Dapper存儲庫（DEPOTS）的監(jiān)控記錄的直接訪問。一般有以下三種方式訪問這些記錄。（1）通過監(jiān)控id訪問（AccessbyTraceid）（2）塊訪問（BulkAccess）（3）索引訪問（IndexedAccess）利用全局唯一的監(jiān)控id直接訪問所需的監(jiān)控數(shù)據(jù)借助MapReduce對數(shù)以十億計的Dapper監(jiān)控數(shù)據(jù)的并行訪問Dapper存儲庫支持單索引（SingleIndex）《云計算》第三版配套PPT課件118Dapper用戶界面（1）選擇監(jiān)控對象（2）用戶對這些執(zhí)行模式進(jìn)行排序并選擇查看更多細(xì)節(jié)（3）分布式執(zhí)行模式圖形化描述呈現(xiàn)給用戶《云計算》第三版配套PPT課件2.6大規(guī)模分布式系統(tǒng)的監(jiān)控基礎(chǔ)架構(gòu)Dapper119Dapper用戶界面（4）根據(jù)最初選擇的開銷度量標(biāo)準(zhǔn)，Dapper以頻度直方圖的形式將步驟（3）中選中的執(zhí)行模式的開銷分布展示出來（5）用戶選擇了某個監(jiān)控樣例后，就會進(jìn)入所謂的監(jiān)控審查視圖（TraceInspectionView）《云計算》第三版配套PPT課件2.6大規(guī)模分布式系統(tǒng)的監(jiān)控基礎(chǔ)架構(gòu)Dapper2.6大規(guī)模分布式系統(tǒng)的監(jiān)控

基礎(chǔ)架構(gòu)Dapper2.6.1基本設(shè)計目標(biāo)2.6.2Dapper監(jiān)控系統(tǒng)簡介2.6.3關(guān)鍵性技術(shù)2.6.4常用Dapper工具2.6.5Dapper使用經(jīng)驗1212.6大規(guī)模分布式系統(tǒng)的監(jiān)控基礎(chǔ)架構(gòu)DapperDapper使用經(jīng)驗新服務(wù)部署中Dapper的使用利用Dapper對系統(tǒng)延遲情況進(jìn)行一系列的跟蹤，進(jìn)而發(fā)現(xiàn)存在的問題定位長尾延遲（AddressingLongTailLatency）端到端性能和關(guān)鍵路徑上的網(wǎng)絡(luò)延遲有著極大的關(guān)系12《云計算》第三版配套PPT課件1222.6大規(guī)模分布式系統(tǒng)的監(jiān)控基礎(chǔ)架構(gòu)DapperDapper使用經(jīng)驗推斷服務(wù)間的依存關(guān)系（InferringServiceDependencies）Google的“服務(wù)依存關(guān)系”項目使用監(jiān)控注釋和DPAI的MapReduce接口實現(xiàn)了服務(wù)依存關(guān)系確定的自動化確定不同服務(wù)的網(wǎng)絡(luò)使用情況利用Dapper平臺構(gòu)建了一個連續(xù)不斷更新的控制臺，用來顯示內(nèi)部集群網(wǎng)絡(luò)通信中最活躍的應(yīng)用層終端34分層的共享式存儲系統(tǒng)沒有Dapper之類的工具的情況下對于這種共享式服務(wù)資源的爭用也同樣難以調(diào)試?yán)肈apper進(jìn)行“火拼”（FirefightingwithDapper）Dapper用戶可以通過和Dapper守護(hù)進(jìn)程的直接通信，將所需的最新數(shù)據(jù)匯總在一起56《云計算》第三版配套PPT課件本章未完待續(xù)第二章Google云計算原理與應(yīng)用of31124高級人工智能人才培養(yǎng)叢書2.1Google文件系統(tǒng)GFS2.2分布式數(shù)據(jù)處理MapReduce2.3分布式鎖服務(wù)Chubby2.4分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable2.5分布式存儲系統(tǒng)Megastore2.6

大規(guī)模分布式系統(tǒng)的監(jiān)控基礎(chǔ)架構(gòu)Dapper2.7海量數(shù)據(jù)的交互式分析工具Dremel2.8內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDrill2.9Google應(yīng)用程序引擎數(shù)據(jù)本身不會產(chǎn)生價值只有經(jīng)過分析才有可能產(chǎn)生價值2.7海量數(shù)據(jù)的交互式分析工具Dremel2.7.1產(chǎn)生背景2.7.2數(shù)據(jù)模型2.7.3嵌套式的列存儲2.7.4查詢語言與執(zhí)行2.7.5性能分析2.7.6小結(jié)127產(chǎn)生背景2.7海量數(shù)據(jù)的交互式分析工具DremelMapReduce優(yōu)點(diǎn)：便攜缺點(diǎn)：效率低Google的團(tuán)隊結(jié)合其自身的實際需求，借鑒搜索引擎和并行數(shù)據(jù)庫的一些技術(shù)，開發(fā)出了實時的交互式查詢系統(tǒng)Dremel?！对朴嬎恪返谌媾涮譖PT課件2.7海量數(shù)據(jù)的交互式分析工具DremelDremel支持的典型應(yīng)用Web文檔的分析Android市場的應(yīng)用安裝數(shù)據(jù)的跟蹤Google產(chǎn)品的錯誤報告Google圖書的光學(xué)字符識別欺詐信息的分析Google地圖的調(diào)試Bigtable實例上的tablet遷移Google分布式構(gòu)建系統(tǒng)的測試結(jié)果分析磁盤I/O信息的統(tǒng)計Google數(shù)據(jù)中心上運(yùn)行任務(wù)的資源監(jiān)控Google代碼庫的符號和依賴關(guān)系分析128《云計算》第三版配套PPT課件2.7海量數(shù)據(jù)的交互式分析工具Dremel2.7.1產(chǎn)生背景2.7.2數(shù)據(jù)模型2.7.3嵌套式的列存儲2.7.4查詢語言與執(zhí)行2.7.5性能分析2.7.6小結(jié)130兩方面的技術(shù)支撐兩方面的技術(shù)支撐一方面：統(tǒng)一的存儲平臺另一方面：統(tǒng)一的數(shù)據(jù)存儲格式實現(xiàn)高效的數(shù)據(jù)存儲，Dremel使用的底層數(shù)據(jù)存儲平臺是GFS存儲的數(shù)據(jù)才可以被不同的平臺所使用2.7海量數(shù)據(jù)的交互式分析工具Dremel《云計算》第三版配套PPT課件1312.7海量數(shù)據(jù)的交互式分析工具Dremel面向記錄和面向列的存儲Google的Dremel是第一個在嵌套數(shù)據(jù)模型基礎(chǔ)上實現(xiàn)列存儲的系統(tǒng)。列存儲更利于數(shù)據(jù)的壓縮處理時只需要使用涉及的列數(shù)據(jù)好處一：好處二：《云計算》第三版配套PPT課件1322.7海量數(shù)據(jù)的交互式分析工具Dremel嵌套模型的形式化定義原子類型（AtomicType）原子類型允許的取值類型包括整型、浮點(diǎn)型、字符串等記錄類型（RecordType）記錄類型則可以包含多個域記錄型數(shù)據(jù)包括三種類型：必須的（Required）、可重復(fù)的（Repeated）以及可選的（Optional）《云計算》第三版配套PPT課件1332.7海量數(shù)據(jù)的交互式分析工具Dremel嵌套結(jié)構(gòu)的模式和實例文檔的模式（Schema）定義符合該模式的兩條記錄利用該數(shù)據(jù)模型，可以使用Java語言，也可以使用C++語言來處理數(shù)據(jù)，甚至可以用Java編寫的MapReduce程序直接處理C++語言產(chǎn)生的數(shù)據(jù)集。這種跨平臺的優(yōu)良特性正是Google所需要的?！对朴嬎恪返谌媾涮譖PT課件2.7海量數(shù)據(jù)的交互式分析工具Dremel2.7.1產(chǎn)生背景2.7.2數(shù)據(jù)模型2.7.3嵌套式的列存儲2.7.4查詢語言與執(zhí)行2.7.5性能分析2.7.6小結(jié)1352.7海量數(shù)據(jù)的交互式分析工具Dremel數(shù)據(jù)結(jié)構(gòu)的無損表示帶有重復(fù)深度和定義深度的r1與r2的列存儲重復(fù)深度主要關(guān)注的是可重復(fù)類型，而定義深度同時關(guān)注可重復(fù)類型和可選類型（optional）每一列最終會被存儲為塊（Block）的集合，每個塊包含重復(fù)深度和定義深度且包含字段值。《云計算》第三版配套PPT課件1362.7海量數(shù)據(jù)的交互式分析工具Dremel高效的數(shù)據(jù)編碼計算重復(fù)和定義深度的基礎(chǔ)算法Dremel利用圖中算法創(chuàng)建一個樹狀結(jié)構(gòu)樹的節(jié)點(diǎn)為字段的writer，它的結(jié)構(gòu)與模式中的字段層級匹配。核心的想法是只在字段writer有自己的數(shù)據(jù)時執(zhí)行更新，非絕對必要時不嘗試往下傳遞父節(jié)點(diǎn)狀態(tài)。子節(jié)點(diǎn)writer繼承父節(jié)點(diǎn)的深度值。當(dāng)任意值被添加時，子writer將深度值同步到父節(jié)點(diǎn)。《云計算》第三版配套PPT課件1372.7海量數(shù)據(jù)的交互式分析工具Dremel數(shù)據(jù)重組Dremel數(shù)據(jù)重組方法的核心思想是為每個字段創(chuàng)建一個有限狀態(tài)機(jī)（FSM），讀取字段值和重復(fù)深度，然后順序地將值添加到輸出結(jié)果上?！对朴嬎恪返谌媾涮譖PT課件138當(dāng)前FSM寫入值下一個重復(fù)深度值動作DocId（開始）100跳轉(zhuǎn)至Links.BackwardLinks.BackwardNULL0跳轉(zhuǎn)至Links.ForwardLinks.Forward201停留在Links.ForwardLinks.Forward401停留在Links.ForwardLinks.Forward600跳轉(zhuǎn)至Name.Language.CodeName.Language.Codeen-us2跳轉(zhuǎn)至Name.Language.CountryName.Language.Countryus2跳轉(zhuǎn)至Name.Language.CodeName.Language.Codeen1跳轉(zhuǎn)至Name.Language.CountryName.Language.CountryNULL1跳轉(zhuǎn)至Name.UrlName.Urlhttp://A1跳轉(zhuǎn)至Name.Language.CodeName.Language.CodeNULL1跳轉(zhuǎn)至Name.Language.CountryName.Language.CountryNULL1跳轉(zhuǎn)至Name.UrlName.Urlhttp://B1跳轉(zhuǎn)至Name.Language.CodeName.Language.Codeen-gb0跳轉(zhuǎn)至Name.Language.CountryName.Language.Countrygb0跳轉(zhuǎn)至Name.UrlName.UrlNULL0結(jié)束2.7海量數(shù)據(jù)的交互式分析工具Dremel數(shù)據(jù)重組r1的完整數(shù)據(jù)重組過程《云計算》第三版配套PPT課件1392.7海量數(shù)據(jù)的交互式分析工具Dremel數(shù)據(jù)重組如果具體的查詢中不是涉及所有列，而是僅涉及很少的列的話，上述數(shù)據(jù)重組的過程會更加便利，下圖中僅僅涉及DocId和Name.Language.Country的有限狀態(tài)機(jī)。《云計算》第三版配套PPT課件1402.7海量數(shù)據(jù)的交互式分析工具Dremel數(shù)據(jù)重組核心的思想如下：設(shè)置t為當(dāng)前字段讀取器的當(dāng)前值f所返回的下一個重復(fù)深度。在模式樹中，找到它在深度t的祖先，然后選擇該祖先節(jié)點(diǎn)的第一個葉子字段n。由此得到一個FSM狀態(tài)變化(f,t)->n。有限狀態(tài)機(jī)的構(gòu)造算法《云計算》第三版配套PPT課件2.7海量數(shù)據(jù)的交互式分析工具Dremel2.7.1產(chǎn)生背景2.7.2數(shù)據(jù)模型2.7.3嵌套式的列存儲2.7.4查詢語言與執(zhí)行2.7.5性能分析2.7.6小結(jié)1422.7海量數(shù)據(jù)的交互式分析工具Dremel查詢語言與執(zhí)行Dremel的SQL查詢輸入的是一個或多個嵌套結(jié)構(gòu)的表以及相應(yīng)的模式，而輸出的結(jié)果是一個嵌套結(jié)構(gòu)的表以及相應(yīng)的模式。嵌套子查詢記錄內(nèi)聚合top-kjoins自定義函數(shù)……《云計算》第三版配套PPT課件1432.7海量數(shù)據(jù)的交互式分析工具DremelDremel利用多層級服務(wù)樹（multi-levelservicetree）的概念來執(zhí)行查詢操作根服務(wù)器接受客戶端發(fā)出的請求，讀取相應(yīng)的元數(shù)據(jù)，將請求轉(zhuǎn)發(fā)至中間服務(wù)器。中間服務(wù)器負(fù)責(zé)查詢中間結(jié)果的聚集葉子服務(wù)器負(fù)責(zé)執(zhí)行數(shù)據(jù)來源查詢語言與執(zhí)行《云計算》第三版配套PPT課件144查詢語言與執(zhí)行Dremel中的數(shù)據(jù)都是分布式存儲的，因此每一層查詢涉及的數(shù)據(jù)實際都被水平劃分后存儲在多個服務(wù)器上。Dremel是一個多用戶系統(tǒng)，因此同一時刻往往會有多個用戶進(jìn)行查詢。查詢分發(fā)器有一個很重要參數(shù)，它表示在返回結(jié)果之前一定要掃描百分之多少的tablet2.7海量數(shù)據(jù)的交互式分析工具Dremel《云計算》第三版配套PPT課件2.7海量數(shù)據(jù)的交互式分析工具Dremel2.7.1產(chǎn)生背景2.7.2數(shù)據(jù)模型2.7.3嵌套式的列存儲2.7.4查詢語言與執(zhí)行2.7.5性能分析2.7.6小結(jié)146表名記錄數(shù)（億)規(guī)模（未壓縮，TB）域數(shù)目數(shù)據(jù)中心復(fù)制因子T185087270A3T224013530A3T340701200A3T4>1000010550B3T5>100002050B22.7海量數(shù)據(jù)的交互式分析工具Dremel由于Dremel并不開源，我們只能通過Google論文中的分析大致了解其性能。Google的實驗數(shù)據(jù)集規(guī)模如下圖：性能分析《云計算》第三版配套PPT課件1472.7海量數(shù)據(jù)的交互式分析工具Dremel性能分析MR從面向記錄轉(zhuǎn)換到列狀存儲后性能提升了一個數(shù)量級（從小時到分鐘），而使用Dremel則又提升了一個數(shù)量級（從分鐘到秒）《云計算》第三版配套PPT課件2.7海量數(shù)據(jù)的交互式分析工具Dremel2.7.1產(chǎn)生背景2.7.2數(shù)據(jù)模型2.7.3嵌套式的列存儲2.7.4查詢語言與執(zhí)行2.7.5性能分析2.7.6小結(jié)1492.7海量數(shù)據(jù)的交互式分析工具Dremel小結(jié)Dremel和MapReduce并不是互相替代，而是相互補(bǔ)充的技術(shù)。在不同的應(yīng)用場景下各有其用武之地。Drill的設(shè)計目標(biāo)就是復(fù)制一個開源的Dremel，但是從目前來看，該項目無論是進(jìn)展還是影響力都達(dá)不到Hadoop的高度。希望未來能出現(xiàn)一個真正有影響力的開源系統(tǒng)實現(xiàn)Dremel的主要功能并被廣泛采用。123《云計算》第三版配套PPT課件第二章Google云計算原理與應(yīng)用of31150高級人工智能人才培養(yǎng)叢書2.1Google文件系統(tǒng)GFS2.2分布式數(shù)據(jù)處理MapReduce2.3分布式鎖服務(wù)Chubby2.4分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable2.5分布式存儲系統(tǒng)Megastore2.6

大規(guī)模分布式系統(tǒng)的監(jiān)控基礎(chǔ)架構(gòu)Dapper2.7海量數(shù)據(jù)的交互式分析工具Dremel2.8內(nèi)存大數(shù)據(jù)分析系統(tǒng)PowerDr