Google全球級(jí)分布式數(shù)據(jù)庫(kù)Spanner原理

arron劉

本文來(lái)自“數(shù)據(jù)庫(kù)開(kāi)發(fā)”微信公眾號(hào)。

Google Spanner簡(jiǎn)介

Spanner 是Google的全球級(jí)的分布式數(shù)據(jù)庫(kù) (Globally-Distributed Database) 。Spanner的擴(kuò)展性達(dá)到了令人咋舌的全球級(jí)，可以擴(kuò)展到數(shù)百萬(wàn)的機(jī)器，數(shù)已百計(jì)的數(shù)據(jù)中心，上萬(wàn)億的行。更給力的是，除了夸張的擴(kuò)展性之外，他還能同時(shí)通過(guò)同步復(fù)制和多版本來(lái)滿足外部一致性，可用性也是很好的。沖破CAP的枷鎖，在三者之間完美平衡。

6.pic.jpg
Spanner是個(gè)可擴(kuò)展，多版本，全球分布式還支持同步復(fù)制的數(shù)據(jù)庫(kù)。他是Google的第一個(gè)可以全球擴(kuò)展并且支持外部一致的事務(wù)。Spanner能做到這些，離不開(kāi)一個(gè)用GPS和原子鐘實(shí)現(xiàn)的時(shí)間API。這個(gè)API能將數(shù)據(jù)中心之間的時(shí)間同步精確到10ms以內(nèi)。因此有幾個(gè)給力的功能：無(wú)鎖讀事務(wù)，原子schema修改，讀歷史數(shù)據(jù)無(wú)block。

EMC中國(guó)研究院實(shí)時(shí)緊盯業(yè)界動(dòng)態(tài)，Google最近發(fā)布的一篇論文《Spanner: Google’s Globally-Distributed Database》, 筆者非常感興趣，對(duì)Spanner進(jìn)行了一些調(diào)研，并在這里分享。由于Spanner并不是開(kāi)源產(chǎn)品，筆者的知識(shí)主要來(lái)源于Google的公開(kāi)資料，通過(guò)現(xiàn)有公開(kāi)資料僅僅只能窺得Spanner的滄海一粟，Spanner背后還依賴有大量Google的專有技術(shù)。

下文主要是Spanner的背景，設(shè)計(jì)和并發(fā)控制。

Spanner背景

要搞清楚Spanner原理，先得了解Spanner在Google的定位。

7.pic.jpg

從上圖可以看到。Spanner位于F1和GFS之間，承上啟下。所以先提一提F1和GFS。

F1

和眾多互聯(lián)網(wǎng)公司一樣，在早期Google大量使用了Mysql。Mysql是單機(jī)的，可以用Master-Slave來(lái)容錯(cuò)，分區(qū)來(lái)擴(kuò)展。但是需要大量的手工運(yùn)維工作，有很多的限制。因此Google開(kāi)發(fā)了一個(gè)可容錯(cuò)可擴(kuò)展的RDBMS——F1。和一般的分布式數(shù)據(jù)庫(kù)不同，F(xiàn)1對(duì)應(yīng)RDMS應(yīng)有的功能，毫不妥協(xié)。起初F1是基于Mysql的，不過(guò)會(huì)逐漸遷移到Spanner。

F1有如下特點(diǎn)：

· 7×24高可用。哪怕某一個(gè)數(shù)據(jù)中心停止運(yùn)轉(zhuǎn)，仍然可用。
· 可以同時(shí)提供強(qiáng)一致性和弱一致。
· 可擴(kuò)展
· 支持SQL
· 事務(wù)提交延遲50-100ms，讀延遲5-10ms，高吞吐

眾所周知Google BigTable是重要的NoSql產(chǎn)品，提供很好的擴(kuò)展性，開(kāi)源世界有HBase與之對(duì)應(yīng)。為什么Google還需要F1，而不是都使用BigTable呢？因?yàn)锽igTable提供的最終一致性，一些需要事務(wù)級(jí)別的應(yīng)用無(wú)法使用。同時(shí)BigTable還是NoSql，而大量的應(yīng)用場(chǎng)景需要有關(guān)系模型。就像現(xiàn)在大量的互聯(lián)網(wǎng)企業(yè)都使用Mysql而不愿意使用HBase，因此Google才有這個(gè)可擴(kuò)展數(shù)據(jù)庫(kù)的F1。而Spanner就是F1的至關(guān)重要的底層存儲(chǔ)技術(shù)。

Colossus（GFS II）

Colossus也是一個(gè)不得不提起的技術(shù)。他是第二代GFS，對(duì)應(yīng)開(kāi)源世界的新HDFS。GFS是著名的分布式文件系統(tǒng)。

8.pic.jpg

初代GFS是為批處理設(shè)計(jì)的。對(duì)于大文件很友好，吞吐量很大，但是延遲較高。所以使用他的系統(tǒng)不得不對(duì)GFS做各種優(yōu)化，才能獲得良好的性能。那為什么Google沒(méi)有考慮到這些問(wèn)題，設(shè)計(jì)出更完美的GFS ?因?yàn)槟莻�(gè)時(shí)候是2001年，Hadoop出生是在2007年。如果Hadoop是世界領(lǐng)先水平的話，GFS比世界領(lǐng)先水平還領(lǐng)先了6年。同樣的Spanner出生大概是2009年，現(xiàn)在我們看到了論文，估計(jì)Spanner在Google已經(jīng)很完善，同時(shí)Google內(nèi)部已經(jīng)有更先進(jìn)的替代技術(shù)在醞釀了。筆者預(yù)測(cè)，最早在2015年才會(huì)出現(xiàn)Spanner和F1的山寨開(kāi)源產(chǎn)品。

Colossus是第二代GFS。Colossus是Google重要的基礎(chǔ)設(shè)施，因?yàn)樗�可以滿足主流應(yīng)用對(duì)FS的要求。Colossus的重要改進(jìn)有：

· 優(yōu)雅Master容錯(cuò)處理 (不再有2s的停止服務(wù)時(shí)間)

· Chunk大小只有1MB (對(duì)小文件很友好)

· Master可以存儲(chǔ)更多的Metadata(當(dāng)Chunk從64MB變?yōu)?MB后，Metadata會(huì)擴(kuò)大64倍，但是Google也解決了)

Colossus可以自動(dòng)分區(qū)Metadata。使用Reed-Solomon算法來(lái)復(fù)制，可以將原先的3份減小到1.5份，提高寫的性能，降低延遲。客戶端來(lái)復(fù)制數(shù)據(jù)。具體細(xì)節(jié)筆者也猜不出。

與BigTable， Megastore對(duì)比

Spanner主要致力于跨數(shù)據(jù)中心的數(shù)據(jù)復(fù)制上，同時(shí)也能提供數(shù)據(jù)庫(kù)功能。在Google類似的系統(tǒng)有BigTable和Megastore。和這兩者相比，Spanner又有什么優(yōu)勢(shì)呢。

BigTable在Google得到了廣泛的使用，但是他不能提供較為復(fù)雜的Schema，還有在跨數(shù)據(jù)中心環(huán)境下的強(qiáng)一致性。Megastore有類RDBMS的數(shù)據(jù)模型，同時(shí)也支持同步復(fù)制，但是他的吞吐量太差，不能適應(yīng)應(yīng)用要求。Spanner不再是類似BigTable的版本化 key-value存儲(chǔ)，而是一個(gè)“臨時(shí)多版本”的數(shù)據(jù)庫(kù)。何為“臨時(shí)多版本”，數(shù)據(jù)是存儲(chǔ)在一個(gè)版本化的關(guān)系表里面，存儲(chǔ)的時(shí)間數(shù)據(jù)會(huì)根據(jù)其提交的時(shí)間打上時(shí)間戳，應(yīng)用可以訪問(wèn)到較老的版本，另外老的版本也會(huì)被垃圾回收掉。

Google官方認(rèn)為 Spanner是下一代BigTable，也是Megastore的繼任者。

Google Spanner設(shè)

功能

從高層看Spanner是通過(guò)Paxos狀態(tài)機(jī)將分區(qū)好的數(shù)據(jù)分布在全球的。數(shù)據(jù)復(fù)制全球化的，用戶可以指定數(shù)據(jù)復(fù)制的份數(shù)和存儲(chǔ)的地點(diǎn)。Spanner可以在集群或者數(shù)據(jù)發(fā)生變化的時(shí)候?qū)��?shù)據(jù)遷移到合適的地點(diǎn)，做負(fù)載均衡。用戶可以指定將數(shù)據(jù)分布在多個(gè)數(shù)據(jù)中心，不過(guò)更多的數(shù)據(jù)中心將造成更多的延遲。用戶需要在可靠性和延遲之間做權(quán)衡，一般來(lái)說(shuō)復(fù)制1，2個(gè)數(shù)據(jù)中心足以保證可靠性。

作為一個(gè)全球化分布式系統(tǒng)，Spanner提供一些有趣的特性。

· 應(yīng)用可以細(xì)粒度的指定數(shù)據(jù)分布的位置。精確的指定數(shù)據(jù)離用戶有多遠(yuǎn)，可以有效的控制讀延遲(讀延遲取決于最近的拷貝)。指定數(shù)據(jù)拷貝之間有多遠(yuǎn)，可以控制寫的延遲(寫延遲取決于最遠(yuǎn)的拷貝)。還要數(shù)據(jù)的復(fù)制份數(shù)，可以控制數(shù)據(jù)的可靠性和讀性能。(多寫幾份，可以抵御更大的事故)

· Spanner還有兩個(gè)一般分布式數(shù)據(jù)庫(kù)不具備的特性：讀寫的外部一致性，基于時(shí)間戳的全局的讀一致。這兩個(gè)特性可以讓Spanner支持一致的備份，一致的MapReduce，還有原子的Schema修改。

這寫特性都得益有Spanner有一個(gè)全球時(shí)間同步機(jī)制，可以在數(shù)據(jù)提交的時(shí)候給出一個(gè)時(shí)間戳。因?yàn)闀r(shí)間是系列化的，所以才有外部一致性。這個(gè)很容易理解，如果有兩個(gè)提交，一個(gè)在T1,一個(gè)在T2。那有更晚的時(shí)間戳那個(gè)提交是正確的。

這個(gè)全球時(shí)間同步機(jī)制是用一個(gè)具有GPS和原子鐘的TrueTime API提供了。這個(gè)TrueTime API能夠?qū)⒉煌瑪?shù)據(jù)中心的時(shí)間偏差縮短在10ms內(nèi)。這個(gè)API可以提供一個(gè)精確的時(shí)間，同時(shí)給出誤差范圍。Google已經(jīng)有了一個(gè)TrueTime API的實(shí)現(xiàn)。筆者覺(jué)得這個(gè)TrueTimeAPI 非常有意義，如果能單獨(dú)開(kāi)源這部分的話，很多數(shù)據(jù)庫(kù)如MongoDB都可以從中受益。

體系結(jié)構(gòu)

Spanner由于是全球化的，所以有兩個(gè)其他分布式數(shù)據(jù)庫(kù)沒(méi)有的概念。

· Universe。一個(gè)Spanner部署實(shí)例稱之為一個(gè)Universe。目前全世界有3個(gè)。一個(gè)開(kāi)發(fā)，一個(gè)測(cè)試，一個(gè)線上。因?yàn)橐粋�(gè)Universe就能覆蓋全球，不需要多個(gè)。

· Zones. 每個(gè)Zone相當(dāng)于一個(gè)數(shù)據(jù)中心，一個(gè)Zone內(nèi)部物理上必須在一起。而一個(gè)數(shù)據(jù)中心可能有多個(gè)Zone�？梢栽谶\(yùn)行時(shí)添加移除Zone。一個(gè)Zone可以理解為一個(gè)BigTable部署實(shí)例。

9.pic.jpg

如圖所示。一個(gè)Spanner有上面一些組件。實(shí)際的組件肯定不止這些，比如TrueTime API Server。如果僅僅知道這些知識(shí)，來(lái)構(gòu)建Spanner是遠(yuǎn)遠(yuǎn)不夠的。但Google都略去了。那筆者就簡(jiǎn)要介紹一下。

· Universemaster: 監(jiān)控這個(gè)universe里zone級(jí)別的狀態(tài)信息

· Placement driver：提供跨區(qū)數(shù)據(jù)遷移時(shí)管理功能

· Zonemaster：相當(dāng)于BigTable的Master。管理Spanserver上的數(shù)據(jù)。

· Location proxy：存儲(chǔ)數(shù)據(jù)的Location信息�？蛻舳艘�先訪問(wèn)他才知道數(shù)據(jù)在那個(gè)Spanserver上。

· Spanserver：相當(dāng)于BigTable的ThunkServer。用于存儲(chǔ)數(shù)據(jù)。

可以看出來(lái)這里每個(gè)組件都很有料，但是Google的論文里只具體介紹了Spanserver的設(shè)計(jì)，筆者也只能介紹到這里。下面詳細(xì)闡述Spanserver的設(shè)計(jì)。

Spanserver

本章詳細(xì)介紹Spanserver的設(shè)計(jì)實(shí)現(xiàn)。Spanserver的設(shè)計(jì)和BigTable非常的相似。參照下圖:

10.pic.jpg

從下往上看。每個(gè)數(shù)據(jù)中心會(huì)運(yùn)行一套Colossus (GFS II) 。每個(gè)機(jī)器有100-1000個(gè)tablet。Tablet概念上將相當(dāng)于數(shù)據(jù)庫(kù)一張表里的一些行，物理上是數(shù)據(jù)文件。打個(gè)比方，一張1000行的表，有10個(gè)tablet，第1-100行是一個(gè)tablet，第101-200是一個(gè)tablet。但和BigTable不同的是BigTable里面的tablet存儲(chǔ)的是Key-Value都是string，Spanner存儲(chǔ)的Key多了一個(gè)時(shí)間戳：

(Key: string, timestamp: int64) ->string。

因此spanner天生就支持多版本，tablet在文件系統(tǒng)中是一個(gè)B-tree-like的文件和一個(gè)write-ahead日志。

每個(gè)Tablet上會(huì)有一個(gè)Paxos狀態(tài)機(jī)。Paxos是一個(gè)分布式一致性協(xié)議。Table的元數(shù)據(jù)和log都存儲(chǔ)在上面。Paxos會(huì)選出一個(gè)replica做leader，這個(gè)leader的壽命默認(rèn)是10s,10s后重選。Leader就相當(dāng)于復(fù)制數(shù)據(jù)的master，其他replica的數(shù)據(jù)都是從他那里復(fù)制的。讀請(qǐng)求可以走任意的replica，但是寫請(qǐng)求只有去leader。這些replica統(tǒng)稱為一個(gè)paxos group。

每個(gè)leader replica的spanserver上會(huì)實(shí)現(xiàn)一個(gè)lock table還管理并發(fā)。Lock table記錄了兩階段提交需要的鎖信息。但是不論是在Spanner還是在BigTable上，但遇到?jīng)_突的時(shí)候長(zhǎng)時(shí)間事務(wù)會(huì)將性能很差。所以有一些操作，如事務(wù)讀可以走lock table，其他的操作可以繞開(kāi)lock table。

每個(gè)leader replica的spanserver上還有一個(gè)transaction manager。如果事務(wù)在一個(gè)paxos group里面，可以繞過(guò)transaction manager。但是一旦事務(wù)跨多個(gè)paxos group，就需要transaction manager來(lái)協(xié)調(diào)。其中一個(gè)Transactionmanager被選為leader，其他的是slave聽(tīng)他指揮。這樣可以保證事務(wù)。

Directories and Placement

之所以Spanner比BigTable有更強(qiáng)的擴(kuò)展性，在于Spanner還有一層抽象的概念directory, directory是一些key-value的集合，一個(gè)directory里面的key有一樣的前綴。更妥當(dāng)?shù)慕蟹ㄊ莃ucketing。Directory是應(yīng)用控制數(shù)據(jù)位置的最小單元，可以通過(guò)謹(jǐn)慎的選擇Key的前綴來(lái)控制。據(jù)此筆者可以猜出，在設(shè)計(jì)初期，Spanner是作為F1的存儲(chǔ)系統(tǒng)而設(shè)立，甚至還設(shè)計(jì)有類似directory的層次結(jié)構(gòu)，這樣的層次有很多好處，但是實(shí)現(xiàn)太復(fù)雜被摒棄了。

Directory作為數(shù)據(jù)放置的最小單元，可以在paxos group里面移來(lái)移去。Spanner移動(dòng)一個(gè)directory一般出于如下幾個(gè)原因：

· 一個(gè)paxos group的負(fù)載太大，需要切分

· 將數(shù)據(jù)移動(dòng)到access更近的地方

· 將經(jīng)常同時(shí)訪問(wèn)的directory放到一個(gè)paxos group里面

Directory可以在不影響client的前提下，在后臺(tái)移動(dòng)。移動(dòng)一個(gè)50MB的directory大概需要的幾秒鐘。

那么directory和tablet又是什么關(guān)系呢。可以理解為Directory是一個(gè)抽象的概念，管理數(shù)據(jù)的單元；而tablet是物理的東西，數(shù)據(jù)文件。由于一個(gè)Paxos group可能會(huì)有多個(gè)directory，所以spanner的tablet實(shí)現(xiàn)和BigTable的tablet實(shí)現(xiàn)有些不同。BigTable的tablet是單個(gè)順序文件。Google有個(gè)項(xiàng)目，名為L(zhǎng)evel DB，是BigTable的底層，可以看到其實(shí)現(xiàn)細(xì)節(jié)。而Spanner的tablet可以理解是一些基于行的分區(qū)的容器。這樣就可以將一些經(jīng)常同時(shí)訪問(wèn)的directory放在一個(gè)tablet里面，而不用太在意順序關(guān)系。

在paxos group之間移動(dòng)directory是后臺(tái)任務(wù)。這個(gè)操作還被用來(lái)移動(dòng)replicas。移動(dòng)操作設(shè)計(jì)的時(shí)候不是事務(wù)的，因?yàn)檫@樣會(huì)造成大量的讀寫block。操作的時(shí)候是先將實(shí)際數(shù)據(jù)移動(dòng)到指定位置，然后再用一個(gè)原子的操作更新元數(shù)據(jù)，完成整個(gè)移動(dòng)過(guò)程。

Directory還是記錄地理位置的最小單元。數(shù)據(jù)的地理位置是由應(yīng)用決定的，配置的時(shí)候需要指定復(fù)制數(shù)目和類型，還有地理的位置。比如(上海，復(fù)制2份；南京復(fù)制1分) 。這樣應(yīng)用就可以根據(jù)用戶指定終端用戶實(shí)際情況決定的數(shù)據(jù)存儲(chǔ)位置。比如中國(guó)隊(duì)的數(shù)據(jù)在亞洲有3份拷貝, 日本隊(duì)的數(shù)據(jù)全球都有拷貝。

前面對(duì)directory還是被簡(jiǎn)化過(guò)的，還有很多無(wú)法詳述。

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

Spanner的數(shù)據(jù)模型來(lái)自于Google內(nèi)部的實(shí)踐。在設(shè)計(jì)之初，Spanner就決心有以下的特性：

· 支持類似關(guān)系數(shù)據(jù)庫(kù)的schema
· Query語(yǔ)句
· 支持廣義上的事務(wù)

為何會(huì)這樣決定呢？在Google內(nèi)部還有一個(gè)Megastore，盡管要忍受性能不夠的折磨，但是在Google有300多個(gè)應(yīng)用在用它，因?yàn)镸egastore支持一個(gè)類似關(guān)系數(shù)據(jù)庫(kù)的schema，而且支持同步復(fù)制 (BigTable只支持最終一致的復(fù)制) 。使用Megastore的應(yīng)用有大名鼎鼎的Gmail, Picasa, Calendar, Android Market和AppEngine。 而必須對(duì)Query語(yǔ)句的支持，來(lái)自于廣受歡迎的Dremel，筆者不久前寫了篇文章來(lái)介紹他。 最后對(duì)事務(wù)的支持是比不可少了，BigTable在Google內(nèi)部被抱怨的最多的就是其只能支持行事務(wù)，再大粒度的事務(wù)就無(wú)能為力了。Spanner的開(kāi)發(fā)者認(rèn)為，過(guò)度使用事務(wù)造成的性能下降的惡果，應(yīng)該由應(yīng)用的開(kāi)發(fā)者承擔(dān)。應(yīng)用開(kāi)發(fā)者在使用事務(wù)的時(shí)候，必須考慮到性能問(wèn)題。而數(shù)據(jù)庫(kù)必須提供事務(wù)機(jī)制，而不是因?yàn)樾阅軉?wèn)題，就干脆不提供事務(wù)支持。

數(shù)據(jù)模型是建立在directory和key-value模型的抽象之上的。一個(gè)應(yīng)用可以在一個(gè)universe中建立一個(gè)或多個(gè)database，在每個(gè)database中建立任意的table。Table看起來(lái)就像關(guān)系型數(shù)據(jù)庫(kù)的表。有行，有列，還有版本。Query語(yǔ)句看起來(lái)是多了一些擴(kuò)展的SQL語(yǔ)句。

Spanner的數(shù)據(jù)模型也不是純正的關(guān)系模型，每一行都必須有一列或多列組件�？雌饋�(lái)還是Key-value。主鍵組成Key,其他的列是Value。但這樣的設(shè)計(jì)對(duì)應(yīng)用也是很有裨益的，應(yīng)用可以通過(guò)主鍵來(lái)定位到某一行。

11.pic.jpg

上圖是一個(gè)例子。對(duì)于一個(gè)典型的相冊(cè)應(yīng)用，需要存儲(chǔ)其用戶和相冊(cè)�？梢杂蒙厦娴膬蓚�(gè)SQL來(lái)創(chuàng)建表。Spanner的表是層次化的，最頂層的表是directory table。其他的表創(chuàng)建的時(shí)候，可以用interleave in parent來(lái)什么層次關(guān)系。這樣的結(jié)構(gòu)，在實(shí)現(xiàn)的時(shí)候，Spanner可以將嵌套的數(shù)據(jù)放在一起，這樣在分區(qū)的時(shí)候性能會(huì)提升很多。否則Spanner無(wú)法獲知最重要的表之間的關(guān)系。

TrueTime



TrueTime API 是一個(gè)非常有創(chuàng)意的東西，可以同步全球的時(shí)間。上表就是TrueTime API。TT.now()可以獲得一個(gè)絕對(duì)時(shí)間TTinterval，這個(gè)值和UnixTime是相同的，同時(shí)還能夠得到一個(gè)誤差e。TT.after(t)和TT.before(t)是基于TT.now()實(shí)現(xiàn)的。

那這個(gè)TrueTime API實(shí)現(xiàn)靠的是GFS和原子鐘。之所以要用兩種技術(shù)來(lái)處理，是因?yàn)閷?dǎo)致這兩個(gè)技術(shù)的失敗的原因是不同的。GPS會(huì)有一個(gè)天線，電波干擾會(huì)導(dǎo)致其失靈。原子鐘很穩(wěn)定。當(dāng)GPS失靈的時(shí)候，原子鐘仍然能保證在相當(dāng)長(zhǎng)的時(shí)間內(nèi)，不會(huì)出現(xiàn)偏差。

實(shí)際部署的時(shí)候。每個(gè)數(shù)據(jù)中心需要部署一些Master機(jī)器，其他機(jī)器上需要有一個(gè)slave進(jìn)程來(lái)從Master同步。有的Master用GPS，有的Master用原子鐘。這些Master物理上分布的比較遠(yuǎn)，怕出現(xiàn)物理上的干擾。比如如果放在一個(gè)機(jī)架上，機(jī)架被人碰倒了，就全宕了。另外原子鐘不是并很貴。Master自己還會(huì)不斷比對(duì)，新的時(shí)間信息還會(huì)和Master自身時(shí)鐘的比對(duì)，會(huì)排除掉偏差比較大的，并獲得一個(gè)保守的結(jié)果。最終GPS master提供時(shí)間精確度很高，誤差接近于0。

每個(gè)Slave后臺(tái)進(jìn)程會(huì)每個(gè)30秒從若干個(gè)Master更新自己的時(shí)鐘。為了降低誤差，使用Marzullo算法。每個(gè)slave還會(huì)計(jì)算出自己的誤差。這里的誤差包括的通信的延遲，機(jī)器的負(fù)載。如果不能訪問(wèn)Master，誤差就會(huì)越走越大，知道重新可以訪問(wèn)。

Google Spanner并發(fā)控制

Spanner使用TrueTime來(lái)控制并發(fā)，實(shí)現(xiàn)外部一致性。支持以下幾種事務(wù)。

· 讀寫事務(wù)
· 只讀事務(wù)
· 快照讀，客戶端提供時(shí)間戳
· 快照讀，客戶端提供時(shí)間范圍

例如一個(gè)讀寫事務(wù)發(fā)生在時(shí)間t，那么在全世界任何一個(gè)地方，指定t快照讀都可以讀到寫入的值。

12.pic.jpg

上表是Spanner現(xiàn)在支持的事務(wù)。單獨(dú)的寫操作都被實(shí)現(xiàn)為讀寫事務(wù) ； 單獨(dú)的非快照被實(shí)現(xiàn)為只讀事務(wù)。事務(wù)總有失敗的時(shí)候，如果失敗，對(duì)于這兩種操作會(huì)自己重試，無(wú)需應(yīng)用自己實(shí)現(xiàn)重試循環(huán)。

時(shí)間戳的設(shè)計(jì)大大提高了只讀事務(wù)的性能。事務(wù)開(kāi)始的時(shí)候，要聲明這個(gè)事務(wù)里沒(méi)有寫操作，只讀事務(wù)可不是一個(gè)簡(jiǎn)單的沒(méi)有寫操作的讀寫事務(wù)。它會(huì)用一個(gè)系統(tǒng)時(shí)間戳去讀，所以對(duì)于同時(shí)的其他的寫操作是沒(méi)有Block的。而且只讀事務(wù)可以在任意一臺(tái)已經(jīng)更新過(guò)的replica上面讀。
對(duì)于快照讀操作，可以讀取以前的數(shù)據(jù)，需要客戶端指定一個(gè)時(shí)間戳或者一個(gè)時(shí)間范圍。Spanner會(huì)找到一個(gè)已經(jīng)充分更新好的replica上讀取。

還有一個(gè)有趣的特性的是，對(duì)于只讀事務(wù)，如果執(zhí)行到一半，該replica出現(xiàn)了錯(cuò)誤。客戶端沒(méi)有必要在本地緩存剛剛讀過(guò)的時(shí)間，因?yàn)槭歉鶕?jù)時(shí)間戳讀取的。只要再用剛剛的時(shí)間戳讀取，就可以獲得一樣的結(jié)果。

讀寫事務(wù)

正如BigTable一樣，Spanner的事務(wù)是會(huì)將所有的寫操作先緩存起來(lái)，在Commit的時(shí)候一次提交。這樣的話，就讀不出在同一個(gè)事務(wù)中寫的數(shù)據(jù)了。不過(guò)這沒(méi)有關(guān)系，因?yàn)镾panner的數(shù)據(jù)都是有版本的。

在讀寫事務(wù)中使用wound-wait算法來(lái)避免死鎖。當(dāng)客戶端發(fā)起一個(gè)讀寫事務(wù)的時(shí)候，首先是讀操作，他先找到相關(guān)數(shù)據(jù)的leader replica，然后加上讀鎖，讀取最近的數(shù)據(jù)。在客戶端事務(wù)存活的時(shí)候會(huì)不斷的向leader發(fā)心跳，防止超時(shí)。當(dāng)客戶端完成了所有的讀操作，并且緩存了所有的寫操作，就開(kāi)始了兩階段提交�？蛻舳碎e置一個(gè)coordinator group，并給每一個(gè)leader發(fā)送coordinator的id和緩存的寫數(shù)據(jù)。

leader首先會(huì)上一個(gè)寫鎖，他要找一個(gè)比現(xiàn)有事務(wù)晚的時(shí)間戳。通過(guò)Paxos記錄。每一個(gè)相關(guān)的都要給coordinator發(fā)送他自己準(zhǔn)備的那個(gè)時(shí)間戳。

Coordinatorleader一開(kāi)始也會(huì)上個(gè)寫鎖，當(dāng)大家發(fā)送時(shí)間戳給他之后，他就選擇一個(gè)提交時(shí)間戳。這個(gè)提交的時(shí)間戳，必須比剛剛的所有時(shí)間戳晚，而且還要比TT.now()+誤差時(shí)間 還有晚。這個(gè)Coordinator將這個(gè)信息記錄到Paxos。

在讓replica寫入數(shù)據(jù)生效之前，coordinator還有再等一會(huì)。需要等兩倍時(shí)間誤差。這段時(shí)間也剛好讓Paxos來(lái)同步。因?yàn)榈却�之后，在任意機(jī)器上發(fā)起的下一個(gè)事務(wù)的開(kāi)始時(shí)間，都比如不會(huì)比這個(gè)事務(wù)的結(jié)束時(shí)間早了。然后coordinator將提交時(shí)間戳發(fā)送給客戶端還有其他的replica。他們記錄日志，寫入生效，釋放鎖。

只讀事務(wù)

對(duì)于只讀事務(wù)，Spanner首先要指定一個(gè)讀事務(wù)時(shí)間戳。還需要了解在這個(gè)讀操作中，需要訪問(wèn)的所有的讀的Key。Spanner可以自動(dòng)確定Key的范圍。

如果Key的范圍在一個(gè)Paxos group內(nèi)�？蛻舳丝梢园l(fā)起一個(gè)只讀請(qǐng)求給group leader。leader選一個(gè)時(shí)間戳，這個(gè)時(shí)間戳要比上一個(gè)事務(wù)的結(jié)束時(shí)間要大。然后讀取相應(yīng)的數(shù)據(jù)。這個(gè)事務(wù)可以滿足外部一致性，讀出的結(jié)果是最后一次寫的結(jié)果，并且不會(huì)有不一致的數(shù)據(jù)。

如果Key的范圍在多個(gè)Paxos group內(nèi)，就相對(duì)復(fù)雜一些。其中一個(gè)比較復(fù)雜的例子是，可以遍歷所有的group leaders，尋找最近的事務(wù)發(fā)生的時(shí)間，并讀取�？蛻舳酥灰獣r(shí)間戳在TT.now().latest之后就可以滿足要求了。

最后的話

本文介紹了GoogleSpanner的背景，設(shè)計(jì)和并發(fā)控制。希望不久的將來(lái)，會(huì)有開(kāi)源產(chǎn)品出現(xiàn)。


更多詳情請(qǐng)參閱：青云社區(qū)。