分布式系統中的時間和順序——關於Spanner中的Linearizability

引言

隨著信息科技的在人類生活中的不斷滲透，數據規模和計算規模也與日俱增，某些問題已經無法在單機系統上進行處理，只能尋求分布式系統的解決方案。

分布式系統用多個設備來處理特定問題，但是如何保證這樣的處理結果像單機系統那樣正確？這裡的正確指的是：以相同的順序進行相同的一系列操作，分布式系統能得到和單機系統相同的結果。

概要

本文主要介紹了分布式系統中 Linearizability 概念，以及它與 Serializability 的區別，並介紹了 Spanner 中是如何通過 TrueTime 來實現 Linearizability。

Linearizability 的概念

如果一系列的操作並發交叉進行，最終形成的 history（可以理解為運行記錄）與順序執行這些操作形成的 sequential history 相同，而且這些操作的先後順序仍然得到保留，那麼這個 history 我們就稱之為是 Linearizability 的 [1]。

我們假設現在有一個寄存器，具有 W 和 R 兩個操作，比如 W(0)A 表示進程 A 往寄存器寫入 0 這個值，R(0)B 表示進程 B 從寄存器讀到 0 這個值。

現實中，操作從開始到結束是具有時延的，我們用 start[W(0)] 表示發起操作，end[W(0)] 表示請求結束。

假設現在有如下圖所示的場景一：

該場景共有三個操作:

1. A 進程執行 W(1)；

2. 操作 1 進行的過程中, B 讀取到 0 這個值, 用 R(0) 表示；

3. 操作 1 和操作 2 都結束後, B 進程再次讀取, 得到了 1 這個值, 用 R(1) 表示。

注意這三個操作中隱含的先後順序：操作 1 先於操作 3，操作 2 先於操作 3。

這個並發執行的場景對應的 history 如下:

start[W(1)]A

start[R(0)]B

end[W(1)]A

end[R(0)]B

start[R(1)]B

end[R(1)]B

這個 history 可以找到一個等價的 sequential history:

start[R(0)]B

end[R(0)]B

start[W(1)]A

end[W(1)]A

start[R(1)]B

end[R(1)]B

而且這個 sequential history 中仍然保持了操作 1 與操作 3，操作 2 與操作 3 的先後順序。因此場景一可以認為是 Linearizability 的。

再看如下的場景二，該場景並不滿足 linearizable 的限制:

在這個場景中，當 B 執行 W(1) 的同時，A 已經讀取到了 1 這個值，之後 C 執行 W(0)，再之後 B 讀取這個值，竟然還讀取到 1 這個值。

分布式系統中，如果可以按照操作發生的先後順序，構造一個 Linearizability 的運行記錄，那麼這個特性就稱之為的 Linearizability。

舉例來說，假設現在有一個全球部署的分布式存儲系統，先後發生以下 4 個操作：

a. x = 1, 在中國發生

b. read x, 在美國發生

c. x = 2, 在日本發生

d. read x, 在美國發生

按照直覺來想, 操作 b 讀取到的 x 值肯定是 1, 操作 d 讀取到的 x 值肯定是 2。但這一切都是建立在系統能夠感知這些操作的先後順序之上, 比如在操作 b 中, 坐落於美國的 server 可以意識到操作 a 已經先發生。

但是在現實的分布式場景中, 我們的系統並不能像上帝一樣, 可以清楚的知道世界各角落中, 每個操作的先後順序, 除非我們為每一個操作都標記上統一的單調遞增的 id, 這個 id 的功能一般由 timestamp 來充當。

但是對於 Spanner[2] 這樣全球部署或者跨地域部署的系統, 如何來為事務分配 timestamp, 才能保證系統的響應時間在可接受的範圍內? 如果整個系統採用一個中心節點來分配 timestamp, 那麼系統的響應時間就變得非常不可控, 對於離中心節點隔了半圈地球的用戶來說, 響應時間估計會是 100ms 級別。

所以, 本文會著重介紹 Spanner 分配 timestamp 的原理, 也即是 TrueTime API。

Linearizability 與 Serializability

需要注意的是 Linearizability 其實是無關於並發控制的, 它只是關於操作順序的一種限制。與 Linearizability 很容易混淆的一個術語是 Serializability, 這個特性才是關於並發控制的一個限制。

如果一個系統可以將並發的事務按照某種調度，達到的效果和某種串列執行的效果一樣（也就是各事務的操作不會相互交錯），那麼這個特性就叫 Serializability。

Serializability 著重於保證編程模型中的一些約束, 這些約束大部分是人為規定的. MySQL 的默認 RR 隔離級別是沒有保證 Serializability, 因為 RR 並不能防止 Lost Update 和 Write Skew 的發生, 這兩種情況都會破壞一些約束, 具體請參考 Weak Isolation in Relational Databases[4]。

對於單機資料庫系統，單機資料庫系統維持一個統一的、遞增的事務 id 是輕而易舉的事情, 所以可以認為它們天生就是具有 Linearizability 特性。另外有些資料庫系統, 比如 MySQL 所支持的 Serializable 隔離級別便是本文所說的 Serializability 的特性。

所以, 我們可以看到所謂的 Serializability 便是 ACID 中的 I, 至於 Linearizability, 是針對於分布式系統而言的一個難點。

Linearizability 的意義

現在的資料庫系統, 都具有 Snapshot read 的概念, 所謂 Snapshot read 指的是對於系統的讀操作, 只是過去某一時刻的一個快照, 也就是對應於該事務 id 所能看到的一份歷史數據, 在 Spanner 的場景來說, 也就一個指定的 timestamp 所能看到的一份歷史數據。

如果一個分布式系統能夠對"歷史"有所感知的話, 也就意味著能夠感知操作的前後順序, 也就是說這個系統支持 Linearizability。

如果一個分布式系統無法支持 Linearizability, 那麼對於指定一個 timestamp 所能看到的歷史數據, 每次可能是不一樣。

舉例來說, 假設現在有一個全球部署的分布式存儲系統, 先後發生以下3個操作:

a. x = 1, 分配的 timestamp 為 s1

b. 指定 timestamp s2 執行 read x

c. x = 2, 分配的 timestamp 為 s3

d. 指定同一個 timestamp s2 執行 read x

假設 s2 > tabs(a)，意思是 s2 是在操作 a 之後一個 timestamp，按照直覺來想, 肯定滿足 s2 > s1 的關係式, 但是對於不支持 Linearizability 的系統來說, 可能存在 s2 < s1, 導致操作 b 這個 Snapshot read 無法看到 a 操作的結果。

類似, 還假設 s2 < tabs(c), 但是可能存在 s2 > s3, 導致操作 d 這個 Snapshot read 看到了 c 操作的結果。

注意, 操作 b 和 d 的都指定同一個 timestamp = s2 進行 Snapshot read，但是 b 和 d 看到的歷史數據卻是不一樣的, 也就是說, 對於同一個 timestamp 對應的快照竟然不一樣。

到這裡可以看出來, 不支持 Linearizability 的分布式系統, Snapshot read 便無從談起, Snapshot Isolation 也就是不可能的事情。

有些系統實現了"部分順序", 也就是在單個節點（或者說單個分區）內的 Linearizability, 也就是能做到單機 Snapshot, 但是沒有全局的 Snapshot。

實現 Linearizability 的難點

從上述描述中, 可以看到, 實現 Linearizability 首先需要對系統中每個事務分配一個統一的、單調遞增的 id, 一般來說是 timestamp。那麼, 在分布式系統中, 如何協調這個 timestamp 呢?

對於這個問題, 我們可能會很迅速的想到一個方案：引入一個專門生成 timestamp 的中心節點, 每次事務提交時, 訪問該中心節點來獲得 timestamp。TiDB 使用的便是這種方案, 它利用 TimeStamp Oracle 模塊來提供授時服務。

但是這種方案引入了中心節點, 也意味著整套系統的部署不可能在地理位置上過於分散, 否則事務延時將會令人難以忍受。

需要指出的是，邏輯時鐘（比如 Lamport 時鐘和 Vector 時鐘）無法實現 Linearizability, 因為它只能區分有"因果關係（也就是有通信）"的事件間的順序。所以, 類似於" 事務 T2 在事務 T1 提交後才開始提交"這樣的場景, 當節點間沒有發生通信時，邏輯時鐘無法區分這兩個事務的順序。

本文著重講解 Spanner 是如何在這種全球部署的分布式系統中, 保證 Linearizability 的。在全球分布式系統中，真實世界裡兩個事務, 先後在不同的地方 commit, 系統怎樣去如實反映事務的 commit 順序?

首先我們先了解下 Spanner 的特性和它的整體架構。

Spanner 簡介

Spanner 是由 Google 公司設計開發的一套可擴展、高可用、可全球部署的分布式資料庫系統，具有如下特性:

1. 提供了基於 SQL 的查詢介面, 使用強類型的 schema, 提供了類型 RDS 的體驗；

2. 一定程度上支持垂直 sharding, 用戶可以通過 INTERLEAVE 語法定義相關的兩個 table 的記錄存放在同一個 spanserver，帶來的好處是形成了數據的 Locality, 對於查詢中的一些操作（比如 join, group by）可以進行下推[3]；

3. 可以自動對數據進行水平 sharding, 並對每個 shard 維護一定的數量的副本, 通過 Multi-Paxos 保證一致性, 這些副本可以分散在全球不同地域；

4. 支持 Snapshot Isolation, 通過 2PL 保證多個並發事務的 Serializability。另外, 對於涉及多個 shard 的 xa 事務, 通過 2PC 保證 Serializability；

5. 保證 External Consistency（等價於 Linearizability, 下文不再區分）, 也就是說如果事務 T1 提交後, 事務 T2 才開始提交, 那麼 T2 的 timestamp 一定大於 T1 的 timestamp。

整體架構

Spanner 是由一系列的 zone 組成, zone 是 Spanner 中的部署的單元, 一般會在某 datacenter 部署一個 zone, 但是也可以有多個 zone。數據副本就是存放在這一系列的 zone 中, zone 之間的物理距離越大, 數據的安全性越高。

• universemaster：是一個控制台, 監控universe里所有zone狀態信息, 用於debug；

• placement driver：幫助維持特定副本數量，自動搬遷數據，實現負載均衡；

• zonemaster：管理 spanserver 上的數據；

• location proxy：作用不詳, 可能是為 client 提供數據的位置信息, client 要先訪問它來定位需要訪問的 spanserver；

• spanserver：對 client 提供服務, 包括讀寫數據。

Spanserver 架構

每個 spanserver 負責管理 100 ~ 1000 個 tablet。

一個 tablet 是維護某個表的一部分數據, 比如一個表有 10,000 行數據, 分成 100 個 tablet, 那麼第 1 個 tablet 維護第 1 ~ 100 行數據, 第 2 個 tablet 維護第 101 ~ 200 行數據。

tablet 維護的數據是一系列的 KV: (key, timestamp) ---> value 。

可以看出, Spanner 的 KV 數據是和 timestamp 綁定的, 所以自然就是支持 multi-version。

為了支持數據複製, spanserver 在每個 tablet 上層實現了 paxos group, 這個 group 中 replica 分布在不同的 zone 中。

每個 leader replica 還維護了一個 lock table, 也就是一系列的 KV: key--->lock-states。

lock-states 指的是對應的數據在2PL過程中的鎖狀態。

spanserver 在每個 leader replica 上都實現了 transaction manager, 這個模塊是用來支持分布式事務的。

如果事務涉及到多個 paxos group, 那麼每個 leader replica 此時就是 participant leader 的身份, 其中一個 participant group 會被 client 選作 coordinator, 通過 2PC 的方式來實現 Serializability。

如果事務只涉及一個 paxos group, 那麼 transaction manager 的功能可以被忽略, 只依賴 lock table 就可以實現 Serializability。

事務 commit 的過程

簡單的實現（但是有問題）

現在假設讓我們來實現事務的 commit 過程, 有一種簡單的方法如下圖所示, 這種方法簡單的從 local clock 分配 timestamp 給事務:

假設現在有先後兩個事務 T1 和 T2, 分別在不同的 spanserver 上執行, T2 在 T1 提交後, 才開始提交, 使用這個方法會導致真實世界中後提交的 trx 反而具有較小的 timestamp。

這個問題出現的原因是, 兩個事務所使用的 local clock 沒有可比性, 無法真實反映兩個 trx 的先後順序：

上圖表明, T2 的 timestamp 是 8, T1 的 timestamp 是 10, 這個和真實世界的先後順序是相反的，原因在於不同設備上的 clock 是沒有可比性。

為了解決這個問題, 我們可能會很迅速的想到一個解決方案：引入一個專門生成 timestamp 的中心節點, 每次事務提交時, 訪問該中心節點來獲得 timestamp。

TiDB 使用的便是這種方案，但是這種方案引入了中心節點, 也意味著整套系統的部署不可能在地理位置上過於分散, 否則事務延時將會令人難以忍受。

Spanner 採用了另外一種方案：TrueTime。TrueTime 不但可以分配統一的具有可比性 timestamp 範圍, 還支持系統的全球範圍部署。

TrueTime

Spanner 的 TrueTime 是利用 GPS 時鐘和原子鐘實現的, 可以提供非常精確的時鐘, 誤差在 1ms~7ms 之間。

• TT.now 返回一個區間[earlist, latest], 保證 abs time(絕對時間)是在區間以內；

• TT.after(t) 判斷一個時間是否已經成為過去時, 是對 TT.now 的簡單封裝：

return TT.now.earlist > t

TT.before(t) 和前者類似,判斷時間是否是未來時。

TrueTime 實現

TrueTime 是通過以下架構實現的:

每個 datacenter 具有若干個 time master, 另外每台設備上運行有 timeslave 進程。前者是 Spanner 的時鐘來源, 大部分是配備 GPS 接收器,剩下一小部分配備原子鐘(防止 GPS 的天線故障或者頻率干擾, 所以也叫"末日時鐘")。

timeslave 以 30s 的間隔從 time master 同步時間。當 timeslave 需要校準 local clock 時, 從就近的 datacenter 和較遠的 datacenter 的 time master 拉取時間信息, 並通過 Marzullo 演算法[5]識別並丟棄異常的時間來源, 並將多個時間信息歸併到一個統一的時間。

TrueTime API 的直接數據來源是設備上的 local clock，所以 TrueTime 的誤差來源有:

1. 從 time master 同步時的網路延遲, 導致的誤差大概是 1ms；

2. local clock 的漂移, 這個誤差是時間的鋸齒函數, 校準後的一瞬間是 0, 校準前的一瞬間是最大值, 範圍在 0~6ms。

所以 TrueTime 總的誤差是 1~7ms, OSID12 論文表示平均是 4ms 左右。

網路延遲導致的誤差如下圖所示:

local clock 漂移導致的誤差, 是因為環境溫度,工作電壓等因素導致的。Spanner 計算這個誤差時, 已經按照最壞的漂移速度(200us/s)來計算的, 真實的差距可能是 local clock 提前了, 或者是 local clock 電壓不夠導致落後了。

為了保證 local clock 的漂移在 0 ~ 6ms 之內, 也就是漂移頻率在 200us/s 之內, Spanner 實現了漂移頻率異常的設備從集群中剔除的功能。

Commit Wait

利用 TrueTime, Spanner 可以保證整個分布式系統中,所有事務分配到的 timestamp 都是具有可比性的, 基於同一個參考系的。

Spanner 在 TureTime 的基礎上,還引入一個 Commit Wait 的限制，保證了 External Consistency, 也就是保證了如下規律:

如果事務 T2 在事務 T1 提交後, 才開始提交, 那麼 T2 的 commit timestamp 肯定大於 T1 的 commit timestamp。

這個限制是一個很關鍵的地方是, Commit Wait:

等待 T1 的 timestamp s成為過去時, 才提交事務(也就是通知其他replica進行重放,回復ack給用戶), 也就是保證事務 commit 的絕對時間大於s, 有了 Commit Wait 之後就可以保證了 External Consistency, 證明如下:

因此, Spanner 的 read-write 事務提交時的步驟如下:

首先, replica leader 接受收到 client 的 commit request 後, 會鎖住相應的 key, 然後分配 TT.now.latest 作為事務的 timestamp s。

因為 TT.now 保證了 abs time 是在區間內的, 所以這個 s是未來時, 需要進行 Commit Wait, 等待s成為過去時後, 再進行提交, 用於保證 External Consistentency。

假設 s = t1 + ε1, 進行 Commit Wait 之後是 Now = t2 ± ε2。

由於 t2 - ε2 >= t1 + ε1, 所以 Commit Wait 所消耗的時間等於 t2 - t1 >= ε1 + ε2, 也就是等待時間至少是平均誤差的 2 倍, 約 8ms（OSDI12 的論文中表示 Commit Wait 的時間大多數情況和 Paxos write 的時間是重疊的）。

關於 External Consistency 的示例如下, 假設圖中事務 T1 所在的 spanserver 的誤差是 1, 事務 T2 所在的 spanserver 誤差是 2:

Spanner 保證了 T1 的 timestamp = 11 小於 T2 的 timestamp = 14。

注意圖中縱坐標不是隨意標註的, 而是注入了一定的限制在這裡：刻度11 >= T1 的 timestamp, 而且 T2 的 timestamp >= 13。

Spanner 巧妙的通過 Truetime 和 Commit Wait, 保證了 T1 的 timestamp < T2 的 timestamp。

Snapshot read

Snapshot read 指的是讀取過去時間的某個快照, 無需加鎖。

client可以指定一個 timestamp t, 或者時間範圍，Spanner 會尋找一個數據充分更新好的 replica 來提供讀服務。

所謂數據充分更新好, 是指 t <= tsafe，其中 tsafe 定義如下:

前者指的已經提交的事務 timestamp, 後者指的是正在 2PC 過程中未決的事務 timestamp - 1。

如果 t > tsafe，Spanner 需要等待 replica 一段時間, 待 tsafe 推進後再進行讀操作。

基於 External Consistency 特性，Spanner 可以感知操作的先後順序, 給定一個時間戳 t, Spanner 能夠明確哪些是歷史數據, 並提供一致的快照。

總結

Spanner 的 TureTime API 設計非常巧妙, 保證了絕對時間一定是落在 TT.now 返回的區間之中。基於這個保證, 使得分布在全球的 spanserver 分配的 timestamp 都是基於同一參考系, 具有可比性。進而讓 Spanner 能夠感知分布式系統中的事件的先後順序, 保證了 External Consistency。

但是 TureTime API 要求對誤差的測量具有非常高的要求, 如果實際誤差 > 預計的誤差, 那麼絕對時間很可能就飄到了區間之外, 後續的操作都無法保證宣稱的 External Consistency。另外, Spanener 的大部分響應時間與誤差的大小是正相關的。

自 Spanner 在 OSDI12 發表論文後, Spanner 一直在努力減少誤差, 並提高測量誤差的技術[3], 但是並沒有透露更多細節。

參考

[1] Linearizability: acorrectness condition for concurrent objects(ACM TOPLAS 1990)

[2] Spanner: Google』s Globally-Distributed Database (OSDI12)

[3] Spanner: Becoming a SQL System (SIGMOD17)

[4] Weak Isolation in Relational Databases, http://www.evanjones.ca/db-isolation-semantics.html

[5] Marzullo"s algorithm, https://en.wikipedia.org/wiki/Marzullo%27s_algorithm

作者介紹

趙百忠，騰訊雲資料庫工程師，從事於高可用雲資料庫服務的構建和管控平台開發，關注 RDS, NoSql, NewSql 等技術發展。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！