云計(jì)算及應(yīng)用課件：分布式存儲(chǔ)系統(tǒng)Megastore

提綱

Google文件系統(tǒng)GFS

分布式數(shù)據(jù)處理MapReduce

分布式鎖服務(wù)Chubby

分布式結(jié)構(gòu)化數(shù)據(jù)表Bigtable

分布式存儲(chǔ)系統(tǒng)Megastore

大規(guī)模分布式系統(tǒng)的監(jiān)控基礎(chǔ)架構(gòu)Dapper

Google應(yīng)用程序引擎分布式存儲(chǔ)系統(tǒng)Megastore

設(shè)計(jì)目標(biāo)及方案選擇

Megastore數(shù)據(jù)模型

Megastore中的事務(wù)及并發(fā)控制

Megastore基本架構(gòu)

核心技術(shù)——復(fù)制

產(chǎn)品性能及控制措施

在互聯(lián)網(wǎng)的應(yīng)用中，為了達(dá)到好的可擴(kuò)展性，常常會(huì)采用NoSQL存儲(chǔ)方式。但是從應(yīng)用程序的構(gòu)建方面來看，傳統(tǒng)的關(guān)系型數(shù)據(jù)庫又有著NoSQL所不具備的優(yōu)勢(shì)。

Google設(shè)計(jì)和構(gòu)建了用于互聯(lián)網(wǎng)中交互式服務(wù)的分布式存儲(chǔ)系統(tǒng)Megastore，該系統(tǒng)成功的將關(guān)系型數(shù)據(jù)庫和NoSQL的特點(diǎn)與優(yōu)勢(shì)進(jìn)行了融合設(shè)計(jì)目標(biāo)及方案選擇

可用性——實(shí)現(xiàn)了一個(gè)同步的、容錯(cuò)的、適合遠(yuǎn)距離傳輸?shù)膹?fù)制機(jī)制。引入Paxos算法并對(duì)其做出一定的改進(jìn)以滿足遠(yuǎn)距離同步復(fù)制的要求

可擴(kuò)展性

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

設(shè)計(jì)目標(biāo)一種介于傳統(tǒng)的關(guān)系型數(shù)據(jù)庫和NoSQL之間的存儲(chǔ)技術(shù)，盡可能達(dá)到高可用性和高可擴(kuò)展性的統(tǒng)一

數(shù)據(jù)分區(qū)和復(fù)制

數(shù)據(jù)分區(qū)和復(fù)制

Megastore中，這些小的數(shù)據(jù)分區(qū)被稱為實(shí)體組集（EntityGroups）。

每個(gè)實(shí)體組集包含若干實(shí)體組（EntityGroup，相當(dāng)于分區(qū)中表的概念），而一個(gè)實(shí)體組中又包含很多的實(shí)體（Entity，相當(dāng)于表中記錄的概念）。

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

分布式存儲(chǔ)系統(tǒng)Megastore

設(shè)計(jì)目標(biāo)及方案選擇

Megastore數(shù)據(jù)模型

Megastore中的事務(wù)及并發(fā)控制

Megastore基本架構(gòu)

核心技術(shù)——復(fù)制

產(chǎn)品性能及控制措施Megastore數(shù)據(jù)模型

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

Megastore數(shù)據(jù)模型怎么設(shè)計(jì)？

Google設(shè)計(jì)了一種能夠提供細(xì)粒度控制的數(shù)據(jù)模型和模式語言

同關(guān)系型數(shù)據(jù)庫一樣，Megastore的數(shù)據(jù)模型是在模式（schema）中定義的且是強(qiáng)類型的（stronglytyped）

每個(gè)模式都由一系列的表（tables）構(gòu)成，表又包含有一系列的實(shí)體（entities），每實(shí)體中包含一系列屬性（properties）

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

數(shù)據(jù)模型實(shí)例

照片共享服務(wù)數(shù)據(jù)模型實(shí)例

圖中表Photo就是一個(gè)子表，因?yàn)樗暶髁艘粋€(gè)外鍵；User則是一個(gè)根表。一個(gè)Megastore實(shí)例中可以有若干個(gè)不同的根表，表示不同類型的實(shí)體組集圖中實(shí)例還可以看到三種不同屬性設(shè)置，既有必須的（如user_id），也有可選的（如thumbnail_url）；值得注意的是Photo中的可重復(fù)類型的tag屬性，這也就意味著一個(gè)Photo中允許同時(shí)出現(xiàn)多個(gè)tag屬性

索引（Index）

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

局部索引定義在單個(gè)實(shí)體組中，作用域僅限于單個(gè)實(shí)體組（如PhotosByTime

）

全局索引則可以橫跨多個(gè)實(shí)體組集進(jìn)行數(shù)據(jù)讀取操作（如PhotosByTag

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

STORING子句（STORINGClause）

可重復(fù)的索引（RepeatedIndexes）

內(nèi)聯(lián)索引（InlineIndexes）Bigtable中數(shù)據(jù)存儲(chǔ)情況

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

設(shè)計(jì)目標(biāo)及方案選擇

Megastore數(shù)據(jù)模型

Megastore中的事務(wù)及并發(fā)控制

Megastore基本架構(gòu)

核心技術(shù)——復(fù)制

產(chǎn)品性能及控制措施Megastore中的事務(wù)及并發(fā)控制

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

其中current讀和snapshot讀總是在單個(gè)實(shí)體組中完成

對(duì)于snapshot讀，系統(tǒng)取出已知的最后一個(gè)完整提交的事務(wù)的時(shí)間戳，接著從這個(gè)位置讀數(shù)據(jù)

inconsistent讀忽略日志的狀態(tài)直接讀取最新的值Megastore中的事務(wù)及并發(fā)控制

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

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

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

消息隊(duì)列機(jī)制

消息能夠橫跨實(shí)體組

每個(gè)消息都有一個(gè)發(fā)送和接收實(shí)體組

如果兩個(gè)實(shí)體組是不同的，則傳輸將是異步

特點(diǎn)

規(guī)模：聲明一個(gè)隊(duì)列后可以在其他所有的實(shí)體組上創(chuàng)建一個(gè)收件箱

支持兩階段提交

增加競(jìng)爭(zhēng)風(fēng)險(xiǎn)，不鼓勵(lì)使用

Megastore中的事務(wù)機(jī)制

分布式存儲(chǔ)系統(tǒng)Megastore

設(shè)計(jì)目標(biāo)及方案選擇

Megastore數(shù)據(jù)模型

Megastore中的事務(wù)及并發(fā)控制

Megastore基本架構(gòu)

核心技術(shù)——復(fù)制

產(chǎn)品性能及控制措施Megastore的基本架構(gòu)

Megastore中三種副本

完整副本：Bigtable中存儲(chǔ)完整的日志和數(shù)據(jù)

見證者副本：在Paxos算法執(zhí)行過程中無法產(chǎn)生一個(gè)決議時(shí)參與投票

只讀副本：讀取最近過去某一個(gè)時(shí)間點(diǎn)一致性數(shù)據(jù)

Megastore的基本架構(gòu)

Megastore中提供快速讀（FastReads）和快速寫（FastWrites）機(jī)制

快速讀

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

利用本地讀?。↙ocalReads）實(shí)現(xiàn)快速讀，能夠帶來更好的用戶體驗(yàn)及更低的延遲

確?？焖僮x成功的關(guān)鍵是保證選擇的副本上數(shù)據(jù)是最新的。為了達(dá)到這一目標(biāo)，引入了協(xié)調(diào)者的概念

協(xié)調(diào)者是一個(gè)服務(wù)，該服務(wù)分布在每個(gè)副本的數(shù)據(jù)中心里面。它的主要作用就是跟蹤一個(gè)實(shí)體組集合

協(xié)調(diào)者的狀態(tài)是由寫算法來保證

快速寫

Megastore采用了一種在主/從式系統(tǒng)中常用的優(yōu)化方法。如果一次寫成功，那么下一次寫的時(shí)候就跳過準(zhǔn)備過程，直接進(jìn)入接受階段

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

leader主要是來裁決哪個(gè)寫入的值可以獲取0號(hào)提議

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

客戶端、網(wǎng)絡(luò)及Bigtable的故障都會(huì)導(dǎo)致一個(gè)寫操作處于不確定的狀態(tài)分布式存儲(chǔ)系統(tǒng)Megastore

設(shè)計(jì)目標(biāo)及方案選擇

Megastore數(shù)據(jù)模型

Megastore中的事務(wù)及并發(fā)控制

Megastore基本架構(gòu)

核心技術(shù)——復(fù)制

產(chǎn)品性能及控制措施復(fù)制的日志

預(yù)寫式日志

當(dāng)日志有不完整的前綴時(shí)我們就稱一個(gè)日志副本有“缺失”（Holes）

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

數(shù)據(jù)讀取

數(shù)據(jù)讀取過程:

本地查詢（QueryLocal）

發(fā)現(xiàn)位置（FindPosition）

本地讀?。↙ocalRead）

多數(shù)派讀?。∕ajorityRead）

追趕（Catchup）

Paxos將會(huì)促使絕大多數(shù)副本達(dá)成一個(gè)共識(shí)值

達(dá)到一種分布式一致狀態(tài)

驗(yàn)證（Validate）

查詢數(shù)據(jù)（QueryData）數(shù)據(jù)寫入

數(shù)據(jù)寫入

數(shù)據(jù)寫入完整過程

:（1）接受leader：請(qǐng)求leader接受值作為0號(hào)提議（快速寫方法），若成功，跳至步驟（3）（2）準(zhǔn)備：將值替換成擁有最高提議號(hào)的那個(gè)值（3）接受：請(qǐng)求剩余的副本接受該值，如果大多數(shù)副本拒絕這個(gè)值，返回步驟（2）（4）失效：將不接受值的副本上的協(xié)調(diào)者進(jìn)行失效操作（5）生效：將值的更新在盡可能多的副本上生效。如果選擇的值和原來提議的有沖突，返回一個(gè)沖突錯(cuò)誤

協(xié)調(diào)者的可用性

協(xié)調(diào)者在系統(tǒng)中是比較重要的——協(xié)調(diào)者的進(jìn)程運(yùn)行在每個(gè)數(shù)據(jù)中心。每次的寫操作中都要涉及協(xié)調(diào)者，因此協(xié)調(diào)者的故障將會(huì)導(dǎo)致系統(tǒng)的不可用

Megastore使用了Chubby鎖服務(wù)，為了處理請(qǐng)求，一個(gè)協(xié)調(diào)者必須持有多數(shù)鎖。一旦因?yàn)槌霈F(xiàn)問題導(dǎo)致它丟失了大部分鎖，協(xié)調(diào)者就會(huì)恢復(fù)到一個(gè)默認(rèn)保守狀態(tài)除了可用性問題，對(duì)于協(xié)調(diào)者的讀寫協(xié)議必須滿足一系列的競(jìng)爭(zhēng)條件

分布式存儲(chǔ)系統(tǒng)Megastore

設(shè)計(jì)目標(biāo)及方案選擇

Megastore數(shù)據(jù)模型

Megastore中的事務(wù)及并發(fā)控制

Megastore基本架構(gòu)

核心技術(shù)——復(fù)制

產(chǎn)品性能及控制措施可用性分布情況

可用性分布情況

Megastore在Google中已經(jīng)部署和使用了若干年，有超過100個(gè)產(chǎn)品使用Megastore作為其存儲(chǔ)系統(tǒng)

從圖中可以看出，絕大多數(shù)產(chǎn)品具有極高的可用性（>99.999%）。這表明Megastore系統(tǒng)的設(shè)計(jì)是非常成功的，基本達(dá)到了預(yù)期目標(biāo)

產(chǎn)品延遲情況分布

應(yīng)用程序的平均讀取延遲在萬分之一毫秒之內(nèi)，平均寫入延遲在100