當前位置：首頁 > 运维知识 > 数据库 >内容正文

数据库

Google Spanner：谷歌的全球分布式数据库

發布時間：2024/2/28 数据库 32 豆豆

生活随笔收集整理的這篇文章主要介紹了 Google Spanner：谷歌的全球分布式数据库小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

摘要

Spanner 是谷歌公司研發的、可擴展的、多版本、全球分布式、同步復制數據庫。它是第一個把數據分布在全球范圍內的系統，并且支持外部一致性的分布式事務。本文描述了 Spanner 的架構、特性、不同設計決策的背后機理和一個新的時間 API，這個 API 可以暴露時鐘的不確定性。這個 API 及其實現，對于支持 外部一致性 和許多強大特性而言是非常重要的，這些強大特性包括：非阻塞的讀、不采用鎖機制的只讀事務、原子模式變更。

關鍵詞：Google Spanner, Bigtable, distributed database;

1.?介紹

Spanner 是一個可擴展的、全球分布式的數據庫，是在谷歌公司設計、開發和部署的。在最高抽象層面，Spanner 就是一個數據庫，把數據分片存儲在許多 Paxos[21] 狀態機上，這些機器位于遍布全球的數據中心內。復制技術可以用來服務于 全球可用性 和 地理局部性。客戶端會自動在副本之間進行失敗恢復。隨著數據的變化和服務器的變化，Spanner 會自動把數據進行重新分片，從而有效應對負載變化和處理失敗。Spanner 被設計成可以擴展到幾百萬個機器節點，跨越成百上千個數據中心，具備幾萬億數據庫行的規模。

應用可以借助于 Spanner 來實現高可用性，通過在一個洲的內部和跨越不同的洲之間復制數據，保證即使面對大范圍的自然災害時數據依然可用。我們最初的 client 是 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 部分討論了相關工作，并給出總結。

2.?實現

本部分內容描述了 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，也實現了下面的映射：

( key:string, timestamp:int64 ) -> string

與 BigTable 不同的是，Spanner 會把時間戳分配給數據，這種非常重要的方式，使得?Spanner 更像一個多版本數據庫，而不是一個鍵值存儲。一個 tablet 的狀態是存儲在類似于 B-樹的文件集合和寫前（write-ahead）的日志中，所有這些都會被保存到一個分布式的文件系統中，這個分布式文件系統被稱為 Colossus，它繼承自 Google File System。

為了支持復制，每個 spanserver 會在每個 tablet 上面實現一個單個的 Paxos 狀態機。?一個之前實現的 Spanner 可以支持在每個 tablet 上面實現多個 Paxos 狀態機，它可以允許更加靈活的復制配置，但是，這種設計過于復雜，被我們舍棄了。每個狀態機都會在相應的 tablet 中保存自己的元數據和日志。我們的 Paxos 實現支持采用基于時間的?Leader 租約，Leader 的生存時間較長，時間通常是?10 秒。當前的 Spanner 實現中，會對每個 Paxos 寫操作進行兩次記錄：一次是寫入到 tablet 日志中，一次是寫入到 Paxos 日志中。這種做法只是權宜之計，我們以后會進行完善。我們在 Paxos 實現上采用了管道化的方式，從而可以在存在廣域網延遲時改進 Spanner 的吞吐量，但是， Paxos 會把寫操作按照順序的方式執行。

Paxos 狀態機被用來實現一致性復制的映射。每個副本的鍵值映射狀態，都會被保存到相應的 tablet 中。寫操作必須在?Leader 上初始化 Paxos 協議，讀操作可以直接從底層的任何副本的 tablet 中訪問狀態信息，只要這個副本足夠新。副本的集合被稱為一個 Paxos?group。

對于每個是?Leader 的副本而言，每個 spanserver 會實現一個鎖表（lock table）來實現并發控制。這個鎖表包含了兩階段鎖機制的狀態：它把鍵的值域映射到鎖狀態上面。注意，Paxos ?Leader 采用的生存期較長，對于有效管理鎖表（lock table）而言是非常關鍵的。在 BigTable 和 Spanner 中，我們都專門為長事務做了設計，比如，對于文檔生成（report generation），可能要持續幾分鐘，當存在沖突時，采用樂觀并發控制機制會表現出很差的性能。對于那些需要同步的操作，比如事務型的讀操作，需要獲得鎖表中的鎖，而其他類型的操作則可以不理會鎖表。

對于每個扮演?Leader 角色的副本，每個 spanserver 也會實現一個事務管理器來支持分布式事務。這個事務管理器被用來實現一個 participant leader，該組內的其他副本則是作為?participant slaves。如果一個事務只包含一個 Paxos 組（對于許多事務而言都是如此），它就可以繞過事務管理器，因為鎖表和 Paxos 二者一起可以保證事務性。如果一個事務包含了多于一個 Paxos 組，那些組的?Leader 之間會彼此協調合作完成兩階段提交。其中一個參與者組，會被選為協調者，該組的 participant leader 被稱為 coordinator leader，該組的 participant slaves 被稱為 coordinator slaves。每個事務管理器的狀態，會被保存到底層的 Paxos 組。

2.2 目錄和放置

在一系列鍵值映射的上層，Spanner 實現支持一個被稱為?"目錄"?的桶抽象，也就是包含公共前綴的連續鍵的集合。（選擇?"目錄"?作為名稱，主要是由于歷史的原因，實際上更好的名稱應該是?"桶"?）。我們會在第 2.3 節解釋前綴的源頭。對目錄的支持，可以讓應用通過選擇合適的鍵來控制數據的局部性。

一個目錄是數據放置的基本單元。屬于一個目錄的所有數據，都具有相同的副本配置。當數據在不同的 Paxos 組之間進行移動時，會一個目錄一個目錄地轉移，如圖 3 所示。Spanner 可能會移動一個目錄從而減輕一個 Paxos 組的負擔，也可能會把那些被頻繁地一起訪問的目錄都放置到同一個組中，或者會把一個目錄轉移到距離訪問者更近的地方。當客戶端操作正在進行時，也可以進行目錄的轉移。我們預期可以在幾秒內轉移 50MB 的目錄。

一個 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）。采用這種結構是很有用的，因為這可以讓應用通過選擇鍵來控制數據的局部性。

圖 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 就無法知道最重要的位置關系。

3.?TrueTime

本部分內容描述 TrueTime API，并大概給出它的實現方法。我們把大量細節內容放在另一篇論文中，我們的目標是展示這種 API 的力量。表 1 列出了 API 的方法。TrueTime 會顯式地把時間表達成 TTinterval，這是一個時間區間，具有有界限的時間不確定性（不像其他的標準時間接口，沒有為客戶端提供?"不確定性"?這種概念）。TTinterval 區間的端點是 TTstamp類型。TT.now()方法會返回一個 TTinterval，它可以保證包含 TT.now()?方法在調用時的絕對時間。這個時間和具備 leap-second smearing 的 UNIX 時間一樣。把即時誤差邊界定義為 ε，平均誤差邊界為??。TT.after() 和 TT.before() 方法是針對 TT.now() 的的包裝。

表示一個事件 e 的絕對時間，可以利用函數。如果用更加形式化的術語，TrueTime 可以保證，對于一個調用 tt = TT.now()，有tt.earliest??≤???≤??tt.latest，其中，是? 是調用的事件。

在底層，TrueTime 使用的時間是 GPS 和原子鐘。TrueTime 使用兩種類型的時間，是因為它們有不同的失效原因。GPS 參考時間的弱點是天線和接收器失效、局部電磁干擾和相關失敗（比如設計上的缺陷導致無法正確處理閏秒和電子欺騙），以及 GPS 系統運行中斷。原子鐘也會失效，不過失效的方式和 GPS 無關，不同原子鐘之間的失效也沒有彼此關聯。由于存在頻率誤差，在經過很長的時間以后，原子鐘都會產生明顯誤差。

TrueTime 是由每個數據中心上面的許多 time master 機器和每臺機器上的一個 timeslave?守護進程來共同實現的。大多數 master 都有具備專用天線的 GPS 接收器，這些 master 在物理上是相互隔離的，這樣可以減少天線失效、電磁干擾和電子欺騙的影響。剩余的 master?我們稱為 Armageddon master）則配備了原子鐘。一個原子鐘并不是很昂貴：一個 Armageddon master 的花費和一個 GPS master 的花費是同一個數量級的。所有 master 的時間參考值都會進行彼此校對。每個 master 也會交叉檢查時間參考值和本地時間的比值，如果二者差別太大，就會把自己驅逐出去。在同步期間，Armageddon master 會表現出一個逐漸增加的時間不確定性，這是由保守應用的最差時鐘漂移引起的。GPS master 表現出的時間不確定性幾乎接近于 0。

每個守護進程會從許多 master[29]中收集投票，獲得時間參考值，從而減少誤差。被選中的 master 中，有些 master 是 GPS master，是從附近的數據中心獲得的，剩余的 GPS master 是從遠處的數據中心獲得的；還有一些是 Armageddon master。守護進程會使用一個 Marzullo 算法[27]的變種，來探測和拒絕欺騙，并且把本地時鐘同步到非撒謊 master 的時間參考值。為了免受較差的本地時鐘的影響，我們會根據組件規范和運行環境確定一個界限，如果機器的本地時鐘誤差頻繁超出這個界限，這個機器就會被驅逐出去。

在同步期間，一個守護進程會表現出逐漸增加的時間不確定性。?ε 是從保守應用的最差時鐘中得到的。ε 也取決于 time master 的不確定性，以及與 time master 之間的通訊延遲。在我們的線上應用環境中，ε 通常是一個關于時間的鋸齒形函數。在每個投票間隔中，ε 會在 1 到 7ms 之間變化。因此，在大多數情況下，?的值是 4ms。守護進程的投票間隔，在當前是 30 秒，當前使用的時鐘移動比率是 200 微秒/秒，二者一起意味著 0 到 6ms 的鋸齒形邊界。剩余的 1ms 主要來自到 time master 的通訊延遲。在失敗的時候，超過這個鋸齒形邊界也是有可能的。例如，偶爾的 time master 不確定性，可能會引起整個數據中心范圍內的 ε?值的增加。類似的，過載的機器或者網絡連接，都會導致 ε 值偶爾地局部增大。

4.?并發控制

本部分內容描述 TrueTime 如何可以用來保證并發控制的正確性，以及這些屬性如何用來實現一些關鍵特性，比如外部一致性的事務、無鎖機制的只讀事務、針對歷史數據的非阻塞讀。這些特性可以保證，在時間戳為 t 的時刻的數據庫讀操作，一定只能看到在 t 時刻之前已經提交的事務。

進一步說，把 Spanner 客戶端的寫操作和 Paxos 看到的寫操作這二者進行區分，是非常重要的，我們把 Paxos 看到的寫操作稱為 Paxos 寫操作。例如，兩階段提交會為準備提交階段生成一個 Paxos 寫操作，這時不會有相應的客戶端寫操作。

4.1 時間戳管理

表 2 列出了 Spanner 支持的操作的類型。Spanner 可以支持讀寫事務、只讀事務（預先聲明的快照隔離事務）和快照讀。 獨立寫操作，會被當成讀寫事務來執行。非快照獨立讀操作，會被當成只讀事務來執行。二者都是在內部進行 retry，客戶端不用進行這種 retry loop。

一個只讀事務具備快照隔離的性能優勢[6]。一個只讀事務必須事先被聲明不會包含任何寫操作，它并不是一個簡單的不包含寫操作的讀寫事務。在一個只讀事務中的讀操作，在執行時會采用一個系統選擇的時間戳，不包含鎖機制，因此，后面到達的寫操作不會被阻塞。在一個只讀事務中的讀操作，可以到任何足夠新的副本上去執行（見第 4.1.3 節）。

一個快照讀操作，是針對歷史數據的讀取，執行過程中，不需要鎖機制。一個客戶端可以為快照讀確定一個時間戳，或者提供一個時間范圍讓 Spanner 來自動選擇時間戳。不管是哪種情況，快照讀操作都可以在任何具有足夠新的副本上執行。

對于只讀事務和快照讀而言，一旦已經選定一個時間戳，那么，提交就是不可避免的，除非在那個時間點的數據已經被垃圾回收了。因此，客戶端不必在 retry loop 中緩存結果。當一個服務器失效的時候，客戶端就可以使用同樣的時間戳和當前的讀位置，在另外一個服務器上繼續執行讀操作。

4.1.1 Paxos ?Leader 租約

Spanner 的 Paxos 實現中使用了時間化的租約，來實現壽命較長的?Leader（默認是 10秒）。一個潛在的?Leader 會發起請求，請求時間化的租約投票，在收到指定數量的投票后，這個?Leader 就可以確定自己擁有了一個租約。一個副本在成功完成一個寫操作后，會隱式地延期自己的租約。對于一個?Leader 而言，如果它的租約快要到期了，就要顯示地請求租約延期。另一個?Leader 的租約有個時間區間，這個時間區間的起點就是這個?Leader 獲得指定數量的投票那一刻，時間區間的終點就是這個?Leader 失去指定數量的投票的那一刻（因為有些投票已經過期了）。Spanner 依賴于下面這些?"不連貫性"?：對于每個 Paxos 組，每個 Paxos ?Leader 的租約時間區間，是和其他?Leader 的時間區間完全隔離的。附錄 A 顯示了如何強制實現這些不連貫性。

Spanner 實現允許一個 Paxos?Leader 通過把 slave 從租約投票中釋放出來這種方式，實現?Leader 的退位。為了保持這種彼此隔離的不連貫性，Spanner 會對什么時候退位做出限制。把 ?定義為一個?Leader 可以使用的最大的時間戳。在退位之前，一個?Leader 必須等到 TT.after() 是真。

4.1.2 為讀寫事務分配時間戳

事務讀和寫采用兩段鎖協議。當所有的鎖都已經獲得以后，在任何鎖被釋放之前，就可以給事務分配時間戳。對于一個給定的事務，Spanner 會為事務分配時間戳，這個時間戳是 Paxos 分配給 Paxos 寫操作的，它代表了事務提交的時間。

Spanner 依賴下面這些單調性：在每個 Paxos 組內，Spanner 會以單調增加的順序給每個 Paxos 寫操作分配時間戳，即使在跨越多個?Leader 時也是如此。單個的?Leader 副本，可以很容易地以單調增加的方式分配時間戳。在多個?Leader 之間就會強制實現彼此隔離的不連貫：一個?Leader 必須只能分配屬于它自己租約時間區間內的時間戳。要注意到，一旦一個時間戳 s 被分配，?就會被增加到 s，從而保證彼此隔離性（不連貫性）。

Spanner 也會實現下面的外部一致性：如果一個事務 T2 在事務 T1 提交以后開始執行，那么，事務 T2 的時間戳一定比事務 T1 的時間戳大。對于一個事務 Ti 而言，定義開始和提交事件??和? ，事務提交時間為 si。對外部一致性的要求就變成了：

? => s1 < s2。執行事務的協議和分配時間戳的協議，遵守兩條規則，二者一起保證外部一致性。對于一個寫操作 Ti 而言，擔任協調者的?Leader 發出的提交請求的事件為 ?。

Start：為一個事務 Ti 擔任協調者的?Leader 分配一個提交時間戳 si，不會小于 TT.now().latest 的值，TT.now().latest 的值是在???事件之后計算得到的。要注意，擔任參與者的?Leader，在這里不起作用。第 4.2.1 節描述了這些擔任參與者的?Leader 是如何參與下一條規則的實現的。

Commit Wait：擔任協調者的?Leader，必須確保客戶端不能看到任何被 Ti 提交的數據，直到?TT.after(si)?為真。提交等待，就是要確保 si 會比 Ti 的絕對提交時間小。提交等待的實現在 4.2.1節中描述。證明如下：

4.1.3 在某個時間戳下的讀操作

第 4.1.2 節中描述的單調性，使得 Spanner 可以正確地確定一個副本是否足夠新，從而能夠滿足一個讀操作的要求。每個副本都會跟蹤記錄一個值，這個值被稱為安全時間??，它是一個副本最近更新后的最大時間戳。如果一個讀操作的時間戳是 t，當滿足 t <= ?時，這個副本就可以被這個讀操作讀取。

這里定義???，其中，每個 Paxos 狀態機都有一個安全時間，每個事務管理器都有一個安全時間。?比較簡單：就是最高應用的 Paxos 寫操作的時間戳。由于時間戳會單調增加，寫操作也是被順序應用的，在小于? 以后，寫操作就不會發生。

對于一個副本而言，如果有 0 個處于準備階段（沒有提交）的事務，是無窮的。?對于一個參與的 slave 而言，?實際上會引用副本的?Leader 的事務管理器， slave 可以根據?Paxos 寫操作傳遞的元數據來推斷事務管理器的狀態。如果存在許多這樣的事務，那么這些事務對狀態的影響是不確定的：一個參與者副本不知道這種事務是否需要提交。正如我們在第 4.2.1 節討論的那樣，提交協議會確保每個參與者會知道一個處于準備提交階段的事務的時間戳的下界。對于事務 Ti 的每個參與?Leader （對于一個組 g 而言），會為準備提交的記錄分配一個準備時間戳??。擔任協調者角色的?Leader，會確保在所有參與者組 g 的事務提交的時間戳 si >= 。因此，在一個組 g 中的每個副本，對于在 g 中準備的所有事務Ti，都有??。

4.1.4 為只讀事務分配時間戳

一個只讀事務分成兩個階段執行：分配一個時間戳 ?[8]，然后當成 ?時刻的快照讀來執行事務讀操作。快照讀可以在任何足夠新的副本上面執行。

在一個事務開始后的任意時刻，可以簡單地分配 = TT.now().latest，通過第 4.1.2 節中描述過的類似的方式來維護外部一致性。但是，對于時間戳而言，如果沒有增加到足夠大，可能需要對時刻的讀操作進行阻塞。除此以外還要注意，選擇一個的值可能也會增加的值，從而保證不連貫性。為了減少阻塞的概率， Spanner 應該分配可以保持外部一致性的最老的時間戳。第 4.2.2 節描述了如何選擇這種時間戳。

4.2 細節

這部分內容介紹一些讀寫操作和只讀操作的實踐細節，以及用來實現原子模式變更的特定事務的實現方法。然后，描述一些基本模式的細化。

4.2.1 讀寫事務

就像 Bigtable 一樣，發生在一個事務中的寫操作會在客戶端進行緩存，直到提交。由此導致的結果是，在一個事務中的讀操作，不會看到這個事務的寫操作的結果。這種設計在?Spanner 中可以很好地工作，因為一個讀操作可以返回任何數據讀的時間戳，未提交的寫操作還沒有被分配時間戳。

在讀寫事務內部的讀操作，使用傷停等待（ wound-wait）[33]來避免死鎖。客戶端對位于合適組內的?Leader 副本發起讀操作，需要首先獲得讀鎖，然后讀取最新的數據。當一個客戶端事務保持活躍的時候，它會發送"保持活躍"信息，防止那些參與的?Leader 讓該事務過時。當一個客戶端已經完成了所有的讀操作，并且緩沖了所有的寫操作，它就開始兩階段提交。客戶端選擇一個協調者組，并且發送一個提交信息給每個參與的、具有協調者標識的?Leader，并發送提交信息給任何緩沖的寫操作。讓客戶端發起兩階段提交操作，可以避免在大范圍連接內發送兩次數據。

一個參與其中的、扮演非協調者角色的?Leader，首先需要獲得寫鎖。然后，它會選擇一個預備時間戳，這個時間戳應該比之前分配給其他事務的任何時間戳都要大（這樣可以保持單調性），并且通過 Paxos 把準備提交記錄寫入日志。然后，每個參與者就把自己的準備時間戳通知給協調者。

扮演協調者的?Leader，也會首先獲得寫鎖，但是，會跳過準備階段。在從所有其他的、扮演參與者的?Leader 那里獲得信息后，它就會為整個事務選擇一個時間戳。這個提交時間戳?s 必須大于或等于所有的準備時間戳（這是為了滿足第 4.1.3 節討論的限制條件），在協調者收到它的提交信息時，s 應該大于 TT.now().latest，并且 s 應該大于這個?Leader 為之前的其他所有事務分配的時間戳（再次指出，這樣做是為了滿足單調性）。這個扮演協調者的?Leader，就會通過 Paxos 在日志中寫入一個提交記錄（或者當等待其他參與者發生超時就在日志中寫入終止記錄）。

在允許任何協調者副本去提交記錄之前，扮演協調者的?Leader 會一直等待到 TT.after(s)，從而可以保證遵循第 4.1.2 節中描述的提交等待規則。因為，扮演協調者的?Leader 會根據?TT.now().latest 來選擇 s，而且必須等待直到那個時間戳可以確保成為過去，預期的等待時間至少是 2*ε。這種等待時間通常會和 Paxos 通信時間發生重疊。在提交等待之后，協調者就會發送一個提交時間戳給客戶端和所有其他參與的?Leader 。每個參與的?Leader 會通過 Paxos 把事務結果寫入日志。所有的參與者會在同一個時間戳進行提交，然后釋放鎖。

4.2.2 只讀事務

分配一個時間戳需要一個協商階段，這個協商發生在所有參與到該讀操作中的 Paxos 組之間。由此導致的結果是，Spanner 需要為每個只讀事務提供一個 scope 表達式，它可以指出整個事務需要讀取哪些鍵。對于單獨的查詢，Spanner 可以自動計算出 scope。

如果 scope 的值是由單個 Paxos 組來提供的，那么，客戶端就會給那個組的?Leader 發起一個只讀事務（當前的 Spanner?實現中，只會為 Paxos leader?中的只讀事務選擇一個時間戳），為那個?Leader 分配? 并且執行讀操作。對于單個位置的讀操作， Spanner 通常會比?TT.now().latest 做得更好。我們把 LastTS()?定義為在 Paxos 組中最后提交的寫操作的時間戳。如果沒有準備提交的事務，這個分配到的時間戳 ?=?LastTS()?就很容易滿足外部一致性要求：這個事務將可以看見最后一個寫操作的結果，然后排隊排在它之后。

如果 scope 的值是由多個 Paxos 組來提供的，就會有幾種選擇。最復雜的選擇就是，和所有組的?Leader 進行一輪溝通，大家根據 LastTS()?進行協商得到 ?。Spanner 當前實現了一個更加簡單的選擇。這個選擇可以避免一輪協商，讓讀操作在 ?=?TT.now().latest 時刻去執行（這可能會等待安全時間的增加）。這個事務中的所有讀操作，可以被發送到任何足夠新的副本上執行。

4.2.3 模式變更事務

TrueTime 允許 Spanner 支持原子模式變更。使用一個標準的事務是不可行的，因為參與者的數量（即數據庫中組的數量）可能達到幾百萬個。Bigtable 可以支持在一個數據中心內進行原子模式變更，但是，這個操作會阻塞所有其他操作。

一個 Spanner 模式變更事務通常是一個標準事務的、非阻塞的變種。首先，它會顯式地分配一個未來的時間戳，這個時間戳會在準備階段進行注冊。由此，跨越幾千個服務器的模式變更，可以在不打擾其他并發活動的前提下完成。其次，讀操作和寫操作，它們都是隱式地依賴于模式，它們都會和任何注冊的模式變更時間戳 t 保持同步：當它們的時間戳小于 t 時，讀寫操作就執行到時刻 t；當它們的時間戳大于時刻 t 時，讀寫操作就必須阻塞，在模式變更事務后面進行等待。如果沒有 TrueTime，那么定義模式變更發生在 t 時刻，就變得毫無意義。

4.2.4 優化

?? 有一個弱點，那就是，一個單獨的準備提交的事務，可能會阻止?? 繼續增加。由此導致的結果是，在那以后的時間戳上就無法執行讀操作，即使讀操作不會和這個事務發生沖突。這種假沖突可以消除，方法是為??增加一個從鍵域（ key ranges）到準備提交時間戳的細粒度的映射。這種信息可以存儲到鎖表，鎖表早已經把鍵域映射到鎖元數據。當一個讀操作到達時，它只需要針對鍵域與讀操作發生沖突的、細粒度的安全時間進行檢查。

LastTS()?也有一個缺陷：如果一個事務已經提交了，一個非沖突的只讀事務就必須被分配??，從而可以跟在那個事務后面。由此導致的結果是，讀操作可能被延遲。消除這個弱點的方法是，為 LastTS()?增加一個從鍵域（ key ranges）到鎖表中的提交時間戳的細粒度的映射（我們還沒有實現這種優化）。當一個只讀事務到達時，它的時間戳就可以被分配，可以采用和這個事務沖突的鍵域的 LastTS()?的最大值，除非有一個沖突的準備提交的事務（這可以從細粒度安全時間里面確定）。

?有一個弱點：當存在 Paxos 寫操作的時候，它就無法增加。也就是說，在 t 時刻快照讀操作，不能在那些最后寫操作發生在 t 之前的 Paxos 組中執行。Spanner 解決了這個問題，方法是充分利用?Leader 租約區間的隔離性。每個 Paxos?Leader 會增加，并且設置一個閾值，未來的寫操作時間戳會達到這個閾值：它維護了一個從 Paxos 序列號 n 到最小時間戳的映射 MinNextTS(n)，這個時間戳是允許分配給 Paxos 序列號 n+1 的最小時間戳。一個副本，當已經應用到 n 的時候，會把? 增加到 MinNextTS(n) - 1。

一個單個的?Leader 會比較容易實現它的 MinNextTS()。因為，MinNextTS() 承諾的時間戳位于一個?Leader 租約內，在不同?Leader 之間可以保證實現前面講過的?"不連貫性"。如果一個?Leader 希望在租約到期后繼續增加 MinNextTS()，它就必須首先擴展它的租約。注意，為了保證不連貫性，總會增加到 MinNextTS() 中的最高值。

在默認情況下，一個?Leader 會每隔 8 秒鐘增加 MinNextTS()。因此，在缺少準備提交的事務的時候，在空閑 Paxos 組中工作正常的 slave，就可以為那些時間戳已經老化超過 8 秒的讀操作提供服務。一個?Leader 也會根據 slave 的要求來增加 MinNextTS()的值。

5. 實驗分析

我們對 Spanner 性能進行了測試，包括復制、事務和可用性。然后，我們提供了一些關于 TrueTime 的實驗數據，并且提供了我們的第一個用例——F1。

5.1 微測試基準

表 3 給出了一用于 Spanner 的微測試基準(microbenchmark)。這些測試是在分時機器上實現的：每個 spanserver 采用 4GB 內存和四核 CPU（AMD Barcelona 2200MHz）。客戶端運行在單獨的機器上。每個 zone 都包含一個 spanserver。客戶端和 zone 都放在一個數據中心集合內，它們之間的網絡距離不會超過 1ms。這種布局是很普通的，許多數據并不需要把數據分散存儲到全球各地）。測試數據庫具有 50 個 Paxos 組和 2500 個目錄。操作都是獨立的4KB 大小的讀和寫。所有的讀操作在完成并壓縮后，就會被移出內存，所以我們只需要衡量 Spanner 調用棧的開銷。此外，還會進行一輪讀操作，來預熱任何位置的緩存。

對于延遲實驗而言，客戶端會發起足夠少量的操作，從而避免在服務器中發生排隊。從?1 個副本的實驗中，提交等待大約是 5ms，Paxos 延遲大約是 9ms。隨著副本數量的增加，延遲大約保持不變，只具有很少的標準差，因為在一個組的副本內，Paxos 會并行執行。隨著副本數量的增加，獲得指定投票數量的延遲對一個 slave 副本的慢速度不會很敏感。

對于吞吐量的實驗而言，客戶端發起足夠數量的操作，從而使得 CPU 處理能力達到飽和。快照讀操作可以在任何足夠新的副本上進行，因此，快照讀的吞吐量會隨著副本的數量增加而線性增加。單個讀的只讀事務，只會在?Leader 上執行，因為，時間戳分配必須發生在?Leader 上。?只讀事務吞吐量會隨著副本數量的增加而增加，因為有效的 spanserver 的數量會增加：在這個實驗的設置中，spanserver 的數量和副本的數量相同，Leader 會被隨機分配到不同的 zone。寫操作的吞吐量也會從這種實驗設置中獲得收益（副本從 3 變到 5 時寫操作吞吐量增加了，就能夠說明這點），但是，隨著副本數量的增加，每個寫操作執行時需要完成的工作量也會線性增加，這就會抵消前面的收益。

表 4 顯示了兩階段提交可以擴展到合理數量的參與者：它是對一系列實驗的總結，這些實驗運行在 3 個 zone 上，每個 zone 具有 25 個 spanserver。擴展到 50 個參與者，無論在平均值還是第 99 個百分位方面，都是合理的。在 100 個參與者的情形下，延遲開發明顯增加。

5.2 可用性

圖 5 顯示了在多個數據中心運行 Spanner 時的可用性方面的收益。它顯示了三個吞吐量實驗的結果，并且存在數據中心失敗的情形，所有三個實驗結果都被重疊放置到一個時間軸上。測試用的 universe 包含 5 個 zone Zi，每個 zone 都擁有 25 個 spanserver。測試數據庫被分片成 1250 個 Paxos 組，100 個客戶端不斷地發送非快照讀操作，累積速率是每秒 50K 個讀操作。所有?Leader 都會被顯式地放置到 Z1。每個測試進行 5 秒鐘以后，一個 zone 中的所有服務器都會被?"殺死"： non-leader 殺掉 Z2，leader-hard 殺掉 Z1，leader-soft 殺掉 Z1，但是，它會首先通知所有服務器它們將要交出領導權。

殺掉 Z2 對于讀操作吞吐量沒有影響。殺掉 Z1，給?Leader 一些時間來把領導權交給另一個 zone 時，會產生一個小的影響：吞吐量會下降，不是很明顯，大概下降 3-4%。另一方面，沒有預警就殺掉 Z1 有一個明顯的影響：完成率幾乎下降到 0。隨著?Leader 被重新選擇，系統的吞吐量會增加到大約每秒 100K 個讀操作，主要是由于我們的實驗設置：系統中有額外的能力，當找不到?Leader 時操作會排隊。由此導致的結果是，系統的吞吐量會增加直到到達系統恒定的速率。

我們可以看看把 Paxos?Leader 租約設置為 10ms 的效果。當我們殺掉這個 zone，對于這個組的?Leader 租約的過期時間，會均勻地分布到接下來的 10 秒鐘內。來自一個死亡的?Leader 的每個租約一旦過期，就會選擇一個新的?Leader。大約在殺死時間過去 10 秒鐘以后，所有的組都會有?Leader，吞吐量就恢復了。短的租約時間會降低服務器死亡對于可用性的影響，但是，需要更多的更新租約的網絡通訊開銷。我們正在設計和實現一種機制，它可以在?Leader 失效的時候，讓 slave 釋放 Paxos?Leader 租約。

5.3 TrueTime

關于 TrueTime，必須回答兩個問題：ε 是否就是時鐘不確定性的邊界？ε 會變得多糟糕？對于第一個問題，最嚴峻的問題就是，如果一個局部的時鐘移動大于 200us/sec，那就會破壞 TrueTime 的假設。我們的機器統計數據顯示，壞的 CPU 的出現概率要比壞的時鐘出現概率大 6 倍。也就是說，與更加嚴峻的硬件問題相比，時鐘問題是很少見的。由此，我們也相信，TrueTime 的實現和 Spanner 其他軟件組件一樣，具有很好的可靠性，值得信任。

圖 6 顯示了 TrueTime 數據，是從幾千個 spanserver 中收集的，這些 spanserver 跨越了多個數據中心，距離 2200 公里以上。圖中描述了 ε 的第 90 個、 99 個和 99.9 個百分位的情況，是在對 timemaster 進行投票后立即對 timeslave?守護進程進行樣本抽樣的。這些抽樣數據沒有考慮由于時鐘不確定性帶來的 ε 值的鋸齒，因此測量的是 timemaster 不確定性（通常是 0）再加上通訊延遲。

圖 6 中的數據顯示了，在決定 ε 的基本值方面的上述兩個問題，通常都不會是個問題。但是，可能會存在明顯的拖尾延遲問題，那會引起更高的 ε 值。圖中，3 月 30 日拖尾延遲的降低，是因為網絡的改進，減少了瞬間網絡連接的擁堵。在 4 月 13 日 ε 的值增加了，持續了大約 1 個小時，主要是因為例行維護時關閉了兩個 time master。我們會繼續調研并且消除引起 TrueTime 突變的因素。

5.4 F1

Spanner 在 2011 年早期開始進行在線負載測試，它是作為谷歌廣告后臺 F1[35]的重新實現的一部分。這個后臺最開始是基于 MySQL 數據庫，在許多方面都采用手工數據分區。未經壓縮的數據可以達到幾十 TB，雖然這對于許多 NoSQL 實例而言數據量是很小的，但是，對于采用數據分區的 MySQL 而言，數據量是非常大的。MySQL 的數據分片機制，會把每個客戶和所有相關的數據分配給一個固定的分區。這種布局方式，可以支持針對單個客戶的索引構建和復雜查詢處理，但是，需要了解一些商業知識來設計分區。隨著客戶數量的增長，對數據進行重新分區，代價是很大的。最近一次的重新分區，花費了兩年的時間，為了降低風險，在多個團隊之間進行了大量的合作和測試。這種操作太復雜了，無法常常執行，由此導致的結果是，團隊必須限制 MySQL 數據庫的增長，方法是，把一些數據存儲在外部的Bigtable 中，這就會犧牲事務和查詢所有數據的能力。

F1 團隊選擇使用 Spanner 有幾個方面的原因。首先，Spanner 不需要手工分區。其次，Spanner 提供了同步復制和自動失敗恢復。在采用 MySQL 的 master-slave 復制方法時，很難進行失敗恢復，會有數據丟失和當機的風險。再次，F1 需要強壯的事務語義，這使得使用其他 NoSQL 系統是不實際的。應用語義需要跨越任意數據的事務和一致性讀。F1 團隊也需要在他們的數據上構建二級索引（因為 Spanner 沒有提供對二級索引的自動支持），也有能力使用 Spanner 事務來實現他們自己的一致性全球索引。

所有應用寫操作，現在都是默認從 F1 發送到 Spanner。而不是發送到基于 MySQL 的應用棧。F1 在美國的西岸有兩個副本，在東岸有三個副本。這種副本位置的選擇，是為了避免發生自然災害時出現服務停止問題，也是出于前端應用的位置的考慮。實際上，Spanner 的失敗自動恢復，幾乎是不可見的。在過去的幾個月中，盡管有不在計劃內的機群失效，但是，F1 團隊最需要做的工作仍然是更新他們的數據庫模式，來告訴 Spanner 在哪里放置 Paxos?Leader，從而使得它們盡量靠近應用前端。

Spanner 時間戳語義，使得它對于 F1 而言，可以高效地維護從數據庫狀態計算得到的、放在內存中的數據結構。F1 會為所有變更都維護一個邏輯歷史日志，它會作為每個事務的一部分寫入到 Spanner。F1 會得到某個時間戳下的數據的完整快照，來初始化它的數據結構，然后根據數據的增量變化來更新這個數據結構。

表 5 顯示了 F1 中每個目錄的分片數量的分布情況。每個目錄通常對應于 F1 上的應用棧中的一個用戶。絕大多數目錄（同時意味著絕大多數用戶）都只會包含一個分片，這就意味著，對于這些用戶數據的讀和寫操作只會發生在一個服務器上。多于 100 個分片的目錄，是那些包含 F1 二級索引的表：對這些表的多個分片進行寫操作，是極其不尋常的。F1 團隊也只是在以事務的方式進行未經優化的批量數據加載時，才會碰到這種情形。

表 6 顯示了從 F1 服務器來測量的 Spanner 操作的延遲。在東海岸數據中心的副本，在選擇 Paxos?Leader 方面會獲得更高的優先級。表 6 中的數據是從這些數據中心的 F1 服務器上測量得到的。寫操作延遲分布上存在較大的標準差，是由于鎖沖突引起的拖尾效應（fat?tail）。在讀操作延遲分布上存在更大的標準差，部分是因為 Paxos?Leader 跨越了兩個數據中心，只有其中的一個是采用了固態盤的機器。此外，測試內容還包括系統中的每個針對兩個數據中心的讀操作：字節讀操作的平均值和標準差分別是 1.6KB 和 119KB。

6. 相關工作

Megastore[5]和 DynamoDB[3]已經提供了跨越多個數據中心的一致性復制。DynamoDB?提供了鍵值存儲接口，只能在一個域內部進行復制。Spanner 和 Megastore 一樣，都提供了半關系數據模型，甚至采用了類似的模式語言。Megastore 無法達到高性能。Megastore 是架構在 Bigtable 之上，這帶來了很高的通訊代價。Megastore 也不支持長時間的?Leader ，多個副本可能會發起寫操作。來自不同副本的寫操作，在 Paxos 協議下一定會發生沖突，即使他們不會發生邏輯沖突：會嚴重影響吞吐量，在一個 Paxos 組內每秒鐘只能執行幾個寫操作。Spanner 提供了更高的性能，通用的事務和外部一致性。

Pavlo 等人[31]對數據庫和 MapReduce[12]的性能進行了比較。他們指出了幾個努力的方向，可以在分布式鍵值存儲之上充分利用數據庫的功能[1][4][7][41]，二者可以實現充分的融合。我們比較贊同這個結論，并且認為集成多個層是具有優勢的：把復制和并發控制集成起來，可以減少 Spanner 中的提交等待代價。

在一個采用了復制的存儲上面實現事務，可以至少追述到 Gifford 的論文[16]。Scatter[17]是一個最近的基于 DHT 的鍵值存儲，可以在一致性復制上面實現事務。Spanner 則要比 Scatter 在更高的層次上提供接口。Gray 和 Lamport[18]描述了一個基于 Paxos 的非阻塞的提交協議，他們的協議會比兩階段提交協議帶來更多的代價，而兩階段提交協議在大范圍分布式的組中的代價會進一步惡化。Walter[36]提供了一個快照隔離的變型，但是無法跨越數據中心。相反，我們的只讀事務提供了一個更加自然的語義，因為，我們對于所有的操作都支持外部語義。

最近，在減少或者消除鎖開銷方面已經有大量的研究工作。Calvin[40]消除了并發控制：它會重新分配時間戳，然后以時間戳的順序執行事務。HStore[39]和 Granola[11]都支持自己的事務類型劃分方法，有些事務類型可以避免鎖機制。但是，這些系統都無法提供外部一致性。Spanner 通過提供快照隔離，解決了沖突問題。

VoltDB[42]是一個分片的內存數據庫，可以支持在大范圍區域內進行主從復制，支持災難恢復，但是沒有提供通用的復制配置方法。它是一個被稱為 NewSQL 的實例，這是實現可擴展的 SQL[38]的強大的市場推動力。許多商業化的數據庫都可以支持歷史數據讀取，比如 Marklogic[26]和 Oracle’ Total Recall[30]。Lomet 和 Li[24]對于這種時間數據庫描述了一種實現策略。

Faresite 給出了與一個受信任的時鐘參考值相關的時鐘不確定性的邊界[13]（要比 TrueTime 更加寬松）：Farsite 中的服務器租約的方式，和 Spanner 中維護 Paxos 租約的方式相同。在之前的工作中[2][23]，寬松同步時鐘已經被用來進行并發控制。我們已經展示了 TrueTime 可以從 Paxos 狀態機集合中推導出全球時間。

7. 未來的工作

在過去一年的大部分時間里，我們都是 F1 團隊一起工作，把谷歌的廣告后臺從 MySQL 遷移到 Spanner。我們正在積極改進它的監控和支撐工具，同時在優化性能。此外，我們已經開展了大量工作來改進備份恢復系統的功能和性能。我們當前正在實現 Spanner 模式語言，自動維護二級索引和自動基于負載的分區。在未來，我們會調研更多的特性。以最優化的方式并行執行讀操作，是我們追求的有價值的策略，但是，初級階段的實驗表明，實現這個目標比較艱難。此外，我們計劃最終可以支持直接變更 Paxos 配置[22][34]。

我們希望許多應用都可以跨越數據中心進行復制，并且這些數據中心彼此靠近。TrueTime ε 可能會明顯影響性能。把 ε 值降低到 1ms 以內，并不存在不可克服的障礙。Time-master-query 間隔可以繼續減少，Time-master-query 延遲應該隨著網絡的改進而減少，或者通過采用分時技術來避免延遲。

最后，還有許多有待改進的方面。盡管 Spanner 在節點數量上是可擴展的，但是與節點相關的數據結構在復雜的 SQL 查詢上的性能相對較差，因為，它們是被設計成服務于簡單的鍵值訪問的。來自數據庫文獻的算法和數據結構，可以極大改進單個節點的性能。另外，根據客戶端負載的變化，在數據中心之間自動轉移數據，已經成為我們的一個目標，但是，為了有效實現這個目標，我們必須具備在數據中心之間自動、協調地轉移客戶端應用進程的能力。轉移進程會帶來更加困難的問題——如何在數據中心之間管理和分配資源。

8. 總結

總的來說，Spanner 對來自兩個研究群體的概念進行了結合和擴充：一個是數據庫研究群體，包括熟悉易用的半關系接口，事務和基于 SQL 的查詢語言；另一個是系統研究群體，包括可擴展性，自動分區，容錯，一致性復制，外部一致性和大范圍分布。自從 Spanner 概念成形，我們花費了 5 年以上的時間來完成當前版本的設計和實現。花費這么長的時間，一部分原因在于我們慢慢意識到，Spanner 不應該僅僅解決全球復制的命名空間問題，而且也應該關注 Bigtable 中所丟失的數據庫特性。

我們的設計中一個亮點特性就是 TrueTime。我們已經表明，在時間 API 中明確給出時鐘不確定性，可以以更加強壯的時間語義來構建分布式系統。此外，因為底層的系統在時鐘不確定性上采用更加嚴格的邊界，實現更強壯的時間語義的代價就會減少。作為一個研究群體，我們在設計分布式算法時，不再依賴于弱同步的時鐘和較弱的時間 API。

參考文獻

可以根據翻譯中的參考文獻標號進行查閱，這里就不一一列舉了。論文原文題目在開頭，很容易就能下載到原文。

總結

以上是生活随笔為你收集整理的Google Spanner：谷歌的全球分布式数据库的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇： BlueStore——先进的用户态文件系
下一篇：操作系统：程序的编译、链接、装入及地址转