1、of55電子工業出版社云計算(第三版)配套課件云 計 算（第三版）CLOUD COMPUTING Third Edition主編：劉鵬 教授第 2 章Google云計算原理與應用（二）本套PPT下載地址：http:/ 教授、博導、學科帶頭人，清華大學博士。現任中國云計算專家咨詢委員會秘書長、中國信息協會大數據分會副會長、工業與信息化部云計算研究中心專家。 主持完成科研項目25項，發表論文80余篇，出版專業書籍15本。獲部級科技進步二等獎4項、三等獎4項。主編了國內第一本云計算教材云計算和第一本云計算編程書籍實戰Hadoop。創辦了知名的中國云計算（）和中國大數據（）網站。 曾率隊奪得2002

2、PennySort國際計算機排序比賽冠軍，兩次奪得全國高校科技比賽最高獎，并三次奪得清華大學科技比賽最高獎。 榮獲“全軍十大學習成才標兵”（排名第一）、南京“十大杰出青年”、江蘇省“333高層次人才培養工程”中青年科學技術帶頭人、清華大學“學術新秀”等稱號。劉 鵬of55云計算第三版配套PPT課件2.1 Google文件系統GFS2.2 分布式數據處理MapReduce2.3 分布式鎖服務Chubby2.4 分布式結構化數據表Bigtable2.5 分布式存儲系統Megastore2.6 大規模分布式系統的監控基礎架構Dapper2.7 海量數據的交互式分析工具Dremel2.8 內存大數據分

3、析系統PowerDrill2.9 Google應用程序引擎of55云計算第三版配套PPT課件初步了解ChubbyChubby是Google設計的提供粗粒度鎖服務的一個文件系統，它基于松耦合分布式系統，解決了分布的一致性問題。通過使用Chubby的鎖服務，用戶可以確保數據操作過程中的一致性Chubby作為一個穩定的存儲系統存儲包括元數據在內的小數據Google內部還使用Chubby進行名字服務（Name Server）52.3 分布式鎖服務Chubbyof55云計算第三版配套PPT課件2.3 分布式鎖服務Chubby2.3.1 Paxos算法2.3.2 Chubby系統設計2.3.3 Chubb

4、y中的Paxos2.3.4 Chubby文件系統2.3.5 通信協議2.3.6 正確性與性能of55云計算第三版配套PPT課件Paxos算法proposersacceptorslearners提出決議批準決議獲取并使用已經通過的決議三個節點決議只有在被proposers提出后才能批準每次只批準一個決議只有決議確定被批準后learners才能獲取這個決議三個條件72.3 分布式鎖服務Chubbyof55云計算第三版配套PPT課件系統的約束條件p1：每個acceptor只接受它得到的第一個決議。p2：一旦某個決議得到通過，之后通過的決議必須和該決議保持一致。p2a：一旦某個決議v得到通過，之后任何

5、acceptor再批準的決議必須是v。p2b：一旦某個決議v得到通過，之后任何proposer再提出的決議必須是v。p2c：如果一個編號為n的提案具有值v，那么存在一個“多數派”，要么它們中沒有誰批準過編號小于n的任何提案，要么它們進行的最近一次批準具有值v。為了保證決議的唯一性，acceptors也要滿足一個約束條件：當且僅當 acceptors 沒有收到編號大于n的請求時，acceptors 才批準編號為n的提案。82.3 分布式鎖服務Chubbyof55云計算第三版配套PPT課件9一個決議分為兩個階段準備階段12批準階段proposers選擇一個提案并將它的編號設為n將它發送給accep

6、tors中的一個“多數派”acceptors 收到后，如果提案的編號大于它已經回復的所有消息，則acceptors將自己上次的批準回復給proposers，并不再批準小于n的提案。當proposers接收到acceptors 中的這個“多數派”的回復后，就向回復請求的acceptors發送accept請求，在符合acceptors一方的約束條件下，acceptors收到accept請求后即批準這個請求。2.3 分布式鎖服務Chubbyof55云計算第三版配套PPT課件2.3 分布式鎖服務Chubby2.3.1 Paxos算法2.3.2 Chubby系統設計2.3.3 Chubby中的Paxos

7、2.3.4 Chubby文件系統2.3.5 通信協議2.3.6 正確性與性能of55云計算第三版配套PPT課件54611Chubby的設計目標主要有以下幾點高可用性和高可靠性213高擴展性支持粗粒度的建議性鎖服務服務信息的直接存儲支持通報機制支持緩存機制2.3 分布式鎖服務Chubbyof55云計算第三版配套PPT課件客戶端應用程序客戶端應用程序Chubby程序率Chubby程序率遠程過程調用Chubby單元的五個服務器主服務器客戶端進程12Chubby的基本架構在客戶這一端每個客戶應用程序都有一個Chubby程序庫（Chubby Library），客戶端的所有應用都是通過調用這個庫中的相關函

8、數來完成的。服務器一端稱為Chubby單元，一般是由五個稱為副本（Replica）的服務器組成的，這五個副本在配置上完全一致，并且在系統剛開始時處于對等地位。客戶端服務器端2.3 分布式鎖服務Chubbyof55云計算第三版配套PPT課件2.3 分布式鎖服務Chubby2.3.1 Paxos算法2.3.2 Chubby系統設計2.3.3 Chubby中的Paxos2.3.4 Chubby文件系統2.3.5 通信協議2.3.6 正確性與性能of55云計算第三版配套PPT課件副本網絡Chubby客戶端網絡Chubby協議快照互換（Sanpshot exchange）Paxos協議本地文件系統日志文

9、件I/O快照容錯的日志（Fault-tolerant Log）容錯的數據庫（Fault-tolerant DB）ChubbyRPC14單個Chubby副本結構文件傳輸2.3 分布式鎖服務Chubbyof55云計算第三版配套PPT課件副本1副本2副本3值值值響應響應響應值提交客戶端應用程序Paxos構架Paxos協議15容錯日志的API2.3 分布式鎖服務Chubbyof55云計算第三版配套PPT課件2.3 分布式鎖服務Chubby2.3.1 Paxos算法2.3.2 Chubby系統設計2.3.3 Chubby中的Paxos2.3.4 Chubby文件系統2.3.5 通信協議2.3.6 正確性

10、與性能of55云計算第三版配套PPT課件17單調遞增的64位編號實例號Instance Number新節點實例號必定大于舊節點的實例號。1鎖生成號Lock Generation Number鎖被用戶持有時該號增加。內容生成號Content Generation Number文件內容修改時該號增加。23ACL生成號ACL Generation NumberACL名被覆寫時該號增加。42.3 分布式鎖服務Chubbyof55云計算第三版配套PPT課件 函 數 名 稱 作 用Open()打開某個文件或者目錄來創建句柄Close()關閉打開的句柄，后續的任何操作都將中止Poison()中止當前未完成及

11、后續的操作，但不關閉句柄GetContentsAndStat()返回文件內容及元數據GetStat()只返回文件元數據ReadDir()返回子目錄名稱及其元數據SetContents()向文件中寫入內容SetACL()設置ACL名稱Delete()如果該節點沒有子節點的話則執行刪除操作Acquire()獲取鎖Release()釋放鎖GetSequencer()返回一個sequencerSetSequencer()將sequencer和某個句柄進行關聯CheckSequencer()檢查某個sequencer是否有效18常用的句柄函數及作用2.3 分布式鎖服務Chubbyof55云計算第三版配套

12、PPT課件2.3 分布式鎖服務Chubby2.3.1 Paxos算法2.3.2 Chubby系統設計2.3.3 Chubby中的Paxos2.3.4 Chubby文件系統2.3.5 通信協議2.3.6 正確性與性能of55云計算第三版配套PPT課件20Chubby客戶端與服務器端的通信過程2.3 分布式鎖服務Chubbyof55云計算第三版配套PPT課件21可能出現的兩種故障2.3 分布式鎖服務Chubby客戶端租約過期主服務器出錯12of55云計算第三版配套PPT課件2.3 分布式鎖服務Chubby2.3.1 Paxos算法2.3.2 Chubby系統設計2.3.3 Chubby中的Paxo

13、s2.3.4 Chubby文件系統2.3.5 通信協議2.3.6 正確性與性能of55云計算第三版配套PPT課件23一致性2.3 分布式鎖服務Chubby正確性與性能每個Chubby單元是由五個副本組成的，這五個副本中需要選舉產生一個主服務器，這種選舉本質上就是一個一致性問題安全性采用的是ACL形式的安全保障措施。只要不被覆寫，子節點都是直接繼承父節點的ACL名性能優化提高主服務器默認的租約期、使用協議轉換服務將Chubby協議轉換成較簡單的協議、客戶端一致性緩存等of55云計算第三版配套PPT課件24Chubby 的 ACL 機制2.3 分布式鎖服務Chubby用戶chinacloud提出向

14、文件CLOUD中寫入內容的請求。CLOUD首先讀取自身的寫ACL名fun，接著在fun中查到了chinacloud這一行記錄，于是返回信息允許chinacloud對文件進行寫操作，此時chinacloud才被允許向CLOUD寫入內容。其他的操作和寫操作類似。of55云計算第三版配套PPT課件2.1 Google文件系統GFS2.2 分布式數據處理MapReduce2.3 分布式鎖服務Chubby2.4 分布式結構化數據表Bigtable2.5 分布式存儲系統Megastore2.6 大規模分布式系統的監控基礎架構Dapper2.7 海量數據的交互式分析工具Dremel2.8 內存大數據分析系統

15、PowerDrill2.9 Google應用程序引擎25of55云計算第三版配套PPT課件2.4 分布式結構化數據表Bigtable2.4.1 設計動機與目標2.4.2 數據模型2.4.3 系統架構2.4.4 主服務器2.4.5 子表服務器2.4.6 性能優化of55云計算第三版配套PPT課件272.4 分布式結構化數據表BigtableBigtable 的設計動機123需要存儲的數據種類繁多海量的服務請求商用數據庫 無法滿足需求包括URL、網頁內容、用戶的個性化設置在內的數據都是Google需要經常處理的Google運行著目前世界上最繁忙的系統，它每時每刻處理的客戶服務請求數量是普通的系統根

16、本無法承受的一方面現有商用數據庫的設計著眼點在于其通用性。另一方面對于底層系統的完全掌控會給后期的系統維護、升級帶來極大的便利of55云計算第三版配套PPT課件282.4 分布式結構化數據表BigtableBigtable 應達到的基本目標廣泛的適用性很強的可擴展性高可用性簡單性Bigtable是為了滿足一系列Google產品而并非特定產品的存儲要求。根據需要隨時可以加入或撤銷服務器確保幾乎所有的情況下系統都可用底層系統的簡單性既可以減少系統出錯的概率，也為上層應用的開發帶來便利of55云計算第三版配套PPT課件2.4 分布式結構化數據表Bigtable2.4.1 設計動機與目標2.4.2 數

17、據模型2.4.3 系統架構2.4.4 主服務器2.4.5 子表服務器2.4.6 性能優化of55云計算第三版配套PPT課件30Bigtable數據的存儲格式2.4 分布式結構化數據表BigtableBigtable是一個分布式多維映射表，表中的數據通過一個行關鍵字（Row Key）、一個列關鍵字（Column Key）以及一個時間戳（Time Stamp）進行索引Bigtable的存儲邏輯可以表示為：(row:string, column:string, time:int64)stringof55云計算第三版配套PPT課件312.4 分布式結構化數據表Bigtable行列時間戳Bigtable

18、的行關鍵字可以是任意的字符串，但是大小不能夠超過64KB表中數據都是根據行關鍵字進行排序的，排序使用的是詞典序同一地址域的網頁會被存儲在表中的連續位置倒排便于數據壓縮，可以大幅提高壓縮率將其組織成所謂的列族（Column Family）族名必須有意義，限定詞則可以任意選定組織的數據結構清晰明了，含義也很清楚族同時也是Bigtable中訪問控制（Access Control）的基本單元Bigtable中的時間戳是64位整型數，具體的賦值方式可以用戶自行定義Google的很多服務比如網頁檢索和用戶的個性化設置等都需要保存不同時間的數據，這些不同的數據版本必須通過時間戳來區分。of55云計算第三版配

19、套PPT課件2.4 分布式結構化數據表Bigtable2.4.1 設計動機與目標2.4.2 數據模型2.4.3 系統架構2.4.4 主服務器2.4.5 子表服務器2.4.6 性能優化of55云計算第三版配套PPT課件33Bigtable 基本架構2.4 分布式結構化數據表Bigtableof55云計算第三版配套PPT課件342.4 分布式結構化數據表BigtableBigtable 中 Chubby 的主要作用作用一選取并保證同一時間內只有一個主服務器（Master Ser ver）。獲取子表的位置信息。保存Bigtable的模式信息及訪問控制列表。作用二作用三of55云計算第三版配套PPT課

20、件2.4 分布式結構化數據表Bigtable2.4.1 設計動機與目標2.4.2 數據模型2.4.3 系統架構2.4.4 主服務器2.4.5 子表服務器2.4.6 性能優化of55云計算第三版配套PPT課件362.4 分布式結構化數據表Bigtable主服務器新子表分配子表服務器狀態監控子服務器之間的負載均衡當一個新的子表產生時，主服務器通過一個加載命令將其分配給一個空間足夠的子表服務器。創建新表、表合并以及較大子表的分裂都會產生一個或多個新子表。分割完成之后子服務器需要向主服務發出一個通知。主服務器必須對子表服務器的狀態進行監控，以便及時檢測到服務器的加入或撤銷of55云計算第三版配套PPT

21、課件372.4 分布式結構化數據表Bigtable從Chubby中獲取一個獨占鎖，確保同一時間只有一個主服務器Bigtable 中 Chubby 的主要作用掃描服務器目錄，發現目前活躍的子表服務器與所有的活躍子表服務器取得聯系以便了解所有子表的分配情況通過掃描元數據表（Metadata Table），發現未分配的子表并將其分配到合適的子表服務器步驟 1 步驟 3 步驟 2 步驟 4of55云計算第三版配套PPT課件2.4 分布式結構化數據表Bigtable2.4.1 設計動機與目標2.4.2 數據模型2.4.3 系統架構2.4.4 主服務器2.4.5 子表服務器2.4.6 性能優化of55云計

22、算第三版配套PPT課件3964KB塊64KB塊SSTable索引SSTable 格式的基本示意2.4 分布式結構化數據表BigtableSSTable是Google為Bigtable設計的內部數據存儲格式。所有的SSTable文件都存儲在GFS上，用戶可以通過鍵來查詢相應的值。of55云計算第三版配套PPT課件40子表實際組成日志64KB塊64KB塊SSTable索引64KB塊64KB塊SSTable索引2.4 分布式結構化數據表Bigtable不同子表的SSTable可以共享每個子表服務器上僅保存一個日志文件Bigtable規定將日志的內容按照鍵值進行排序每個子表服務器上保存的子表數量可以從

23、幾十到上千不等，通常情況下是100個左右of55云計算第三版配套PPT課件41Chubby文件根子表（元數據表中第一條記錄）用戶表1用戶表N其他元數據子表子表地址組成2.4 分布式結構化數據表BigtableBigtable系統的內部采用的是一種類似B+樹的三層查詢體系of55云計算第三版配套PPT課件42Bigtable 數據存儲及讀/寫操作 內 存 表 寫 操 作 讀 操 作 子 表 日 志 內 存 GFS SSTable文 件 2.4 分布式結構化數據表Bigtable較新的數據存儲在內存中一個稱為內存表（Memtable）的有序緩沖里，較早的數據則以SSTable格式保存在GFS中。讀

24、和寫操作有很大的差異性of55云計算第三版配套PPT課件43三種形式壓縮之間的關系2.4 分布式結構化數據表BigtableSSTableSSTable內存表SSTable內存表內存表次壓縮次壓縮SSTableSSTable合并壓縮SSTable主壓縮of55云計算第三版配套PPT課件2.4 分布式結構化數據表Bigtable2.4.1 設計動機與目標2.4.2 數據模型2.4.3 系統架構2.4.4 主服務器2.4.5 子表服務器2.4.6 性能優化of55云計算第三版配套PPT課件45 內容 語言 排名 SSTable SSTable n.www 局部性群組2.4 分布式結構化數據表BigtableBigtable允許用戶將原本并不存儲在一起的數據以列族為單位，根據需要組織在一個單獨的SSTable中，以構成一個局部性群組。用戶可以只看自己感興趣的內容。對于一些較小的且會被經常讀取的局部性群組，明顯地改善讀取效率。of55云計算第三版配套PPT課件462.4 分布式結構化數據表Bigtable壓縮12利用Bentley & McIlroy方式（BMDiff）在大的掃描窗口將常見的長串進行壓縮