「資料庫」雲原生分布式資料庫事務隔離級别

Part 1 事務簡介

事務的定義

事務（transaction）是資料庫系統中保證一緻性與執行可靠計算的基本機關。當确定了查詢的執行政策并将其翻譯成資料庫操作原語後，将以事務為機關執行查詢。

區分資料庫一緻性（database consistency）與事務一緻性（transaction consistency）：

資料庫一緻性：如果一個資料庫服從定義于其上的所有一緻性（完整性）限制，則資料庫處于一緻性狀态。修改、插入、删除（統稱更新）都會造成狀态的改變。理想是保證資料庫不會進入不一緻狀态。雖然事務在執行過程中資料庫有可能會暫時變得不一緻，但是當事務執行完畢後資料庫必須恢複到一緻的狀态。

事務一緻性：涉及到并發事務的行為，理想是多個使用者同時通路（讀或寫）的時候保持一緻狀态。考慮到資料庫中資料複制，對使用者通路的處理變得複雜。對于複制資料庫，若一個資料項的所有拷貝都具有相同的值，稱這個複制資料庫處于互相一緻狀态（mutually consistency state）。這種情況稱為單拷貝等價（one-copy equivalence），在事務都執行結束時所有複制的拷貝都被強制處于同一狀态。

事務是一緻性與可靠計算的基本機關。直覺上一個事務會通過執行某個操作将資料庫從一個版本變成一個新版本，由此造成資料庫狀态轉移。通過事務可以保證如果資料庫在執行事務之前是一緻的，那麼它在執行完事務後依然是一緻的，無論過程中是否有其他事務并行或是發生系統故障。

如果事務成功地完成了它的任務，稱這個事務已送出(commit)；如果事務沒有完成任務卻中途停止了，稱它已取消(abort)。事務會由于多種原因被取消。此外，死鎖等其他原因也會令DBMS将事務取消。當事務被取消的時候，所有正在執行的動作都會停止，所有已經執行過的動作都将反做(undo)，資料庫會回退到執行該事務之前的狀态。這一過程被稱為復原(rollback)。

事務的性質

事務ACID四個性質：

1. 原子性(atomicity)：事物的所有操作要麼全部被執行，要麼就一個都不執行，又被稱為“All or Nothing”性質。

注意這裡把原子性的概念從單獨的一個個操作擴充到整個事務了。如果一個事務的執行過程被某種故障所打斷，那麼事務的原子性就要求DBMS能夠響應這個故障，并能夠決定如何将事務從中恢複回來。當然，這裡有兩種恢複方式:要麼完成餘下的操作，要麼反做所有已經完成的操作。

一般事務在執行時會遇到兩種故障。第一種故障是由輸人資料錯誤、死鎖等原因造成的。在這種情況下，事務要麼自己将自己取消，要麼在死鎖等情況出現的時候由DBMS将其取消。在這種故障下維護事務的原子性的操作稱為事務恢複(transaction recovery)。第二種故障通常源于系統癱瘓，例如存儲媒體故障、處理器故障、通信線路損毀、供電中斷等。在這種情況下保障事務的原子性的操作稱為癱瘓恢複(crashrecovery)。上述兩種故障的一個重要差別是，在某些系統癱瘓故障中，存儲在易失性存儲器中的資訊可能會丟失或不可通路。這兩類恢複操作屬于處理可靠性問題的一部分。

1. 一緻性(consistency):事務是能夠正确的将資料庫從一個一緻狀态變換到另一個一緻狀态的程式。驗證一個事務是否具有一緻性是完整性實施所涉及到的工作。如何保證事務一緻性是并發控制機制的目的。
2. 隔離性( isolation) ：在事務送出前，一個執行中的事務不能向其他并發事務透露自己的執行結果。保證事務隔離性的一個原因在于，保護事務的一緻性。
3. 持久性(durability)：如果一個事務已經送出，那麼它産生的結果是永久的，這一結果不能從資料庫中抹去。持久性會引入資料庫恢複（database recovery）問題。

這四個性質通常并不是互相獨立而是互相依賴的。

事務的類型

這裡僅簡單介紹幾種事務類型：

1. 平面事務（flat transaction）：有一個起始點（Begin_transaction）和一個結束點（End_transaction）。
2. 嵌套事務（nested transaction）：一個事務中包含其他具有單獨的起始點和送出點的事務。
3. 工作流（workflow model）：實際含義暫沒有清晰與統一的定義，目前一個可行定義：為了完成某個商業過程而組織起來的一組任務。

以上主要參考 Principles of Distributed Database Systems (Third Edition)。

Part 2 事務的隔離級别

隔離級别的定義

ANSI（美國國家标準協會）給出的 SQL-92 中隔離級别是根據現象（phenomena）來定義的，下面給出三個現象的解釋：

• P1 (Dirty Read) : Transaction T1 modifies a data item. Another transaction T2 then reads that data item before T1 performs a COMMIT or ROLLBACK. If T1 then performs a ROLLBACK, T2 has read a data item that was never committed and so never really existed.
• P2 (Non-repeatable or Fuzzy Read) : Transaction T1 reads a data item. Another transaction T2 then modifies or deletes that data item and commits. If T1 then attempts to reread the data item, it receives a modified value or discovers that the data item has been deleted.
• P3 (Phantom) : Transaction T1 reads a set of data items satisfying some . Transaction T2 then creates data items that satisfy T1’s and commits. If T1 then repeats its read with the same , it gets a set of data items different from the first read.

在論文 A Critique of ANSI SQL Isolation Levels 中作者指出 ANSI 給出的現象是不明确的，即使在最寬松的解釋中也不排除執行曆史中可能出現的一些異常行為，會導緻一些反直覺的結果。并且，基于鎖的隔離級别與等效 ANSI phenomena 有不同的特性，而商業資料庫系統通常使用鎖實作隔離級别。此外，ANSI 的現象不能區分出商業系統中許多類流行的隔離級别的行為。

由于 ANSI 給出的現象在語義上存在模糊性，是以可以對現象進行廣義的解釋以及狹義的解釋。

廣義的解釋記為 P，狹義解釋記為 A。事務1滿足謂詞P的讀取和寫入一組記錄分别由“r1[P]”和“w1[P]”表示。事務1的送出（COMMIT）和中止（ROLLBACK）分别被記為“c1”和“a1”。上述三個現象重新表述如下：

• P1: w1[x]...r2[x]...((c1 or a1) and (c2 or a2) in any order)
• A1: w1[x]...r2[x]...(a1 and c2 in any order)
• P2: r1[x]...w2[x]...((c1 or a1) and (c2 or a2) in any order)
• A2: r1[x]...w2[x]...c2...r1[x]...c1
• P3: r1[P]...w2[y in P]...((c1 or a1) and (c2 or a2) any order)
• A3: r1[P]...w2[y in P]...c2...r1[P]...c1

根據現象給出隔離級别的定義。

ANSI SQL 定義了四個級别的隔離，每個隔離級别的特征是事務中禁止發生的現象（廣義或狹義的表述），具體如表1所示：

但是，ANSI SQL規範沒有僅根據這些現象來定義可串行化（SERIALIZABLE）隔離級别。ANSI SQL 指出，可串行化隔離級别必須提供“共識的完全可串行化的執行”。與這個必要條件相比，表1導緻了一個常見的誤解，即不允許三個現象發生就意味着可串行化。不允許在表1中出現的三種現象應該被稱為異常可串行化（ANOMALY SERIALIZABLE）（注：異常可串行化意為基于禁止異常（或phenomena）的可串行化，并非“真正的”可串行化）。 基于鎖機制的隔離級别

大多數SQL産品都使用基于鎖的隔離。是以，盡管存在某些問題，但從鎖方面表征ANSI SQL隔離級别是有效的。

事務在基于鎖排程下執行的讀/寫會請求資料項或資料項集合上讀（共享）和寫（獨占）鎖（read lock and write lock）。在兩個不同的事務下的鎖對應着同一個資料項的情況下，當至少一個是寫鎖的時候會沖突。

讀取（或寫入）的謂詞鎖（給定的<搜尋條件>确定的一組資料項下）（read/write predicate lock）實際上是對滿足<搜尋條件>的所有資料項的鎖。這可能是一個無限集，因為它包括資料庫中存在的資料以及目前不在資料庫中的所有幻影（phantom）資料項（如果它們被插入，或者目前資料項被更新以滿足<搜尋條件> ）。在SQL術語中，謂詞鎖覆寫滿足謂詞的所有資料項以及INSERT，UPDATE或DELETE後滿足謂詞的所有資料項。不同僚務的兩個謂詞鎖中如果一個是寫鎖，并且兩個鎖覆寫了相同的（可能是幻影）資料項，則兩個謂詞鎖相沖突。資料項（item）鎖（記錄鎖）是一個謂詞鎖，其中謂詞指定特定記錄。

事務具有好形式的寫（讀）（well-formed writes/reads）要求在寫（讀）該資料項或謂詞定義的資料項集之前，每個資料項或謂詞請求寫鎖（讀鎖）（譯者注：也就是說在讀（寫）時對指定資料項集進行有且僅有一次的加讀（寫）鎖）。事務是好形式（well-formed）的，要求事務有好形式的讀與寫。事務具有兩階段寫（讀）（two-phase writes/reads）要求在釋放寫（讀）鎖之後，在資料項上沒有設定新的寫（讀）鎖。事務是兩階段（two-phase）的，要求事務在釋放一些鎖之後不會請求任何新的鎖（讀或寫鎖）。

長鎖（long duration）要求鎖到事務送出或中止為止。否則，為短鎖（short duration）。短鎖通常在操作完成後立即釋放。

如果一個事務持有一個鎖，另一個事務請求一個沖突的鎖，那麼在前一個事務的沖突鎖已經被釋放之前，新的鎖請求是不被授予的。

表2根據鎖定範圍（資料項項或謂詞），模式（讀或寫）及其持續時間（短或長）定義了多個隔離類型。基于鎖的隔離級别：“鎖讀未送出”、“鎖讀已送出”、“鎖可重複讀”、“鎖可串行化”是滿足ANSI SQL隔離級别要求的，但表2與表1完全不同，必須将基于鎖定義的隔離級别與基于 ANSI SQL 現象的隔離級别進行區分。為了區分，表2中的級别标有“Locking”字首，而不是表1的“ANSI”字首。

ANSI SQL 現象的修正

下面重點分析鎖隔離級别與ANSI SQL的要求。這裡先給出P0定義：

P0 (Dirty Write): Transaction T1 modifies a data item. Another transaction T2 then further modifies that data item before T1 performs a COMMIT or ROLLBACK. If T1 or T2 then performs a ROLLBACK, it is unclear what the correct data value should be.

形式化表達為：

• P0: w1[x]...w2[x]...((c1 or a1) and (c2 or a2) in any order)

髒寫不好的一個原因是它可以違反資料庫一緻性，并且在沒有P0保護的情況下，系統無法通過恢複映像（image）來撤消更新（事務復原）。是以，ANSI SQL隔離應修改為要求所有隔離級别至少避免P0現象。

論文指出應該對 ANSI SQL 三個現象給出廣義的定義。先回顧ANSI SQL三個現象狹義解釋：

• A1: w1[x]...r2[x]...(a1 and c2 in either order) (Dirty Read)
• A2: r1[x]...w2[x]...c2...r1[x]...c1 (Fuzzy or Non-Repeatable Read)
• A3: r1[P]...w2[y in P]...c2....r1[P]...c1 (Phantom)

給出三個狹義解釋不能囊括如下銀行轉賬的場景：

• H1: r1[x=50]w1[x=10]r2[x=10]r2[y=50]c2 r1[y=50]w1[y=90]c1
• H2: r1[x=50]r2[x=50]w2[x=10]r2[y=50]w2[y=90]c2r1[y=90]c1
• H3: r1[P] w2[insert y to P] r2[z] w2[z] c2 r1[z] c1

表1中展示，“讀已送出”隔離的曆史禁止現象A1，“可重複讀”隔離的曆史禁止現象A1和A2，“可串行化”隔離的曆史禁止現象A1，A2和A3。考慮上面銀行轉賬場景：

• 場景1（H1）：事務T1将40元從x轉移到y，要求保持餘額總數為100，但T2讀到了總餘額為60的不一緻狀态。曆史H1不違反任何異常A1，A2或A3。但是廣義解釋的P1解決這個問題。
• 場景2（H2）：事務T2看到總餘額為140，交易都沒有讀取髒（即未送出）的資料。是以P1滿足。并且，沒有任何資料項被讀取兩次，也沒有謂詞範圍内的資料被更改。H2的問題是，當T1讀取y時，x的值已過期。如果T2再次讀取x，則會被更改。但由于T2不會讀兩次，A2不适用。但是廣義解釋的P2解決這個問題。
• 場景3（H3）：事務T1執行<搜尋條件>以找到雇員的清單。然後T2執行新的員工的插入，然後更新公司中的員工數量z。此後，T1将員工的數量讀出，并看到差異。這個曆史顯然是不可串行化的，但由于謂詞範圍沒有被通路兩次，是以它是被A3所允許的。但是廣義解釋的P3解決這個問題。

綜上，狹義解釋的A1，A2和A3有意想不到的缺點，是以廣義解釋的P1，P2和P3更加合理。同時，ANSI SQL隔離現象定義的不完整，還有一些異常仍然可能出現，必須定義新的現象來完成鎖的定義。此外，必須重新進行定義P3。廣義現象解釋如下：

• P0: w1[x]...w2[x]...(c1 or a1) (Dirty Write)
• P1: w1[x]...r2[x]...(c1 or a1) (Dirty Read)
• P2: r1[x]...w2[x]...(c1 or a1) (Fuzzy or Non-Repeatable Read)
• P3: r1[P]...w2[y in P]...(c1 or a1) (Phantom)

注意，ANSI SQL 中P3隻禁止對謂詞插入（和更新），而上面的P3的定義禁止任何滿足謂詞的寫被讀取，這裡的寫可以是插入，更新或删除。

根據上面定義的現象，将 ANSI SQL 隔離級别重新定義，如表3所示：

對于單版本曆史，容易得出 P0，P1，P2，P3 現象是“假”的鎖版本現象。實際，禁止 P0 排除了在第一個事務寫入資料項後第二個事務的寫，相當于在資料項（和謂詞）上持有長寫鎖。是以髒寫是不可能的。類似地，禁止P1 相當于對資料項進行了好形式的讀取。禁止 P2 表示資料項加上長讀鎖。最後，禁止 P3 意味着持有長謂詞讀鎖。是以，表3中基于上述現象定義的隔離級别與表2的鎖隔離級别是相同的。換句話說，P0，P1，P2和 P3 是對于鎖版本隔離級别的重新定義。

其他隔離類型

首先是遊标穩定（cursor stability），遊标穩定旨在防止丢失更新現象。

• P4 (Lost Update) : The lost update anomaly occurs when transaction T1 reads a data item and then T2 updates the data item (possibly based on a previous read), then T1 (based on its earlier read value) updates the data item and commits. 将上述曆史轉化為：
• P4: r1[x]...w2[x]...w1[x]...c1 (Lost Update) （注意P4隻是基于P0髒寫和P1髒讀，從鎖隔離的角度上來說隻是持有短讀鎖和長寫鎖，沒有達到鎖可重複讀P2（也就是說不持有長讀鎖））
• H4: r1[x=100] r2[x=100] w2[x=120] c2 w1[x=130] c1

如曆史 H4 所示，問題是即使T2送出，T2的更新也會丢失。x的最終值為T1寫入的130，P4 至少在讀已送出隔離級别，因為禁止 P0（事務執行第一次寫操作的資料項被另一個事務第二次寫入）或 P1（寫後送出前被讀取）的情況下允許出現 H4。當然，禁止 P2 也排除了 P4，因為 P2 是r1[x],w2[x]，（c1 or a1），包括了 P4 。是以，P4 可用于作為區分讀已送出和可重複讀強度中間的隔離級别。即 READ COMMITTED « Cursor Stability « REPEATABLE READ。

遊标穩定擴充了讀已送出隔離級别下對于SQL遊标的鎖行為。其提出遊标上的Fetching操作rc（read cursor）。rc要求在遊标的目前資料項上保持長讀鎖，直到遊标移動或關閉（可能通過送出關閉）。當然，遊标上的Fetching事務可以更新行（read cursor），即使遊标在随後的Fetch上移動，寫鎖也将保持在行上直到事務送出。rc1[x] 和以後的 wc1[x] 排除了介入的 w2 [x]。是以，針對遊标上的情況，提出現象 P4C：

• P4C：rc1[x] ... w2[x] ... w1[x] ... c1（Lost Update）

其次是快照隔離（Snapshot Isolation)。

在快照隔離下執行的事務始終從事務開始時起的資料（已送出）的快照中讀取資料。事務開始時擷取的時間戳稱為其開始時間戳（Start-Timestamp）。這一個時間戳可能為事務第一次讀之前的任何時間。事務運作在快照隔離中時，隻要可以維護其開始時間戳對應的快照資料，在就不會阻塞讀。事務的寫入（更新，插入和删除）也将反映在此快照中，如果事務第二次通路（即讀取或更新）資料，則能再次讀到。這個事務開始時間戳之後的其他事務的更新對于本次事務是不可見的。

快照隔離是一種多版本并發控制（Multiversion Concurrency Control，MVCC）。當事務T1準備好送出時，它将獲得一個送出時間戳（Commit-Timestamp），該值大于任何現有的時間戳。當其他事務T2送出了資料的送出時間戳在T1事務的間隔[Start-Timestamp，Commit-Timestamp]中，隻有T1與T2資料不重疊，事務才成功送出。否則，T1将中止。這個功能叫做先送出者成功（First-Committer-Wins），防止丢失更新（P4）。當T1送出時，其更改對于開始時間戳大于T1的送出時間戳的所有事務都可見。

快照隔離是一種多版本（MV）方法，是以單版本（SV）曆史不能正确地反映時間上的操作序列。在任何時候，每個資料項可能有多個版本，由活動的和已送出的事務寫入。事務必須讀取合适的版本。考慮上面提到的曆史H1，其表明在單值執行中需要P1。在快照隔離下，相同的操作序列将導緻多值曆史：

H1.SI：

r1[x0=50] w1[x1=10] r2[x0=50] r2[y0=50] c2

• r1[y0=50] w1[y1=90] c1

将MV曆史映射到SV曆史是在隔離層次中放置快照隔離的關鍵。例如，可以将H1.SI映射成的單值曆史：

• H1.SI.SV：r1[x=50] r1[y=50] r2[x=50] r2[y=50] c2 w1[x=10] w1[y=90] c1

快照隔離是不可串行化的，因為事務的讀在一個時刻，寫在另一個時刻。例如，考慮單值曆史：

• H5：r1[x=50] r1[y=50] r2[x=50] r2[y=50] w1[y=-40] w2[x=-40] c1 c2

H5 是不可串行化的，并且具有與快照隔離下事務相同的事務間資料流（事務讀取的版本沒有選擇）。這裡假設為x和y寫入一個新值的每個事務有保持x + y>0的限制，而T1和T2兩者都是隔離的，是以限制不能保持在H5中。

限制違反（Constraint violation）是一種通用和重要的并發異常類型。個别資料庫滿足多個資料項的限制（例如，鍵的唯一性，引用完整性，兩個表中的行的複制關系等）。

它們一起形成資料庫不變量限制謂詞C（DB）。如果資料庫狀态DB與限制一緻，則不變量為TRUE，否則為FALSE。事務必須保留限制謂詞以保持一緻性：如果資料庫在事務啟動時保持一緻，則事務送出時資料庫将一緻。如果事務讀取到違反限制謂詞的資料庫狀态，則事務将受到限制違反并發異常的影響。這種限制違反在[DAT]中稱為不一緻分析（inconsistent analysis）。

給出了幾個相關的定義。

• A5 (Data Item Constraint Violation) . Suppose C() is a database constraint between two data items x and y in the database. 這裡提出兩個由于違反限制引起的現象。
• A5A Read Skew Suppose transaction T1 reads x, and then a second transaction T2 updates x and y to new values and commits. If now T1 reads y, it may see an inconsistent state, and therefore produce an inconsistent state as output. In terms of histories, we have the anomaly:
• A5A: r1[x]...w2[x]...w2[y]...c2...r1[y]...(c1 or a1) (Read Skew)
• A5B Write Skew Suppose T1 reads x and y, which are consistent with C(), and then a T2 reads x and y, writes x, and commits. Then T1 writes y. If there were a constraint between x and y, it might be violated. In terms of histories:
• A5B: r1[x]...r2[y]...w1[y]...w2[x]...(c1 and c2 occur) (Write Skew)

不可重複度 P2 是讀傾斜的退化形式，其中令x=y。更典型地，事務讀取兩個不同但相關的項目（如引用完整性）。寫傾斜（A5B）可能來自銀行業務語義的限制，如隻要總共持有的餘額保持非負，賬戶餘額才能變為負值。如曆史H5中出現的異常。

在排除 P2 的曆史中，A5A 和 A5B 都不會出現，因為 A5A 和 A5B 都有T2寫入一個先前未被送出的T1讀取的資料項的情況。是以，現象 A5A 和 A5B 僅用于區分低于可重複讀取的隔離級别。

對于快照隔離，比讀已送出更強，即 READ COMMITTED « Snapshot Isolation。

證明：在快照隔離中，first-committer-wins排除了P0（髒寫入），并且時間戳機制阻止了P1（髒讀），是以快照隔離不比讀已送出弱。此外，A5A可能在讀已送出下，但不在快照隔離與時間戳機制下。是以 READ COMMITTED « Snapshot Isolation。

在單版本現象中，難以描述快照隔離曆史如何違反現象 P2。異常 A2 不能發生，因為快照隔離下的事務即使在另一個事務更新資料項之後也會隻讀取資料項的相同版本對應的值。然而偏寫（A5B）顯然會發生在快照隔離下（比如H5），并且在單值曆史解釋中已經提到，禁止了 P2 也會排除 A5B。是以，快照隔離承認可重複讀沒有曆史異常。

快照隔離下不會發生 A3 異常（幻讀）。在一個事務更新資料項集時，另一個事務多次謂詞讀的将始終看到相同的舊資料項集。但是可重複讀隔離級别可能會遇到 A3 異常。快照隔離禁止具有異常 A3 的曆史，但允許 A5B，而可重複讀則相反（允許 A3 禁止 A5B）。是以，REPEATABLE READ »« Snapshot Isolation。

但是，快照隔離（能排除 A3）并不排除 P3（謂詞讀事務送出前謂詞範圍内被另一事務寫入）。考慮一個限制，表示由謂詞确定的一組作業任務不能有大于8的小時數。T1讀取此謂詞，确定總和隻有7小時，并添加1小時持續時間的新任務，而并發事務T2做同樣的事情。由于兩個事務正在插入不同的資料項（以及不同的索引條目（如果有的話）），是以First-Committer-Wins不排除此情況，并且可能發生在快照隔離中。但是在任何等價的串行曆史中，在這種情況下會出現 P3 現象。

另外，快照隔離沒有幻讀（在 ANSI SQL 中狹義定義下的A3），因為每個事務都不會看到并發事務的更新。快照隔離曆史排除了現象 A1，A2 和 A3 。是以，在表1中的異常可串行化（ANOMALY SERIALIZABLE）的解釋語境下：ANOMALY SERIALIZABLE « SNAPSHOT ISOLATION。

快照隔離的“樂觀”并發控制方法對于隻讀事務具有明顯的并發優勢，但其對更新事務的好處仍然存在争議。

表4展示了上述提到的所有的隔離級别以及對應的現象：

綜上，作者認為原始 ANSI SQL隔離級别的定義存在嚴重問題。英文文字上的定義是模糊和不完整的，髒寫 P0 沒有被排除。同時建議 ANSI SQL 隔離級别替換為對應鎖隔離級别。同時将各種商業資料庫中實作的隔離級别進行比對，對應關系如圖2所示：

以上内容主要參考論文 A Critique of ANSI SQL Isolation Levels。

Part 3 快照隔離的發展

論文 A Critique of ANSI SQL Isolation Levels 中提出了快照隔離（Snapshot Isolation)的定義：

• 事務的讀操作從已送出（Committed）快照中讀取資料，快照時間可以是事務的第一次讀操作之前的任意時間，記為StartTimestamp；
• 事務準備送出時，擷取一個CommitTimestamp，它需要比現存的StartTimestamp和CommitTimestamp都大；
• 事務送出時進行沖突檢查，如果沒有其他事務在[StartTS, CommitTS]區間内送出了與自己的WriteSet有交集的資料，則本事務可以送出；
• 快照隔離允許事務用很舊的StartTS來執行，進而不被任何的寫操作阻塞，或者讀一個曆史資料。

這裡需要注意：

• 上述時間和空間沒有交集的檢查，主要是為了阻止LostUpdate的異常；
• 實作的時候通常利用鎖和LastCommit Map，送出之前鎖住相應的行，然後周遊自己的WriteSet，檢查是否存在一行記錄的LastCommit落在了自己的[StartTS, CommitTS]内；
• 如果不存在沖突，就把自己的CommitTS更新到LastCommit中，并送出事務釋放鎖。

仔細考慮上述快照隔離的定義，考慮如下幾個問題：

1. CommitTS的擷取：如何得到一個比現有的StartTS和CommitTS都大的時間戳，尤其是在分布式系統中；
2. StartTS的擷取：雖然上面提到的StartTS可以是一個很舊的時間，那麼StartTS是否需要單調遞增；
3. 送出時進行的沖突檢查是為了解決Lost Update異常，那麼對于這個異常來說，寫寫沖突檢查是否是充分且必要的；
4. 分布式、去中心的快照隔離級别該怎樣實作。

針對上述問題，下面進行展開。這裡将上述提到的快照隔離（SI）記為Basic SI。

分布式快照隔離

本節主要講解HBase、Percolator以及Omid在快照隔離方面工程實踐進展。

HBase

HBase中快照隔離是完全基于多個HBase表來實作的分布式SI：

• Version Table：記錄一行資料的最後的CommitTS；
• Committed Table：記錄CommitLog，事務送出時将commit log寫到這張表中可認為Committed；
• PreCommit Table：用作檢查并發沖突，可了解為鎖表；
• Write Label Table：用于生成全局唯一的Write Label；
• Committed Index Table：加速StartTS的生成；
• DS：實際存儲資料。

協定大緻實作如下：

• StartTS：從Committed Table中周遊找到單調連續遞增的最大送出時間戳，即前面不存在空洞（這裡的空洞指的是事務拿了CommitTS但沒有按照CommitTS順序送出）；
• Committed Index：為了避免擷取StartTS過程周遊太多資料，每個事務在獲得StartTS之後會寫到Committed Index Table中，之後的事務從這個時間戳開始周遊即可，相當于緩存了一下；
• read：需要判斷一個事務的資料是否送出了，去VersionTable和Committed Table檢查；
• precommit: 先檢查Committed Table是否存在沖突事務，然後在PreCommit Table記錄一行，再檢查PreCommitTable中是否存在沖突的事務；
• commit：拿到一個commitTS，在CommittedTable寫一條記錄，更新PreCommit Table。

HBase采用結構上解耦的方式實作分布式SI，所有的狀态都存儲到HBase中，每個場景的需求都用不同的表來實作，但這種解耦也帶來了性能損失。這裡将HBase實作的快照隔離記為HBaseSI。

Percolator

在2010年提出的Percolator在HBase的基礎上更加工程化，将涉及到的多個Table合并成了一個，在原有資料的基礎上增加了lock、write列：

• lock：用作是WW沖突檢查，實際使用時lock會區分Primary Lock和Secondary Lock；
• write：可了解為commit log，事務送出仍然走2PC，Coordinator決定Commit時會在write列寫一條commit log，寫完之後事務即認為Committed。

同時，作為一個分布式的SI方案，仍然需要依賴2PC實作原子性送出；而prewrite和commit過程，則很好地将事務的加鎖和2PC的prepare結合到一起，并利用Bigtable的單行事務，來避免了HBaseSI方案中的諸多沖突處理。這裡将Percolator實作的快照隔離記為PercolatorSI。

Omid

Omid是Yahoo的作品，同樣是基于HBaseSI，但和Percolator的Pessimistic方法相比，Omid是一種Optimistic的方式。其架構相對優雅簡潔，工程化做得也不錯，近幾年接連在ICDE、FAST、PVLDB發表文章。

Percolator的基于Lock的方案雖然簡化了事務沖突檢查，但是将事務的驅動交給用戶端，在用戶端故障的情況下，遺留的Lock清理會影響到其他事務的執行，并且維護額外的lock和write列，顯然也會增加不小的開銷。而Omid這樣的Optimistic方案完全由中心節點來決定Commit與否，在事務Recovery方面會更簡單；并且，Omid其實更容易适配到不同的分布式存儲系統，侵入較小。

ICDE 2014 的文章奠定Omid架構：

• TSO（TimestampOracle）：負責時間戳配置設定、事務送出；
• BookKeeper: 分布式日志元件，用來記錄事務的Commit Log；
• DataStore：用HBase存儲實際資料，也可适配到其他的分布式存儲系統。

TSO維護如下幾個狀态：

• 時間戳：單調遞增的時間戳用于SI的StartTS和CommitTS；
• lastCommit: 所有資料的送出時間戳，用于WW沖突檢測，這裡會根據事務的送出時間進行一定裁剪，使得在記憶體中能夠存下；
• committed：一個事務送出與否，事務ID用StartTS辨別，這裡記錄StartTS -> CommitTS的映射即可；
• uncommitted：配置設定了CommitTS但還未送出的事務；
• T_max：lastCommit所保留的低水位，小于這個時間戳的事務來送出時一律Abort。

這裡的lastCommit即關鍵所在，表明了事務送出時不再采用和Percolator一樣的先加鎖再檢測沖突的Pessimistic方式，而是：

• 将Commit請求發到TSO來進行Optimistic的沖突檢測；
• 根據lastCommit資訊，檢測一個事務的WriteSet是否與lastCommit存在時間和空間的重疊。如果沒有沖突，則更新lastCommit，并寫commit log到BookKeeper；
• TSO的lastCommit顯然會占用很多記憶體，并且成為性能瓶頸。為此，僅保留最近的一段lastCommit資訊，用Tmax維護低水位，小于這個Tmax時一律abort。

另外提出了一個用戶端緩存Committed的優化方案，減少到TSO的查詢；在事務的start請求中，TSO會将截止到start時間點的committed事務傳回給用戶端，進而用戶端能夠直接判斷一個事務是否已經送出，整體架構如下圖所示。

在FAST 2017中，Omid對之前的架構進行了調整，做了一些工程上的優化：

• commit log不再存儲于BookKeeper，而是用一張額外的HBase表存儲；
• 用戶端不再緩存committed資訊，而是緩存到了資料表上；是以大部分時候，使用者讀資料時根據commit字段就能夠判斷這行資料是否已經送出了。

在PLVDB 2018中，Omid再次進行了大幅的工程優化，覆寫了更多的場景：

• Commit Log不再由TSO來寫，而是offload到用戶端，提高了擴充性，也降低了事務延遲；
• 優化單行讀寫事務，在資料上增加一個maxVersion的記憶體記錄，實作了單行的讀寫事務不再需要進行中心節點校驗。

去中心化快照隔離

上述都是針對分布式SI的實作，它們都有一個共同特征：保留了中心節點，或用于事務協調，或用于時間戳配置設定。對于大規模或者跨區域的事務系統來說，這仍然存在風險。針對這點，就有了一系列對去中心化快照隔離的探索。

Clock-SI

Clock-SI首先指出，Snapshot Isolation的正确性包含三點：

• Consistent Snapshot：所謂Consistent，即快照包含且僅包含Commit先于SnapshotTS的所有事務；
• Commit Total Order：所有事務送出構成一個全序關系，每次送出都會生成一個快照，由CommitTS辨別；
• Write-Write Conflict: 事務Ti和Tj有沖突，即它們WriteSet有交集，且[SnapshotTS, CommitTS]有交集。

基于這三個點，Clock-SI提出了如下的算法：

• StartTS：直接從本地時鐘擷取。
• Read：當目标節點的時鐘小于StartTS時，進行等待，即下圖中的Read Delay；當事務處于Prepared或者Committing狀态時，也進行等待；等待結束之後，即可讀小于StartTS的最新資料；這裡的Read Delay是為了保證Consistent Snapshot。
• CommitTS：區分出單Partition事務和分布式事務，單Partition事務可以使用本地時鐘作為CommitTS直接送出；而分布式事務則選擇max{PrepareTS}作為CommitTS進行2PC送出；為了保證CommitTS的全序，會在時間戳上加上節點的id，和Lamport Clock的方法一緻。

Commit：不論是單partition還是多partition事務，都由單機引擎進行WW沖突檢測。

Clock-SI有幾點創新：

• 使用普通的實體時鐘，不再依賴中心節點配置設定時間戳。
• 對單機事務引擎的侵入較小，能夠基于一個單機的Snapshot Isolation資料庫實作分布式的SI。
• 區分單機事務和分布式事務，幾乎不會降低單機事務的性能，分布式使用2PC進行原子性送出。

在工程實作中，還需考慮這幾個問題：

• StartTS選擇：可以使用較舊的快照時間，進而不被并發事務阻塞；
• 時鐘漂移：雖然算法的正确性不受時鐘漂移的影響，但時鐘漂移會增加事務的延遲，增加abort rate；
• Session Consistency：事務送出後将時間戳傳回給用戶端記為latestTS，用戶端下次請求帶上這個latestTS，并進行等待。

論文實驗結果很突出，不過正确性論證較為簡略，還有待進一步證明。

ConfluxDB

如果說Clock-SI還有什麼不足，那可能就是依賴了實體時鐘，在時鐘漂移的場景下會對事務的延遲和abort rate造成影響。能否不依賴實體時鐘，同時又能夠實作去中心化呢？

ConfluxDB提出的方案中，僅僅依賴邏輯時鐘來捕獲事務的先于關系，基于先于關系來檢測沖突：

• 當事務Ti準備送出時，2PC的Coordinator向所有參與者請求事務的concurrent(Ti)清單，這裡的concurrenct(Ti)定義為begin(Tj) < commit(Ti)的事務；
• Coordinator在收到所有參與者的concurrent(Ti)之後，将其合并成一個大的gConcurrent(Ti)，并發回給所有參與者；
• 參與者根據gConcurrent(Ti)，檢查是否存在一個事務Tj，dependents(Ti,Tj) ∧ (Tj ∈ gConcurrent(Ti)) ∧ (Tj ∈ serials(Ti))，即存在一個事務Tj，在不同的partition中有不同的先後關系，違背了Consistent Snapshot的規則；
• 參與者将沖突檢測的結果發回給Coordinator，Coordinator據此決定是Commit還是Abort；
• 除此之外Coordinator需要給這個事務生成一個CommitTS，這裡選擇和ClockSI類似的方式，commitTS=max{prepareTS}，這裡的prepareTS和commitTS會按照Logical Clock的方式在節點之間傳遞。

ConfluxDB的這種方案不需要依賴實體時鐘，不需要任何wait，甚至不需要單機的事務引擎支援讀時間點快照的功能。但是這個方案的不足是，可能Abort rate并不是很好，以及在執行分布式事務時的延遲問題。

Generalized SI

Generalized SI将Snapshot Isolation應用到Replicated Database中，使得事務的Snapshot可以從複制組的從節點讀取。這帶來的意義有兩點，使用一個舊的快照，不會被目前正在運作的事務阻塞，進而降低事務延遲；而從Secondary節點讀取資料，則可以實作一定程度上的讀寫分離，擴充讀性能。

Parallel SI

上面的方案中，可以将讀請求offload到Secondary節點，一定程度上能夠擴充讀性能。那麼繼續将這個思路延伸一下，能不能把事務的送出也交給Secondary節點來執行呢？

這就是Parallel Snapshot Isolation的思路，在跨區域複制的場景下，業務通常會有地理位置局部性的要求，在上海的使用者就近把請求發到上海的機房，在廣州的使用者把請求發到廣州的機房；并且在實際的業務場景中，往往可以放松對一緻性和隔離性的要求。Parallel放棄了Snapshot Isolation中對Commit Total Order的限制，進而實作了多點的事務送出。在通用資料庫中可能很難使用這樣的方案，但實際的業務場景中會很有價值。

Serializable SI

Snapshot Isolation所差別于Serializable的是Write Skew異常，為了解決這個異常，可以基于Snapshot Isolation進行優化，并且盡量保留Snapshot Isolation的優秀性質，進而提出了Serializable SI。

論文 Serializable isolation for snapshot databases 是 Alan D. Fekete 和 Michael J. Cahill 在2009年發表的，是早期研究SSI的理論成果。

論文從串行化圖理論說起，在Multi-Version的串行圖中，增加一種稱之為RW依賴的邊，即事務T1先寫了一個版本，事務T2讀了這個版本，則産生RW依賴。當這個圖産生環時，則違背了Serializable。

在論文中作者證明，SI産生的環中，兩條RW邊必然相鄰，也就意味着會有一個pivot點，既有出邊也有入邊。那麼隻要檢測出這個pivot點，選擇其中一個事務abort掉，自然就打破了環的結構。算法的核心就在于動态檢測出這個結構，是以會在每個事務記錄一些狀态，為了減少記憶體使用，使用inConflict和outConflict兩個bool值來記錄；在事務執行讀寫操作的過程中，會将與其他事務的讀寫依賴記錄于這兩個狀态中。

• 雖然用bool值減少了記憶體使用，但顯然也增加了false positive，會導緻一部分沒有異常的事務被abort。
• 據文中的實驗結果表明，性能好于S2PL（嚴格兩階段鎖，可實作串行化），abort較低，給Snapshot Isolation帶來的開銷也比較小。
• 但據後來的PostgreSQL的SSI實作，為了減少記憶體占用仍需要不少的工作量，有興趣可參考 Serializable Snapshot Isolation in PostgreSQL。

Write SI

Yabandeh在 論文 A critique of snapshot isolation 中提出Write-Snapshot Isolation。作者首先批判Basic SI，因為Basic SI給人造成了一種誤導：進行寫寫沖突檢測是必須的。文章開篇即提出，SI中的LostUpdate異常，不一定需要阻止WW沖突；換成RW檢測，允許WW沖突，既能夠阻止LostUpdate異常，同時能夠實作Serializable，一舉兩得。

為何WW檢測不是必須的？簡要論證一下，在MVCC中，寫沖突的事務寫的是不同的版本，為何一定會有沖突？實際上隻有兩個事務都是RW操作時才有異常，如果其中一個事務隻有W操作，并不會出現Lost Update；換言之，未必要檢測WW沖突，RW沖突才是根源所在。

基于RW沖突檢測的思想，作者提出Write Snapshot Isolation，将之前的Snapshot Isolation命名為Read Snapshot Isolation。如下圖中：

• TXNn和TXNc'有沖突，因為TXNc'修改了TXNn的ReadSet;
• TXNn和TXNc沒有沖突，雖然他們都修改了r'這條記錄，Basic SI會認為有沖突，但Write SI認為TXNc沒有修改TXNn的ReadSet，則沒有RW沖突。

如何檢測RW沖突：事務讀寫過程中維護ReadSet，送出時檢查自己的ReadSet是否被其他事務修改過。但實際也不會這麼簡單，因為通常維護ReadSet的開銷比WriteSet要大，且這個沖突檢查如何做，難道加讀鎖？是以在原文中，作者隻解釋了中心化的Write SI如何實作（BadgerDB使用了這個算法，實作了支援事務的KV引擎）。至于去中心化的實作，可從CockroachDB找到一點影子。

不過RW檢測會帶來很多好處：

• 隻讀事務不需要檢測沖突，它的StartTS和CommitTS一樣；
• 隻寫事務不需要檢測沖突，它的ReadSet為空；
• 更重要的是，這種算法實作的隔離級别是Serializable而不是Snapshot Isolation。

綜合上述内容，為實作串行化，傳統上隻能采用基于鎖的并發控制，由于性能問題，很難在實際工程中應用。Serializable SI為高性能的實作可串行化，提供了一種新的路徑。

以上内容主要參考 Snapshot Isolation綜述。

寫在最後

在wiki上PostgreSQL對SSI解釋有這麼一句話：Documentation of Serializable Snapshot Isolation (SSI) in PostgreSQL compared to plain Snapshot Isolation (SI). These correspond to the SERIALIZABLE and REPEATABLE READ transaction isolation levels, respectively, in PostgreSQL beginning with version 9.1。是以，在讨論任何一款資料庫産品實作的隔離級别時，必須了解該隔離級别背後實作的算法原理。

文章來源：KaiwuDB_https://juejin.cn/post/7052496886061596709