Part 1 事務簡介

事務的定義

事務（transaction）是資料庫系統中保證一致性與執行可靠計算的基本單位。當確定了查詢的執行策略並將其翻譯成資料庫操作原語後，將以事務為單位執行查詢。

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

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

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

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

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

事務的性質

事務ACID四個性質：

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

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

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

一致性(consistency):事務是能夠正確的將資料庫從一個一致狀態變換到另一個一致狀態的程序。驗證一個事務是否具有一致性是完整性實施所涉及到的工作。如何保證事務一致性是並發控制機制的目的。
隔離性( isolation) ：在事務提交前，一個執行中的事務不能向其他並發事務透露自己的執行結果。保證事務隔離性的一個原因在於，保護事務的一致性。
持久性(durability)：如果一個事務已經提交，那麼它產生的結果是永久的，這一結果不能從資料庫中抹去。持久性會引入資料庫恢復（database recovery）問題。

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

事務的類型

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

平面事務（flat transaction）：有一個起始點（Begin_transaction）和一個結束點（End_transaction）。
嵌套事務（nested transaction）：一個事務中包含其他具有單獨的起始點和提交點的事務。
工作流（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中，並提交事務釋放鎖。

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

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

針對上述問題，下面進行展開。這裡將上述提到的快照隔離（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

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

Part 1 事務簡介

Part 2 事務的隔離級別

Part 3 快照隔離的發展