Google Spanner 事務在存儲層的實現

04-19

本文為授權轉載
原作者：@Eric Fu
原文鏈接：Google Spanner 事務在存儲層的實現
版權聲明：原文使用 CC BY-NC-SA 3.0 許可協議。轉載請註明出處！

Google Spanner 的論文於 2012 年發表，至今仍是世界上最先進的、規模最大的分散式資料庫架構，毫無疑問對現代資料庫設計產生了深遠影響。其最大的亮點莫過於 TrueTime API，憑藉原子鐘和 GPS 的加持在全球範圍實現了單調遞增的時間戳，從而達到外部一致性；其次則是驗證了分散式 MVCC 的高性能實現，為業界指明一條發展方向。

不過，論文對存儲層實現只作了模糊的闡述：原文中說到 Tablet 的實現類似於 Bigtable（復用了不少 Bigtable 的代碼），底層基於 Colossus —— 繼承 GFS 的下一代分散式文件系統。可以確定的一點是，存儲層要為 Read-Only 和 Read-Write 事務提供支持：

Read-Only 事務: 讀取最新或給定時間戳 $t_{read}$ 的快照，也就是 Snapshot Read
Read-Write 事務：讀取事務開始時間戳 $t_{start}$ 的快照，而寫入操作在提交時間戳 $t_{commit}$ 生效

本文從 Spanner 本身設計出發，並結合開源實現 TiKV 和 CockroachDB，談談如何為 Spanner 設計一個存儲層。本文假設讀者閱讀過原論文 Spanner: Google』s Globally-Distributed Database。

數據的 KV 表示

Spanner 對外提供（半）關係型數據模型：每張表定義了一個或多個主鍵列，以及其他的非主鍵列。這和我們熟知的 SQL 關係型模型幾乎一摸一樣，唯一的不同是 schema 定義中必須含有主鍵。

Spanner 早期的設計中大量復用了 BigTable（開源實現即 HBase）的代碼。回憶一下 BigTable 的數據模型：每一條數據包含 (Key, Column, Timestamp) 三個維度，滿足我們需要的 MVCC 特性。從 BigTable 開始的確是個不錯的選擇。

不過，從性能上考慮 Bigtable 畢竟是分散式的 KV 存儲系統，在存儲這一層我們大可不用搞的那麼複雜，分散式的問題例如 Scale-out 和 Replication 應當留給上層的 Sharding 機制和 Paxos 解決。事實上，一個單機的存儲引擎足矣。

Google 自家的 LSM-Tree + SSTable 的實現 LevelDB 是個可選項。它介面非常簡單，是一個標準的 KV 存儲，可以方便的在它基礎上實現我們想要的數據模型。主要介面其實就是兩個：

Write(WriteBatch *) 原子地寫入一個 WriteBatch，包含一組 Put(K, V) 和 Delete(K) 操作
Iterator() 及 Seek() 從指定位置開始順序掃描讀取 (K, V) 數據

如何實現列和時間戳呢？舉個例子，有如下數據表 Accounts。在資料庫中，主鍵索引通常也是唯一的聚簇索引，它存放了真實的數據，而我們暫時不考慮其他索引。

| UserID (PK) | Balance | LastModified ||-------------|---------|--------------|| Alice | 20 | 2018-02-20 || Bob | 10 | 2018-02-01 |

Spanner 內部使用 MVCC 機制，所以還有一個隱藏的時間戳維度：

| UserID | Timestamp | Balance | LastModified ||--------|-----------|---------|--------------|| Alice | 103 | 20 | 2018-02-20 || Alice | 101 | 15 | 2018-01-20 || Bob | 102 | 10 | 2018-02-01 |

上述數據表用 KV 模型存儲，可以表示為

| Key | Value ||---------------------------------|------------|| Accounts/Alice/Balance/103 | 20 || Accounts/Alice/Balance/101 | 15 || Accounts/Alice/LastModified/103 | 2018-02-20 || Accounts/Alice/LastModified/101 | 2018-01-20 || Accounts/Bob/Balance/102 | 10 || Accounts/Bob/LastModified/102 | 2018-02-01 |

上表中 / 表示一個分隔符，真實情況要更複雜。Key 這樣編碼：從左到右依次是表名（因為可以有不止一張表）、主鍵欄位、列的標識符、時間戳（通常倒序排列，Tips. 取反即可）。Value 則對應原表中的數據。

顯然，對於半關係型數據一定能由表名、主鍵欄位、列名唯一地確定一個值，所以這個編碼方式能滿足我們的要求。

如果一張表只有主鍵怎麼辦呢？這種情況下可以為每個主鍵填充一個 Placeholder 的 Value 即可。

事務的原子性

眾所周知，事務具有四個特性：原子性（Atomicity）、一致性（Consistency）、隔離性（Isolation）、持久性（Durability）。其中一致性和持久性其實是資料庫系統的特性，對於事務，我們更多討論的是原子性和隔離性。

對於存儲層而言，為上層提供原子性 Commit 的介面是必須的功能。如何在 KV 存儲的基礎上實現原子性呢？以下思路是一種常見的方案：

首先，準備一個開關，初始狀態為 Off，當我們把開關打開的那一刻，意味著 Commit 生效可見；
將所有變更以一種可回滾的方式（e.g. 不能覆蓋現有的值）寫入存儲中。開關同時決定了其它 Reader 的視圖，由於開關還是 Off 狀態，現在寫入的變更不會被其它事務看到。
之後，寫入開關狀態為 On，標誌著 Commit 的成功，新數據生效，即所謂 Commit Point。這個寫入操作本身的原子性由 LevelDB 保證。
最後，清除掉中間狀態（比如第 2 步中的臨時數據）並寫入最終的數據。這一步可以非同步地完成，因為在第 3 步中事實上 Commit 已經成功了，無需等待。

保證原子性的關鍵在於 Commit Point。例如，在單機資料庫中，Commit Point 是 Commit 的 Redo-log 寫入磁碟的一瞬間；在 XA 兩階段提交中，Commit Point 是協調器發出 Commit 的指令的那一瞬間。

在我們的存儲中，Commit Point 也就是第 3 步的寫入操作。如果提交過程意外終止在 Commit Point 之前，我們會在讀取時發現第 2 步中的臨時寫入，然後輕鬆的清除它；如果意外終止在 Commit Point 之後，部分臨時狀態沒有被清除，只需繼續執行 4 即可。

上述只是一個解決問題的思路。具體的解決方案可以參考 Percolator 的事務實現。這同時也是 TiDB 的做法，CockroachDB 做法略有不同，但同樣遵從這個模式。

Percolator 事務方案

Percolator 是 Google 早期的分散式事務解決方案，用於進行大規模增量數據處理。Percolator 在 BigTable 基礎上基於 2PL 思想實現了分散式事務。這個演算法很簡單，你可以把它看作是是封裝了一系列 BigTable 的 API 訪問（本身無狀態），所以可以容易地移植到 KV 存儲模型上。

Percolator 事務模型基於單調遞增的時間戳，來源於集群中唯一的 Timestamp Oracle。每個事務擁有提交時間戳 $t_{commit}$ 和開始時間戳 $t_{start}$ Percolator 事務模型和之前說到的 Write-Read 事務一致：事務中總是讀取 $t_{start}$ 時的 snapshot，而寫入則全部在 $t_{commit}$ 生效。這也意味著事務中所有寫入都被 Buffer 到最後進行，不支持類似於 Read-Write-Read 這樣的模式。

事務 2 看到的是事務 1 提交前的狀態，而事務 3 看到的是事務 1、2 提交後的狀態

除了數據本身（bal:data 列）以外，我們給數據再加上兩列：lock 和 write。

write 列存放了一個指針，指向寫入的 data 的時間戳
lock 列用於 2PL，加鎖時也保存了 Primary Lock 的位置。

Primary Lock 不僅代表當前行的鎖狀態，還兼任上文中「開關」的作用。通常選取第一個寫入的數據作為 Primary Lock。

以下表為例。表中 6: data @ 5 表示： $ts = 6$ 時事務提交，確定了 Bob 對應的值是 5: $10（所以推測出該事務 $t_{start}=5$ ）。其他事務讀取時，為了避免讀到 Uncommitted 的數據，都會先從 write 列開始找，然後再讀出其指向的 data。

現在，用戶要從 Bob 賬戶里轉 $7 給 Joe，為此必須開啟一個事務。 $ts=7$ 時，轉賬事務開始，向 Bob 和 Joe 的 data 寫入新的餘額。

$ts=8$ 時，用戶 Commit 事務。事務的第一階段（Prewrite）亦即是 2PL 的加鎖階段，先為 Bob 和 Joe 都加上鎖。如下圖所示，lock 不為空即代表加上了鎖，其內容指向 Primary Lock 的位置。簡單起見，不妨設第一條被鎖的數據為 Primary Row。

下一步很關鍵：清除 Primary Row 的 Lock 並向 write 列寫入新 data 的位置。這也就是所謂 Commit Point，這個寫入的成功或失敗決定了事務提交成功與否：

若寫入成功，則代表整個事務成功。之後會遍歷所有加鎖的行，解除 lock 並向 write 列寫入新的 data位置。這樣一來，其他事務就能讀到當前事務寫入的數據。
否則，整個事務失敗。之後會遍歷所有加鎖的行，解除 lock 並清除之前寫入的 data，恢復原狀。

回到例子中，當 Commit Point 完成後，表的狀態如下：

解除 Joe 的 lock 並向 write 列寫入新 data 的位置，至此事務 Commit 完成：

Commit point 這一步本身的原子性由 BigTable 行事務保證。對於 Commit Point 前後的其他操作，如果系統當機重啟，恢複線程可以通過檢查 Commit Point 操作的結果，來確定該 Roll Forward 還是 Roll Back。具體而言：

通過 lock 找到 Primary Lock，如果已經解除，說明 Commit Point 已經完成，需要 Roll Forward 事務。
否則，如果 Primary Lock 還在，說明 Commit Point 還沒到，只能 Roll Back 事務。

於是，通過 2PL，我們成功地在 BigTable 的行級事務基礎上實現了表級事務。

上述過程很容易的能映射到 KV 存儲模型上。按照前一節描述的方法，將 lock 和 write 列都視作普通的列即可。這裡不再贅述。

事務的隔離性

上述的討論只考慮了單個事務的原子性保證——如何確保能從從中間狀態恢復到未提交或已提交的狀態，而沒有考慮多線程並發的情況。如果同時有多個 Client 在運行多個事務，如何保證嚴格互相隔離？（Serializable 級別）

Percolator 是一個典型的 Snapshot Isolation 實現。Percolator 包含一個被稱為 Strict-SI 的改進：在事務 Commit 中，如果發現有一個高於 $t_{start}$ 的版本出現，則放棄 Commit。這能避免 Lost Update 問題。但是 Write-Skew 問題依然存在。

Spanner 提供 Serializable 隔離性保證，其演算法被稱為 Serializable Snapshot Isolation (SSI)。

衝突圖理論

首先對以上問題建模。考慮兩個事務對同一條數據先後發生兩次讀或寫操作，於是有 4 種情況：

Read-Read：這是OK的，它不會引起衝突；
Read-Write：後發生的操作覆蓋了前一個讀的數據，這是一種衝突；
Write-Read：讀到另一個事務的寫入，這是一種衝突。
Write-Write：即覆蓋寫，這是一種衝突。

上述三種衝突的情況，並不是一定會導致問題。舉個例子：事務 $T_2$ 僅僅是覆蓋了事務 $T_1$ 寫入的數據，那麼 $T_1$ 和 $T_2$ 仍然是符合 Serializable 的，只要邏輯上認為 $T_2$ 發生在 $T_1$ 之後。

哪些情況會違反 Serializable 呢？簡單來說，如果衝突A迫使我們規定 $T_1$ 先於 $T_2$ ，衝突B迫使我們規定 $T_2$ 先於 $T_1$ ，這個因果關係就沒法成立了， $T_1$ 、 $T_2$ 無法以任何方式串列化。形式化的說：以所有事務 $T$ 作為節點、以所有衝突 $C$ 作為有向邊構成一張有向圖（這被稱為衝突圖或依賴圖），如果這張圖是有向無環圖（DAG）則滿足 Serializable；否則（有環）不滿足。

舉個例子：

這是一個有向無環圖， $T_1、T_2、T_3$ 滿足 Serializable。

這是一個有環的圖， $T_1、T_2、T_3$ 無法滿足 Serializable。

圖論告訴我們，如果一張圖是 DAG，等價於我們能為它進行拓撲排序，即給每個節點 Assign 一個編號，使得所有邊都是從編號小的節點指向編號大的。換而言之，如果我們能給每個節點 Assign 一個這樣的編號，則可以反推出原圖是 DAG，進而證明 T 集合滿足 Serializable。

你可能已經隱約感覺到，這個編號和事務發生的順序有關！事實上，編號代表 Serializable 後的邏輯順序，大多數時候，這個順序和真實的時間順序都是一致的。
Spanner 中強調自己滿足的是比 Serializable 更強的一致性：Linearizable，說的就是不僅能序列化，而且序列化的「邏輯順序」和時間上的「物理順序」也一致。

Serializable Snapshot Isolation (SSI)

不妨把事務開始的時間戳 $t_{start}$ 作為這個編號。將上述約束條件略微加強一些，就得到了簡單有效的判斷法則：對於衝突 $T_1 o T_2$ ，如果時間戳滿足 $t_1 < t_2$ 則允許發生；如果 $t_1 > t_2$ 則終止事務。

具體的來說，對於三種衝突，分別用以下方式處理：

Write-Read 衝突：感謝 MVCC，這是不會發生的，在 Percolator 的事務模型中，讀操作一定是從一個過去時間點的 Snapshot 上讀取，而不會讀到一個正在進行中事務的臟數據。（但是 MVCC 會引發另一個問題——Staled Read。見下文）
Write-Write 衝突：如果 Write 發生的時候，出現了一條 $t_{start}$ 比較大的記錄，則終止寫事務。

在 Percolator 中使用了更強的約束：如果出現另一條比開始時間大的記錄，無論其時間戳如何都會終止當前提交，這被稱為 Strict-SI，與 SSI 的機制有所區別。
Strict-SI 無法完全避免 Read-Write 衝突（例如 Write-Skew 問題），所以在 Write-Write 衝突的處理上更為激進；但 SSI 已經解決了 Read-Write 衝突檢測，不必用更強的約束。

Read-Write 衝突：為了知道 Write 和另一個事務的 Read 衝突，必須要以某種方式記錄下所有被讀過的數據、以及讀取事務的 $t_{start}$ 。這通常用範圍鎖（Range Lock）來實現——將所有查詢的 TableScan 範圍記錄在內存中，如果某一條寫入的數據滿足某個 where 條件，則有必要檢查一下二者的時間戳先後順序。如果不滿足上述判斷法則，需要終止寫事務。

由於 MVCC 的存在，Read-Write 衝突還有另一種形式： $T_2$ 的 Read 發生地更遲，但是由於 MVCC 它讀到的是 $T_1$ 寫之前的值（Staled Read），而且這裡 $T_1$ 先於 $T_2$ 從而構成 Read-Write 衝突。

對此，一個簡單的解決方案既是：如果 $T_2$ 發現 $T_1$ 寫入的中間數據（lock），則立即終止自己。經典 SSI 的做法是，在 $T_2$ Commit 時如果發現 $T_1$ 已經 Commit 則放棄本次提交。

綜上，通過給每個事務賦予一個時間戳，並保證每個衝突都符合時間戳順序，達到 Serializable 隔離級別。

總結

將 (Table, Key, Column, Timestamp) 作為 Key 的編碼，從而把（半）關係型數據存儲在 KV 引擎中；
用兩階段鎖（2PL）的方式在 KV 引擎上實現事務的原子性提交。
禁止衝突違反時間戳先後順序，從而保證 Serializable 的隔離性。

參考文獻

Spanner: Google』s Globally-Distributed Database (OSDI』12)
Large-scale Incremental Processing Using Distributed Transactions and Notifications - USENIX 2010 - Daniel Peng, Frank Dabek
How CockroachDB Does Distributed, Atomic Transactions - Cockroach Labs
Serializable, Lockless, Distributed: Isolation in CockroachDB - Cockroach Labs
Designing Data?Intensive Applications - Martin Kleppmann