原帖轉自http://qing.weibo.com/2294942122/88ca09aa3300221n.html
Spanner 是Google的全球級的分布式資料庫 (Globally-Distributed Database) 。Spanner的擴充性達到了令人咋舌的全球級，可以擴充到數百萬的機器，數已百計的資料中心，上萬億的行。更給力的是，除了誇張的擴充性之外，他還能同時通過同步複制和多版本來滿足外部一緻性，可用性也是很好的。沖破CAP的枷鎖，在三者之間完美平衡。
Spanner是個可擴充，多版本，全球分布式還支援同步複制的資料庫。他是Google的第一個可以全球擴充并且支援外部一緻的事務。Spanner能做到這些，離不開一個用GPS和原子鐘實作的時間API。這個API能将資料中心之間的時間同步精确到10ms以内。是以有幾個給力的功能：無鎖讀事務，原子schema修改，讀曆史資料無block。由于Spanner并不是開源産品，筆者的知識主要來源于Google的公開資料，通過現有公開資料僅僅隻能窺得Spanner的滄海一粟，Spanner背後還依賴有大量Google的專有技術。
下文主要是Spanner的背景，設計和并發控制。
Spanner 背景要搞清楚Spanner原理，先得了解Spanner在Google的定位。
從上圖可以看到。Spanner位于F1和GFS之間，承上啟下。是以先提一提F1和GFS。
F1和衆多網際網路公司一樣，在早期Google大量使用了Mysql。Mysql是單機的，可以用Master-Slave來容錯，分區來擴充。但是需要大量的手工運維工作，有很多的限制。是以Google開發了一個可容錯可擴充的RDBMS——F1。和一般的分布式資料庫不同，F1對應RDMS應有的功能，毫不妥協。起初F1是基于Mysql的，不過會逐漸遷移到Spanner。
F1有如下特點：
· 7×24高可用。哪怕某一個資料中心停止運轉，仍然可用。
· 可以同時提供強一緻性和弱一緻。
· 可擴充
· 支援SQL
· 事務送出延遲50-100ms，讀延遲5-10ms，高吞吐
衆所周知Google BigTable是重要的NoSql産品，提供很好的擴充性，開源世界有HBase與之對應。為什麼Google還需要F1，而不是都使用BigTable呢？因為BigTable提供的最終一緻性，一些需要事務級别的應用無法使用。同時BigTable還是NoSql，而大量的應用場景需要有關系模型。就像現在大量的網際網路企業都使用Mysql而不願意使用HBase，是以Google才有這個可擴充資料庫的F1。而Spanner就是F1的至關重要的底層存儲技術。
Colossus （ GFS II ）Colossus也是一個不得不提起的技術。他是第二代GFS，對應開源世界的新HDFS。GFS是著名的分布式檔案系統。
初代GFS是為批處理設計的。對于大檔案很友好，吞吐量很大，但是延遲較高。是以使用他的系統不得不對GFS做各種優化，才能獲得良好的性能。那為什麼Google沒有考慮到這些問題，設計出更完美的GFS ?因為那個時候是2001年，Hadoop出生是在2007年。如果Hadoop是世界領先水準的話，GFS比世界領先水準還領先了6年。同樣的Spanner出生大概是2009年，現在我們看到了論文，估計Spanner在Google已經很完善，同時Google内部已經有更先進的替代技術在醞釀了。筆者預測，最早在2015年才會出現Spanner和F1的山寨開源産品。
Colossus是第二代GFS。Colossus是Google重要的基礎設施，因為他可以滿足主流應用對FS的要求。Colossus的重要改進有：
· 優雅Master容錯處理 (不再有2s的停止服務時間)
· Chunk大小隻有1MB (對小檔案很友好)
· Master可以存儲更多的Metadata(當Chunk從64MB變為1MB後，Metadata會擴大64倍，但是Google也解決了)
Colossus可以自動分區Metadata。使用Reed-Solomon算法來複制，可以将原先的3份減小到1.5份，提高寫的性能，降低延遲。用戶端來複制資料。具體細節筆者也猜不出。
與 BigTable ， Megastore 對比Spanner主要緻力于跨資料中心的資料複制上，同時也能提供資料庫功能。在Google類似的系統有BigTable和Megastore。和這兩者相比，Spanner又有什麼優勢呢。
BigTable在Google得到了廣泛的使用，但是他不能提供較為複雜的Schema，還有在跨資料中心環境下的強一緻性。Megastore有類RDBMS的資料模型，同時也支援同步複制，但是他的吞吐量太差，不能适應應用要求。Spanner不再是類似BigTable的版本化 key-value存儲，而是一個“臨時多版本”的資料庫。何為“臨時多版本”，資料是存儲在一個版本化的關系表裡面，存儲的時間資料會根據其送出的時間打上時間戳，應用可以通路到較老的版本，另外老的版本也會被垃圾回收掉。
Google官方認為 Spanner是下一代BigTable，也是Megastore的繼任者。
Google Spanner 設計 功能從高層看Spanner是通過Paxos狀态機将分區好的資料分布在全球的。資料複制全球化的，使用者可以指定資料複制的份數和存儲的地點。Spanner可以在叢集或者資料發生變化的時候将資料遷移到合适的地點，做負載均衡。使用者可以指定将資料分布在多個資料中心，不過更多的資料中心将造成更多的延遲。使用者需要在可靠性和延遲之間做權衡，一般來說複制1，2個資料中心足以保證可靠性。
作為一個全球化分布式系統，Spanner提供一些有趣的特性。
· 應用可以細粒度的指定資料分布的位置。精确的指定資料離使用者有多遠，可以有效的控制讀延遲(讀延遲取決于最近的拷貝)。指定資料拷貝之間有多遠，可以控制寫的延遲(寫延遲取決于最遠的拷貝)。還要資料的複制份數，可以控制資料的可靠性和讀性能。(多寫幾份，可以抵禦更大的事故)
· Spanner還有兩個一般分布式資料庫不具備的特性：讀寫的外部一緻性，基于時間戳的全局的讀一緻。這兩個特性可以讓Spanner支援一緻的備份，一緻的MapReduce，還有原子的Schema修改。
這寫特性都得益有Spanner有一個全球時間同步機制，可以在資料送出的時候給出一個時間戳。因為時間是系列化的，是以才有外部一緻性。這個很容易了解，如果有兩個送出，一個在T1,一個在T2。那有更晚的時間戳那個送出是正确的。
這個全球時間同步機制是用一個具有GPS和原子鐘的TrueTime API提供了。這個TrueTime API能夠将不同資料中心的時間偏差縮短在10ms内。這個API可以提供一個精确的時間，同時給出誤差範圍。Google已經有了一個TrueTime API的實作。筆者覺得這個TrueTimeAPI 非常有意義，如果能單獨開源這部分的話，很多資料庫如MongoDB都可以從中受益。
體系結構
Spanner由于是全球化的，是以有兩個其他分布式資料庫沒有的概念。
· Universe。一個Spanner部署執行個體稱之為一個Universe。目前全世界有3個。一個開發，一個測試，一個線上。因為一個Universe就能覆寫全球，不需要多個。
· Zones. 每個Zone相當于一個資料中心，一個Zone内部實體上必須在一起。而一個資料中心可能有多個Zone。可以在運作時添加移除Zone。一個Zone可以了解為一個BigTable部署執行個體.
如圖所示。一個Spanner有上面一些元件。實際的元件肯定不止這些，比如TrueTime API Server。如果僅僅知道這些知識，來建構Spanner是遠遠不夠的。但Google都略去了。那筆者就簡要介紹一下。
· Universemaster: 監控這個universe裡zone級别的狀态資訊
· Placement driver：提供跨區資料遷移時管理功能
· Zonemaster：相當于BigTable的Master。管理Spanserver上的資料。
· Location proxy：存儲資料的Location資訊。用戶端要先通路他才知道資料在那個Spanserver上。
· Spanserver：相當于BigTable的ThunkServer。用于存儲資料。
可以看出來這裡每個元件都很有料，但是Google的論文裡隻具體介紹了Spanserver的設計，筆者也隻能介紹到這裡。下面詳細闡述Spanserver的設計。
Spanserver本章詳細介紹Spanserver的設計實作。Spanserver的設計和BigTable非常的相似。參照下圖
從下往上看。每個資料中心會運作一套Colossus (GFS II) 。每個機器有100-1000個tablet。Tablet概念上将相當于資料庫一張表裡的一些行，實體上是資料檔案。打個比方，一張1000行的表，有10個tablet，第1-100行是一個tablet，第101-200是一個tablet。但和BigTable不同的是BigTable裡面的tablet存儲的是Key-Value都是string，Spanner存儲的Key多了一個時間戳：
(Key: string, timestamp: int64) ->string。
是以spanner天生就支援多版本，tablet在檔案系統中是一個B-tree-like的檔案和一個write-ahead日志。
每個Tablet上會有一個Paxos狀态機。Paxos是一個分布式一緻性協定。Table的中繼資料和log都存儲在上面。Paxos會選出一個replica做leader，這個leader的壽命預設是10s,10s後重選。Leader就相當于複制資料的master，其他replica的資料都是從他那裡複制的。讀請求可以走任意的replica，但是寫請求隻有去leader。這些replica統稱為一個paxos group。
每個leader replica的spanserver上會實作一個lock table還管理并發。Lock table記錄了兩階段送出需要的鎖資訊。但是不論是在Spanner還是在BigTable上，但遇到沖突的時候長時間事務會将性能很差。是以有一些操作，如事務讀可以走lock table，其他的操作可以繞開lock table。
每個leader replica的spanserver上還有一個transaction manager。如果事務在一個paxos group裡面，可以繞過transaction manager。但是一旦事務跨多個paxos group，就需要transaction manager來協調。其中一個Transactionmanager被選為leader，其他的是slave聽他指揮。這樣可以保證事務。
Directories and Placement之是以Spanner比BigTable有更強的擴充性，在于Spanner還有一層抽象的概念directory, directory是一些key-value的集合，一個directory裡面的key有一樣的字首。更妥當的叫法是bucketing。Directory是應用控制資料位置的最小單元，可以通過謹慎的選擇Key的字首來控制。據此筆者可以猜出，在設計初期，Spanner是作為F1的存儲系統而設立，甚至還設計有類似directory的層次結構，這樣的層次有很多好處，但是實作太複雜被摒棄了。
Directory作為資料放置的最小單元，可以在paxos group裡面移來移去。Spanner移動一個directory一般出于如下幾個原因：
· 一個paxos group的負載太大，需要切分
· 将資料移動到access更近的地方
· 将經常同時通路的directory放到一個paxos group裡面
Directory可以在不影響client的前提下，在背景移動。移動一個50MB的directory大概需要的幾秒鐘。
那麼directory和tablet又是什麼關系呢。可以了解為Directory是一個抽象的概念，管理資料的單元；而tablet是實體的東西，資料檔案。由于一個Paxos group可能會有多個directory，是以spanner的tablet實作和BigTable的tablet實作有些不同。BigTable的tablet是單個順序檔案。Google有個項目，名為Level DB，是BigTable的底層，可以看到其實作細節。而Spanner的tablet可以了解是一些基于行的分區的容器。這樣就可以将一些經常同時通路的directory放在一個tablet裡面，而不用太在意順序關系。
在paxos group之間移動directory是背景任務。這個操作還被用來移動replicas。移動操作設計的時候不是事務的，因為這樣會造成大量的讀寫block。操作的時候是先将實際資料移動到指定位置，然後再用一個原子的操作更新中繼資料，完成整個移動過程。
Directory還是記錄地理位置的最小單元。資料的地理位置是由應用決定的，配置的時候需要指定複制數目和類型，還有地理的位置。比如(上海，複制2份；南京複制1分) 。這樣應用就可以根據使用者指定終端使用者實際情況決定的資料存儲位置。比如中國隊的資料在亞洲有3份拷貝, 日本隊的資料全球都有拷貝。
前面對directory還是被簡化過的，還有很多無法詳述。
資料模型Spanner的資料模型來自于Google内部的實踐。在設計之初，Spanner就決心有以下的特性：
· 支援類似關系資料庫的schema
· Query語句
· 支援廣義上的事務
為何會這樣決定呢？在Google内部還有一個Megastore，盡管要忍受性能不夠的折磨，但是在Google有300多個應用在用它，因為Megastore支援一個類似關系資料庫的schema，而且支援同步複制 (BigTable隻支援最終一緻的複制) 。使用Megastore的應用有大名鼎鼎的Gmail, Picasa, Calendar, Android Market和AppEngine。 而必須對Query語句的支援，來自于廣受歡迎的Dremel，筆者不久前寫了篇文章來介紹他。 最後對事務的支援是比不可少了，BigTable在Google内部被抱怨的最多的就是其隻能支援行事務，再大粒度的事務就無能為力了。Spanner的開發者認為，過度使用事務造成的性能下降的惡果，應該由應用的開發者承擔。應用開發者在使用事務的時候，必須考慮到性能問題。而資料庫必須提供事務機制，而不是因為性能問題，就幹脆不提供事務支援。
資料模型是建立在directory和key-value模型的抽象之上的。一個應用可以在一個universe中建立一個或多個database，在每個database中建立任意的table。Table看起來就像關系型資料庫的表。有行，有列，還有版本。Query語句看起來是多了一些擴充的SQL語句。
Spanner的資料模型也不是純正的關系模型，每一行都必須有一列或多列元件。看起來還是Key-value。主鍵組成Key,其他的列是Value。但這樣的設計對應用也是很有裨益的，應用可以通過主鍵來定位到某一行。
上圖是一個例子。對于一個典型的相冊應用，需要存儲其使用者和相冊。可以用上面的兩個SQL來建立表。Spanner的表是階層化的，最頂層的表是directory table。其他的表建立的時候，可以用interleave in parent來什麼層次關系。這樣的結構，在實作的時候，Spanner可以将嵌套的資料放在一起，這樣在分區的時候性能會提升很多。否則Spanner無法獲知最重要的表之間的關系。
TrueTime TrueTime API 是一個非常有創意的東西，可以同步全球的時間。上表就是TrueTime API。TT.now()可以獲得一個絕對時間TTinterval，這個值和UnixTime是相同的，同時還能夠得到一個誤差e。TT.after(t)和TT.before(t)是基于TT.now()實作的。
那這個TrueTime API實作靠的是GFS和原子鐘。之是以要用兩種技術來處理，是因為導緻這兩個技術的失敗的原因是不同的。GPS會有一個天線，電波幹擾會導緻其失靈。原子鐘很穩定。當GPS失靈的時候，原子鐘仍然能保證在相當長的時間内，不會出現偏差。
實際部署的時候。每個資料中心需要部署一些Master機器，其他機器上需要有一個slave程序來從Master同步。有的Master用GPS，有的Master用原子鐘。這些Master實體上分布的比較遠，怕出現實體上的幹擾。比如如果放在一個機架上，機架被人碰倒了，就全宕了。另外原子鐘不是并很貴。Master自己還會不斷比對，新的時間資訊還會和Master自身時鐘的比對，會排除掉偏差比較大的，并獲得一個保守的結果。最終GPS master提供時間精确度很高，誤差接近于0。
每個Slave背景程序會每個30秒從若幹個Master更新自己的時鐘。為了降低誤差，使用Marzullo算法。每個slave還會計算出自己的誤差。這裡的誤差包括的通信的延遲，機器的負載。如果不能通路Master，誤差就會越走越大，知道重新可以通路。
Spanner使用TrueTime來控制并發，實作外部一緻性。支援以下幾種事務。
· 讀寫事務
· 隻讀事務
· 快照讀，用戶端提供時間戳
· 快照讀，用戶端提供時間範圍
例如一個讀寫事務發生在時間t，那麼在全世界任何一個地方，指定t快照讀都可以讀到寫入的值。
上表是Spanner現在支援的事務。單獨的寫操作都被實作為讀寫事務 ； 單獨的非快照被實作為隻讀事務。事務總有失敗的時候，如果失敗，對于這兩種操作會自己重試，無需應用自己實作重試循環。
時間戳的設計大大提高了隻讀事務的性能。事務開始的時候，要聲明這個事務裡沒有寫操作，隻讀事務可不是一個簡單的沒有寫操作的讀寫事務。它會用一個系統時間戳去讀，是以對于同時的其他的寫操作是沒有Block的。而且隻讀事務可以在任意一台已經更新過的replica上面讀。
對于快照讀操作，可以讀取以前的資料，需要用戶端指定一個時間戳或者一個時間範圍。Spanner會找到一個已經充分更新好的replica上讀取。
還有一個有趣的特性的是，對于隻讀事務，如果執行到一半，該replica出現了錯誤。用戶端沒有必要在本地緩存剛剛讀過的時間，因為是根據時間戳讀取的。隻要再用剛剛的時間戳讀取，就可以獲得一樣的結果。
讀寫事務正如BigTable一樣，Spanner的事務是會将所有的寫操作先緩存起來，在Commit的時候一次送出。這樣的話，就讀不出在同一個事務中寫的資料了。不過這沒有關系，因為Spanner的資料都是有版本的。
leader首先會上一個寫鎖，他要找一個比現有事務晚的時間戳。通過Paxos記錄。每一個相關的都要給coordinator發送他自己準備的那個時間戳。
Coordinatorleader一開始也會上個寫鎖，當大家發送時間戳給他之後，他就選擇一個送出時間戳。這個送出的時間戳，必須比剛剛的所有時間戳晚，而且還要比TT.now()+誤差時間 還有晚。這個Coordinator将這個資訊記錄到Paxos。
在讓replica寫入資料生效之前，coordinator還有再等一會。需要等兩倍時間誤差。這段時間也剛好讓Paxos來同步。因為等待之後，在任意機器上發起的下一個事務的開始時間，都比如不會比這個事務的結束時間早了。然後coordinator将送出時間戳發送給用戶端還有其他的replica。他們記錄日志，寫入生效，釋放鎖。
隻讀事務對于隻讀事務，Spanner首先要指定一個讀事務時間戳。還需要了解在這個讀操作中，需要通路的所有的讀的Key。Spanner可以自動确定Key的範圍。
如果Key的範圍在一個Paxos group内。用戶端可以發起一個隻讀請求給group leader。leader選一個時間戳，這個時間戳要比上一個事務的結束時間要大。然後讀取相應的資料。這個事務可以滿足外部一緻性，讀出的結果是最後一次寫的結果，并且不會有不一緻的資料。
如果Key的範圍在多個Paxos group内，就相對複雜一些。其中一個比較複雜的例子是，可以周遊所有的group leaders，尋找最近的事務發生的時間，并讀取。用戶端隻要時間戳在TT.now().latest之後就可以滿足要求了。
最後的話本文介紹了GoogleSpanner的背景，設計和并發控制。希望不久的将來，會有開源産品出現