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

1、Google全球級分布式數(shù)據(jù)庫 Spanner提綱lSpanner背景l(fā)功能l體系結(jié)構(gòu)lSpanserverl目錄與放置l數(shù)據(jù)模型lTrueTimelGoogle Spanner并發(fā)控制SpannerlSpanner是個可擴展，多版本(multi-version )，全球分布式(globally-distributed )還支持同步復制(synchronously-replicated )的數(shù)據(jù)庫。它是Google的第一個可以全球擴展并且支持外部一致的事務的數(shù)據(jù)庫。 lSpanner支持多用途的事務處理，并且提供了一個基于SQL的查詢語言。作為世界級分布的數(shù)據(jù)庫，Spanner更有一些令人感興

2、趣的特色：Spannerl1. 應用程序可以通過復制裝置動態(tài)的對數(shù)據(jù)進行微控制。還可以通過制定約束條件來指定數(shù)據(jù)中心和其中包含的數(shù)據(jù)（無視數(shù)據(jù)與用戶間的距離，數(shù)據(jù)與數(shù)據(jù)間的距離及數(shù)據(jù)保持的份數(shù)）。系統(tǒng)動態(tài)的和透明的在數(shù)據(jù)中心之間轉(zhuǎn)移數(shù)據(jù)來保證資源的平衡利用。l2. Spanner有兩個特性是很難在分布式數(shù)據(jù)庫中實現(xiàn)的：讀寫的外部一致性和基于時間標記的全局讀一致性。這讓Spanner可以在全球范圍內(nèi)保持數(shù)據(jù)的一致備份，MapReduce一致執(zhí)行和原子的Schema修改，即使是連續(xù)操作。Spannerl這些特性保證了Spanner可以有序的在世界范圍內(nèi)響應事務處理，即使是分散式的事務。時間標記反應

3、了事務的順序。另外，序列化的時間確保了外部一致性：如果事務T1在另一個事務T2之前提交，那么T1提交的時間標記是小于T2的。Spanner能做到這些，離不開一個用GPS和原子鐘實現(xiàn)的時間API。這個API能將數(shù)據(jù)中心之間的時間同步精確到10ms以內(nèi)。l功能：無鎖讀事務，原子schema修改，讀歷史數(shù)據(jù)無阻塞。Spanner背景l(fā)Spanner 是Google的全球級的分布式數(shù)據(jù)庫 (Globally-Distributed Database) 。Spanner的擴展性達到了令人咋舌的全球級，可以擴展到數(shù)百萬的機器，數(shù)已百計的數(shù)據(jù)中心，上萬億的行。更給力的是，除了夸張的擴展性之外，它還能同時通過

4、同步復制和多版本來滿足外部一致性，可用性也是很好的。沖破CAP的枷鎖，在三者之間完美平衡。 Design GoalsSpanner背景背景l(fā)要搞清楚Spanner原理，先得了解Spanner在Google的定位。F1l和眾多互聯(lián)網(wǎng)公司一樣，在早期Google大量使用了Mysql。Mysql是單機的，可以用Master-Slave來容錯，分區(qū)來擴展。但是需要大量的手工運維工作，有很多的限制。因此Google開發(fā)了一個可容錯可擴展的RDBMS-F1。和一般的分布式數(shù)據(jù)庫不同，F(xiàn)1對應RDMS( Relational Database Management System )應有的功能，毫不妥協(xié)。起初

5、F1是基于Mysql的，不過以后會逐漸遷移到Spanner。F1特點l724高可用。哪怕某一個數(shù)據(jù)中心停止運轉(zhuǎn)，仍然可用。 l可以同時提供強一致性和弱一致性。 l可擴展 l支持SQL l事務提交延遲50-100ms，讀延遲5-10ms，高吞吐 l眾所周知Google BigTable是重要的NoSql產(chǎn)品，提供很好的擴展性，開源世界有HBase與之對應。為什么Google還需要F1，而不是都使用 BigTable呢？因為BigTable提供的最終一致性，一些需要事務級別的應用無法使用。同時BigTable還是NoSql，而大量的應用場景需要有關(guān)系模型。就像現(xiàn)在大量的互聯(lián)網(wǎng)企業(yè)都使用Mysql而

6、不愿意使用HBase，因此Google才有這個可擴展數(shù)據(jù)庫的F1。而Spanner就是 F1的至關(guān)重要的底層存儲技術(shù)。Colossus（GFS II） klss lColossus是第二代GFS，對應開源世界的新HDFS。Google文件系統(tǒng)GFS是構(gòu)建在廉價的服務器之上的大型分布式系統(tǒng)。它將服務器故障視為正?，F(xiàn)象，通過軟件的方式自動容錯，在保證系統(tǒng)可靠性和可用性的同時，大大減少了系統(tǒng)的成本。lGFS是Google云存儲的基石，其它存儲系統(tǒng)，如Google Bigtable，Google Megastore，Google Percolator p:klet(r)均直接或者間接地構(gòu)建在GFS之上

7、。另外，Google大規(guī)模批處理系統(tǒng)MapReduce也需要利用GFS作為海量數(shù)據(jù)的輸入輸出。 Colossus系統(tǒng)架構(gòu)Colossus（GFS II）lGFS將整個系統(tǒng)的節(jié)點分為三種角色：GFS Master（總控服務器），GFS Chunkserver（數(shù)據(jù)塊服務器，簡稱CS）以及GFS Client（客戶端）。lGFS文件被劃分為固定大小的數(shù)據(jù)塊（Chunk），由Master在創(chuàng)建時分配一個64位全局唯一的Chunk句柄。CS以普通的Linux文件的形式將Chunk存儲在磁盤中。為了保證可靠性，Chunk在不同的機器中復制多份，默認為三份。lMaster中維護了系統(tǒng)的元數(shù)據(jù)，包括文件及C

8、hunk名字空間，GFS文件到Chunk之間的映射，Chunk位置信息。它也負責整個系統(tǒng)的全局控制，如Chunk租約管理，垃圾回收無用Chunk，Chunk復制等等。Master會定期與CS通過心跳的方式交換信息。Colossus（GFS II）lClient是GFS提供給應用程序的訪問接口，它是一組專用接口，不遵守POSIX( Portable Operating System Interface，可移植操作系統(tǒng)接口)規(guī)范，以庫文件的形式提供。Client訪問GFS時，首先訪問Master節(jié)點，獲取與之進行交互的CS信息，然后直接訪問這些CS，完成數(shù)據(jù)存取工作。l需要注意的是，GFS中的客戶

9、端不緩存文件數(shù)據(jù)，只緩存Master中獲取的元數(shù)據(jù)，這是由GFS的應用特點決定的。GFS最主要的應用有兩個：MapReduce與Bigtable。對于MapReduce，GFS客戶端使用方式為順序讀寫，沒有緩存文件數(shù)據(jù)的必要；而Bigtable作為云表格系統(tǒng)，內(nèi)部實現(xiàn)了一套緩存機制。另外，如何維護客戶端緩存與實際數(shù)據(jù)之間的一致性是一個極其復雜的問題。Colossus（GFS II）lColossus的重要改進有：l優(yōu)雅Master容錯處理(不再有2s的停止服務時間) lChunk大小只有1MB (對小文件很友好) lMaster可以存儲更多的Metadata(當Chunk從64MB變?yōu)?MB后

10、，Metadata會擴大64倍) lColossus可以自動分區(qū)Metadata。使用Reed-Solomon算法來復制，可以將原先的3份減小到1.5份，提高寫的性能，降低延遲。客戶端來復制數(shù)據(jù)。GFS與與BigTable、Megastore對比對比lSpanner主要致力于跨數(shù)據(jù)中心的數(shù)據(jù)復制上，同時也能提供數(shù)據(jù)庫功能。lBigTable在Google得到了廣泛的使用，但是它不能提供較為復雜的Schema，也不能提供在跨數(shù)據(jù)中心環(huán)境下的強一致性。lMegastore 有類RDBMS的數(shù)據(jù)模型，同時也支持同步復制，但是它的吞吐量太差，不能適應應用要求。lSpanner不再是類似BigTable

11、的版本化 key-value存儲，而是一個“臨時多版本”的數(shù)據(jù)庫。何為“臨時多版本”，數(shù)據(jù)是存儲在一個版本化的關(guān)系表里面，存儲的時間數(shù)據(jù)會根據(jù)其提交的時間打上時間戳，應用可以訪問到較老的版本，另外老的版本也會被垃圾回收掉。lGoogle官方認為 Spanner是下一代BigTable，也是Megastore的繼任者。Spanner設(shè)計l功能l體系結(jié)構(gòu)lSpanserverl目錄與放置l數(shù)據(jù)模型lTrueTimelGoogle Spanner并發(fā)控制Spanner功能l從高層看Spanner是通過Paxos狀態(tài)機將分區(qū)好的數(shù)據(jù)分布在全球的、復制全球化的，用戶可以指定數(shù)據(jù)復制的份數(shù)和存儲的地點。

12、Spanner可以在集群或者數(shù)據(jù)發(fā)生變化的時候?qū)?shù)據(jù)遷移到合適的地點，做負載均衡。用戶可以指定將數(shù)據(jù)分布在多個數(shù)據(jù)中心，不過更多的數(shù)據(jù)中心將造成 更多的延遲。用戶需要在可靠性和延遲之間做權(quán)衡，一般來說復制1，2個數(shù)據(jù)中心足以保證可靠性。Spanner功能l應用可以細粒度的指定數(shù)據(jù)分布的位置。精確的指定數(shù)據(jù)離用戶有多遠，可以有效的控制讀延遲(讀延遲取決于最近的拷貝)。指定數(shù)據(jù)拷貝之間有多遠，可以控制寫的延遲(寫延遲取決于最遠的拷貝)。還要數(shù)據(jù)的復制份數(shù)，可以控制數(shù)據(jù)的可靠性和讀性能。(多寫幾份，可以抵御更大的事故) lSpanner還有兩個一般分布式數(shù)據(jù)庫不具備的特性：讀寫的外部一致性，基于時間

13、戳的全局的讀一致。這兩個特性可以讓Spanner支持一致的備份，一致的MapReduce，還有原子的Schema修改。 體系結(jié)構(gòu)lSpanner由于是全球化的，所以有兩個其他分布式數(shù)據(jù)庫沒有的概念。lUniverse。一個Spanner部署實例稱之為一個Universe。目前全世界有3個。一個開發(fā)，一個測試，一個線上。因為一個Universe就能覆蓋全球，不需要多個。 lZones。每個Zone相當于一個數(shù)據(jù)中心，一個Zone內(nèi)部物理上必須在一起。而一個數(shù)據(jù)中心可能有多個Zone?？梢栽谶\行時添加移除Zone。一個Zone可以理解為一個BigTable部署實例。 體系結(jié)構(gòu)lUniversema

14、ster: 監(jiān)控這個universe里zone級別的狀態(tài)信息 lPlacement driver：提供跨區(qū)數(shù)據(jù)遷移時管理功能 lZonemaster:相當于BigTable的Master。管理Spanserver上的數(shù)據(jù)。 lLocation proxyprksi: :存儲 數(shù)據(jù)的Location信息?？蛻舳艘仍L問它才知道數(shù)據(jù)在那個Spanserver上。 lSpanserver:相當于BigTable的ThunkServer,用于存儲數(shù)據(jù). SpanserverSpanserverl從下往上看。每個數(shù)據(jù)中心會運行一套Colossus (GFS II) 。每個機器有100-1000個tabl

15、et。l和BigTable不同的是BigTable里面的 tablet存儲的是Key-Value都是string，Spanner存儲的Key多了一個時間戳： (Key: string, timestamp: int64) -string。 Spanserverl每個Tablet上會有一個Paxos狀態(tài)機。Paxos是一個分布式一致性協(xié)議。Table的元數(shù)據(jù)和log都存儲在上面。Paxos會選出一個 replica做leader，這個leader的壽命默認是10s，10s后重選。Leader就相當于復制數(shù)據(jù)的master，其他replica的 數(shù)據(jù)都是從他那里復制的。讀請求可以走任意的repli

16、ca，但是寫請求只有去leader。這些replica統(tǒng)稱為一個paxos group。 Spanserverl每個leader replica的spanserver上會實現(xiàn)一個lock table還管理并發(fā)。Lock table記錄了兩階段提交需要的鎖信息。但是不論是在Spanner還是在BigTable上，但遇到?jīng)_突的時候長時間事務會將性能很差。所以有一些操作，如事務讀可以走lock table，其他的操作可以繞開lock table。Spanserverl每個leader replica的spanserver上還有一個transaction manager。如果事務在一個paxos gr

17、oup里面，可以繞過transaction manager。但是一旦事務跨多個paxos group，就需要transaction manager來協(xié)調(diào)。其中一個Transactionmanager被選為leader，其他的是slave聽他指揮。Directoryl之所以Spanner比BigTable有更強的擴展性，在于Spanner還有一層抽象的概念directory, directory是一些key-value的集合，一個directory里面的key有一樣的前綴。更妥當?shù)慕蟹ㄊ莃ucketing。 Directory是應用控制數(shù)據(jù)位置的最小單元，可以通過謹慎的選擇Key的前綴來控制，以

18、在paxos group里面移來移去。 DirectorylDirectory可以在不影響client的前提下，在后臺移動。移動一個50MB的directory大概需要幾秒鐘 。ldirectory和tablet是什么關(guān)系？ 可以理解為Directory是一個抽象的概念，管理數(shù)據(jù)的單元；而tablet是物理的東西，數(shù)據(jù)文件。 Directoryl由于一個Paxos group可能會有多個directory，所以spanner的tablet實現(xiàn)和BigTable的tablet實現(xiàn)有些不同。BigTable的 tablet是單個順序文件。而Spanner的tablet可以理解是一些基于行的分區(qū)的容

19、器?？梢詫⒁恍┙?jīng)常同時訪問 的directory放在一個tablet里面，而不用太在意順序關(guān)系。 Directoryl在paxos group之間移動directory是后臺任務。這個操作還被用來移動replicas。移動操作設(shè)計的時候不是事務的，因為這樣會造成大量的讀寫 block。操作的時候是先將實際數(shù)據(jù)移動到指定位置，然后再用一個原子的操作更新元數(shù)據(jù)，完成整個移動過程。 DirectorylDirectory還是記錄地理位置的最小單元。數(shù)據(jù)的地理位置是由應用決定的，配置的時候需要指定復制數(shù)目和類型，還有地理的位置。比如(上海，復制2份；南京復制1份) 。這樣應用就可以根據(jù)用戶指定終端用戶

20、實際情況決定數(shù)據(jù)存儲位置。數(shù)據(jù)模型lSpanner的數(shù)據(jù)模型來自于Google內(nèi)部的實踐。在設(shè)計之初，Spanner就決心有以下的特性：l支持類似關(guān)系數(shù)據(jù)庫的schema ，Query語句 ，支持廣義上的事務 。l數(shù)據(jù)模型是建立在directory和key-value模型的抽象之上的。一個應用可以在一個universe中建立一個或多個 database，在每個database中建立任意的table。Table看起來就像關(guān)系型數(shù)據(jù)庫的表。有行，有列，還有版本。Query語句看起來是多了一些擴展的SQL語句。lSpanner的數(shù)據(jù)模型也不是純正的關(guān)系模型，每一行都必須有一列或多列組件。看起來還是K

21、ey-value。主鍵組成Key,其他的列是Value。 Spanner的數(shù)據(jù)模型也不是純正的關(guān)系模型，每一行都必須有一列或多列組件?？雌饋磉€是Key-value。主鍵組成Key,其他的列是Value。 TrueTimelTrueTime API 是一個非常有創(chuàng)意的東西，可以同步全球的時間。上表就是TrueTime API。TT.now()可以獲得一個絕對時間TTinterval，這個值和UnixTime是相同的，同時還能夠得到一個誤差e。 TT.after(t)和TT.before(t)是基于TT.now()實現(xiàn)的。TrueTimelTrueTime API實現(xiàn)靠的是GFS和原子鐘。之所以要

22、用兩種技術(shù)來處理，是因為導致這兩個技術(shù)的失敗的原因是不同的。GPS會有一個天線，電波干擾會導致其失靈。原子鐘很穩(wěn)定。當GPS失靈的時候，原子鐘仍然能保證在相當長的時間內(nèi)，不會出現(xiàn)偏差。 TrueTimel實際部署的時候。每個數(shù)據(jù)中心需要部署一些Master機器，其他機器上需要有一個slave進程來從Master同步。有的Master用 GPS，有的Master用原子鐘。這些Master物理上分布的比較遠，怕出現(xiàn)物理上的干擾。 TrueTimel每個Slave后臺進程會每隔30秒從若干個Master更新自己的時鐘。為了降低誤差，使用Marzullo算法。每個slave還會計算出自己的誤差。這里的

23、誤差包括通信的延遲，機器的負載。如果不能訪問Master，誤差就會越走越大，直到重新可以訪問。Spanner并發(fā)控制 lSpanner使用TrueTime來控制并發(fā)，實現(xiàn)外部一致性。支持以下幾種事務。 讀寫事務 只讀事務 快照讀，客戶端提供時間戳 快照讀，客戶端提供時間范圍 l例如一個讀寫事務發(fā)生在時間t，那么在全世界任何一個地方，指定t快照讀都可以讀到寫入的值。Spanner并發(fā)控制Spanner并發(fā)控制l上表是Spanner現(xiàn)在支持的事務。單獨的寫操作都被實現(xiàn)為讀寫事務；單獨的非快照被實現(xiàn)為只讀事務。事務總有失敗的時候，如果失敗，對于這兩種操作會自己重試，無需應用自己實現(xiàn)重試循環(huán)。 l時間

24、戳的設(shè)計大大提高了只讀事務的性能。事務開始的時候，要聲明這個事務里沒有寫操作。只讀事務不是一個簡單的沒有寫操作的讀寫事務，它會用一個系統(tǒng)時間戳去讀，所以對于同時的其他的寫操作是沒有Block的。而且只讀事務可以在任意一臺已經(jīng)更新過的replica上面讀。Spanner并發(fā)控制讀寫事務l正如BigTable一樣，Spanner的事務是會將所有的寫操作先緩存起來，在Commit的時候一次提交。但這樣就讀不出在同一個事務中寫的數(shù)據(jù)了。不過這沒有關(guān)系，因為Spanner的數(shù)據(jù)都是有版本的。Spanner并發(fā)控制讀寫事務l在讀寫事務中使用wound-wait算法來避免死鎖。當客戶端發(fā)起一個讀寫事務的時候，首先是讀操作，他先找到相關(guān)數(shù)據(jù)的leader replica，然后加上讀鎖，讀取最近的數(shù)據(jù)。在客戶端事務存活的時候會不斷的向leader發(fā)心跳，防止超時。當客戶端完成了所有的讀操作，并且緩存了所有的寫操作，就開始兩階段提交?？蛻舳碎e置一個coordinator group，并給每一個leader發(fā)送coordinator的id和緩存的寫數(shù)據(jù)。Spanner并發(fā)控制讀寫事務lleader首