云計算Google云計算原理與應(yīng)用

1、電子工業(yè)出版社云計算(第三版)配套課件云計算（第三版）CLOUD COMPUTING Third Edition主編：劉鵬 教授第 2 章Google云計算原理與應(yīng)用（二） 教授、博導(dǎo)、學(xué)科帶頭人，清華大學(xué)博士?，F(xiàn)任中國云計算專家咨詢委員會秘書長、中國信息協(xié)會大數(shù)據(jù)分會副會長、工業(yè)與信息化部云計算研究中心專家。 主持完成科研項目25項，發(fā)表論文80余篇，出版專業(yè)書籍15本。獲部級科技進(jìn)步二等獎4項、三等獎4項。主編了國內(nèi)第一本云計算教材云計算和第一本云計算編程書籍實戰(zhàn)Hadoop。創(chuàng)辦了知名的中國云計算（）和中國大數(shù)據(jù)（）網(wǎng)站。 曾率隊奪得2002 PennySort國際計算機排序比賽冠軍，兩

2、次奪得全國高校科技比賽最高獎，并三次奪得清華大學(xué)科技比賽最高獎。 榮獲“全軍十大學(xué)習(xí)成才標(biāo)兵”（排名第一）、南京“十大杰出青年”、江蘇省“333高層次人才培養(yǎng)工程”中青年科學(xué)技術(shù)帶頭人、清華大學(xué)“學(xué)術(shù)新秀”等稱號。劉 鵬目錄 2.1 Google文件系統(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.9 Google應(yīng)用程序引擎初步了解Chu

3、bbyChubby是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ù)（Name Server）42.3 分布式鎖服務(wù)Chubby2.3 分布式鎖服務(wù)Chubby2.3.1 Paxos算法2.3.2 Chubby系統(tǒng)設(shè)計2.3.3 Chubby中的Paxos2.3.4 Chubby文件系統(tǒng)2.3.5 通信協(xié)議2.3.6 正確性與性能Paxos算法proposersacceptor

4、slearners提出決議批準(zhǔn)決議獲取并使用已經(jīng)通過的決議三個節(jié)點決議只有在被proposers提出后才能批準(zhǔn)每次只批準(zhǔn)一個決議只有決議確定被批準(zhǔn)后learners才能獲取這個決議三個條件62.3 分布式鎖服務(wù)Chubby系統(tǒng)的約束條件p1：每個acceptor只接受它得到的第一個決議。p2：一旦某個決議得到通過，之后通過的決議必須和該決議保持一致。p2a：一旦某個決議v得到通過，之后任何acceptor再批準(zhǔn)的決議必須是v。p2b：一旦某個決議v得到通過，之后任何proposer再提出的決議必須是v。p2c：如果一個編號為n的提案具有值v，那么存在一個“多數(shù)派”，要么它們中沒有誰批準(zhǔn)過編號小

5、于n的任何提案，要么它們進(jìn)行的最近一次批準(zhǔn)具有值v。為了保證決議的唯一性，acceptors也要滿足一個約束條件：當(dāng)且僅當(dāng) acceptors 沒有收到編號大于n的請求時，acceptors 才批準(zhǔn)編號為n的提案。72.3 分布式鎖服務(wù)Chubby8一個決議分為兩個階段準(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ù)派

6、”的回復(fù)后，就向回復(fù)請求的acceptors發(fā)送accept請求，在符合acceptors一方的約束條件下，acceptors收到accept請求后即批準(zhǔn)這個請求。2.3 分布式鎖服務(wù)Chubby2.3 分布式鎖服務(wù)Chubby2.3.1 Paxos算法2.3.2 Chubby系統(tǒng)設(shè)計2.3.3 Chubby中的Paxos2.3.4 Chubby文件系統(tǒng)2.3.5 通信協(xié)議2.3.6 正確性與性能54610Chubby的設(shè)計目標(biāo)主要有以下幾點高可用性和高可靠性213高擴展性支持粗粒度的建議性鎖服務(wù)服務(wù)信息的直接存儲支持通報機制支持緩存機制2.3 分布式鎖服務(wù)Chubby客戶端應(yīng)用程序客戶端應(yīng)用

7、程序Chubby程序率Chubby程序率遠(yuǎn)程過程調(diào)用Chubby單元的五個服務(wù)器主服務(wù)器客戶端進(jìn)程11Chubby的基本架構(gòu)在客戶這一端每個客戶應(yīng)用程序都有一個Chubby程序庫（Chubby Library），客戶端的所有應(yīng)用都是通過調(diào)用這個庫中的相關(guān)函數(shù)來完成的。服務(wù)器一端稱為Chubby單元，一般是由五個稱為副本（Replica）的服務(wù)器組成的，這五個副本在配置上完全一致，并且在系統(tǒng)剛開始時處于對等地位?？蛻舳朔?wù)器端2.3 分布式鎖服務(wù)Chubby2.3 分布式鎖服務(wù)Chubby2.3.1 Paxos算法2.3.2 Chubby系統(tǒng)設(shè)計2.3.3 Chubby中的Paxos2.3.4

8、Chubby文件系統(tǒng)2.3.5 通信協(xié)議2.3.6 正確性與性能副本網(wǎng)絡(luò)Chubby客戶端網(wǎng)絡(luò)Chubby協(xié)議快照互換（Sanpshot exchange）Paxos協(xié)議本地文件系統(tǒng)日志文件I/O快照容錯的日志（Fault-tolerant Log）容錯的數(shù)據(jù)庫（Fault-tolerant DB）ChubbyRPC13單個Chubby副本結(jié)構(gòu)文件傳輸2.3 分布式鎖服務(wù)Chubby副本1副本2副本3值值值響應(yīng)響應(yīng)響應(yīng)值提交客戶端應(yīng)用程序Paxos構(gòu)架Paxos協(xié)議14容錯日志的API2.3 分布式鎖服務(wù)Chubby2.3 分布式鎖服務(wù)Chubby2.3.1 Paxos算法2.3.2 Chub

9、by系統(tǒng)設(shè)計2.3.3 Chubby中的Paxos2.3.4 Chubby文件系統(tǒng)2.3.5 通信協(xié)議2.3.6 正確性與性能16單調(diào)遞增的64位編號實例號Instance Number新節(jié)點實例號必定大于舊節(jié)點的實例號。1鎖生成號Lock Generation Number鎖被用戶持有時該號增加。內(nèi)容生成號Content Generation Number文件內(nèi)容修改時該號增加。23ACL生成號ACL Generation NumberACL名被覆寫時該號增加。42.3 分布式鎖服務(wù)Chubby 函 數(shù) 名 稱 作 用Open()打開某個文件或者目錄來創(chuàng)建句柄Close()關(guān)閉打開的句柄，后

10、續(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é)點沒有子節(jié)點的話則執(zhí)行刪除操作Acquire()獲取鎖Release()釋放鎖GetSequencer()返回一個sequencerSetSequencer()將sequencer和某個句柄進(jìn)行關(guān)聯(lián)CheckSequencer()檢查某個sequencer是否有效17常用的句柄函數(shù)及作用2.

11、3 分布式鎖服務(wù)Chubby2.3 分布式鎖服務(wù)Chubby2.3.1 Paxos算法2.3.2 Chubby系統(tǒng)設(shè)計2.3.3 Chubby中的Paxos2.3.4 Chubby文件系統(tǒng)2.3.5 通信協(xié)議2.3.6 正確性與性能19Chubby客戶端與服務(wù)器端的通信過程2.3 分布式鎖服務(wù)Chubby20可能出現(xiàn)的兩種故障2.3 分布式鎖服務(wù)Chubby客戶端租約過期主服務(wù)器出錯122.3 分布式鎖服務(wù)Chubby2.3.1 Paxos算法2.3.2 Chubby系統(tǒng)設(shè)計2.3.3 Chubby中的Paxos2.3.4 Chubby文件系統(tǒng)2.3.5 通信協(xié)議2.3.6 正確性與性能22一

12、致性2.3 分布式鎖服務(wù)Chubby正確性與性能每個Chubby單元是由五個副本組成的，這五個副本中需要選舉產(chǎn)生一個主服務(wù)器，這種選舉本質(zhì)上就是一個一致性問題安全性采用的是ACL形式的安全保障措施。只要不被覆寫，子節(jié)點都是直接繼承父節(jié)點的ACL名性能優(yōu)化提高主服務(wù)器默認(rèn)的租約期、使用協(xié)議轉(zhuǎn)換服務(wù)將Chubby協(xié)議轉(zhuǎn)換成較簡單的協(xié)議、客戶端一致性緩存等23Chubby 的 ACL 機制2.3 分布式鎖服務(wù)Chubby用戶chinacloud提出向文件CLOUD中寫入內(nèi)容的請求。CLOUD首先讀取自身的寫ACL名fun，接著在fun中查到了chinacloud這一行記錄，于是返回信息允許china

13、cloud對文件進(jìn)行寫操作，此時chinacloud才被允許向CLOUD寫入內(nèi)容。其他的操作和寫操作類似。目錄 2.1 Google文件系統(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.9 Google應(yīng)用程序引擎242.4 分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable2.4.1 設(shè)計動機與目標(biāo)2.4.2 數(shù)據(jù)模型2.4.3 系統(tǒng)架構(gòu)2.4.4 主服

14、務(wù)器2.4.5 子表服務(wù)器2.4.6 性能優(yōu)化262.4 分布式結(jié)構(gòu)化數(shù)據(jù)表BigtableBigtable 的設(shè)計動機123需要存儲的數(shù)據(jù)種類繁多海量的服務(wù)請求商用數(shù)據(jù)庫 無法滿足需求包括URL、網(wǎng)頁內(nèi)容、用戶的個性化設(shè)置在內(nèi)的數(shù)據(jù)都是Google需要經(jīng)常處理的Google運行著目前世界上最繁忙的系統(tǒng)，它每時每刻處理的客戶服務(wù)請求數(shù)量是普通的系統(tǒng)根本無法承受的一方面現(xiàn)有商用數(shù)據(jù)庫的設(shè)計著眼點在于其通用性。另一方面對于底層系統(tǒng)的完全掌控會給后期的系統(tǒng)維護(hù)、升級帶來極大的便利272.4 分布式結(jié)構(gòu)化數(shù)據(jù)表BigtableBigtable 應(yīng)達(dá)到的基本目標(biāo)廣泛的適用性很強的可擴展性高可用性簡單性B

15、igtable是為了滿足一系列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è)計動機與目標(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)化29Bigtable數(shù)據(jù)的存儲格式2.4 分布式結(jié)構(gòu)化數(shù)據(jù)表BigtableBigtable是一個分布式多維映射表，表中的數(shù)據(jù)通過一個行關(guān)鍵字（Row Key）、一個列關(guān)鍵字（Column Key）以及一個時間戳（Time St

16、amp）進(jìn)行索引Bigtable的存儲邏輯可以表示為：(row:string, column:string, time:int64)string302.4 分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable行列時間戳Bigtable的行關(guān)鍵字可以是任意的字符串，但是大小不能夠超過64KB表中數(shù)據(jù)都是根據(jù)行關(guān)鍵字進(jìn)行排序的，排序使用的是詞典序同一地址域的網(wǎng)頁會被存儲在表中的連續(xù)位置倒排便于數(shù)據(jù)壓縮，可以大幅提高壓縮率將其組織成所謂的列族（Column Family）族名必須有意義，限定詞則可以任意選定組織的數(shù)據(jù)結(jié)構(gòu)清晰明了，含義也很清楚族同時也是Bigtable中訪問控制（Access Control）的基本單

17、元Bigtable中的時間戳是64位整型數(shù)，具體的賦值方式可以用戶自行定義Google的很多服務(wù)比如網(wǎng)頁檢索和用戶的個性化設(shè)置等都需要保存不同時間的數(shù)據(jù)，這些不同的數(shù)據(jù)版本必須通過時間戳來區(qū)分。2.4 分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable2.4.1 設(shè)計動機與目標(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)化32Bigtable 基本架構(gòu)2.4 分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable332.4 分布式結(jié)構(gòu)化數(shù)據(jù)表BigtableBigtable 中 Chubby 的主要作用作用一選取并保證同一時間內(nèi)只有一個主服務(wù)器（Master Server）

18、。獲取子表的位置信息。保存Bigtable的模式信息及訪問控制列表。作用二作用三2.4 分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable2.4.1 設(shè)計動機與目標(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)化352.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ù)

19、器的加入或撤銷362.4 分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable從Chubby中獲取一個獨占鎖，確保同一時間只有一個主服務(wù)器Bigtable 中 Chubby 的主要作用掃描服務(wù)器目錄，發(fā)現(xiàn)目前活躍的子表服務(wù)器與所有的活躍子表服務(wù)器取得聯(lián)系以便了解所有子表的分配情況通過掃描元數(shù)據(jù)表（Metadata Table），發(fā)現(xiàn)未分配的子表并將其分配到合適的子表服務(wù)器步驟 1 步驟 3 步驟 2 步驟 42.4 分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable2.4.1 設(shè)計動機與目標(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)化3864KB塊64KB塊SSTabl

20、e索引SSTable 格式的基本示意2.4 分布式結(jié)構(gòu)化數(shù)據(jù)表BigtableSSTable是Google為Bigtable設(shè)計的內(nèi)部數(shù)據(jù)存儲格式。所有的SSTable文件都存儲在GFS上，用戶可以通過鍵來查詢相應(yīng)的值。39子表實際組成日志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個左右40Chubby文件根子表（元數(shù)據(jù)表中第一條記錄）用

21、戶表1用戶表N其他元數(shù)據(jù)子表子表地址組成2.4 分布式結(jié)構(gòu)化數(shù)據(jù)表BigtableBigtable系統(tǒng)的內(nèi)部采用的是一種類似B+樹的三層查詢體系41Bigtable 數(shù)據(jù)存儲及讀/寫操作2.4 分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable較新的數(shù)據(jù)存儲在內(nèi)存中一個稱為內(nèi)存表（Memtable）的有序緩沖里，較早的數(shù)據(jù)則以SSTable格式保存在GFS中。讀和寫操作有很大的差異性42三種形式壓縮之間的關(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è)計動機與目標(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)化44局部性群組2.4 分布式結(jié)構(gòu)化數(shù)據(jù)表BigtableBigtable允許用戶將原本并不存儲在一起的數(shù)據(jù)以列族為單位，根據(jù)需要組織在一個單獨的SSTable中，以構(gòu)成一個局部性群組。用戶可以只看自己感興趣的內(nèi)容。對于一些較小的且會被經(jīng)常讀取的局部性群組，明顯地改善讀取效率。452.4 分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable壓縮12利用Bentley