資料庫事務隔離標準分析

來自專欄分散式與存儲技術108 人贊了文章

1 概述與背景

這是資料庫事務原理和工程實踐系列文章的第一篇，本文主要在Jim Gray的論文<A Critique of ANSI SQL Isolation Levels>基礎上分析關係資料庫的事務隔離級別標準和不同隔離級別情況下的行為。第2節主要討論ANSI標準的下的隔離級別，第3節主要討論基於悲觀鎖實現的事務隔離級別，第4節主要討論基於多版本技術的事務隔離，最後總結排序本文討論到的各個隔離級別。

ACID是關係資料庫的一組重要特性，其中Isolation（隔離性）描述了資料庫允許多個並發事務同時對其數據進行讀寫和修改的能力，隔離性可以防止多個事務並發時由於交錯執行而導致數據的不一致。在最極端的情況下，資料庫完全串列化執行每一個事務，所有事務之間遵守全序關係，在這種情況下，不存在並發事務間的隔離問題，但是在實際工程實踐中，處於對資料庫性能吞吐量的考慮，允許多個事務之間按照一定的規則，打破串列話的全序關係，ANSI SQL Isolation Levels即規定了這種「規則」，通過將隔離性劃分為4個級別，來換取多層級的事務間並發能力（即資料庫的吞吐能力）。

注，本文內容融入了作者個人的理解，並沒有嚴格遵守<A Critique of ANSI SQL Isolation Levels>原文的內容；其中cursor stability隔離級別將在後續文章中討論，快照隔離級別與ANSI標準異象的比較也有所不同。

2 ANSI事務隔離級別

ANSI SQL-92標準(http://www.contrib.andrew.cmu.edu/~shadow/sql/sql1992.txt)將資料庫並發事務間的隔離性行為劃分為3種"異象(phenomena)"，從低到高的自然語言定義依次為：

1. P1 臟讀 ("Dirty read"): SQL-transaction T1 modifies a row. SQL- transaction T2 then reads that row before T1 performs a COMMIT. If T1 then performs a ROLLBACK, T2 will have read a row that was never committed and that may thus be considered to have never existed.
2. P2 不可重複讀 ("Non-repeatable read"): SQL-transaction T1 reads a row. SQL- transaction T2 then modifies or deletes that row and performs a COMMIT. If T1 then attempts to reread the row, it may receive the modified value or discover that the row has been deleted.
3. P3 幻讀 ("Phantom"): SQL-transaction T1 reads the set of rows N that satisfy some <search condition>. SQL-transaction T2 then executes SQL-statements that generate one or more rows that satisfy the <search condition> used by SQL-transaction T1. If SQL-transaction T1 then repeats the initial read with the same <search condition>, it obtains a different collection of rows.

通過依次禁止這三種異象，ANSI確定了4種標準隔離級別，如下表所示：

如標準文檔所述，禁止了P1/P2/P3異象的事務即滿足Serializable級別，但矛盾的是，標準文檔中對Serializable又做了如下說明：

The execution of concurrent SQL-transactions at isolation level SERIALIZABLE is guaranteed to be serializable. A serializable execution is defined to be an execution of the operations of concurrently executing SQL-transactions that produces the same effect as some serial execution of those same SQL-transactions.

它要求多個並發事務執行的效果與某種串列化執行的效果一致，但是僅僅禁止P1/P2/P3異象，並不一定能夠保證「serial execution」的效果，因此論文中將ANSI Serializable稱為Anomaly Serializable。

P1/P2/P3的形式化描述

根據標準文檔的定義，可以將這三種異象使用形式化語言描述如下，稱為A1/A2/A3（其中w1[x]表示事務1寫入記錄x，r1表示事務1讀取記錄x，c1表示事務1提交，a1表示事務1回滾，r1[P]表示事務1按照謂詞P的條件讀取若干條記錄，w1[y in P]表示事務1寫入記錄y滿足謂詞P的條件）：

• A1 臟讀：w1[x] ... r2[x] ... (a1 and c2 in any order)

• A2 不可重複讀：r1[x] ... w2[x] ... c2 ... r1[x] ... c1

• A3 幻讀：r1[P] ... w2[y in P] ... c2 ... r1[P] ... c1

上述A1/A2/A3形式化描述，根據標準定義的P1/P2/P3異象的自然語言描述轉化而來，但是ANSI標準定義的異象只針對了單個記錄或謂詞描述，對於多條記錄需滿足業務一致性的場景並未能覆蓋（比如兩個賬戶間轉賬要求餘額總和不變），舉例如下：

• H1：r1[x=50]w1[x=10] r2[x=10]r2[y=50] c2 r1[y=50]w1[y=90] c1
• 事務1執行賬戶x向賬戶y轉賬40，事務2讀取到了進行到了一半的事務1（Read Uncommitted），破壞了餘額總和的一致性
• 因為事務1並未回滾，H1的行為並不符合A1的形式化定義
• H2：r1[x=50] r2[x=50]w2[x=10]r2[y=50]w2[y=90] c2 r1[y=90] c1
• 事務2執行賬戶x向賬戶y轉賬40，事務1在事務2提交前後讀取到了破壞餘額總和一致性的數據（Unrepeatable Read）
• 因為事務1並未重複讀取記錄x，H2的行為並不符合A2的形式化定義
• H3：r1[P] w2[insert y to P] r2[z] w2[z] c2 r1[z] c1
• 事務2增加新僱員並更新僱員總數z，事務1在事務2提交前後讀取到了破壞僱員列表與僱員總數的一致性的數據（Phantom）
• 因為事務1並未重複讀取謂詞P指定的數據集合，H3的行為並不符合A3的形式化定義

因為要增強對上述H1/H2/H3異象的約束，論文將A1/A2/A3的形式化描述稱為「狹義的描述(strict interpretations)」，然後增加了「廣義的描述(broad interpretation)」，去除了strict interpretations中對事務提交、回滾和數據讀取範圍的約束，只保留事務之間讀寫的時序關係，即事務之間只要包含如下時序的操作，即可能產生包含H1/H2/H3在內的異象，如下：

• P1 臟讀：w1[x] ... r2[x] ... ((c1 or a1) and (c2 or a2) in any order)
• P2 不可重複讀：r1[x] ... w2[x] ... ((c1 or a1) and (c2 or a2) in any order)
• P3 幻讀：r1[P] ... w2[y in P] ... ((c1 or a1) and (c2 or a2) in any order)

在上述形式化描述下，禁止P1即可禁止H1，禁止P1/P2即可禁止H2，禁止P1/P2/P3即可禁止H3。至此，ANSI標準隔離級別定義的三種異象，可以被擴展為適用範圍更廣的的P1/P2/P3的形式化定義，這種隔離級別定義被論文稱之為「phenomena-based」，即基於「異象」的隔離級別定義。

3 基於鎖的事務隔離

在上一節的討論中，P1/P2/P3這三種形式化定義指出了三個不同級別的異象，但是並沒有與實際的工程實踐相關聯，在本小節中，我們將介紹基於鎖(lock base)的事務隔離實現，並且將不同的加鎖行為與上述三種異象關聯起來討論。

在討論加鎖行為之前，需要定義如下幾種讀寫和鎖的操作：

• Predicate lock 謂詞鎖(gap鎖)：Locks on all data items satisfying the search condition
• Well-formed Writes 合法write：Requests a Write(Exclusive) lock on each data item or predicate before writing
• Well-formed Reads 合法read：Requests a Read(share) lock on each data item or predicate before reading
• Long duration locks 長周期鎖：Locks are held until after the transaction commits or aborts
• Shord duration locks 短周期鎖：Locks are released immediately after the action completes

通過組合上述讀寫鎖操作，我們能夠構建不同級別的事務隔離標準。因為「No Well-formed Writes」或「Short duration write locks」的保護等級可能造成dirty write，它的約束已經低到難以找到實際應用場景，我們將其忽略，因此所有寫入操作都使用「Well-formed Writes, Long duration Write locks」，通過對讀取操作應用不同的保護等級，得到4種隔離級別，使用locking前綴與ANSI隔離級別區分，如下表所示：

將locking標記的四種隔離級別與ANSI隔離級別對比：

• Well-formed Reads, Short duration read lock 禁止了 P1發生，r2[x]將被讀鎖阻塞，直到事務1提交或回滾
• Well-formed Reads, Long duration data-item Read locks, Short duration Read Predicate locks 禁止了P2發生，w2[x]將被寫鎖阻塞，直到事務1提交或回滾
• 其中Short duration Read Predicate locks的作用論文中並沒有說明，實際上它保護了r[P]的一致性，保證r[P]讀取到的多行數據是一個「well-formed history」
• Well-formed Reads, Long duration Read locks 禁止了P3發生，w2[y in P]將被謂詞寫鎖阻塞，直到事務1提交或回滾

4 基於快照的事務隔離

對於基於鎖實現事務隔離的資料庫，讀寫、寫寫事務之間也可能因為鎖衝突而被阻塞，資料庫的整體吞吐能力受到比較大的限制，特別是在目前多核的CPU條件下，難以充分發揮計算能力。因此現代關係型資料庫和NewSQL，比如MySQL/Oracle/PostgreSQL/OceanBase/TiDB等，都使用多版本並發控制(mvcc)技術，來實現事務隔離，它的核心設計思想是，為數據的每次修改保存一個用時間戳標記的版本，數據讀取不需要加鎖，而是在讀取事務開始的時候獲取當前時間戳(snapshot)，對於每條數據，將版本號小於snapshot的最大已提交版本的內容作為讀取結果返回。

Snapshot Isolation保證只讀事務與讀寫事務相互不阻塞，只讀事務通過讀取合法的歷史快照，保證了讀取到的數據的一致性，我們在快照隔離下與A1/A2/A3逐個對比分析：

• P1描述的w1[x] ... r2[x] ...操作時序不可能出現，因為在快照隔離下，實際的操作時序為w1[x] ... r2[last version of x] ...，因此可知快照隔離禁止P1
• P2描述的r1[x] ... w2[x] ... 它實際的操作時序為r1[x] ... w2[new version of x] ...，可以知道快照隔離也禁止了P2。至此，我們可以確定快照隔離的效果至少大於Read Committed
• P3描述的r1[P] ... w2[y in P] ... 它實際的操作時序為r1[P] ... w2[new version of y in P] ...，可以知道快照隔離也禁止了P3，達到了第2小節中ANSI的Anomaly Serializable級別

但是，從上一小節基於鎖的隔離級別定義來分析，快照隔離的安全級別可能並沒有那麼高，我們來看如下兩種異象的形式化描述：

• A5A Read Skew: r1[x]...w2[x]...w2[y]...c2...r1[y]...(c1 or a1)
• A5B Writer Skew: r1[x]...r2[y]...w1[y]...w2[x]...(c1 and c2 occur)
• 擴展的Write Skew（並非來自原文）：r1[P]...r2[P]...w1[x]...w2[y]...(c1 and c2 occur)

快照隔離性高於Read Committed：第一，考慮到快照隔離讀已提交的數據版本的特性，禁止了P1，因此保證至少不低於Read Committed。第二，A5A的Read Skew異象符合P2的定義，並且從一致性的角度分析，事務1對x和y的讀取的兩個值不在線性的歷史中，可能會違背某種外部約束（比如保證x+y的和為一個常量），因此Read Committed隔離級別下允許A5A Read Skew異象。總和以上兩點，我們可以得出結論，快照隔離性高於Read Committed。

快照隔離性與Repeatable Read不相容：考慮到快照隔離能夠保證讀取到的數據在一個一致的歷史快照上，禁止了P1/P2/P3，因此保證不低於ANSI的Anomaly Serializable級別；但是，另一方面，經典的快照隔離對於多寫衝突是基於First- committer-wins的處理方式，依賴衝突的事務間至少修改同一條記錄（現代快照隔離有更優的SSI，我們將在後續的文章中介紹）無法避免上述A5B Write Skew的兩種異象，而基於鎖事項的Repeatable Read級別卻可以禁止A5B。快照隔離與Repeatable Read雙方禁止的異象，有可能在對方出現，因此他們的隔離性無法相比較。

5 總結

從前面幾個小節的隔離性分析來看，我們可以得到如下幾種隔離級別的關係：

Read Uncommitted < Read Committed < (Repeatable Read >< Snapshot) < Serializable

本文首先介紹了ANSI基於「異象」的隔離級別標準，並分析了其狹義和廣義的描述；然後介紹了基於鎖的隔離級別標準，與ANSI隔離級別進行了比較；最後分析快照隔離級別，在ANSI隔離級別標準基礎上，提出了兩種新的「異象」，得出快照隔離在幾種標準隔離級別特性中的位置。