介紹
Spanner是一個可擴展的、全球分散式的資料庫，是在谷歌公司設計、開發和部署的。在最高抽象層面，Spanner就是一個資料庫，把數據分片存儲在許多Paxos[21]狀態機上，這些機器位於遍布全球的數據中心內。複製技術可以用來服務於全球可用性和地理局部性。客戶端會自動在副本之間進行失敗恢復。隨著數據的變化和伺服器的變化，Spanner會自動把數據進行重新分片，從而有效應對負載變化和處理失敗。Spanner被設計成可以擴展到幾百萬個機器節點，跨越成百上千個數據中心，具備幾萬億資料庫行的規模。 套用可以藉助於Spanner來實現高可用性，通過在一個洲的內部和跨越不同的洲之間複製數據，保證即使面對大範圍的自然災害時數據依然可用。我們最初的客戶是F1[35]，一個谷歌廣告後台的重新編程實現。F1使用了跨越美國的5個副本。絕大多數其他套用很可能會在屬於同一個地理範圍內的3-5個數據中心內放置數據副本，採用相對獨立的失敗模式。也就是說，許多套用都會首先選擇低延遲，而不是高可用性，只要系統能夠從1-2個數據中心失敗中恢復過來。 Spanner的主要工作，就是管理跨越多個數據中心的數據副本，但是，在我們的分散式系統體系架構之上設計和實現重要的資料庫特性方面，我們也花費了大量的時間。儘管有許多項目可以很好地使用BigTable[9]，我們也不斷收到來自客戶的抱怨，客戶反映BigTable無法套用到一些特定類型的套用上面，比如具備複雜可變的模式，或者對於在大範圍內分布的多個副本數據具有較高的一致性要求。其他研究人員也提出了類似的抱怨[37]。谷歌的許多套用已經選擇使用Megastore[5]，主要是因為它的半關係數據模型和對同步複製的支持，儘管Megastore具備較差的寫操作吞吐量。由於上述多個方面的因素，Spanner已經從一個類似BigTable的單一版本的鍵值存儲，演化成為一個具有時間屬性的多版本的資料庫。數據被存儲到模式化的、半關係的表中，數據被版本化，每個版本都會自動以提交時間作為時間戳，舊版本的數據會更容易被垃圾回收。套用可以讀取舊版本的數據。Spanner支持通用的事務，提供了基於SQL的查詢語言。 作為一個全球分散式資料庫，Spanner提供了幾個有趣的特性：
第一，在數據的副本配置方面，套用可以在一個很細的粒度上進行動態控制。套用可以詳細規定，哪些數據中心包含哪些數據，數據距離用戶有多遠（控制用戶讀取數據的延遲），不同數據副本之間距離有多遠（控制寫操作的延遲），以及需要維護多少個副本（控制可用性和讀操作性能）。數據也可以被動態和透明地在數據中心之間進行移動，從而平衡不同數據中心內資源的使用。
第二，Spanner有兩個重要的特性，很難在一個分散式資料庫上實現，即Spanner提供了讀和寫操作的外部一致性，以及在一個時間戳下面的跨越資料庫的全球一致性的讀操作。這些特性使得Spanner可以支持一致的備份、一致的MapReduce執行[12]和原子模式變更，所有都是在全球範圍內實現，即使存在正在處理中的事務也可以。 之所以可以支持這些特性，是因為Spanner可以為事務分配全球範圍內有意義的提交時間戳，即使事務可能是分散式的。這些時間戳反映了事務序列化的順序。除此以外，這些序列化的順序滿足了外部一致性的要求：如果一個事務T1在另一個事務T2開始之前就已經提交了，那么，T1的時間戳就要比T2的時間戳小。Spanner是第一個可以在全球範圍內提供這種保證的系統。 實現這種特性的關鍵技術就是一個新的TrueTime API及其實現。這個API可以直接暴露時鐘不確定性，Spanner時間戳的保證就是取決於這個API實現的界限。如果這個不確定性很大，Spanner就降低速度來等待這個大的不確定性結束。谷歌的簇管理器軟體提供了一個TrueTime API的實現。這種實現可以保持較小的不確定性（通常小於10ms），主要是藉助於現代時鐘參考值（比如GPS和原子鐘）。 第2部分描述了Spanner實現的結構、特性集和工程方面的決策；第3部分介紹我們的新的TrueTime API，並且描述了它的實現；第4部分描述了Spanner如何使用TrueTime來實現外部一致性的分散式事務、不用鎖機制的唯讀事務和原子模式更新。第5部分提供了測試Spanner性能和TrueTime行為的測試基準，並討論了F1的經驗。第6、7和8部分討論了相關工作，並給出總結。
實現
本部分內容描述了Spanner的結構和背後的實現機理，然後描述了目錄抽象，它被用來管理副本和局部性，並介紹了數據的轉移單位。最後，將討論我們的數據模型，從而說明，為什麼Spanner看起來更加像一個關係資料庫，而不是一個鍵值資料庫；還會討論套用如何可以控制數據的局部性。 一個Spanner部署稱為一個universe。假設Spanner在全球範圍內管理數據，那么，將會只有可數的、運行中的universe。我們當前正在運行一個測試用的universe，一個部署/線上用的universe和一個只用於線上套用的universe。 Spanner被組織成許多個zone的集合，每個zone都大概像一個BigTable伺服器的部署。zone是管理部署的基本單元。zone的集合也是數據可以被複製到的位置的集合。當新的數據中心加入服務，或者老的數據中心被關閉時，zone可以被加入到一個運行的系統中，或者從中移除。zone也是物理隔離的單元，在一個數據中心中，可能有一個或者多個zone，例如，屬於不同套用的數據可能必須被分區存儲到同一個數據中心的不同伺服器集合中。
圖1顯示了在一個Spanner的universe中的伺服器。一個zone包括一個zonemaster，和一百至幾千個spanserver。Zonemaster把數據分配給spanserver，spanserver把數據提供給客戶端。客戶端使用每個zone上面的location proxy來定位可以為自己提供數據的spanserver。Universe master和placement driver，當前都只有一個。Universe master主要是一個控制台，它顯示了關於zone的各種狀態信息，可以用於相互之間的調試。Placement driver會周期性地與spanserver進行互動，來發現那些需要被轉移的數據，或者是為了滿足新的副本約束條件，或者是為了進行負載均衡。
2.1 Spanserver軟體棧
本部分內容主要關注spanserver實現，來解釋複製和分散式事務是如何被架構到我們的基於BigTable的實現之上的。圖2顯示了軟體棧。在底部，每個spanserver負載管理100-1000個稱為tablet的數據結構的實例。一個tablet就類似於BigTable中的tablet，也實現了下面的映射：
spanner 與BigTable不同的是，Spanner會把時間戳分配給數據，這種非常重要的方式，使得Spanner更像一個多版本資料庫，而不是一個鍵值存儲。一個tablet的狀態是存儲在類似於B-樹的檔案集合和寫前(write-ahead)的日誌中，所有這些都會被保存到一個分散式的檔案系統中，這個分散式檔案系統被稱為Colossus，它繼承自Google File System。 為了支持複製，每個spanserver會在每個tablet上面實現一個單個的Paxos狀態的機器。一個之前實現的Spanner可以支持在每個tablet上面實現多個Paxos狀態機，它可以允許更加靈活的複製配置，但是，這種設計過於複雜，被我們捨棄了。每個狀態機器都會在相應的tablet中保存自己的元數據和日誌。我們的Paxos實現支持採用基於時間的領導者租約的長壽命的領導者，時間通常在0到10秒之間。當前的Spanner實現中，會對每個Paxos寫操作進行兩次記錄：一次是寫入到tablet日誌中，一次是寫入到Paxos日誌中。這種做法只是權宜之計，我們以後會進行完善。我們在Paxos實現上採用了管道化的方式，從而可以在存在廣域網延遲時改進Spanner的吞吐量，但是，Paxos會把寫操作按照順序的方式執行。 Paxos狀態機是用來實現一系列被一致性複製的映射。每個副本的鍵值映射狀態，都會被保存到相應的tablet中。寫操作必須在領導者上初始化Paxos協定，讀操作可以直接從底層的任何副本的tablet中訪問狀態信息，只要這個副本足夠新。副本的集合被稱為一個Paxos group。 對於每個是領導者的副本而言，每個spanserver會實現一個鎖表來實現並發控制。這個鎖表包含了兩階段鎖機制的狀態：它把鍵的值域映射到鎖狀態上面。注意，採用一個長壽命的Paxos領導者，對於有效管理鎖表而言是非常關鍵的。在BigTable和Spanner中，我們都專門為長事務做了設計，比如，對於報表操作，可能要持續幾分鐘，當存在衝突時，採用樂觀並發控制機制會表現出很差的性能。對於那些需要同步的操作，比如事務型的讀操作，需要獲得鎖表中的鎖，而其他類型的操作則可以不理會鎖表。 對於每個扮演領導者角色的副本，每個spanserver也會實施一個事務管理器來支持分散式事務。這個事務管理器被用來實現一個participant leader，該組內的其他副本則是作為participant slaves。如果一個事務只包含一個Paxos組（對於許多事務而言都是如此），它就可以繞過事務管理器，因為鎖表和Paxos二者一起可以保證事務性。如果一個事務包含了多於一個Paxos組，那些組的領導者之間會彼此協調合作完成兩階段提交。其中一個參與者組，會被選為協調者，該組的participant leader被稱為coordinator leader，該組的participant slaves被稱為coordinator slaves。每個事務管理器的狀態，會被保存到底層的Paxos組。
2.2 目錄和放置
在一系列鍵值映射的上層，Spanner實現支持一個被稱為“目錄”的桶抽象，也就是包含公共前綴的連續鍵的集合。（選擇“目錄”作為名稱，主要是由於歷史沿襲的考慮，實際上更好的名稱應該是“桶”）。我們會在第2.3節解釋前綴的源頭。對目錄的支持，可以讓套用通過選擇合適的鍵來控制數據的局部性。 一個目錄是數據放置的基本單元。屬於一個目錄的所有數據，都具有相同的副本配置。當數據在不同的Paxos組之間進行移動時，會一個目錄一個目錄地轉移，如圖3所示。Spanner可能會移動一個目錄從而減輕一個Paxos組的負擔，也可能會把那些被頻繁地一起訪問的目錄都放置到同一個組中，或者會把一個目錄轉移到距離訪問者更近的地方。當客戶端操作正在進行時，也可以進行目錄的轉移。我們可以預期在幾秒內轉移50MB的目錄。
spanner 一個Paxos組可以包含多個目錄，這意味著一個Spanner tablet是不同於一個BigTable tablet的。一個Spanner tablet沒有必要是一個行空間內按照詞典順序連續的分區，相反，它可以是行空間內的多個分區。我們做出這個決定，是因為這樣做可以讓多個被頻繁一起訪問的目錄被整合到一起。 Movedir是一個後台任務，用來在不同的Paxos組之間轉移目錄[14]。Movedir也用來為Paxos組增加和刪除副本[25]，因為Spanner目前還不支持在一個Paxos內部進行配置的變更。Movedir並不是作為一個事務來實現，這樣可以避免在一個塊數據轉移過程中阻塞正在進行的讀操作和寫操作。相反，Movedir會註冊一個事實(fact)，表明它要轉移數據，然後在後台運行轉移數據。當它幾乎快要轉移完指定數量的數據時，就會啟動一個事務來自動轉移那部分數據，並且為兩個Paxos組更新元數據。 一個目錄也是一個套用可以指定的地理複製屬性（即放置策略）的最小單元。我們的放置規範語言的設計，把管理複製的配置這個任務單獨分離出來。管理員需要控制兩個維度：副本的數量和類型，以及這些副本的地理放置屬性。他們在這兩個維度裡面創建了一個命名選項的選單。通過為每個資料庫或單獨的目錄增加這些命名選項的組合，一個套用就可以控制數據的複製。例如，一個套用可能會在自己的目錄里存儲每個終端用戶的數據，這就有可能使得用戶A的數據在歐洲有三個副本，用戶B的數據在北美有5個副本。 為了表達的清晰性，我們已經做了儘量簡化。事實上，當一個目錄變得太大時，Spanner會把它分片存儲。每個分片可能會被保存到不同的Paxos組上（因此就意味著來自不同的伺服器）。Movedir在不同組之間轉移的是分片，而不是轉移整個目錄。
2.3 數據模型
Spanner會把下面的數據特性集合暴露給套用：基於模式化的半關係表的數據模型，查詢語言和通用事務。支持這些特性的動機，是受到許多因素驅動的。需要支持模式化的半關係表是由Megastore[5]的普及來支持的。在谷歌內部至少有300個套用使用Megastore（儘管它具有相對低的性能），因為它的數據模型要比BigTable簡單，更易於管理，並且支持在跨數據中心層面進行同步複製。BigTable只可以支持跨數據中心的最終事務一致性。使用Megastore的著名的谷歌套用是Gmail,Picasa,Calendar,Android Market, AppEngine。在Spanner中需要支持SQL類型的查詢語言，也很顯然是非常必要的，因為Dremel[28]作為互動式分析工具已經非常普及。最後，在BigTable中跨行事務的缺乏來導致了用戶頻繁的抱怨；Percolator[32]的開發就是用來部分解決這個問題的。一些作者都在抱怨，通用的兩階段提交的代價過於昂貴，因為它會帶來可用性問題和性能問題[9][10][19]。我們認為，最好讓應用程式開發人員來處理由於過度使用事務引起的性能問題，而不是總是圍繞著“缺少事務”進行編程。在Paxos上運行兩階段提交弱化了可用性問題。 套用的數據模型是架構在被目錄桶裝的鍵值映射層之上。一個套用會在一個universe中創建一個或者多個資料庫。每個資料庫可以包含無限數量的模式化的表。每個表都和關係資料庫表類似，具備行、列和版本值。我們不會詳細介紹Spanner的查詢語言，它看起來很像SQL，只是做了一些擴展。 Spanner的數據模型不是純粹關係型的，它的行必須有名稱。更準確地說，每個表都需要有包含一個或多個主鍵列的排序集合。這種需求，讓Spanner看起來仍然有點像鍵值存儲：主鍵形成了一個行的名稱，每個表都定義了從主鍵列到非主鍵列的映射。當一個行存在時，必須要求已經給行的一些鍵定義了一些值（即使是NULL）。採用這種結構是很有用的，因為這可以讓套用通過選擇鍵來控制數據的局部性。
spanner 圖4包含了一個Spanner模式的實例，它是以每個用戶和每個相冊為基礎存儲圖片元數據。這個模式語言和Megastore的類似，同時增加了額外的要求，即每個Spanner資料庫必須被客戶端分割成一個或多個表的層次結構（hierarchy）。客戶端套用會使用INTERLEAVE IN語句在資料庫模式中聲明這個層次結構。這個層次結構上面的表，是一個目錄表。目錄表中的每行都具有鍵K，和子孫表中的所有以K開始（以字典順序排序）的行一起，構成了一個目錄。ON DELETE CASCADE意味著，如果刪除目錄中的一個行，也會級聯刪除所有相關的子孫行。這個圖也解釋了這個實例資料庫的交織層次（interleaved layout），例如Albums(2,1)代表了來自Albums表的、對應於user_id=2和album_id=1的行。這種表的交織層次形成目錄，是非常重要的，因為它允許客戶端來描述存在於多個表之間的位置關係，這對於一個分片的分散式資料庫的性能而言是很重要的。沒有它的話，Spanner就無法知道最重要的位置關係。
並發控制
本部分內容描述TrueTime如何可以用來保證並發控制的正確性，以及這些屬性如何用來實現一些關鍵特性，比如外部一致性的事務、無鎖機制的唯讀事務、針對歷史數據的非阻塞讀。這些特性可以保證，在時間戳為t的時刻的資料庫讀操作，一定只能看到在t時刻之前已經提交的事務。 進一步說，把Spanner客戶端的寫操作和Paxos看到的寫操作這二者進行區分，是非常重要的，我們把Paxos看到的寫操作稱為Paxos寫操作。例如，兩階段提交會為準備提交階段生成一個Paxos寫操作，這時不會有相應的客戶端寫操作。
總結
總的來說，Spanner對來自兩個研究群體的概念進行了結合和擴充：一個是資料庫研究群體，包括熟悉易用的半關係接口，事務和基於SQL的查詢語言；另一個是系統研究群體，包括可擴展性，自動分區，容錯，一致性複製，外部一致性和大範圍分布。自從Spanner概念成形，我們花費了5年以上的時間來完成當前版本的設計和實現。花費這么長的時間，一部分原因在於我們慢慢意識到，Spanner不應該僅僅解決全球複製的命名空間問題，而且也應該關注Bigtable中所丟失的資料庫特性。
