譯 Spanner: Google 的全球分佈式資料庫

分布式系統翻譯系列的最後一篇，原文 https://research.google.com/archive/spanner-osdi2012.pdf

現在 Google Cloud 支持 Cloud Spanner 可以從產品文檔上查看到其特性的一些細節。

翻譯的很差，很多句子保留了英文的語序導致中文讀起來很難理解，以後可能還是不要做全文翻譯了。

還是語言能力太糟糕，無論英文還是中文。😢

介紹#

Spanner 是 Google 設計，構建和部署的一個可擴展，全球分布的數據庫。從最高層次的抽象來看，它是一個數據庫，將數據分片到分布在全球各地數據中心的許多 Paxos 狀態機中。副本用於實現全球可用性和地理上的局部性，客戶端會在副本之間自動進行故障轉移。隨著數據量或者服務器數量的改變，Spanner 自動在機器之間重新分片。並且 Spanner 會自動在跨數據中心的機器之間遷移數據，以平衡負載和處理故障。Spanner 被設計成可以擴展到跨越數百個數據中心，數百萬台機器，萬億行的數據。應用可以使用 Spanner 實現高可用性，即便在發生跨地區自然災害的情況下，通過在同一個大陸內，甚至跨大陸複製。

我們的首個客戶是 F1: 重寫的 Google 廣告後端。F1 使用分布在跨越全美的五個副本。大多數其他應用可能會同一地理區域內的三到五個數據中心之間複製數據，有相對獨立的故障模式。也就是說，大多數應用可能會選擇低延遲而非高可用，只要在故障時能有一到兩個數據中心存活。Spanner 主要關注的點是管理跨數據中心的副本數據，但是我們也花費了大量的時間設計和實現在分布式系統基礎設施之上重要的數據庫特性。

儘管很多項目樂於使用 Bigtable 我們也一直收到用戶關於 Bigtable 很難在一些類型的應用上使用的抱怨：比如某些具有複雜且容易改變的 schemas 的應用，或者想要在多地區複製的情況下實現強一致性的應用。

Google 的許多應用選擇使用 Megastore 因為它的語義化關係模型和對同步複製操作的支持，儘管他的寫帶寬相對很低。作為一個共識 Spanner 從類似 Bigtable 的帶版本的 key-value 存儲發展成一個臨時多版本數據庫。數據存儲在有模式的半關係型的表上；數據有版本；且每個版本自動賦值成提交時的時間戳；舊數據遵循可配置的垃圾回收策略；應用可以讀取舊時間戳上的數據。Spanner 支持通用事務，並且提供了一個基於 SQL 的查詢語言。作為一個全球分布數據庫，Spanner 支持很多有趣的特性。首先，應用可以在很細的粒度上動態控制和配置數據副本，應用可以指定一些限制來控制：哪個數據中心上包含哪些數據，數據距離用戶的距離有多遠 (用來控制讀延遲)，每個副本間的距離有多遠 (控制寫延遲)，維護多少副本 (控制數據持久性，可用性和讀性能)。數據可以動態且透明的在數據中心之間移動，通過系統平衡跨數據中心的資源使用。其次 Spanner 有兩個難以在分布式數據庫中實現的特性：它提供外部一致的讀和寫，並且在同一個時間戳上支持跨數據庫的全球讀一致性。這些特性使得 Spanner 在全球規模的級別上支持一致性備份，一致性 MapReduce 執行，和原子性的 schema 更新，即使有正在運行的事務的情況下也能保證。

這些特性之所以能夠實現，基於一個事實：Spanner 可以給事務上賦值全球有意義的提交時間戳，即使事務可能是分布式的，此時間戳能夠反映事務的序列化順序。除此以外，序列化順序適應外部一致性 (或者說等效於線性一致性)。如果一個事務 $T_{1}$ 在另一個事務 $T_{2}$ 開始之前提交，那麼 $T_{1}$ 的提交時間戳比 $T_{2}$ 小。Spanner 是第一個在全球規模上提供這種保證的系統。

提供這種特性的關鍵支持是一個新的 TrueTime API 和它的實現。這個 API 直接反映了時鐘的不確定性 Spanner 的時間戳對序列化順序的保證依賴於 TrueTime 實現提供的範圍界限 (bound 譯注：時鐘是不確定的，所以 TrueTime 的實現提供的是一個範圍而非固定的時刻)。如果不確定性很大 Spanner 會放慢速度以消除不確定性。Google 的集群管理軟件提供了 TrueTime API 的實現。這個實現通過多種現代時鐘源 (GPS 和原子鐘) 保證了不確定性足夠小 (通常小於 10ms)。

實現#

這一節首先描述了 Spanner 的結構和實現的基本原理，然後描述了用於管理副本和局部性的目錄抽象，它也是數據移動的基本單元，最後描述了我們的數據模型，為什麼 Spanner 更像是關係型數據庫而非鍵值存儲，以及應用如何控制數據的局部性。

一個 Spanner 部署稱為一個 universe 鑒於 Spanner 能夠直接管理全球範圍內的數據，運行的 universe 數量會很少。我們目前運行了一個 test/playground universe 一個 development/production universe 和一個 production universe. Spanner 由一組 zones 組成，每個 zone 大致類似於一組 Bigtable 服務器的部署。zones 是管理部署的基本單元。zones 的集合也是數據可以被複製的位置的集合。

隨著新的數據中心投入使用和舊的數據中心關閉，可以動態的在系統中添加和移除 zone 同時 zones 也是物理隔離的單元：在一個數據中心內可能有多個 zones, 比如某些情況下同一個數據中心中不同應用的數據必須劃分到的不同服務器集合上。

組織架構

上圖表示一個 Spanner universe 的不同服務器。一個 zone 有一個 zonemaster 和幾百到上千個 spanserver 前者將數據分配到 spanservers 後者為客戶端提供數據服務。每個 zone 的 location proxies 用於客戶端尋址其數據分配到的 spanservers. universe master 和 placement driver 目前都是單例的。universe master 主要是一個控制台，用於交互式調試顯示所有的 zones 的狀態信息。placement driver 處理分鐘級別的跨 zone 的數據自動移動，placement driver 週期性的和 spanservers 通信，找到需要移動的數據，以滿足更新後的複製約束或者負載均衡。篇幅所限，這裡我們只詳細描述 spanserver.

Spanserver 軟件棧#

這一段聚焦於 spanserver 的實現來說明如何在基於 Bigtable 的實現上構建副本和分布式事務。軟件棧如圖：

軟件棧

在底層，每個 spanserver 負責 100 到 1000 個叫做 tablet 的數據結構的實例。這裡的 tablet 和 Bigtable 的 tablet 的抽象概念類似，它實現了以下映射關係的多重集合 (bag of mapping 多對一的映射)。

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

不像 Bigtable, Spanner 會直接給數據賦值時間戳，這是 Spanner 更像是數據庫而非 key-value 存儲的一個重要體現。每個 tablet 的狀態存儲在一組類似 B-tree 的文件和一個 write-ahead 日誌中 (WAL)，這些文件全都存放在一個叫做 Colossus 的分布式文件系統中 (GFS 的繼承者)。為了支持複製，每個 spanserver 在每個 tablet 之上實現了一個單獨的 Paxos 狀態機 (早期版本的 Spanner 支持每個 tablet 多 Paxos 狀態機，允許更靈活的複製配置，但是這個設計的複雜度讓我們放棄了)。每個狀態機存儲其元數據和負責的 tablet 的日誌。我們的 Paxos 實現支持基於時間租約機制的 long-lived Leader, 默認租約時間 10 秒。目前的 Spanner 實現對每個 Paxos 寫記錄兩次日誌：一次在 tablet 的日誌中，一次在 Paxos 的日誌中。這個選擇是出於便利考慮，並且最終可能會進行改善。我們實現的 Paxos 是流水線化的，以改善 Spanner 在 WAN 延遲情況下的吞吐量；但是寫操作是 Paxos 順序執行的。

Paxos 狀態機用於實現一致性複製的映射關係多重集合 (consistently replicated bag of mappings)。每個副本的鍵值映射狀態在對應的 tablet 中存儲。寫操作必須在 Leader 發起 Paxos 協議；讀操作直接訪問任何一個足夠新的副本的底層 tablet 的狀態。

一組副本的集合組成一個 Paxos 組，在每個 leader 副本上每個 spanserver 實現了一個 lock table 以實現並發控制。這個 lock table 包含了兩階段鎖的狀態：映射鍵的範圍到鎖狀態 $K_{0..n} \Rightarrow lock$ (有一個 long-lived Paxos leader 是高效管理 lock table 的關鍵)。在 Bigtable 和 Spanner 我們都設計了 long-lived 事務 (比如報表生成，耗時可能在分鐘級)，在產生衝突的場景下，樂觀並發控制訪問性能很差。需要同步的操作，比如事務讀操作需要先獲取到 lock table 的鎖，其他操作則可以跳過 lock table 鎖。

在每個副本 leader 上每個 spanserver 也實現了一個事務管理器以支持分布式事務。這個事務管理器用於實現參與領導者；同一組的其他副本會成為參與從節點。如果一個事務僅涉及一個 Paxos 組 (大多數事務)，可以不通過事務管理器，因為 lock table 和 Paxos 一起提供事務支持就足夠了。如果一個事務涉及超過一個 Paxos 組，這些組的 leader 會協調執行兩階段提交。執行事務時會從涉及到的所有組中選取一個組作為協調員 (coordinator)，這個被選定的組內的 leader 會被稱為協調領導者 (coordinator leader) 該組的從節點被稱為協調者從節點。每個事務管理器的狀態在底層 Paxos 組上存儲 (因此是被複製的)。

目錄和放置#

Spanner 的實現在鍵值映射多重集合之上支持一個稱為 directory 的 bucket 抽象，即一組有相同前綴的連續鍵 (選擇使用術語 directory 是一個歷史遺留問題，更好的叫法可能是 bucket) 支持 directories 使得應用可以通過小心的選擇鍵來控制他們的數據的局部性。一個 directory 是數據放置的單元，同一個 directory 下的所有數據有相同的副本配置。他們以 directory 為單位在 Paxos 組之間移動。如下圖：

directory 移動

Spanner 可能會從一個 Paxos 組中移出一個 directory 以降低負載；將經常一起訪問的 directories 放到相同的組；或者將一個 directory 移動到離它的訪問者更近的組。directory 可以在客戶端證正在進行操作時移動。一個 50MB 的 directory 可以在大約幾秒鐘內移動。

一個 Paxos 可能包含有多個 directories 這是 Spanner 的 tablet 和 Bigtable 的 tablet 不同之處：前者不一定是單個行空間按字典序連續的分區。相反，一個 Spanner tablet 是一個容器，可以封裝行空間的多個分區。我們做出這個決定，使得多個被經常一起訪問的分區共存成為可能。

Movedir 是一個後台任務用於在 Paxos 組之間移動 directories, Movedir 也用於在 Paxos 組中添加和移除副本，因為 Spanner 目前不支持基於 Paxos 的配置修改。Movedir 沒有作為單個事務實現，以避免阻塞大量數據移動期間的正在進行的讀寫操作。相反 movedir 只是記錄下它開始在後台移動數據，當它基本移動了全部數據，它使用一個事務自動移動剩下很少的數據然後更新兩個 Paxos 組的元數據。

一個 directory 同時也是應用可以指定地理複製屬性 (或放置策略) 的最小單元。我們的 placement-specification 語言將管理副本配置的責任分開。管理員控制兩個維度：副本的數量和類型，和這些副本放置的地址位置。在這兩個維度上創建了一個命名選項的菜單 (比如：北美，採用五副本加上一個見證副本)(譯注：見證副本一般用於參與 Leader 選舉投票，仲裁衝突，防止 brain split 等，參考 Cloud 文檔) 應用通過這些選項的組合給每個數據庫和 (或) 各個 directories 加上標籤，來控制數據如何被複製。比如，一個應用可能將每個終端用戶的數據存在他自己的目錄中，可以使得用戶 A 的數據在歐洲有三個副本，用戶 B 的數據在北美有五個副本。

為了簡化說明，我們做了過度的簡化。事實上如果 directory 過大 Spanner 會將其分片成多個 fragments 然後 fragments 可能在不同的 Paxos 組上 (因此也就是不同的服務器上) 提供服務。Movedir 實際上是在組之間移動 fragments 而非整個 directories.

數據模型#

Spanner 給應用暴露了以下一些數據特性：一個基於有模式的半關係型表的數據模型，查詢語言，和通用事務。朝著支持這些功能轉變是由多種因素驅動的。

支持有模式的半關係型表和同步複製的需求是 Megastore 的流行所推動的。Google 至少有 300 個應用使用 Megastore (儘管它的性能相對較低) 因為它的數據模型比 Bigtable 管理起來更簡單，並且支持跨數據中心的同步複製 (Bigtable 僅支持跨數據中心的最終一致性複製)。比較知名的使用 Megastore 的應用有 Gmail, Picasa, Calendar, Android Market, and AppEngine 等。鑒於 Dremel 作為一個交互式數據分析工具的流行度，在 Spanner 中支持類 SQL 查詢語言的需求也非常明了。

最後 Bigtable 中缺失的跨行事務也經常招致抱怨 (led to frequent complaints); 構建 Percolator 的部分原因就是解決這個問題。一些作者認為支持通用的兩階段提交太過昂貴，因為其帶來了性能或者可用性問題。我們認為最好讓應用程序員在濫用事務導致出現性能瓶頸時處理性能問題，而不是在缺失事務的情況下編程。通過 Paxos 運行兩階段提交減輕可用性問題。

應用的數據模型構建在以目錄為桶的鍵值映射之上。一個應用可以在一個 universe 上創建一個或多個數據庫。每個數據庫可以包含無限制數量的結構化表。表類似於關係型數據表，包含行，列和版本化的值。我們不會深入 Spanner 的查詢語言的細節。它看起來像是 SQL 並進行了一些擴展以支持 protocol-buffer 值字段。

Spanner 的數據模型不是純關係型的，因為每個行必須具有名稱。更準確的說，每個表需要有一個或多個有序的主鍵列的集合。這個要求使得 Spanner 看起來仍像是個鍵值存儲：主鍵組成行的名稱，每個表定義了一個主鍵列到非主鍵列的映射。一個行只有在為主鍵定義了值 (即使是 NULL) 時才存在。強制使用這種結構是有用的，因為這讓應用可以通過選擇鍵來控制數據的局部性。

spanner-figure4

上圖包含一個 Spanner 示例結構：在每個用戶，每個相冊的基礎上排序照片元數據。這種 schema 定義語言和 Megastore 類似，但是增加了額外的需求：每個 Spanner 數據庫必須被客戶端按照一個或多個層級結構對表進行分區。

客戶端應用在數據庫 schemas 中通過 INTERLEAVE IN 聲明層級結構。層級結構最上層的表是一個 directory 表。在 directory 表中以鍵 K 為起始的，按照字典序排列的之後的所有以 K 開頭的所有行，組成一個 directory.

ON DELETE CASCADE 表示刪除 directory 表的一個行時刪除所有相關子行。上圖也顯示了 example 數據庫的交錯佈局：比如 Albums (2,1) 表示 Albums 表中從 user_id == 2 && album_id == 1 開始的行。這種表交錯構成 directory 非常重要，因為這允許客戶端在描述多個表之間的局部性關係，對於在分片的分布式數據庫中取得良好的性能是必要的。沒有這個功能 Spanner 無法知道最重要的局部性關係。

TrueTime#

這一段描述 TrueTime API 和實現的大概 (sketches)。我們將大部分的細節留在了另外一篇論文，這一段的目標是為了證明有這樣一個 API 帶給我們的力量。

方法	返回
TT.now()	TTinterval: [earlist, latest]
TT.after(t)	true if t has definitely passed
TT.before(t)	true if t has definitely not arrived

上表列出了 API 的方法 TrueTime 明確的將時間表示為 $TTinterval$ 一個具有有界時間不確定性的時間間隔 (不像標準庫時間接口不過告訴客戶端不確定性的概念)。 $TTinterval$ 的節點的類型是 $TTstamp$ , $TT.now()$ 方法返回一個 $TTinterval$ 範圍，它保證包含調用 $TT.now()$ 時的絕對時間。time epoch 類似於有閏秒模糊處理的 UNIX 時間。定義瞬時誤差界限為 $\varepsilon$ 也就是時間區間寬度的一半，平均誤差為 $\bar{\varepsilon}$ 其中 $TT.after()$ 和 $TT.before()$ 方法是對 $TT.now()$ 的簡易封裝。

用函數 $t_{abs}(e)$ 表示事件 $e$ 發生的絕對時間。更正式的說 TrueTime 保證：對於任意一個調用 (invocation) $tt = TT.now(), tt.earliest \le t_{abs}(e_{now}) \le tt.latest$ 其中 $e_{now}$ 是調用 (invocation) 事件。

TrueTime 底層時間參考的是 GPS 和原子鐘。TrueTime 使用兩種形式的時間參考是因為他們有不同的故障模式。GPS 參考源的漏洞包括天線和接收器故障，本地無線電干擾，相關故障 (涉及缺陷，比如錯誤的閏秒處理和欺騙)，以及 GPS 系統中斷。原子鐘可能會以與 GPS 和其他原子鐘無關的方式產生故障，隨著時間的推移，由於頻率誤差會出現明顯的漂移。

TrueTime 是由每個數據中心的一組 time master 機器和每台機器上的 timeslave 進程實現的。大多數的 master 有配備有專用天線的 GPS 接收器；這些 master 在物理上隔離以減少天線故障，無線電干擾和欺騙的影響。剩下的 master (我們稱之為 Armageddon 世界末日 master) 裝備有原子鐘。一個原子鐘沒那麼貴：一個 Armageddon master 的成本和一個 GPS master 的成本相當。

所有 master 時間參考會定期相互比較，每個 master 也會將參考時間的推進速率與自己本地的時鐘進行交叉檢查，並且在有顯著的偏差時將自己退出。在兩次同步之間 Armageddon master 會宣告一種緩慢增加的時間誤差 (time uncertainty)，這個誤差根據時鐘漂移最壞的情況下保守估算出來的。GPS master 宣告的誤差一般接近於零。

每個守護進程會輪詢多個 master 以減少依賴任何一個 master 節點產生錯誤的脆弱性。一些是從數據中心附近選擇的 GPS master; 剩下的 GPS maste 來自較遠的數據中心；當然還有一些 Armageddon master. 守護進程使用一種 Marzullo 算法變種來檢測和拒絕虛假信息，並將本地機器時鐘和非虛假信息 (nonliars) 進行同步。為了防止本地時鐘故障，頻率偏移超過對應組件標準和操作環境下最壞情況誤差界限的機器會被剔除。

在兩次同步之間，守護進程宣告一個緩慢的增加的時間誤差。e 表示保守估計最壞情況下本地時鐘漂移 e 也依賴於 time-master 的誤差和與 time-master 的通信延遲。在我們的生產環境中 e 通常是一個關於時間的鋸齒函數。在每個輪詢間隔內會有 1ms 到 7ms 的變化，因此 e 大多數時間是 4ms 守護進程的輪詢間隔目前是 30s 當前使用的漂移率被設置為 200 microseconds/second 加起來共同導致了 0 到 6ms 的鋸齒變化範圍，剩下的 1ms 來自於到 time master 的通信延遲。在出現故障的情況下，這種鋸齒會出現偏移，比如偶現的 time-master 不可用會導致 e 在數據中心範圍上增加。類似的，機器和網絡連接過載也會導致偶爾局部的尖刺 (spike 突發峰值)。

並發控制#

這一段描述如何使用 TrueTime 在並發控制中保證正確性，以及如何使用這些性質來實現類似於外部一致性事務，只讀無鎖事務，歷史非阻塞讀之類的特性。這些特性能夠使得，比如：在時間戳 $t$ 時整個數據庫的審計讀取會讀取到在 $t$ 之前提交的所有事務產生的效果。

區分 Paxos 看到的寫入 (後續稱為 Paxos 寫) 和 Spanner 客戶端寫入很重要。比如兩階段提交在 prepare 階段產生了一個 Paxos 寫但是沒有對應的 Spanner 客戶端寫。

時間戳管理#

操作	並發控制	副本要求
讀寫事務	悲觀	leader
只讀事務	無鎖	leader for timestamp; any for read
快照讀，客戶端提供的時間戳	無鎖	any
快照讀，客戶端提供的界限	無鎖	any

上表列出了 Spanner 支持的操作類型。Spanner 的實現支持讀寫事務，只讀事務 (預聲明快照隔離事務)，和快照讀。獨立寫作為讀寫事務實現；非快照獨立讀作為只讀事務實現，兩者都有內部重試 (不需要客戶端顯式循環重試)。

只讀事務是一種有快照隔離性能優勢的事務。一個只讀事務必須提前聲明不包含任何寫入，它不僅僅是一個沒有任何寫操作的讀寫事務。在只讀事務中，讀操作在系統選擇的時間戳上無鎖執行，所以不會阻塞後續的寫操作。只讀事務中的讀操作可以在任何足夠新的副本上執行。

快照讀是對過去的讀取，執行時也不加鎖。一個客戶端可以指定快照讀的時間戳，或者提供一個期望時間戳的過期上限 (bound on the desired timestamp’s staleness) 然後讓 Spanner 選擇一個時間戳。在任何一種情況下，快照讀都會在足夠新的副本上執行。

對於只讀事務和快照讀，一旦選擇了一個時間戳，提交時不可避免的，除非這個時間戳的數據已經被垃圾回收了。最終，客戶端可以避免在重試循環緩衝結果。當一個服務故障，客戶端內部會向另外一個服務器提供時間戳和當前讀取位置繼續查詢。

Paxos Leader 租約#

Spanner 的 Paxos 實現使用了基於時間的租約來保證 long-live-leader (默認 10s)。一個潛在的 leader 發送基於時間的租約投票請求；收到足夠 quorum 的票數後他可以認為自己獲得了租約。一個副本在成功寫入後顯式的延長租約投票，並且 leader 會在租約臨近過期時會請求租約續期投票。

定義一個 leader 的租約間隔：從他發現自己收到足夠 quorum 的租約投票開始，到他不再有足夠 quorum 的租約投票時結束 (因為某些投票過期了)。

Spanner 依賴以下不相交性不變量 (disjointness invariant)：對於每個 Paxos 組，每個 Paxos 的 leader 和其他每個 leader 的租約間隔不重疊 (附錄 A 描述了如何維持這種不變量)。

Spanner 的實現允許一個 Paxos leader 通過釋放他的租約投票的 slave 來放棄 leader 地位。為了保持不相交性不變量 Spanner 限制何時允許棄權。定義 $s_{max}$ 為 leader 使用的最大時間戳，後續的段落會描述何時 $s_{max} {\huge }$ 會被提前，在棄權之前，leader 必須保證 $TT.after(s_{max})$ 為 true.

為 RW 事務分配時間戳#

事務讀和寫使用兩階段鎖，最終，他們可以在 [獲得所有鎖後，釋放任何鎖之前] 的任何時間被賦值時間戳。對於一個給定的事務 Spanner 將其時間戳賦值成 Paxos 賦值給表示事務提交的 Paxos 寫入的時間戳。

Spanner 依賴以下單調不變性：在每個 Paxos 組中 Spanner 以單調遞增的順序給 Paxos 寫賦值時間戳，即使是跨 leader (譯注：leader 變成其他節點了)。一個單獨的 leader 副本可以很容易的按照單調遞增的順序賦值時間戳。通過利用不相交不變性，可以在各個 leader 之間維持這種不變性：一個 leader 僅能在其 leader 租約間隔內賦值時間戳。

注意無論合適賦值了一個時間戳 $s$ 則 $s_{max}$ 一定比 $s$ 大以維持不相交。Spanner 也強制如下的外部一致性不變量：如果事務 $T2$ 的開始發生在事務 $T1$ 的提交之後，則 $T2$ 的提交時間一定比 $T1$ 的提交時間大。

定義對於事務 $T_{i}$ 的開始和提交時間為 $e_{i}^{start}$ 和 $e_{i}^{commit}$ 提交時間戳為 $s_{i}$ , 則不變性變成了：

$t_{abs}(e_{1}^{commit}) < t_{abs}(e_{2}^{start}) \Rightarrow s_{1} < s_{2}$

執行事務和分配時間戳的協議遵守兩條規則，共同保證了不可變性，如下所示。定義寫事務 $T_{i}$ 提交請求到達協調 leader 的事件為 $e_{i}^{server}$

Start: 協調 leader 給寫事務 $T_{i}$ 分配一個時間戳 $s_{i}$ 這裡 $s_{i}$ 不小於在 $e_{i}^{server}$ 計算過后的 $TT.now().latest$ 注意參與者 leader 在這裡不重要，後續會描述它們如何參與第二條規則的實現
Commit Wait: 協調 leader 確保在 $TT.after(s_{i})$ 為 true 之前客戶端不可能看到任何 $T_{i}$ 提交的數據。提交等待確保 $s_{i}$ 小於 $T_{i}$ 提交的絕對時間，即 $s_{i} < t_{abs}(e_{i}^{commit})$ 提交等待的實現在後續會介紹，證明：

Proof

在時間戳上提供讀取#

前面描述過的單調不變性允許 Spanner 正確的決定一個副本的狀態是否足夠新來滿足一個讀請求。每個副本跟踪一個叫做安全時間 $t_{safe}$ 的值，即此副本更新到的最大時間戳。如果請求時間戳 $t \le t_{safe}$ 則副本可以滿足一個讀請求。

定義 $t_{safe} = min(t_{Paxos}^{safe}, t_{TM}^{safe})$ 其中每個 Paxos 狀態機有一個安全時間 $t_{Paxos}^{safe}$ 每個事務管理器有一個安全時間 $t_{TM}^{safe}$ 其中 $t_{Paxos}^{safe}$ 很簡單：它是已經 apply 過的 Paxos 寫操作的最大時間戳。由於時間戳單調遞增且寫操作順序 apply, 就 Paxos 而言，在 $t_{Paxos}^{safe}$ 或者之後的時間上上不存在寫操作。其 $t_{TM}^{safe}$ 使用的是其副本的 leader 的事務管理器的狀態，這個狀態通過 Paxos 寫入過程中的元數據。

如果副本上沒有 "準備好但是還沒有提交 prepared but not commited" 的事務：即處於兩階段提交的的兩個步驟中間的事務，則副本上的 $t_{TM}^{safe}$ 為 $\infty$ (對於一個參與者 slave 服務器來說 $t_{TM}^{safe}$ 實際上使用的是其副本 leader 的事務管理器的狀態，這個狀態可以通過 Paxos 寫操作傳遞的元數據來推斷)。如果存在這樣的事務，這些事務對狀態的影響是不確定的：參與者副本還不知道這個事務是否會提交。如之前所描述過的，提交協議確保每個參與者知道一個 prepared 事務的時間戳下限。對於一個組 g 每個參與者 leader 給事務的 prepare 記錄分配一個 prepare 時間戳 $s_{i,g}^{prepare}$ 協調 leader 確保在組 g 內的所有參與者上，事務的提交時間 $s_{i} \ge s_{i,g}^{prepare}$ 因此 g 中的任何副本，對於在 g 上 prepare 的所有事務 $T_{i}$ 有 $t_{TM}^{safe} = min_{i}(s_{i,g}^{prepare}) - 1$

為 RO 事務分配時間戳#

一個只讀事務的執行分為兩個階段：分配一個時間戳 $s_{read}$ 然後在 $s_{read}$ 將事務讀作快照讀執行。快照讀可以在任何足夠新的副本上執行。s_read 可以在事務開始後的任何時間賦值為 $s_{read} = TT.now().latest$ 通過類似之前討論寫的情況一樣提供外部一致性。然而，如果 $t_{safe}$ 還沒有足夠新 (advanced sufficiently)(譯注：即比 $s_{read}$ 小) 則數據讀取操作需要阻塞在 $s_{read}$ (此外，選擇一個自定義的 $s_{read}$ 值可能會提升 $s_{max}$ 以保持不相交性 disjointness)。為了減少阻塞的機會，Spanner 應該分配最老的時間戳來保護外部一致性。4.2.2 解釋了如何選擇這樣一個時間戳。

詳細信息#

這一段解釋了之前忽略的讀寫事務和只讀事務的一些實踐細節，和一種用於實現原子性 schema 變更的特殊事務的實現。然後描述了一些之前描述的基本方案的改進。

讀寫事務#

和 Bigtable 相似，事務中的寫操作會在客戶端中緩存直到提交。最終，事務中的讀操作不會看到事務中寫操作的效果。這種設計在 Spanner 中工作的不錯，因為一個讀操作返回任何讀取到的數據的時間戳，而未提交寫還沒有被分配時間戳。

讀寫事務中的讀操作使用 woundwait 來避免死鎖。客戶端向對應 group 的副本 leader 發起讀操作請求，申請一個讀鎖然後讀取最近的數據。如果一個客戶端事務保持打開，它會發送一個 keepalive 消息以避免參與者 leader 將其事務超時。當一個客戶端完成了所有的讀操作，緩存了所有寫操作，就開始兩階段提交。客戶端選擇一個協調組並且向每個參與者 leader 發送 commit 消息：包括協調者標識和所有的寫操作。使用客戶端驅動兩階段提可以交避免跨區域傳輸數據兩次。

一個非協調員參與者 (non-coordinator-participant) leader 首先申請一個寫鎖，然後選擇一個必須大於它給之事務分配的所有時間戳的 prepare 時間戳 (保證單調性)，然後通過 Paxos 添加一條 prepare 記錄日誌。每個參與者將其 prepare 時間戳通知給協調員。

協調員 leader 首先也要申請一個寫鎖，但是跳過 prepare 階段。在收到所有其他參與 leader 的消息後，它給整個事務選擇一個時間戳。提交時間戳 $s$ 必須大於等於所有的 prepare 時間戳 (滿足一致性)，大於協調者在收到其 commit 消息時的 $TT.now().latest$ , 大於 leader 已經給之前事務分配過的所有時間戳 (再一次，保證單調性)。然後協調 leader 通過 Paxos 記錄提交日誌 (或者中斷，如果在等待其他參與者時超時)。

在允許任何協調者副本應用提交記錄之前，協調 leader 等到 $TT.after(s)$ 為 true 來遵守 4.1.2 中描述的 commit-wait 規則。由於協調 leader 根據 $TT.now().latest$ 來選擇提交時間戳 s 並且現在等待直到這個時間戳在過去 (譯注：要等到當前的絕對時間一定大於 s)，所以預期的等待時間是 $2 * \bar{\varepsilon}$ (譯注: Section 3 提到的平均誤差時間)。這個等待時間通常和與 Paxos 的通信時間重疊。在提交等待之後，協調者將提交時間戳發送到客戶端和所有其他參與 leader, 每個參與 leader 通過 Paxos 記錄事務的結果。所有參與者應用相同的時間戳，然後釋放鎖。

只讀事務#

賦值一個時間戳需要在讀操作涉及到的所有的 Paxos 組之間有一個溝通階段 (negotiation phase) 最終，Spanner 需要每個只讀事務都有一個 scope 表達式，這個表達式概括了整個事務要讀取的鍵的集合。Spanner 會為單個請求自動推導這個 scope. 如果 scope 的值可以通過單個 Paxos 組提供，則客戶端可以向這個組的 leader 發起只讀事務請求 (目前的 Spanner 實現只在 Paxos leader 上給只讀事務選擇一個時間戳)。這個 leader 分配 $s_{read}$ 時間戳，然後執行讀操作。對於單點讀取，Spanner 有一個比直接調用 $TT.now().latest$ 更好的分配時間戳的方法。定義 $LastTS()$ 為 Paxos 組上最後一次寫提交的時間戳。如果沒有 prepare 事務，則直接賦值 $s_{read} = LastTS()$ 輕鬆滿足外部一致性：事務將會看到最後一次寫入的結果，並且因此排在它之後。

如果 scope 的值需要多個 Paxos 組提供，會有多種選擇。最複雜的選擇是跟所有的組 leader 進行一輪通信並基於 $LastTS()$ 協商選擇 $s_{read}$ . Spanner 目前實現了一種簡單的方式，避免客戶端進行一整輪溝通，僅僅是將其讀取執行時間設置為 $s_{read} = TT.now().latest$ (可能需要等到安全時間趕上，譯注：是說這個時間可能會超過安全時間)。事務中的所有讀取都可以被發送到足夠新的副本。

Schema-Change 事務#

TrueTime 使得 Spanner 支持原子性 schema 修改。使用一個標準的事務是不可行的，因為參與者的數量 (數據庫中的組數量) 的數據可能有數百萬。Bigtable 支持在一個數據中心中的原子性 schema 修改，但是它的 schema 修改會阻塞所有操作。而 Spanner 的 schema-change 事務通常是一個非阻塞標準事務的變體 (variant)。

首先，它顯式分配一個未來的時間戳，註冊在 prepare 階段，最終跨越數千台服務器的 schema 修改可以在對其他並行活動產生非常小的中斷的情況下完成。其次，讀寫操作，顯式依賴 schema.

其次，任何隱式依賴模式的讀寫操作，在時間 $t$ 時與任何註冊過的 schema-change 同步：如果它們的時間戳在 $t$ 之前，可能會執行，否則它們必須阻塞到 schemachange 事務之後 (譯注：因為此事務時間比 $t$ 大，所以一定要等 schemachange 事務先執行完保證提交等待)。沒有 TrueTime (這樣一個穩定且全局一致的時間 API) 定義 schemachange 在時間 $t$ 發生沒有意義。

改進#

上面我們定義的 $t_{safe}^{TM}$ 有一個弱點，即一個 prepared 事務可以阻止了 $t_{safe}$ 前進。最終，在後續的時間戳中不能執行任何讀操作，即使讀操作跟事務沒有任何衝突。這種錯誤的衝突可以通過增加一個細粒度的，從鍵範圍到 prepare 事務時間戳的映射來移除。這個信息可以存儲在 lock 表中，這個表已經將鍵範圍映射到 lock 元數據。當一個讀操作到達，它只需要檢查其衝突的鍵範圍對應的細粒度安全時間。

之前定義的 $LastTS()$ 有一個類似的弱點：如果一個事務剛剛提交，一個沒有衝突的只讀事務必須將 $s_{read}$ 賦值成這個事務的時間戳。最終，讀操作可能會被延遲 (譯注：這個事務剛提交，可能還沒有在所有參與者上同步，在某個副本上讀的時候可能需要等待)。這個弱點同樣可以通過類似的在 lock 表中給 $LastTS()$ 添加一個細粒度的從鍵範圍到提交時間戳的映射來補救 (我們目前還沒有實現這個優化)。當一個只讀事務到達，它的時間戳可以被賦值為具有鍵範圍衝突的 $LastTS()$ 的最大值，除非當前有一個衝突的 prepare 事務 (可以通過細粒度的安全時間來確定)。

之前定義的 $t_{safe}^{Paxos}$ 有一個弱點是在沒有 Paxos 寫操作時無法增加 (譯注: $t_{safe}^{Paxos}$ 用的是最後的寫操作時間戳)。即一個在 $t$ 的快照讀不能在最後的寫操作在 $t$ 之前的 Paxos 組上執行。Spanner 利用 leader-lease 間隔的不相交性來解決這個問題。每個 Paxos leader 通過維護一個閾值，並且使未來的寫操作時間戳一定高於這個閾值來推進 $t_{safe}^{Paxos}$ 增長：它維護一個從 Paxos 序列號 n 到可能分配給未來的 Paxos 序列號 n+1 的最小時間戳的映射 $MinNextTS(n)$ 副本在已經應用了第 n 序列號後可以將自己的 $t_{safe}^{Paxos}$ 推進到 $MinNextTS(n)−1$

單個 leader 可以輕鬆的執行 $MinNextTS()$ 承諾，因為 $MinNextTS()$ 承諾的時間戳在 leader 的租約內，不相交不變性 (譯注：每個 leader 的租約時間不會重疊) 使得可以在 leader 之間執行 $MinNextTS()$ 承諾。如果一個 leader 想要將 $MinNextTS()$ 推進到超出其 leader-lease 必須將其租約續期。注意 $s_{max}$ 總是超過 $MinNextTS()$ 中的最大值以保證不相交性。

leader 默認每 8s 推進一次 $MinNextTS()$ 值，因此在缺失 prepared 事務的情況下，一個空閒的 Paxos 組中的健康的 slave 在最糟糕的情況下，可以為大於最舊時間戳 8s 的時間戳提供讀服務。leader 也可以根據 slave 的需求提升 $MinNextTS()$ 值的時間。

評估#

省略...

未來工作#

去年我們花費了大部分的時間和 F1 組一起將 Google 的廣告後端從 MySQL 遷移到 Spanner. 我們正在積極改善監控和支持工具，也優化了它的性能。此外，我們也改善備份和恢復系統的功能和性能。我們目前正在實現 Spanner schema language, 自動化輔佐索引的維護，和基於負載的自動化重新分片。長遠來看，我們計劃研究很多新特性。樂觀並行讀取可能是一個比較有價值的策略，但是初步的實驗表明正確的實現可能並不簡單。此外，我們計劃最終支持直接修改 Paxos 配置的。

考慮到我們預期許多應用會在非常相近的數據中心複製他們的數據，TrueTime $\varepsilon$ 可能會顯著的影響性能。我們沒有看到將 $\varepsilon$ 降低到 1ms 有什麼不可逾越的障礙。Time-master-query (譯注：向 time-master 請求校準時間) 間隔可以減少，更好的石英鐘也相對便宜。Time-master-query 延遲可以通過改善網絡拓撲來改善，甚至可能通過替代的 time-distribution 技術來避免。

最終，有很多明顯的地方可以改善。儘管 Spanner 可以在節點數量上進行擴展，但是 node-local 數據結構對複雜 SQL 查詢的性能相對較差，因為他們是為簡單的 key-value 訪問而設計的。來自數據庫文獻的算法和數據結構可以極大的改善單節點的性能。其次，根據客戶端負載在數據中心之間自動移動數據一直是我們的一個目標，但是為了高效實現這個目標，我們仍然需要自動化，協調式的在數據中心之間遷移客戶端應用進程的能力。遷移進程帶來了在數據中心之間管理資源申請和分配這個更加嚴峻的問題。

結論#

總之 Spanner 結合並擴展來自兩個社區的研究：從數據庫社區獲得了熟悉的，易用的半關係型接口，事務和基於 SQL 的查詢語言；從系統社區獲取了可擴展性，自動分片，錯誤容忍，一致性複製，外部一致性和廣域分布。

從 Spanner 啟動開始，我們花費了超過 5 年的時間迭代到當前的設計和實現。如此長迭代的部分原因是我們逐漸意識到 Spanner 不應該只是解決全局複製命名空間的問題，也應該專注於 Bigtable 缺失的數據庫特性。

我們設計的表明：實現 Spanner 各種 feature 的關鍵因素是 TrueTime. 我們已經展示了，在時間 API 中具象化時鐘不確定性，會使得構建的分布式系統有更健壯的時間語義。此外，隨著底層系統對時鐘不確定性執行更強的約束，實現較強語義的開銷也會減小。作為一個社區，在設計分布式算法時，我們不應該再依賴鬆散同步的時鐘和弱時間 API.

且听风吟