568      阿裏雲  技術社區[雲棲]

A Critique of ANSI SQL Isolation Levels 論文翻譯

A Critique of ANSI SQL Isolation Levels
對ANSI SQL 隔離級別的批評

     摘要：ANSI SQL-92 [MS，ANSI]根據phenomena（可譯為現象，讀時現象）定義了隔離級別：髒讀，不可重複讀和幻讀。本文顯示，這些phenomena和ANSI SQL定義無法正確表征幾個流行的隔離級別，包括對於不同隔離級別標準的鎖實現。本文調查了phenomena說明中的歧義，並提出了更正式的說明;此外，介紹了更好地表征隔離類型的新phenomena。最後，定義了一個稱為快照隔離的重要的多版本隔離類型。

1.簡介

在不同的隔離級別運行並發事務可以讓程序員在保證正確性的條件下權衡並發和吞吐量。較低的隔離級別會增加事務並發性，從而有可能讓事務遵守模煳或不正確的數據庫狀態。令人驚訝的是，可以在一些事務在最高的隔離級別（完全可串行化）執行時，並發執行在較低隔離級別運行的事務（讀未提交或讀過時數據）[GLPT]。當然，以較低隔離級別運行的事務可能會產生無效數據。程序員必須防止以較高隔離級別運行的後續事務訪問這些無效數據並傳播此類錯誤。

ANSI / ISO SQL-92規範[MS，ANSI]定義四個隔離級別：（1）讀未提交（READ UNCOMMITTED），（2）讀已提交（READ COMMITTED），（3）可重複讀（REPEATABLE READ），（4）可串行化（SERIALIZABLE）。

這些級別是使用經典的串行化定義和三個禁止的操作子序列來定義的，被命名為phenomena，包括：髒讀，不可重複讀和幻讀。phenomena的概念在ANSI規範中沒有明確定義，但是規範表明phenomena是可能導致異常（anomalies）（也許是不可串行化的）行為的操作子序列。當提出對ANSI Phenomena進行添加的建議時，我們將參考這些異常（anomalies）。如後文所示，異常和phenomena之間有一個技術上的區別，但這個區別對於一般的理解並不重要。

ANSI隔離級別與鎖調度器（lock schedulers）的行為有關。一些鎖調度器允許事務改變其鎖請求的範圍和持續時間，從而偏離純粹的兩階段鎖。這個想法是由[GLPT]引入的，它以三種角度定義了一致性度（Degree of consistency）：鎖，數據流圖和異常。通過phenomena（或異常）定義隔離級別旨在允許不基於鎖實現的SQL標準。

本文介紹了定義隔離級別的phenomena方法的一些缺點。三個ANSI phenomena是不明確的，即使在最寬鬆的解釋中也不排除執行曆史中可能出現的一些異常行為。這導致一些反直覺的結果。特別地，基於鎖的隔離級別與等效ANSI phenomena有不同的特性。而商業數據庫係統通常使用鎖實現隔離級別，所以情況很尷尬。此外，ANSI phenomena不能區分出商業係統中許多類流行的隔離級別的行為。本文提出了表征這些隔離級別的其他phenomena。

第2節介紹了隔離級別的基本術語，定義了ANSI SQL和鎖隔離級別。

第3節探討了ANSI隔離級別的一些缺點，並提出了一個新的phenomena。還定義了其他流行的隔離級別。這些定義映射了ANSI SQL隔離級別和1977年[GLPT]中定義的一致性度。它們還包括Chris Date定義的遊標穩定（Cursor Stability）和可重複讀[DAT]。在統一框架下討論隔離級別可以減少獨立術語產生的誤解。

第4節介紹了一種稱為快照隔離的多版本並發控製機製，可以避免使用ANSI SQL phenomena，但不能串行化。快照隔離本身是有趣的，因為它提供了一個位於讀已提交和可重複讀之間隔離級別。有一種新的方法學（在本次會議文件的較長版本中提供）將多版本數據的隔離級別規約到經典的單版本鎖定可串行化（single-version locking serializability）理論。

第5節探討了一些新的異常來區分第3和第4節引入的隔離級別。這裏提出的擴展ANSI SQL phenomena缺乏表征快照隔離和遊標穩定的能力。

第6節提出了一個總結和結論。

2.隔離定義

2.1序列化概念

文獻[BHG，PAP，PON，GR]中已經很好地說明了事務和鎖的概念。接下來的幾段會回顧這些文章裏使用的術語。

事務（transaction）意為一組合並成組的操作，能將數據庫從一個一致的狀態轉換到另一個狀態。曆史（history）意為將一組事務的交錯執行建模成其操作排序後的線性操作序列，其中操作（operation）意為某特定數據項的讀取和寫入（如插入，更新和刪除）。如果曆史中對於相同數據項的兩個操作由不同事務執行，並且至少其中一個操作寫入數據項（item），則稱這兩個操作衝突（conflict）（譯者注：可看作數據相關）。在[EGLT]之後，該定義對“數據項”的含義進行了廣泛的解釋：它可以是表行，頁麵上的空間，整個表或通信對象（例如隊列上的消息）。衝突操作也可能發生在由謂詞鎖（predicate lock）保護的一組數據項上或者單個數據項上。

特定曆史能生成出多個事務之間的以時間為軸的數據流依賴圖（dependency graph）。曆史中提交的事務的操作表示為點。如果事務T1的操作op1與曆史中的事務T2的操作op2衝突，則<op1，op2>成為依賴圖中的邊。（譯者注：也就是說以操作為點，衝突為邊，構造出依賴圖）。如果說兩個曆史是相等的，那麼曆史中提交的事務和依賴圖都相同。曆史是可串行化（Serializable）的，意味著曆史可以等同於一個串行曆史（serial history）——也就是說，它的依賴圖（多個事務間基於時序的數據流圖）與依次串行執行多個事務的曆史的依賴圖相同。

2.2 ANSI SQL隔離級別

ANSI SQL隔離設計人員尋求一種允許許多不同實現的定義，而不僅僅是基於鎖的。他們使用以下三種phenomena定義了隔離：

P1（髒讀）：事務T1修改數據項。另一個事務T2則在T1執行COMMIT或ROLLBACK之前讀取該數據項。如果T1 然後執行ROLLBACK，則T2讀取了一個從未提交的數據項。

P2（不可重複讀或Fuzzy Read）：事務T1讀取數據項。另一個事務T2則修改或刪除該數據項並提交。如果T1嚐試重新讀取數據項，則它會看見修改後的值或發現數據項已被刪除。

P3（幻讀（Phantom））：事務T1讀取滿足一些<搜索條件>的一組數據項。事務T2然後創建滿足T1的<搜索條件>並提交的數據項。如果T1然後使用相同的<搜索條件>重複讀取，它將獲得與第一次讀取不同的組數據項。

這些現象都不會發生在串行曆史上。因為通過串行化定理，它們不能發生在可串行化的曆史中[EGLT, BHG Theorem 3.6, G R Section 7.5.8.2, PON Theorem 9.4.2].

由讀取，寫入，提交（commit）和中止（abort）組成的曆史記錄可以用簡寫符號表示：“w1 [x]”表示數據項x上的事務1的寫入（數據項被“修改”），而“r2 [x]”表示事務2對x的讀取。事務1滿足謂詞P的讀取和寫入一組記錄分別由r1 [P]和w1 [P]表示。事務1的提交和中止（ROLLBACK）分別被記為“c1”和“a1”。

Phenomena P1可能會被重新表述為不允許以下情況：

（2.1）w1 [x]. . . r2 [x] . . . (a1 and c2 in either order)

P1的語義是不明確的（譯者注：語義為第二個提交了的事務讀到了第一個中止事務寫的數據）。實際上並不強調T1一定要中止;它隻是指出，如果這種情況發生可能會發生不一致。一些看過P1說明的人解釋為：

（2.2） w1[x]...r2[x]...((c1 or a1) and (c2 or a2) in any order)

P1的（2.2）變體不允許曆史中有T1修改數據項x，然後T2在T1提交或中止之前讀取數據項這種操作序列。它不強調T1中止或T2提交。

定義（2.2）對P1比（2.1）更為寬鬆，因為它禁止所有四個可能的事務T1和T2的提交中止順序，而（2.1）隻禁止四個中的兩個。解釋（2.2）作為P1的含義，禁止在將來出現異常情況的執行順序。我們稱（2.2）是P1的寬鬆解釋（loose interpretation），（2.1）是P1的嚴格解釋。解釋（2.2）規定了可能導致phenomena的現象，而（2.1）規定了實際的異常。分別表示為P1和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)

類似地，phenomena P2和P3也具有嚴格和寬鬆的解釋，P2和P3為寬鬆解釋，A2和A3為嚴格解釋（譯者注：P表示異常的讀現象的操作序列，A表示造成數據不一致的操作序列）：

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

第3節分析了更多的已經開發出來的替代概念，並提出需要針對phenomena進行寬鬆的解釋。注意到ANSI SQL P3的英文語義隻是禁止謂詞（範圍內的）插入，但是上述P3完全禁止在讀滿足謂詞的元組集合後，對滿足謂詞的元組進行任何寫入（插入，更新，刪除）。

本文稍後討論多值曆史（multi-valued history）的概念（MV-history for short，見[BHG]，第5章）。現在不詳細介紹，多版本係統中可能會同時存在多個版本的數據項。任何讀操作必須明確指定讀取哪個版本。已經有文章嚐試將ANSI隔離級別定義與多版本係統以及基於標準鎖調度器（locking scheduler）的單版本係統（SV-histories）相關聯。即使如此，P1，P2和P3 phenomena的語義也僅限於單版本的曆史。我們在下一節中解釋它們。

ANSI SQL通過表1的矩陣定義了四個級別的隔離。每個隔離級別的特征是事務中禁止發生的（鬆散或嚴格的解釋的）phenomena。但是，ANSI SQL規範沒有僅根據這些phenomena來定義可串行化隔離級別。 “ANSI”中的4.28“SQL事務”指出，可串行化隔離級別必須提供“共識的完全可串行化的執行”。與這個額外的附加條件相比，這個表導致了一個常見的誤解，即不允許三個phenomena意味著可串行化。不允許這三種phenomena的曆史在表1中被稱為異常可串行化（ANOMALY SERIALIZABLE）（譯者注：異常可串行化意為基於禁止異常（或phenomena）的可串行化，並非“真正的”可串行化）。

由於在曆史中寬鬆解釋遠遠多於嚴格解釋，而且隔離級別是由它們被禁止經曆的phenomena所定義的。我們在第3節中對寬鬆解釋的討論意味著我們想討論更多的限製性隔離級別（更多種曆史將被禁止）。但是第3節顯示，即使對P1，P2和P3進行了寬鬆的解釋，也禁止了這些phenomena，也並不能保證真正的可串行化。在ANSI中刪除P3並僅使用4.28定義ANSI 可串行化會更簡單。請注意，表1不是最終結果;它將被表3所取代。

2.3鎖

大多數SQL產品都使用基於鎖的隔離。因此，盡管存在某些問題，但從鎖方麵表征ANSI SQL隔離級別是有效的。

事務在基於鎖調度下執行的讀寫會請求數據項或數據項集合上讀（共享）和寫（獨占）鎖。在兩個不同的事務下的鎖對應著同一個數據項的情況下，當至少一個是寫鎖的時候會衝突。

讀取（或寫入）的謂詞鎖（給定的<搜索條件>確定的一組數據項下）實際上是對滿足<搜索條件>的所有數據項的鎖。這可能是一個無限集，因為它包括數據庫中存在的數據以及當前不在數據庫中的所有幻影（phantom）數據項（如果它們被插入，或者當前數據項被更新以滿足<搜索條件> ）。在SQL術語中，謂詞鎖覆蓋滿足謂詞的所有數據項以及INSERT，UPDATE或DELETE後滿足謂詞的所有數據項。不同事務的兩個謂詞鎖中如果一個是寫鎖，並且兩個鎖覆蓋了相同的（可能是幻影）數據項，則兩個謂詞鎖相衝突。數據項（item）鎖（記錄鎖）是一個謂詞鎖，其中謂詞指定特定記錄。

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

長鎖，要求鎖到事務提交或中止為止。否則，為短鎖。實際上，短鎖通常在操作完成後立即釋放。

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

基本的串行化定理是好形式的兩階段鎖（well-formed two-phase locking）保證可串行化 ——兩階段鎖下的每個曆史等同於一些串行曆史。相反，如果一個事務不是好形式的或兩階段的，那麼（除了在退化的情況下）可能出現不可串行化的執行曆史 [EGLT]。 [GLPT]論文定義了四個一致性度，試圖說明鎖，依賴和基於異常的表征的等價性。異常定義（見定義1）太模煳。其作者在定義上持續受到批評（同見[GR]）。隻有在曆史和依賴圖或鎖方麵更多的數學定義經受住了時間的考驗。

表2根據鎖定範圍（數據項項或謂詞），模式（讀或寫）及其持續時間（短或長）定義了多個隔離類型。我們認為基於鎖的隔離級別 鎖讀未提交、鎖讀已提交、鎖可重複讀、鎖可串行化是滿足ANSI SQL隔離級別要求的，但如圖所示，它們與表1完全不同。因此，它是必須將根據鎖定義的隔離級別與基於ANSI SQL phenomena的隔離級別進行區分。為了區分，表2中的級別標有“鎖”前綴，而不是表1的“ANSI”前綴。

[GLPT]定義了0級一致性以允許髒讀和寫：隻需要操作原子性。度1，2和3分別對應於鎖讀未提交，鎖讀已提交和鎖可串行化。沒有隔離度與鎖可重複讀匹配。

Date和IBM最初使用名稱“Repeatable Reads”[DAT，DB2]表示可串行化或鎖可串行化。這似乎是一個比[GLPT]術語“隔離度3”更易理解的名稱，盡管它們是相同的。可重複讀的ANSI SQL含義與Date的原始定義不同，我們認為這是不幸的。Phenomena P3是ANSI SQL 可重複讀隔離級別不考慮的，但從P3的定義可以看出，讀取是不可重複的！（譯者注：P3 違反了“可重複讀”中文詞義）我們在表2中仍然誤用“鎖可重複讀”術語，來對應ANSI定義。類似地，Date將術語“遊標穩定”作為一個更易於理解的度2隔離名稱，增強了對丟失遊標更新的保護，如下麵4.1節所述。

定義：如果符合L2標準的所有不可串行化曆史都滿足L1，並且至少存在一個不可串行化的曆史發生在L1級，但不在L2級，則隔離級別L1比隔離級別L2弱（weaker）（或L2比L1強（stronger）），表示為L1<L2。當滿足L1和L2的不可串行化曆史集合相同時，兩個隔離級L1和L2是相等的，表示為L1 == L2。 如果L1<L2或L1 == L2表示為L1<=L2。兩個隔離級別是無法比較的，表示為L1><L2。比如當每個隔離級別允許另一個不允許的不可串行化的曆史。

在比較隔離級別時，我們僅在不可串行化的曆史上區分它們，比如一些曆史可能發生在一個級別而不可能發生在另一個級別。兩個隔離級別在他們允許出現的可串行化曆史方麵也可能不同。即使眾所周知，鎖調度程序不接受所有可能的可串行化曆史，但是我們認為鎖可串行化==可串行化。由於不允許太多種可串行化的曆史，這種隔離級別可能是不切實際的，但是我們在這裏不考慮這些。

結論如下，這些定義和一些簡單的例子表明<關係是合理的。

結論1：鎖讀未提交<鎖讀已提交<鎖可重複讀<鎖可串行化

在下一節中，我們將重點比較ANSI和基於鎖的隔離級別定義。

3.分析ANSI SQL隔離級別

從好的結論開始，鎖隔離級別符合ANSI SQL要求。

結論2：表2的鎖協議定義了至少與表1相應的基於phenomena的隔離級別一樣強大的鎖隔離級別。參考[OOBBGM]的證明。

因此，鎖隔離級別至少與同名ANSI級別隔離相當。它們隔離度更強嗎？答案是肯定的，即使在最低級別也一樣。鎖讀未提交提供長寫鎖，以避免我們稱之為“髒寫”的現象，但ANSI SQL並不排除其基於ANSI 可序列化的異常行為。

P0（髒寫）：事務T1修改數據項。另一個事務T2然後在T1執行COMMIT或ROLLBACK之前進一步修改該數據項。如果T1或T2然後執行ROLLBACK，則不清楚正確的數據值應該是什麼。寬鬆的解釋是：

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

髒寫不好的一個原因是它可以違反數據庫一致性。假設在x和y之間存在約束（例如，x = y），並且如果單獨運行，則T1和T2每個維持約束的一致性。但是，如果兩個事務以不同的順序寫入x和y，那麼這個約束很容易被違反，這隻有在有髒寫時才會發生。例如，如果曆史是w1 [x] w2 [x] w2 [y] c2 w1 [y] c1，則T1到y和T2到x間修改都是“存活”的。如果T1在x和y兩者中寫入1同時T2寫入2，則結果將為x = 2、y = 1。違反了x = y約束。

如[GLPT，BHG]和其他地方所述，自動事務回滾是說明P0重要性的另一個原因。在沒有P0保護的情況下，係統無法通過恢複映像（image）來撤消更新。考慮曆史：w1 [x] w2 [x] a1。您不想通過恢複x的前一個映像來撤消w1 [x]，因為這會覆蓋w2的更新。但是，如果您不還原其前映像，並且事務2稍後中止，則無法通過還原其前映像來撤消w2 [x]！這就是為什麼即使是最弱的鎖係統也要持有長寫鎖。否則，他們的恢複係統將失效。

結論3：ANSI SQL隔離應修改為要求所有隔離級別至少有P0。

我們認為，需要對三種ANSI phenomena進行寬鬆的解釋。回想一下，嚴格的解釋是：

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)

之前的表1顯示，讀已提交隔離的曆史禁止異常A1，可重複讀隔離的曆史禁止異常A1和A2，可串行化隔離的曆史禁止異常A1，A2和A3。考慮曆史H1，在銀行餘額行x和y之間轉移$ 40：

H1：r1 [x = 50] w1 [x = 10] r2 [x = 10] r2 [y = 50] c2 r1 [y = 50] w1 [ y = 90] c1

H1是不可串行化的，這是一個經典的不一致分析（inconsistent analysis）問題。其中事務T1將40元從x轉移到y，要求保持餘額總數為100，但T2讀到了總餘額為60的不一致狀態。曆史H1不違反任何異常A1，A2或A3。在A1的情況下，兩個事務之一將不得不中止（譯者注：也就是讀未提交要求一個事務讀，另一個事務終止提交，但在H1中兩個事務都提交了）;對於A2，數據項將必須由相同的事務讀取第二次; A3需要謂詞範圍內的值改變。這些事情都不會發生在H1。考慮到A1的寬鬆解釋，phenomena P1：

P1: w1[x]...r2[x]...((c1 or a1) and (c2 or a2) in any order)

H1顯然違反了P1。因此，我們認為ANSI定義意圖說明的是解釋P1而不是A1，寬鬆的解釋是正確的解釋。

類似的論點表明，P2應該被視為ANSI的定義而不是A2。區分這兩個解釋的曆史是：

H2：r1 [x = 50] r2 [x = 50] w2 [x = 10] r2 [y = 50] w2 [y = 90] c2 r1 [y = 90]

H2是不可串行化的——這是另一個經典不一致分析，其中T2看到總餘額為140.這一次，交易都沒有讀取髒（即未提交）的數據。因此P1滿足。並且，沒有任何數據項被讀取兩次，也沒有謂詞範圍內的數據被更改。 H2的問題是，當T1讀取y時，x的值已過期。如果T2再次讀取x，則會被更改;但由於T2不會讀兩次，A2不適用。用P2代替A2，寬鬆解釋解決了這個問題。

P2: r1[x]...w2[x]...((c1 or a1) and (c2 or a2) any order)

當w2 [x = 20]發生時，由於覆蓋了r1 [x = 50]，H2將不再正確。最後，考慮A3和曆史H3：

A3：r1 [P] ... w2 [y in P] ... c2 ... r1 [P] ... c1（Phantom）

H3：r1 [P] w2 [insert y到P] r2 [z] w2 [z] c2 r1 [z] c1

這裏T1執行<搜索條件>以找到雇員的列表。然後T2執行新的員工的插入，然後更新公司中的員工數量z。此後，T1將員工的數量讀出，並看到差異。這個曆史顯然是不可串行化的，但由於謂詞範圍沒有被訪問兩次，所以它是被A3所允許的。同樣，寬鬆解釋P3解決了這個問題。

P3: r1[P]...w2[y in P]...((c1 or a1) and (c2 or a2) any order)

如果P3被禁止，曆史H3無效。這顯然是ANSI的意圖。上述討論有助於證明以下結果。

結論4:嚴格的解釋A1，A2和A3有意想不到的缺點。正確的解釋是寬鬆的。我們認為ANSI意在定義P1，P2和P3。

結論5: ANSI SQL隔離phenomena不完整。還有一些異常仍然可能出現。必須定義新的phenomena來完成鎖的定義。此外，必須重新進行定義P3。在以下定義中，我們刪除不加強曆史限製的操作（c2 or a2）。

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的定義禁止任何滿足謂詞的寫被讀取——寫可以是插入，更新或刪除。

關於這些phenomena的提出的ANSI隔離級別的定義在表3中給出。

對於單個版本曆史，容易得出P0，P1，P2，P3 phenomena是“假”的鎖版本phenomena。例如，禁止P0排除了在第一個事務寫入數據項後第二個事務的寫，相當於在在數據項（和謂詞）上持有長寫鎖。所以髒寫是不可能的。類似地，禁止P1相當於對數據項進行了好形式的讀取。禁止P2表示數據項加上長讀鎖。最後，禁止P3意味著持有長謂詞讀鎖。因此，由這些phenomena定義的表3的隔離級別提供與表2的鎖隔離級別相同的行為。

結論6:表2的鎖定隔離級別和表3基於phenomena的定義是等效的。換句話說，P0，P1，P2和P3是對於鎖版本隔離級別的重新定義。

接下來，我們將通過表3中的名稱來引用表3中列出的隔離級別，相當於表2的這些隔離級別的鎖定版本。當我們參考ANSI READ UNCOMMITTED，ANSI READ COMMITTED，ANSI REPEATABLE READ和ANOMALY SERIALIZED，我們指的是表1的ANSI定義（因不包括P0而不完備）。

下一節顯示，許多商業上可用的隔離實現提供了落在讀已提交和可重複讀之間的隔離級別。為了實現區分這些實現的有意義的隔離級別，我們以P0和P1作為基礎，然後添加新的phenomena。

4.其他隔離類型

4.1遊標穩定（Cursor Stability）

遊標穩定旨在防止丟失更新現象。

P4（丟失更新（Lost Update））：當事務T1讀取數據項，然後T2更新數據項（可能基於先前的讀取），然後T1（基於其較早的讀取值）更新數據項並提交時，會發生丟失的更新異常。在從曆史上考慮，這是：

P4: r1[x]...w2[x]...w1[x]...c1 (Lost Update)

（譯者注：注意P4隻是基於P0髒寫和P1髒讀，從鎖隔離的角度上來說隻是持有短讀鎖和長寫鎖，沒有達到鎖可重複讀P2（也就是說不持有長讀鎖））

如曆史H4所示，問題是即使T2提交，T2的更新也會丟失。

H4：r1 [x = 100] r2 [x = 100] w2 [x = 120] c2 w1 [x = 130] c1

x的最終值為T1寫入的x+30=130。 P4至少在讀已提交隔離級別，因為禁止P0（事務執行第一次寫操作的數據項被另一個事務第二次寫入）或P1（寫後提交前被讀取）的情況下允許出現H4。當然，禁止P2也排除了P4，因為P2是r1[x],w2[x]，（c1 or a1），包括了P4。因此，P4可用於作為區分讀已提交和可重複讀強度中間的隔離級別。

遊標穩定擴展了讀已提交隔離級別下對於SQL遊標的鎖行為。其提出遊標上的Fetching操作rc（意思是讀取遊標）。rc要求在遊標的當前數據項上保持長讀鎖，直到遊標移動或關閉（可能通過提交關閉）。當然，遊標上的Fetching事務可以更新行（wc），即使遊標在隨後的Fetch上移動，寫鎖也將保持在行上直到事務提交。 rc1 [x]和以後的wc1 [x]排除了介入的w2 [x]。因此，針對遊標上的情況，提出phenomena P4C。

P4C：rc1 [x] ... w2 [x] ... w1 [x] ... c1（丟失更新）

結論7：讀已提交<遊標穩定<可重複讀

遊標穩定被SQL係統廣泛實現，以防止丟失通過遊標讀取的行的更新。在某些係統中的讀已提交，實際上僅是更強的遊標穩定。ANSI標準允許這一點。

將遊標放在數據項上以保持其值穩定的技術可以用於多個數據項，代價是使用多個遊標。因此，程序員可以將訪問穩定性調整為鎖讀已提交隔離，以便訪問少量固定數量的數據項。然而，這種方法不方便也不通用。因此，總是有曆史適合P4（當然適用於更通用的P2）phenomena，處於遊標穩定隔離級別上。

4.2快照隔離（Snapshot Isolation，SI）

在快照隔離下執行的事務始終從事務開始時起的（已提交）數據的快照中讀取數據。事務開始時獲取的時間戳稱為其開始時間戳（Start-Timestamp）。這一個時間戳可能為事務第一次讀之前的任何時間。事務運行在快照隔離中時，隻要可以維護其開始時間戳對應的快照數據，在就不會阻塞讀。事務的寫入（更新，插入和刪除）也將反映在此快照中，如果事務第二次訪問（即讀取或更新）數據，則能再次讀到。這個事務開始時間戳之後的其他事務的更新對於本次事務是不可見的。

快照隔離是一種多版本並發控製（Multiversion Concurrency Control，MVCC）。它擴展了[BHG]中描述的多版本混合方法（Multiversion Mixed Method）。其允許通過隻讀事務進行快照讀（snapshot read）。

當事務T1準備好提交時，它將獲得一個提交時間戳（Commit-Timestamp），該值大於任何現有的時間戳。當其他事務T2提交了的數據的提交時間戳在T1事務的間隔[Start-Timestamp，Commit-Timestamp]中，隻有T1, T2數據不重疊，事務才成功提交。否則，T1將中止。這個功能叫做先提交者成功（First-committer-wins），防止丟失更新（P4）。當T1提交時，其更改對於開始時間戳大於T1的提交時間戳的所有事務都可見。

快照隔離是一種多版本（MV）方法，因此單值（SV）曆史不能正確地反映時間上的操作序列。在任何時候，每個數據項可能有多個版本，由活動的和已提交的事務寫入。事務必須讀取合適的版本。考慮第3節開始的曆史H1，其表明在單值執行中需要P1。在快照隔離下，相同的操作序列將導致多值曆史：

H1.SI：    r1 [x0 = 50] w1 [x1 = 10] r2 [x0 = 50] r2 [y0 = 50] c2

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

（譯者注：事務1讀到x0=50，寫x1=10，之所以事務2讀的是x0的值，是因為事務1還沒有獲得提交時間戳並提交x1，從而事務2的開始時間戳在一定在事務1的提交時間戳之前。最終沒有髒讀）

但是H1.SI具有可串行化執行的數據流。在[OOBBGM]中，我們說明了所有快照隔離曆史都可以映射到單值曆史，同時保留數據流依賴性（MV曆史被視為與SV曆史視圖等效，轉換的方法在[BHG]第5章中）。例如，MV曆史H1.SI將映射到可串行化的SV曆史：

H1.SI.SV：r1 [x = 50] r1 [y = 50] r2 [x = 50] r2 [y = 50] c2

   w1 [x = 10] w1 [y = 90] c1

將MV曆史映射到SV曆史是在隔離層次中放置快照隔離的關鍵。

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

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

H5是不可串行化的（譯者注：但可以看出，如果SI讀寫數據項集相同，則可串行化），並且具有與快照隔離下事務相同的事務間數據流（事務讀取的版本沒有選擇）。這裏我們假設為x和y寫入一個新值的每個事務有保持x + y>0的約束，而T1和T2兩者都是隔離的，所以約束不能保持在H5中。

約束違反（Constraint violation）是一種通用和重要的並發異常類型。個別數據庫滿足多個數據項的約束（例如，鍵的唯一性，引用完整性，兩個表中的行的複製關係等）。它們一起形成數據庫不變量約束謂詞C（DB）。如果數據庫狀態DB與約束一致，則不變量為TRUE，否則為FALSE。事務必須保留約束謂詞以保持一致性：如果數據庫在事務啟動時保持一致，則事務提交時數據庫將一致。如果事務讀取到違反約束謂詞的數據庫狀態，則事務將受到約束違反並發異常的影響。這種約束違反在[DAT]中稱為不一致分析（inconsistent analysis）。

A5（數據項約束違反）。假設C（）是數據庫中兩個數據項x和y之間的數據庫約束。這裏提出兩種由於約束違反引起的異常。

A5A 讀偏（Read Skew）假設事務T1讀取x，然後第二個事務T2將x和y更新並提交。如果現在T1讀取y，它可能會看到不一致的狀態。就曆史而言，我們有異常：

A5A：r1 [x] ... w2 [x] ... w2 [y] ... c2 ... r1 [y] ...（c1 or a1）（讀偏）

A5B 寫偏（Write Skew）假設T1讀取與C（）一致的x和y，然後T2讀取x和y，寫入x和提交。然後T1寫y。如果x和y之間存在約束，則可能會被違反。在曆史方麵：

A5B：r1 [x] ... r2 [y] ... w1 [y] ... w2 [x] ...（c1 and c2 occur）（寫偏）

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

在排除P2的曆史中，A5A和A5B都不會出現，因為A5A和A5B都有T2寫入一個先前未被提交的T1讀取的數據項的情況。因此，phenomena A5A和A5B僅用於區分低於可重複讀取的隔離級別。

ANSI SQL定義中可重複讀的在其嚴格的解釋中捕獲了行約束的退化形式，但在概念上有缺失。具體來說，表2的鎖可重複讀提供了對行約束違反的保護，但表1的ANSI SQL定義僅僅禁止異常A1和A2，不提供對行約束違反的保護。

現在回到快照隔離，這個隔離級別十分強，比讀已提交更強。

結論 8:讀已提交<快照隔離

證明：在快照隔離中，first-committer-wins排除了P0（髒寫入），並且時間戳機製阻止了P1（髒讀），因此快照隔離不比讀已提交弱。此外，A5A可能在讀已提交下，但不在快照隔離與時間戳機製下。因此讀已提交<快照隔離。

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

快照隔離下不會發生A3異常（幻讀）。在一個事務更新數據項集時，另一個事務多次謂詞讀的將始終看到相同的舊數據項集。但是可重複讀隔離級別可能會遇到A3異常。快照隔離禁止具有異常A3的曆史，但允許A5B，而可重複讀則相反（允許A3禁止A5B）。因此：

結論9：可重複讀><快照隔離。

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

也許最引人注目的是，快照隔離沒有幻讀（在ANSI定義A3的嚴格意義上）。每個事務都不會看到並發事務的更新。所以，可以說出以下令人驚訝的結果（請注意，表1定義了異常可串行化（ANOMALY SERIALIZABLE）作為ANSI SQL定義的SERIALIZABLE），而沒有[ANSI]中的4.28中的額外限製：

結論10：快照隔離曆史排除了異常A1，A2和A3 。因此，在表1 異常可串行化的異常解釋中：可串行化<快照隔離。

快照隔離允許以非常老的時間戳運行事務，從而從數據庫的曆史允許進行“時間旅行”——過程中寫入不會被阻塞。當然，具有非常舊的時間戳的事務，如果嚐試更新任何由比較新的事務更新過的數據項，將會中止。

快照隔離的簡單實現模仿了Reed [REE]。這種多版本數據庫有幾種商業實現。 Borland的InterBase 4 [THA]和基於Microsoft Exchange係統的引擎都提供了快照隔離與First-committer-wins功能。 First-Committer-wins要求係統記住屬於每個活動事務的開始時間戳之後提交的任何事務的所有更新（寫入鎖信息）。如果其更新與係統記憶中其他人的已有的更新衝突，則中止該事務。

快照隔離的“樂觀”並發控製方法對於隻讀事務具有明顯的並發優勢，但其對更新事務的好處仍然存在爭議。這可能不利於長時間運行的與高競爭性短事務執行，因為長期運行的事務不太可能是他們寫的一切的第一作者，因此可能會被中止。（請注意，這種情況也會成為鎖實現中的一個真正的問題，如果解決方案是不允許長期運行會持有短事務鎖的更新事務，快照隔離也是可以接受的。）當然，當在短期更新事務衝突最小化，長時間運行的事務大多為隻讀事務的情況下，快照隔離應該有較好的效果。在高數據衝突的長事務中，快照隔離提供了一種古典樂觀的方法。對此種情況下的快照隔離的價值存在不同的看法。

4.3其他多版本係統

還有其他模式的多版本並發控製。一些商業數據庫維護對象的版本，但將快照隔離限製為隻讀事務（例如，僅在某些其他數據庫中的SQL-92，Rdb和[MS，HOB，ORA]的SET TRANSACTION READ; Postgres和Illustra [STO，ILL]長期維護多版本，並提供“時間旅行”查詢）。其他產品允許更新事務，但不保證first-committer-wins（例如，Oracle讀一致性隔離[ORA]）。

Oracle讀一致性（Read Consistency）隔離在每個SQL語句開始後，根據事務開始時間戳，給出最近提交的數據庫值。就好像在每個SQL語句中事務的開始時間戳都是最新的。啟動遊標的時間作為遊標集的成員。底層機製根據語句時間戳重新計算行的適當版本。寫鎖保護了行插入，更新和刪除，以提供first-writer-wins而不是first-committer-wins策略。讀一致性比讀已提交（它禁止遊標丟失更新（P4C））更強，但允許不可重複讀取（P3），丟失更新（P4）和讀偏（A5A）。快照隔離不允許P4或A5A。

如果仔細查看SQL標準，它將每個語句定義為原子操作。它在每個語句的開頭都有可串行化的子事務（或時間戳）。可以想象出一種隔離級別層次，其通過為語句分配時間戳而定義的隔離級別（例如，在Oracle中，一次遊標fetch具有其啟動的時間戳）。

5.總結

總之，原始ANSI SQL隔離級別的定義存在嚴重問題（如第3節所述）。英文文字上的定義是模煳和不完整的。髒寫（P0）沒有被排除。結論5是我們建議清理ANSI 隔離級別以對應鎖隔離級別[GLPT].

ANSI SQL希望定義可重複讀隔離以排除除幻讀之外的所有異常。表1的異常定義沒有達到這個目標，但是表2的鎖版本定義做到了。 ANSI對術語“可重複讀”的選擇是非常不合適的：（1）可重複的讀取不會產生可重複的結果，（2）行業已經使用該術語來表示：可重複的讀取意味著可序列化——幾種產品術語中都是這麼認為的。我們建議為此找到另一個術語。

許多商業產品中流行的隔離級別處於表3的可重複讀和可串行化之間。第4節中進行了闡述。這裏命名的所有隔離級別已經被表征如圖2所示和表4，如下。圖2中較高級別的隔離度在強度上較高（參見4.1節開頭的定義），連接線標有區別它們的phenomena和異常。

值得注意的是，從來沒有文章討論過降低多版本係統的隔離級別，盡管其已經在幾個產品中實現。許多應用程序通過使用遊標穩定性或Oracle的一致性隔離來避免鎖爭用。這樣的應用程序會發現快照隔離比兩者更好：它避免了丟失的更新異常，一些幻讀異常（例如ANSI SQL所定義的）。它不會阻塞隻讀事務，並且讀不阻塞更新。

感謝聲明（略）

引用

[ANSI] ANSI X3.135-1992, American National Standard for Information Systems — Database Language — SQL, November, 1992

[ABJ] V. Atluri, E. Bertino, S. Jajodia, "A Theoretical Formulation for Degrees of Isolation in Databases," Technical Report, George Mason University, Fairfax, VA, 1995

[BHG] P. A. Bernstein, V. Hadzilacos, N. Goodman, “Concurrency Control and Recovery in Database Systems,” Addison-Wesley 1987.

[DAT] C. J. Date, “An Introduction to Database Systems,” Fifth Edition, Addison-Wesley, 1990 [DB2] C. J. Date and C. J. White, “A Guide to DB2,” Third Edition, Addison-Wesley, 1989.

[EGLT] K. P. Eswaran, J. Gray, R. Lorie, I. Traiger, “The Notions of Consistency and Predicate Locks in a Database System,” CACM V19.11, pp. 624- 633, Nov. 1978

[GLPT] J. Gray, R. Lorie, G. Putzolu and, I. Traiger, “Granularity of Locks and Degrees of Consistency in a Shared Data Base,” in Readings in Database Systems, Second Edition, Chapter 3, Michael Stonebraker, Ed., Morgan Kaufmann 1994 (originally published in 1977).

[GR] J. Gray and A. Reuter, “Transaction Processing: Concepts and Techniques,” Corrected Second Printing, Morgan Kaufmann 1993, Section 7.6 and following.

[HOB] L . Hobbs and K. England, “Rdb/VMS, A Comprehensive Guide,” Digital Press, 1991.

[ILL] Illustra Information Technologies, "Illustra User's Guide," , Illustra Information Technologies, Oakland, CA. 1994.

[MS] J. Melton and A. R. Simon, “Understanding The New SQL: A Complete Guide,” Morgan Kaufmann 1993.

[OOBBGM] P. O'Neil, E. O'Neil, H. Berenson, P. Bernstein, J. Gray, J. Melton, “An Investigation of Transactional Isolation Levels,” UMass/Boston Dept. of Math & C.S. Preprint.

[ORA] “PL/SQL User’s Guide and Reference, Version 1.0,” Part. 800-V1.0, Oracle Corp., 1989.

[PAP] C. Papadimitriou, “The Theory of Database Concurrency Control, Computer Science Press, 1986.

[PON] P. O’Neil, “Database: Principles, Programming, Performance, Morgan Kaufmann 1994, Section 9.5.

[REE] D. Reed, “Implementing Atomic Actions On Decentralized Data,” ACM TOCS 1.1,1981, pp. 3- 23.

[STO] M. J. Stonebraker, “The Design of the POSTGRES Storage System,” 13th VLDB, 1987, reprinted in Readings in Database Systems, Second Edition, M. J. Stonebraker, Ed., Morgan Kaufmann 1994

[THA] M. Thakur, “Transaction Models in InterBase 4,” Proceedings of the Borland International Conference, June 1994.

最後更新：2017-05-04 12:01:17

  上一篇： #運維俠客行·杭州站# 如何實現高容量大並發數據庫服務

  下一篇： V8 Ignition：JS 引擎與字節碼的不解之緣