電子工業出版社《云計算(第三版)》配套課件第2章Google云計算原理與應用（三）目錄

2.1Google文件系統GFS2.2分布式數據處理MapReduce2.3分布式鎖服務Chubby2.4分布式結構化數據表Bigtable2.5分布式存儲系統Megastore2.6

大規模分布式系統的監控基礎架構Dapper2.7海量數據的交互式分析工具Dremel2.8內存大數據分析系統PowerDrill2.9Google應用程序引擎2.5分布式存儲系統Megastore2.5.1設計目標及方案選擇2.5.2Megastore數據模型2.5.3Megastore中的事務及并發控制2.5.4Megastore基本架構2.5.5核心技術——復制2.5.6產品性能及控制措施在互聯網的應用中，為了達到好的可擴展性，常常會采用NoSQL存儲方式。但是從應用程序的構建方面來看，傳統的關系型數據庫又有著NoSQL所不具備的優勢。

Google設計和構建了用于互聯網中交互式服務的分布式存儲系統Megastore，該系統成功的將關系型數據庫和NoSQL的特點與優勢進行了融合針對可用性的要求，實現了一個同步的、容錯的、適合遠距離傳輸的復制機制。針對可擴展性的要求，將整個大的數據分割成很多小的數據分區，每個數據分區連同它自身的日志存放在NoSQL數據庫中，具體來說就是存放在Bigtable中。設計目標及方案選擇2.5分布式存儲系統Megastore設計一種介于傳統的關系型數據庫和NoSQL之間的存儲技術，盡可能達到高可用性和高可擴展性的統一。方法一設計目標方法二5數據分區和復制

數據分區和復制Megastore中，這些小的數據分區被稱為實體組集（EntityGroups）。每個實體組集包含若干實體組（EntityGroup，相當于分區中表的概念），而一個實體組中又包含很多的實體（Entity，相當于表中記錄的概念）。從圖中還可以看出單個實體組支持ACID語義實體組集之間只具有比較松散的一致性。每個實體組都通過復制技術在數據中心中保存若干數據副本，這些實體組及其副本都存儲在NoSQL數據庫（Bigtable）中

2.5分布式存儲系統Megastore2.5.1設計目標及方案選擇2.5.2Megastore數據模型2.5.3Megastore中的事務及并發控制2.5.4Megastore基本架構2.5.5核心技術——復制2.5.6產品性能及控制措施82.5分布式存儲系統Megastore傳統的關系型數據庫不合適的三個原因傳統的關系型數據庫是通過連接（Join）來滿足用戶的需求的，但是就Megastore而言，這種數據模型是不合適的，主要有以下三個原因：原因1對于高負載的交互式應用來說，可預期的性能提升要比使用一種代價高昂的查詢語言所帶來的好處多原因2Megastore所面對的應用是讀遠多于寫，因此好的選擇是將讀操作所需要做的工作盡可能地轉移到寫操作上原因3在Bigtable這樣的鍵/值存儲系統中存儲和查詢級聯數據（HierarchicalData）是很方便的Megastore數據模型怎么設計？102.5分布式存儲系統Megastore細粒度控制的數據模型和模式語言同關系型數據庫一樣，Megastore的數據模型是在模式（schema）中定義的且是強類型的（stronglytyped）每個模式都由一系列的表（tables）構成，表又包含有一系列的實體（entities），每實體中包含一系列屬性（properties）屬性是命名的且具有類型，這些類型包括字符型（strings）、數字類型（numbers）或者Google的ProtocolBuffers。Google團隊設計的Megastore數據模型112.5分布式存儲系統Megastore照片共享服務數據模型實例表Photo就是一個子表，因為它聲明了一個外鍵User則是一個根表一個Megastore實例中可以有若干個不同的根表，表示不同類型的實體組集三種不同屬性設置，既有必須的（如user_id），也有可選的（如thumbnail_url）Photo中的可重復類型的tag屬性122.5分布式存儲系統MegastoreMegastore索引局部索引定義在單個實體組中，作用域僅限于單個實體組（如PhotosByTime）可以橫跨多個實體組集進行數據讀取操作（如PhotosByTag）全局索引主要兩類額外索引STORING子句（STORINGClause）可重復的索引（RepeatedIndexes）內聯索引（InlineIndexes）132.5分布式存儲系統MegastoreBigtable中存儲情況行鍵（RowKey）UPhoto.timePhoto.tagPhoto._url101John101,50012:30:01Dinner,Paris…101,50212:15:22Betty,Paris…102MaryBigtable的列名實際上是表名和屬性名結合在一起得到，不同表中實體可存儲在同一個Bigtable行中2.5分布式存儲系統Megastore2.5.1設計目標及方案選擇2.5.2Megastore數據模型2.5.3Megastore中的事務及并發控制2.5.4Megastore基本架構2.5.5核心技術——復制2.5.6產品性能及控制措施15Megastore提供的三種讀currentsnapshotinconsistent總是在單個實體組中完成總是在單個實體組中完成系統取出已知的最后一個完整提交的事務的時間戳，接著從這個位置讀數據忽略日志的狀態直接讀取最新的值2.5分布式存儲系統MegastoreMegastore中的事務及并發控制Megastore事務中的寫操作采用了預寫式日志（Write-aheadLog）

一個寫事務總是開始于一個current讀以便確認下一個可用的日志位置。提交操作將數據變更聚集到日志，接著分配一個比之前任意一個都高的時間戳，然后使用Paxos將數據變更加入到日志中

協議使用了樂觀并發（OptimisticConcurrency）：盡管可能有多個寫操作同時試圖寫同一個日志位置，但只會有1個成功17完整的事務周期讀應用邏輯提交生效清除獲取最后一次提交的事務的時間戳和日志位置從Bigtable讀取且聚集數據到日志入口使用Paxos達到一致，將入口追加到日志將數據更新到Bigtable中的實體和索引清理不再需要的數據2.5分布式存儲系統Megastore182.5分布式存儲系統MegastoreMegastore中的事務機制2.5分布式存儲系統Megastore2.5.1設計目標及方案選擇2.5.2Megastore數據模型2.5.3Megastore中的事務及并發控制2.5.4Megastore基本架構2.5.5核心技術——復制2.5.6產品性能及控制措施Megastore的基本架構Megastore中三種副本

完整副本：Bigtable中存儲完整的日志和數據見證者副本：在Paxos算法執行過程中無法產生一個決議時參與投票只讀副本：讀取最近過去某一個時間點一致性數據

Megastore的基本架構Megastore中提供快速讀（FastReads）和快速寫（FastWrites）機制

快速讀如果讀操作不需要副本之間進行通信即可完成，那么讀取的效率必然相對較高利用本地讀取（LocalReads）實現快速讀，能夠帶來更好的用戶體驗及更低的延遲確保快速讀成功的關鍵是保證選擇的副本上數據是最新的。為了達到這一目標，引入了協調者的概念

協調者是一個服務，該服務分布在每個副本的數據中心里面。它的主要作用就是跟蹤一個實體組集合協調者的狀態是由寫算法來保證快速寫

Megastore采用了一種在主/從式系統中常用的優化方法。如果一次寫成功，那么下一次寫的時候就跳過準備過程，直接進入接受階段

Megastore沒有使用專門的主服務器，而是使用leadersleader主要是來裁決哪個寫入的值可以獲取0號提議優化：提交值最多的位置附近選擇一副本作為leader

客戶端、網絡及Bigtable的故障都會導致一個寫操作處于不確定的狀態2.5分布式存儲系統Megastore2.5.1設計目標及方案選擇2.5.2Megastore數據模型2.5.3Megastore中的事務及并發控制2.5.4Megastore基本架構2.5.5核心技術——復制2.5.6產品性能及控制措施242.5分布式存儲系統Megastore復制的日志每個副本都存有記錄所有更新的數據。Megastore允許副本不按順序接受日志，這些日志將獨立的存儲在Bigtable中。預寫式日志復制的日志

預寫式日志當日志有不完整的前綴時我們就稱一個日志副本有“缺失”（Holes）

圖中0～99的日志位置已經被全部清除；100的日志位置被部分清除；101的日志位置被全部副本接受；102的日志位置被γ獲得；103的日志位置被副本A和C接受，副本B則留下了一個“缺失”；104的日志位置則未達到一致性數據讀取

數據讀取數據讀取過程:本地查詢（QueryLocal）發現位置（FindPosition）

本地讀取（LocalRead）

多數派讀取（MajorityRead）追趕（Catchup）

Paxos將會促使絕大多數副本達成一個共識值達到一種分布式一致狀態驗證（Validate）查詢數據（QueryData）數據寫入

數據寫入數據寫入完整過程:（1）接受leader：請求leader接受值作為0號提議（快速寫方法），若成功，跳至步驟（3）（2）準備：將值替換成擁有最高提議號的那個值（3）接受：請求剩余的副本接受該值，如果大多數副本拒絕這個值，返回步驟（2）（4）失效：將不接受值的副本上的協調者進行失效操作（5）生效：將值的更新在盡可能多的副本上生效。如果選擇的值和原來提議的有沖突，返回一個沖突錯誤

282.5分布式存儲系統Megastore協調者的可用性協調者在系統中是比較重要的——協調者的進程運行在每個數據中心。每次的寫操作中都要涉及協調者，因此協調者的故障將會導致系統的不可用Megastore使用了Chubby鎖服務，為了處理請求，一個協調者必須持有多數鎖。一旦因為出現問題導致它丟失了大部分鎖，協調者就會恢復到一個默認保守狀態除了可用性問題，對于協調者的讀寫協議必須滿足一系列的競爭條件2.5分布式存儲系統Megastore2.5.1設計目標及方案選擇2.5.2Megastore數據模型2.5.3Megastore中的事務及并發控制2.5.4Megastore基本架構2.5.5核心技術——復制2.5.6產品性能及控制措施302.5分布式存儲系統Megastore可用性的分布情況Megastore在Google中已經部署和使用了若干年，有超過100個產品使用Megastore作為其存儲系統從圖中可以看出，絕大多數產品具有極高的可用性（>99.999%）。這表明Megastore系統的設計是非常成功的，基本達到了預期目標31產品延遲情況的分布2.5分布式存儲系統Megastore應用程序的平均讀取延遲在萬分之一毫秒之內，平均寫入延遲在100至400毫秒之間避免Megastore的性能下降，可采取以下三種應對方法：（1）重新選擇路由使客戶端繞開出現問題的副本（2）將出現問題副本上的協調者禁用，確保問題的影響降至最小。（3）禁用整個副本需要指出：Megastore已經是Google相對過時的存儲技術。Google目前正在使用的存儲系統是Spanner架構，Spanner的設計目標是能夠控制一百萬到一千萬臺服務器，Spanner最強大之處在于能夠在50毫秒之內為數據傳遞提供通道目錄

2.1Google文件系統GFS2.2分布式數據處理MapReduce2.3分布式鎖服務Chubby2.4分布式結構化數據表Bigtable2.5分布式存儲系統Megastore2.6大規模分布式系統的監控基礎架構Dapper2.7海量數據的交互式分析工具Dremel2.8內存大數據分析系統PowerDrill2.9Google應用程序引擎2.6大規模分布式系統的監控

基礎架構Dapper2.6.1基本設計目標2.6.2Dapper監控系統簡介2.6.3關鍵性技術2.6.4常用Dapper工具2.6.5Dapper使用經驗在我們看來很簡單的一次搜索實際上涉及了眾多Google后臺子系統，這些子系統的運行狀態都需要進行監控用戶的平均每一次前臺搜索會導致Google的后臺發生1011次的處理352.6大規模分布式系統的監控基礎架構Dapper兩個基本要求設計出的監控系統應當能夠對盡可能多的Google服務進行監控Google的服務是全天候的，如果不能對Google的后臺同樣進行全天候的監控很可能會錯過某些無法再現的關鍵性故障監控系統設計兩個基本要求1.廣泛可部署性（UbiquitousDeployment）2.不間斷的監控362.6大規模分布式系統的監控基礎架構Dapper三個基本設計目標低開銷這個是廣泛可部署性的必然要求。監控系統的開銷越低，對于原系統的影響就越小，系統的開發人員也就越愿意接受這個監控系統。對應用層透明監控系統對程序員應當是不可見的。如果監控系統的使用需要程序開發人員對其底層的一些細節進行調整才能正常工作的話，這個監控系統肯定不是一個完善的監控系統。可擴展性Google的服務增長速度是驚人的，設計出的系統至少在未來幾年里要能夠滿足Google服務和集群的需求。2.6大規模分布式系統的監控

基礎架構Dapper2.6.1基本設計目標2.6.2Dapper監控系統簡介2.6.3關鍵性技術2.6.4常用Dapper工具2.6.5Dapper使用經驗基本概念

圖中，用戶發出請求X，前端A發現該請求的處理需要涉及服務器B和服務器C，因此A又向B和C發出兩個RPC（遠程過程調用）。B收到后立刻做出響應，但是C在接到后發現它還需要調用服務器D和E才能完成請求X，因此C對D和E分別發出了RPC，D和E接到后分別做出了應答，收到D和E的應答之后C才向A做出響應，在接收到B和C的應答之后A才對用戶請求X做出一個應答X

在監控系統中記錄下所有這些消息不難，如何將這些消息記錄同特定的請求（本例中的X）關聯起來才是分布式監控系統設計中需要解決的關鍵性問題之一典型分布式系統的請求及應答過程

方案一黑盒（BlackBox）方案——方案比較輕便，但在消息關系判斷過程中，主要是利用一些統計學知識來進行推斷，有時不是很準確方案二基于注釋的方案

——利用應用程序或中間件給每條記錄賦予一個全局性的標示符，借此將相關消息串聯起來（Google最終選擇）基本概念

Dapper監控系統中三個基本概念：監控樹（TraceTree）、區間（Span）和注釋（Annotation）圖示是一個典型的監控樹，實際上就是一個同特定事件相關的按照一定的規律以樹的形式組織起來所有消息，每一個節點稱為一個區間（一條記錄），所有記錄聯系在一起就構成了對某個事件的完整監控。每個區間包括如下的內容：區間名（SpanName）、區間id（Spanid）、父id（Parentid）和監控id（Traceid）

監控樹監控id圖中并沒有列出，一棵監控樹中所有區間的監控id相同，隨機分配且唯一區間Helper.Call的詳細信息圖中區間包含來自客戶端的注釋信息：“<Start>”、“ClientSend”、“ClientRecv”和“<End>”，也包含來自服務器端的注釋信息：“ServerRecv”、“foo”和“ServerSend”。除“foo”是用戶自定義的注釋外，其他的注釋信息都是和時間相關的信息。Dapper不但支持用戶進行簡單的文本方式的注釋，還支持鍵-值對方式的注釋基本概念

412.6大規模分布式系統的監控基礎架構Dapper監控信息的匯總（1）將區間的數據寫入到本地的日志文件（2）所有機器上的本地日志文件匯集（3）匯集后的數據寫入到Bigtable存儲庫中監控數據匯總是單獨進行的，而不是伴隨系統對用戶的應答一起返回的，如此選擇主要原因：內置的匯總方案（監控數據隨RPC應答頭返回）會影響網絡動態內置的匯總方案需要保證所有的RPC都是完全嵌套安全問題

應用層注釋提供一種方便的選擇機制（Opt-inMechanism）：應用程序開發者可以將任何對后期分析有益的數據和區間關聯起來

2.6大規模分布式系統的監控

基礎架構Dapper2.6.1基本設計目標2.6.2Dapper監控系統簡介2.6.3關鍵性技術2.6.4常用Dapper工具2.6.5Dapper使用經驗Dapper三個設計目標中，實現難度最大的是？應用層透明怎么實現應用層透明輕量級的核心功能庫

二次抽樣技術

452.6大規模分布式系統的監控基礎架構Dapper輕量級核心功能庫最關鍵的代碼基礎是基本RPC、線程和控制流函數庫的實現主要功能是實現區間創建、抽樣和在本地磁盤上記錄日志。將復雜的功能實現限制在一個輕量級的核心功能庫中保證了Dapper的監控過程基本對應用層透明。小規模庫通用線程（UbiquitousThreading）控制流（ControlFlow）RPC代碼庫（RPCLibraryCode）462.6大規模分布式系統的監控基礎架構Dapper二次抽樣技術利用二次抽樣技術成功地解決了低開銷及廣泛可部署性的問題。第一次抽樣第二次抽樣實踐中，設計人員發現當抽樣率低至1/1024時也能夠產生足夠多的有效監控數據，即在1024個請求中抽取1個進行監控也是可行的，從而可以捕獲有效數據發生在數據寫入Bigtable前，具體方法是將監控id散列成一個標量z（0≤z≤1），如果某個區間的z小于事先定義好的匯總抽樣系數，則保留這個區間并將它寫入Bigtable，否則丟棄2.6大規模分布式系統的監控

基礎架構Dapper2.6.1基本設計目標2.6.2Dapper監控系統簡介2.6.3關鍵性技術2.6.4常用Dapper工具2.6.5Dapper使用經驗482.6大規模分布式系統的監控基礎架構DapperDapper存儲APIDapper的“存儲API”簡稱為DAPI，提供了對分散在區域Dapper存儲庫（DEPOTS）的監控記錄的直接訪問。一般有以下三種方式訪問這些記錄。（1）通過監控id訪問（AccessbyTraceid）（2）塊訪問（B