提綱

Google文件系統GFS

分布式數據處理MapReduce

分布式鎖服務Chubby

分布式結構化數據表Bigtable

分布式存儲系統Megastore

大規模分布式系統的監控基礎架構Dapper

Google應用程序引擎分布式存儲系統Megastore

設計目標及方案選擇

Megastore數據模型

Megastore中的事務及并發控制

Megastore基本架構

核心技術——復制

產品性能及控制措施

在互聯網的應用中，為了達到好的可擴展性，常常會采用NoSQL存儲方式。但是從應用程序的構建方面來看，傳統的關系型數據庫又有著NoSQL所不具備的優勢。

Google設計和構建了用于互聯網中交互式服務的分布式存儲系統Megastore，該系統成功的將關系型數據庫和NoSQL的特點與優勢進行了融合設計目標及方案選擇

可用性——實現了一個同步的、容錯的、適合遠距離傳輸的復制機制。引入Paxos算法并對其做出一定的改進以滿足遠距離同步復制的要求

可擴展性

——借鑒了數據庫中數據分區的思想，將整個大的數據分割成很多小的數據分區，每個數據分區連同它自身的日志存放在NoSQL數據庫中，具體來說就是存放在Bigtable中

設計目標一種介于傳統的關系型數據庫和NoSQL之間的存儲技術，盡可能達到高可用性和高可擴展性的統一

數據分區和復制

數據分區和復制

Megastore中，這些小的數據分區被稱為實體組集（EntityGroups）。

每個實體組集包含若干實體組（EntityGroup，相當于分區中表的概念），而一個實體組中又包含很多的實體（Entity，相當于表中記錄的概念）。

從圖中還可以看出單個實體組支持ACID語義實體組集之間只具有比較松散的一致性。每個實體組都通過復制技術在數據中心中保存若干數據副本，這些實體組及其副本都存儲在NoSQL數據庫（Bigtable）中

分布式存儲系統Megastore

設計目標及方案選擇

Megastore數據模型

Megastore中的事務及并發控制

Megastore基本架構

核心技術——復制

產品性能及控制措施Megastore數據模型

傳統的關系型數據庫是通過連接（Join）來滿足用戶的需求的，但是就Megastore而言，這種數據模型是不合適的，主要有以下三個原因：（1）對于高負載的交互式應用來說，可預期的性能提升要比使用一種代價高昂的查詢語言所帶來的好處多（2）Megastore所面對的應用是讀遠多于寫，因此好的選擇是將讀操作所需要做的工作盡可能地轉移到寫操作上（3）在Bigtable這樣的鍵/值存儲系統中存儲和查詢級聯數據（HierarchicalData）是很方便的

Megastore數據模型怎么設計？

Google設計了一種能夠提供細粒度控制的數據模型和模式語言

同關系型數據庫一樣，Megastore的數據模型是在模式（schema）中定義的且是強類型的（stronglytyped）

每個模式都由一系列的表（tables）構成，表又包含有一系列的實體（entities），每實體中包含一系列屬性（properties）

屬性是命名的且具有類型，這些類型包括字符型（strings）、數字類型（numbers）或者Google的ProtocolBuffers。這些屬性可以被設置成必須的（required）、可選的（optional）或者可重復的（repeated，即允許單個屬性上有多個值）

數據模型實例

照片共享服務數據模型實例

圖中表Photo就是一個子表，因為它聲明了一個外鍵；User則是一個根表。一個Megastore實例中可以有若干個不同的根表，表示不同類型的實體組集圖中實例還可以看到三種不同屬性設置，既有必須的（如user_id），也有可選的（如thumbnail_url）；值得注意的是Photo中的可重復類型的tag屬性，這也就意味著一個Photo中允許同時出現多個tag屬性

索引（Index）

Megastore索引分成兩大類：局部索引（localindex）和全局索引（globalindex）

局部索引定義在單個實體組中，作用域僅限于單個實體組（如PhotosByTime

）

全局索引則可以橫跨多個實體組集進行數據讀取操作（如PhotosByTag

）Megastore還提供了一些額外的索引特性：

STORING子句（STORINGClause）

可重復的索引（RepeatedIndexes）

內聯索引（InlineIndexes）Bigtable中數據存儲情況

行鍵（RowKey）UPhoto.timePhoto.tagPhoto._url101John101,50012:30:01Dinner,Paris…101,50212:15:22Betty,Paris…102Mary表中不難看出——Bigtable的列名實際上是表名和屬性名結合在一起得到，不同表中實體可存儲在同一個Bigtable行中分布式存儲系統Megastore

設計目標及方案選擇

Megastore數據模型

Megastore中的事務及并發控制

Megastore基本架構

核心技術——復制

產品性能及控制措施Megastore中的事務及并發控制

Megastore三種方式的讀，分別是current、snapshot和inconsistent

其中current讀和snapshot讀總是在單個實體組中完成

對于snapshot讀，系統取出已知的最后一個完整提交的事務的時間戳，接著從這個位置讀數據

inconsistent讀忽略日志的狀態直接讀取最新的值Megastore中的事務及并發控制

Megastore事務中的寫操作采用了預寫式日志（Write-aheadLog）

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

協議使用了樂觀并發（OptimisticConcurrency）：盡管可能有多個寫操作同時試圖寫同一個日志位置，但只會有1個成功讀：獲取最后一次提交的事務的時間戳和日志位置完整事務周期應用邏輯：從Bigtable讀取且聚集數據到日志入口提交：使用Paxos達到一致，將個入口追加到日志生效：將數據更新到Bigtable中的實體和索引清除：清理不再需要的數據Megastore中的事務機制

消息隊列機制

消息能夠橫跨實體組

每個消息都有一個發送和接收實體組

如果兩個實體組是不同的，則傳輸將是異步

特點

規模：聲明一個隊列后可以在其他所有的實體組上創建一個收件箱

支持兩階段提交

增加競爭風險，不鼓勵使用

Megastore中的事務機制

分布式存儲系統Megastore

設計目標及方案選擇

Megastore數據模型

Megastore中的事務及并發控制

Megastore基本架構

核心技術——復制

產品性能及控制措施Megastore的基本架構

Megastore中三種副本

完整副本：Bigtable中存儲完整的日志和數據

見證者副本：在Paxos算法執行過程中無法產生一個決議時參與投票

只讀副本：讀取最近過去某一個時間點一致性數據

Megastore的基本架構

Megastore中提供快速讀（FastReads）和快速寫（FastWrites）機制

快速讀

如果讀操作不需要副本之間進行通信即可完成，那么讀取的效率必然相對較高

利用本地讀取（LocalReads）實現快速讀，能夠帶來更好的用戶體驗及更低的延遲

確保快速讀成功的關鍵是保證選擇的副本上數據是最新的。為了達到這一目標，引入了協調者的概念

協調者是一個服務，該服務分布在每個副本的數據中心里面。它的主要作用就是跟蹤一個實體組集合

協調者的狀態是由寫算法來保證

快速寫

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

Megastore沒有使用專門的主服務器，而是使用leaders

leader主要是來裁決哪個寫入的值可以獲取0號提議

優化：提交值最多的位置附近選擇一副本作為leader

客戶端、網絡及Bigtable的故障都會導致一個寫操作處于不確定的狀態分布式存儲系統Megastore

設計目標及方案選擇

Megastore數據模型

Megastore中的事務及并發控制

Megastore基本架構

核心技術——復制

產品性能及控制措施復制的日志

預寫式日志

當日志有不完整的前綴時我們就稱一個日志副本有“缺失”（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）生效：將值的更新在盡可能多的副本上生效。如果選擇的值和原來提議的有沖突，返回一個沖突錯誤

協調者的可用性

協調者在系統中是比較重要的——協調者的進程運行在每個數據中心。每次的寫操作中都要涉及協調者，因此協調者的故障將會導致系統的不可用

Megastore使用了Chubby鎖服務，為了處理請求，一個協調者必須持有多數鎖。一旦因為出現問題導致它丟失了大部分鎖，協調者就會恢復到一個默認保守狀態除了可用性問題，對于協調者的讀寫協議必須滿足一系列的競爭條件

分布式存儲系統Megastore

設計目標及方案選擇

Megastore數據模型

Megastore中的事務及并發控制

Megastore基本架構

核心技術——復制

產品性能及控制措施可用性分布情況

可用性分布情況

Megastore在Google中已經部署和使用了若干年，有超過100個產品使用Megastore作為其存儲系統

從圖中可以看出，絕大多數產品具有極高的可用性（>99.999%）。這表明Megastore系統的設計是非常成功的，基本達到了預期目標

產品延遲情況分布

應用程序的平均讀取延遲在萬分之一毫秒之內，平均寫入延遲在100