分布式事務(wù)中的時(shí)間戳怎么搞？
點(diǎn)擊關(guān)注公眾號(hào)，Java干貨及時(shí)送達(dá)
作者：Eric Fu
鏈接：https://ericfu.me/timestamp-in-distributed-trans/
本文聊一聊時(shí)間戳的前世今生，為了把討論集中在主題上，假設(shè)讀者已經(jīng)對(duì)數(shù)據(jù)庫(kù)的 MVCC、2PC、一致性、隔離級(jí)別等概念有個(gè)基本的了解。
為什么需要時(shí)間戳？
MVCC 的全稱(chēng)是多版本并發(fā)控制（Multi-Version Concurrency Control），這個(gè)名字似乎暗示我們一定會(huì)有個(gè)版本號(hào)（時(shí)間戳）存在。然而事實(shí)上，時(shí)間戳還真不是必須的。MySQL 的 ReadView 實(shí)現(xiàn)就是基于事務(wù) ID 大小以及活躍事務(wù)列表進(jìn)行可見(jiàn)性判斷。
事務(wù) ID 在事務(wù)開(kāi)啟時(shí)分配，體現(xiàn)了事務(wù) begin 的順序；提交時(shí)間戳 commit_ts 在事務(wù)提交時(shí)分配，體現(xiàn)了事務(wù) commit 的順序。
分布式數(shù)據(jù)庫(kù) Postgres-XL 也用了同樣的方案，只是將這套邏輯放在全局事務(wù)管理器（GTM）中，由 GTM 集中式地維護(hù)集群中所有事務(wù)狀態(tài)，并為各個(gè)事務(wù)生成它們的 Snapshot。這種中心化的設(shè)計(jì)很容易出現(xiàn)性能瓶頸，制約了集群的擴(kuò)展性。
另一套方案就是引入時(shí)間戳，只要比較數(shù)據(jù)的寫(xiě)入時(shí)間戳（即寫(xiě)入該數(shù)據(jù)的事務(wù)的提交時(shí)間戳）和 Snapshot 的讀時(shí)間戳，即可判斷出可見(jiàn)性。在單機(jī)數(shù)據(jù)庫(kù)中產(chǎn)生時(shí)間戳很簡(jiǎn)單，用原子自增的整數(shù)就能以很高的性能分配時(shí)間戳。Oracle 用的就是這個(gè)方案。
MVCC 原理示意：比較 Snapshot 讀取時(shí)間戳和數(shù)據(jù)上的寫(xiě)入時(shí)間戳，其中最大但不超過(guò)讀時(shí)間戳的版本，即為可見(jiàn)的版本
而在分布式數(shù)據(jù)庫(kù)中，最直接的替代方案是引入一個(gè)集中式的分配器，稱(chēng)為 TSO（Timestamp Oracle，此 Oracle 非彼 Oracle），由 TSO 提供單調(diào)遞增的時(shí)間戳。TSO 看似還是個(gè)單點(diǎn)，但是考慮到各個(gè)節(jié)點(diǎn)取時(shí)間戳可以批量（一次取 K 個(gè)），即便集群的負(fù)載很高，對(duì) TSO 也不會(huì)造成很大的壓力。TiDB 用的就是這套方案。
MVCC 和 Snapshot Isolation 有什么區(qū)別？前者是側(cè)重于描述數(shù)據(jù)庫(kù)的并發(fā)控制實(shí)現(xiàn)，后者從隔離級(jí)別的角度定義了一種語(yǔ)義。本文中我們不區(qū)分這兩個(gè)概念。
可線(xiàn)性化
可線(xiàn)性化（linearizable）或線(xiàn)性一致性意味著操作的時(shí)序和（外部觀(guān)察者所看到的）物理時(shí)間一致，因此有時(shí)也稱(chēng)為外部一致性。具體來(lái)說(shuō)，可線(xiàn)性化假設(shè)讀寫(xiě)操作都需要執(zhí)行一段時(shí)間，但是在這段時(shí)間內(nèi)必然能找出一個(gè)時(shí)間點(diǎn)，對(duì)應(yīng)操作真正“發(fā)生”的時(shí)刻。
線(xiàn)性一致性的解釋。其中 (a)、(b) 滿(mǎn)足線(xiàn)性一致性，因?yàn)槿鐖D所示的時(shí)間軸即能解釋線(xiàn)程 A、B 的行為；(c) 是不允許的，無(wú)論如何 A 都應(yīng)當(dāng)看到 B 的寫(xiě)入
注意不要把一致性和隔離級(jí)別混為一談，這完全是不同維度的概念。理想情況下的數(shù)據(jù)庫(kù)應(yīng)該滿(mǎn)足 strict serializability，即隔離級(jí)別做到 serializable、一致性做到 linearizabile。本文主要關(guān)注一致性。
TSO 時(shí)間戳能夠提供線(xiàn)性一致性保證。完整的證明超出了本文的范疇，這里只說(shuō)說(shuō)直覺(jué)的解釋?zhuān)河糜谂袛嗫梢?jiàn)性的 snapshot_ts 和 commit_ts 都是來(lái)自于集群中唯一的 TSO，而 TSO 作為一個(gè)單點(diǎn)，能夠確保時(shí)間戳的順序關(guān)系與分配時(shí)間戳的物理時(shí)序一致。
可線(xiàn)性化是一個(gè)極好的特性，用戶(hù)完全不用考慮一致性方面的問(wèn)題，但是代價(jià)是必須引入一個(gè)中心化的 TSO。我們后邊會(huì)看到，想在去中心化的情況下保持可線(xiàn)性化是極為困難的。
TrueTime
Google Spanner 是一個(gè)定位于全球部署的數(shù)據(jù)庫(kù)。如果用 TSO 方案則需要橫跨半個(gè)地球拿時(shí)間戳，這個(gè)延遲可能就奔著秒級(jí)去了。但是 Google 的工程師認(rèn)為 linearizable 是必不可少的，這就有了 TrueTime。
TrueTime 利用原子鐘和 GPS 實(shí)現(xiàn)了時(shí)間戳的去中心化。但是原子鐘和 GPS 提供的時(shí)間也是有誤差的，在 Spanner 中這個(gè)誤差范圍 εε 被設(shè)定為 7ms。換句話(huà)說(shuō)，如果兩個(gè)時(shí)間戳相差小于 2ε2ε ，我們就無(wú)法確定它們的物理先后順序，稱(chēng)之為“不確定性窗口”。
Spanner 對(duì)此的處理方法也很簡(jiǎn)單——等待不確定性窗口時(shí)間過(guò)去。
在事務(wù)提交過(guò)程中 Spanner 會(huì)做額外的等待，直到滿(mǎn)足 TT.now()?Tstart>2εTT.now()?Tstart>2ε，然后才將提交成功返回給客戶(hù)端。在此之后，無(wú)論從哪里發(fā)起的讀請(qǐng)求必然會(huì)拿到一個(gè)更大的時(shí)間戳，因而必然能讀到剛剛的寫(xiě)入。
Lamport 時(shí)鐘與 HLC
Lamport 時(shí)鐘是最簡(jiǎn)單的邏輯時(shí)鐘（Logical Clock）實(shí)現(xiàn)，它用一個(gè)整數(shù)表示時(shí)間，記錄事件的先后/因果關(guān)系（causality）：如果 A 事件導(dǎo)致了 B 事件，那么 A 的時(shí)間戳一定小于 B。
當(dāng)分布式系統(tǒng)的節(jié)點(diǎn)間傳遞消息時(shí)，消息會(huì)附帶發(fā)送者的時(shí)間戳，而接收方總是用消息中的時(shí)間戳“推高”本地時(shí)間戳：Tlocal=max(Tmsg,Tlocal)+1Tlocal=max(Tmsg,Tlocal)+1。
Lamport Clock 只是個(gè)從 0 開(kāi)始增長(zhǎng)的整數(shù)，為了讓它更有意義，我們可以在它的高位存放物理時(shí)間戳、低位存放邏輯時(shí)間戳，當(dāng)物理時(shí)間戳增加時(shí)邏輯位清零，這就是 HLC（Hybrid Logical Clock）。很顯然，從大小關(guān)系的角度看，HLC 和 LC 并沒(méi)有什么不同。
HLC/LC 也可以用在分布式事務(wù)中，我們將時(shí)間戳附加到所有事務(wù)相關(guān)的 RPC 中，也就是 Begin、Prepare 和 Commit 這幾個(gè)消息中：
Begin：取本地時(shí)間戳 local_ts 作為事務(wù)讀時(shí)間戳 snapshot_ts Snapshot Read: 用 snapshot_ts 讀取其他節(jié)點(diǎn)數(shù)據(jù)（MVCC） Prepare：收集所有事務(wù)參與者的當(dāng)前時(shí)間戳，記作 prepare_ts Commit：計(jì)算推高后的本地時(shí)間戳，即 commit_ts = max{ prepare_ts } + 1
HLC/LC 并不滿(mǎn)足線(xiàn)性一致性。我們可以構(gòu)造出這樣的場(chǎng)景，事務(wù) A 和事務(wù) B 發(fā)生在不相交的節(jié)點(diǎn)上，比如事務(wù) TATA 位于節(jié)點(diǎn) 1、事務(wù) TBTB 位于節(jié)點(diǎn) 2，那么這種情況下 TATA、TBTB 的時(shí)間戳是彼此獨(dú)立產(chǎn)生的，二者之前沒(méi)有任何先后關(guān)系保證。具體來(lái)說(shuō)，假設(shè) TATA 物理上先于 TBTB 提交，但是節(jié)點(diǎn) 2 上發(fā)起的 TBTB 的 snapshot_ts 可能滯后（偏小），因此無(wú)法讀到 TATA 寫(xiě)入的數(shù)據(jù)。
T1: w(C1)
T1: commit
T2: r(C2) (not visible! assuming T2.snapshot_ts < T1.commit_ts)
HLC/LC 滿(mǎn)足因果一致性（Causal Consistency）或 Session 一致性，然而對(duì)于數(shù)據(jù)庫(kù)來(lái)說(shuō)這并不足以滿(mǎn)足用戶(hù)需求。想象一個(gè)場(chǎng)景：應(yīng)用程序中使用了連接池，它有可能先用 Session A 提交事務(wù) TATA（用戶(hù)注冊(cè)），再用 Session B 進(jìn)行事務(wù) TBTB（下訂單），但是 TBTB 卻查不到下單用戶(hù)的記錄。
如果連接池的例子不能說(shuō)服你，可以想象一下：微服務(wù)節(jié)點(diǎn) A 負(fù)責(zé)用戶(hù)注冊(cè)，之后它向微服務(wù)節(jié)點(diǎn) B 發(fā)送消息，通知節(jié)點(diǎn) B 進(jìn)行下訂單，此時(shí) B 卻查不到這條用戶(hù)的記錄。根本問(wèn)題在于應(yīng)用無(wú)法感知數(shù)據(jù)庫(kù)的時(shí)間戳，如果應(yīng)用也能向數(shù)據(jù)庫(kù)一樣在 RPC 調(diào)用時(shí)傳遞時(shí)間戳，或許因果一致性就夠用了。
有限誤差的 HLC
上個(gè)小節(jié)中介紹的 HLC 物理時(shí)間戳部分僅供觀(guān)賞，并沒(méi)有發(fā)揮實(shí)質(zhì)性的作用。CockroachDB 創(chuàng)造性地引入了 NTP 對(duì)時(shí)協(xié)議。NTP 的精度當(dāng)然遠(yuǎn)遠(yuǎn)不如原子鐘，誤差大約在 100ms 到 250ms 之間，如此大的誤差下如果再套用 TrueTime 的做法，事務(wù)延遲會(huì)高到無(wú)法接受。
CockroachDB 要求所有數(shù)據(jù)庫(kù)節(jié)點(diǎn)間的時(shí)鐘偏移不能超過(guò) 250ms，后臺(tái)線(xiàn)程會(huì)不斷探測(cè)節(jié)點(diǎn)間的時(shí)鐘偏移量，一旦超過(guò)閾值立即自殺。通過(guò)這種方式，節(jié)點(diǎn)間的時(shí)鐘偏移量被限制在一個(gè)有限的范圍內(nèi)，即所謂的半同步時(shí)鐘（semi-synchronized clocks）。
下面是最關(guān)鍵的部分：進(jìn)行 Snapshot Read 的過(guò)程中，一旦遇到 commit_ts 位于不確定性窗口 [snapshot_ts, snapshot_ts + max_clock_shift] 內(nèi)的數(shù)據(jù)，則意味著無(wú)法確定這條記錄到底是否可見(jiàn)，這時(shí)將會(huì)重啟整個(gè)事務(wù)（并等待 max_clock_shift 過(guò)去），取一個(gè)新的 snapshot_ts 進(jìn)行讀取。
有了這套額外的機(jī)制，上一節(jié)中的“寫(xiě)后讀”場(chǎng)景下，可以保證讀事務(wù) TBTB 一定能讀到 TATA 的寫(xiě)入。具體來(lái)說(shuō)，由于 TATA 提交先于 TBTB 發(fā)起，TATA 的寫(xiě)入時(shí)間戳一定小于 B.snapshot_ts + max_clock_shift，因此要么讀到可見(jiàn)的結(jié)果（A.commit_ts < B.snapshot_ts），要么事務(wù)重啟、用新的時(shí)間戳讀到可見(jiàn)的結(jié)果。
那么，CockroachDB 是否滿(mǎn)足可線(xiàn)性化呢？答案是否定的。Jepsen 的一篇測(cè)試報(bào)告中提到以下這個(gè)“雙寫(xiě)”場(chǎng)景（其中，數(shù)據(jù) C1、C2 位于不同節(jié)點(diǎn)上）：
T3: r(C1) (not found)
T1: w(C1)
T1: commit
T2: w(C2)
T2: commit (assuming T2.commit_ts < T3.snapshot_ts due to clock shift)
T3: r(C2) (found)
T3: commit
雖然 T1 先于 T2 寫(xiě)入，但是 T3 卻看到了 T2 而沒(méi)有看到 T1，此時(shí)事務(wù)的表現(xiàn)等價(jià)于這樣的串行執(zhí)行序列：T2 -> T3 -> T1（因此符合可串行化），與物理順序 T1 -> T2 不同，違反了可線(xiàn)性化。歸根結(jié)底是因?yàn)?T1、T2 兩個(gè)事務(wù)的時(shí)間戳由各自的節(jié)點(diǎn)獨(dú)立產(chǎn)生，無(wú)法保證先后關(guān)系，而 Read Restart 機(jī)制只能防止數(shù)據(jù)存在的情況，對(duì)于這種尚不存在的數(shù)據(jù)（C1）就無(wú)能為力了。
Jepsen 對(duì)此總結(jié)為：CockroachDB 僅對(duì)單行事務(wù)保證可線(xiàn)性化，對(duì)于涉及多行的事務(wù)則無(wú)法保證。這樣的一致性級(jí)別是否能滿(mǎn)足業(yè)務(wù)需要呢？這個(gè)問(wèn)題就留給讀者判斷吧。
結(jié)合 TSO 與 HLC
最近看到 TiDB 的 Async Commit 設(shè)計(jì)文檔 引起了我的興趣。Async Commit 的設(shè)計(jì)動(dòng)機(jī)是為了降低提交延遲，在 TiDB 原本的 Percolator 2PC 實(shí)現(xiàn)中，需要經(jīng)過(guò)以下 4 個(gè)步驟：
Prewrite：將 buffer 的修改寫(xiě)入 TiKV 中 從 TSO 獲取提交時(shí)間戳 commit_ts Commit Primary Key Commit 其他 Key（異步進(jìn)行）
為了降低提交延遲，我們希望將第 3 步也異步化。但是第 2 步中獲取的 commit_ts 需要由第 3 步來(lái)保證持久化，否則一旦協(xié)調(diào)者在 2、3 步之間宕機(jī)，事務(wù)恢復(fù)時(shí)就不知道用什么 commit_ts 繼續(xù)提交（roll forward）。為了避開(kāi)這個(gè)麻煩的問(wèn)題，設(shè)計(jì)文檔對(duì) TSO 時(shí)間戳模型的事務(wù)提交部分做了修改，引入 HLC 的提交方法：
Prewrite
TiDB 向各參與事務(wù)的 TiKV 節(jié)點(diǎn)發(fā)出 Prewrite 請(qǐng)求 TiKV 持久化 Prewrite 的數(shù)據(jù)以及 min_commit_ts，其中 min_commit_ts = 本地最大時(shí)間戳 max_ts TiKV 返回 Prewrite 成功消息，包含剛剛的 min_commit_ts Finalize
（異步）：計(jì)算 commit_ts = max{ min_commit_ts }，用該時(shí)間戳進(jìn)行提交
Commit Primary Key Commit 其他 Key
上述流程和 HLC 提交流程基本是一樣的。注意，事務(wù)開(kāi)始時(shí)仍然是從 TSO 獲取 snapshot_ts，這一點(diǎn)保持原狀。
我們嘗試代入上一節(jié)的“雙寫(xiě)”場(chǎng)景發(fā)現(xiàn)：由于依賴(lài) TSO 提供的 snapshot_ts，T1、T2 的時(shí)間戳依然能保證正確的先后關(guān)系，但是只要稍作修改，即可構(gòu)造出失敗場(chǎng)景（這里假設(shè) snapshot_ts 在事務(wù) begin 時(shí)獲取）：
T1: begin T2: begin T3: begin (concurrently)
T1: w(C1)
T1: commit (assuming commit_ts = 105)
T2: w(C2)
T2: commit (assuming commit_ts = 103)
T3: r(C1) (not found)
T3: r(C2) (found)
T3: commit
雖然 T1 先于 T2 寫(xiě)入，但 T2 的提交時(shí)間戳卻小于 T1，于是，并發(fā)的讀事務(wù) T3 看到了 T2 而沒(méi)有看到 T1，違反了可線(xiàn)性化。根本原因和 CockroachDB 一樣：T1、T2 兩個(gè)事務(wù)的提交時(shí)間戳由各自節(jié)點(diǎn)計(jì)算得出，無(wú)法確保先后關(guān)系。
Async Commit Done Right
上個(gè)小節(jié)給出的 Async Commit 方案破壞了原本 TSO 時(shí)間戳的線(xiàn)性一致性（雖然僅僅是個(gè)非常邊緣的場(chǎng)景）。這里特別感謝 @Zhifeng Hu 的提醒，在 #8589 中給出了一個(gè)巧妙的解決方案：引入 prewrite_ts 時(shí)間戳，即可讓并發(fā)事務(wù)的 commit_ts 重新變得有序。完整流程如下，注意 Prewrite 的第 1、2 步：
Prewrite
TiDB 從 TSO 獲取一個(gè) prewrite_ts，附帶在其中一個(gè) Prewrite 請(qǐng)求上發(fā)送給 TiKV TiKV 用 prewrite_ts（如果收到的話(huà)）推高本地最大時(shí)間戳 max_ts TiKV 持久化 Prewrite 的數(shù)據(jù)以及 min_commit_ts = max_ts TiKV 返回 Prewrite 成功消息，包含剛剛的 min_commit_ts Finalize
（異步）：計(jì)算 commit_ts = max{ min_commit_ts }，用該時(shí)間戳進(jìn)行提交
Commit Primary Key Commit 其他 Key
對(duì)應(yīng)到上面的用例中，現(xiàn)在 T1、T2 兩個(gè)事務(wù)的提交時(shí)間戳不再是獨(dú)立計(jì)算，依靠 TSO 提供的 prewrite_ts 可以構(gòu)建出 T1、T2 的正確順序：T2.commit_ts >= T2.prewrite_ts > T1.commit_ts，從而避免了上述異常。
更進(jìn)一步，該方案能夠滿(mǎn)足線(xiàn)性一致性。這里只給一個(gè)直覺(jué)的解釋?zhuān)何覀儗?TSO 看作是外部物理時(shí)間，依靠 prewrite_ts 可以保證 commit_ts 的取值位于 commit 請(qǐng)求開(kāi)始之后，而通過(guò)本地 max_ts 計(jì)算出的 commit_ts 一定在 commit 請(qǐng)求結(jié)束之前，故 commit_ts 取值落在執(zhí)行提交請(qǐng)求的時(shí)間范圍內(nèi)，滿(mǎn)足線(xiàn)性一致性。
總結(jié)
上述已知的時(shí)間戳方案中，僅有 TSO 和 TrueTime 能夠保證線(xiàn)性一致性； Logical Clock 方案僅能保證 Session 一致性； Cockroach 的 HLC 方案僅能保證行級(jí)線(xiàn)性一致性，不保證多行事務(wù)的線(xiàn)性一致性； TiDB Async Commit 通過(guò)引入 Prewrite 時(shí)間戳保持了外部一致性；但如果去掉 Prewrite 時(shí)間戳、使用 HLC 的提交方式，則不保證多行的并發(fā)事務(wù)的線(xiàn)性一致性。
References
https://en.wikipedia.org/wiki/Lamport_timestamp https://www.slideshare.net/josemariafuster1/spanner-osdi2012-39872703 https://jepsen.io/analyses/cockroachdb-beta-20160829 https://www.cockroachlabs.com/blog/living-without-atomic-clocks/) https://sergeiturukin.com/2017/06/29/eventual-consistency.html https://github.com/tikv/sig-transaction/blob/master/design/async-commit/initial-design.md https://github.com/tikv/tikv/issues/8589
關(guān)注Java技術(shù)棧看更多干貨
