再談資料庫事務隔離性

寫在前面

近兩年分散式資料庫技術加速發展，而由於金融行業技術生態的限制，周圍很多同學對其並沒有深入的瞭解，所以進行高性能、高可靠系統設計時往往缺少這一利器。Ivan希望以系列文章的方式與大家交流探討，加深我們對分散式資料庫的認識。本文是該系列文章的第一篇，主要探討事務管理中的隔離性，釐清相關概念和關鍵技術，為後面闡述分散式資料庫的事務管理做一個鋪墊，姑且算是一篇前傳吧。

正文

我們首先從定義出發，事務管理包括原子性、一致性、隔離性和持久性四個方面，即ACID。所有資料庫專著都會給出這個四個特性的定義，本文我們引用了Jim Gray對其的定義。

Jim Gray是事務處理方面的大師，本文中很多內容都來自他的專著和論文。為避免翻譯引入的歧義，這裡我們直接引用原文。

Atomicity: Either all the changes from the transaction occur (writes, and messages sent), or none occur.
Consistency: The transaction preserves the integrity of stored information.
Isolation: Concurrently executing transactions see the stored information as if they were running serially (one after another).
Durability: Once a transaction commits, the changes it made (writes and messages sent) survive any system failures.

在上述隔離性（Isolation）的定義中，我們可以發現其目標是使併發事務的執行效果與串列一致，但在具體技術實現上往往需要在併發能力和串列化效果之間進行平衡，很難兩者兼顧。平衡的結果就是會出現違反串列效果的現象即異常現象（Phenomenon）。通常來說，隔離級別的提升伴隨著併發能力的下降，兩者負相關。各種資料庫在談到隔離級別時都會引用ANSI SQL-92標準隔離級別，我們來看看它的具體內容。

ANSI SQL-92 Isolation Levels

ANSI SQL-92可能是最早提出了基於異常現象來定義隔離級別的方法，同時沒有將隔離級別與具體實現機制綁定，隔離的實現可以基於鎖（lock-based）或者無鎖（lock-free），相容了後續的技術發展。該標準根據三種異常現象將隔離性定義為四個級別，具體如下。

臟讀，事務（T1）中修改的數據項在尚未提交的情況下被其他事務（T2）讀取到，而T1進行Rollback操作，則T2剛剛讀取到的數據並沒有實際存在。
不可重覆讀，T1讀取數據項，T2對其中的數據進行了修改或刪除且Commit成功。如果T1嘗試再次讀取這些數據，會得到T2修改後的數據或者發現數據已刪除。這樣T1在一個事務中兩次同樣條件的讀取，且結果集內容變更或結果集數量減少。
幻讀，T1使用特定的查詢條件獲得一個結果集，T2插入新的數據且這些數據符合T2剛剛操作的查詢條件。T2 commit 成功後，T1再次執行同樣的查詢，此時得到的結果集增大。

很多文章都結合資料庫產品對上述異常現象的實例和處理機制進行了說明，本文中不再贅述，有興趣的同學可以參考文末的鏈接[1]。

ANSI SQL-92標準早在92年發佈，但無論是當時還是後來都沒有被各大資料庫廠商嚴格遵循，部分原因可能是標準過於簡化與實際應用有一定程度的脫離。Jim Gray等人在1995發佈了論文“A Critique of ANSI SQL Isolation Levels” （本文中簡稱為Critique[2]）對隔離級別進行更全面的闡述，可以幫助我們加深理解。

Critique Isolation Levels

Critique提出了ANSI SQL-92存在的兩個問題，首先是自然語言方式界定的異常現象並不嚴格導致一些同質化的異常現象被遺漏；其次是一些典型的異常現象並沒有被涵蓋進去，導致隔離級別存在明顯缺失。因此，文中對ANSI SQL-92的三種異常現象（將其編號為A1/A2/A3）進行了擴展（編號為P1/P2/P3），並增加了另外5種常見的異常現象。受限於篇幅，這裡僅對兩種異常現象進行說明。

Lost Update

丟失更新（Lost Update）是一個經典的資料庫問題，由於太過重要所有主流資料庫都解決了該問題，我們這裡將操作稍加變形來舉例。

我們使用MySQL進行演示，創建表並初始化數據

create table account (balance int,name varchar(20)) ENGINE=InnoDB;
insert into account values(50,'Tom');

在上述操作中T1、T2串列執行效果是對餘額進行兩次扣減，分別為40和1，最終值為9，但並行的最終值為49，T2的修改被丟失。我們可以發現Lost update的實質是T1事務讀取數據，而後該數據被T2事務修改並提交，T1基於已經過期的數據進行了再次修改，造成T2的修改被覆蓋。

Read Skew

讀偏序（Read Skew）是RC級遇到的問題。如果數據項x與y存在一致性約束，T1先對讀x，而後T2修改x和y後commit，此時T1再讀y。T1得到的x與y不滿足原有的一致性約束。

MySQL預設隔離級別為RR，我們需要手工設置為RC並初始化數據

set session transaction isolation level read committed;
insert into account values(70,'Tom');
insert into account values(30,'Kevin');

初始數據Tom與Kevin的賬戶合計為100，在T1事務內的兩次讀取得到賬戶合計為130，顯然不符合之前的一致性約束。

補充這些異常現象後，Critique給出了新的矩陣，相比ANSI更加完善也更貼合真實的資料庫產品。

主流資料庫考慮到串列化效果與併發性能的平衡，一般預設隔離級別都介於RC與RR之間，部分提供了Serializable。特別提醒，無論ASNI SQL-92還是Critique的隔離級別都不能確保直接映射到實際資料庫的同名隔離級別。

SI&MVCC

快照隔離（SI,Snapshot Isolation）是討論隔離性時常見的術語，可以做兩種的解讀，一是具體的隔離級別，SQL Server、CockroachDB都直接定義了這個隔離級別；二是一種隔離機制用於實現相應的隔離級別，在Oracle、MySQL InnoDB、PostgreSQL等主流資料庫中普遍使用。多版本併發控制（MVCC，multiversion concurrency control）是通過記錄數據項歷史版本的方式提升系統應對多事務訪問的併發處理能力，例如避免單值（Single-Valued）存儲情況下寫操作對讀操作的鎖排斥。MVCC和鎖都是SI的重要實現手段，當然也存在無鎖的SI實現。以下是Critique描述的SI運作過程。

事務（記為T1）開始的瞬間會獲取一個時間戳Start Timestamp（記為ST），而資料庫內的所有數據項的每個歷史版本都記錄著對應的時間戳Commit Timestamp（記為CT）。T1讀取的快照由所有數據項版本中那些CT小於ST且最近的歷史版本構成，由於這些數據項內容只是歷史版本不會再次被寫操作鎖定，所以不會發生讀寫衝突，快照內的讀操作永遠不會被阻塞。其他事務在ST之後的修改，T1不可見。當T1 commit的瞬間會獲得一個CT，並保證大於此刻資料庫中已存在的任意時間戳（ST或CT），持久化時會將這個CT將作為數據項的版本時間戳。T1的寫操作也體現在T1的快照中，可以被T1內的讀操作再次讀取。當T1 commit後，修改會對那些持有ST大於T1 CT的事務可見。
如果存在其他事務（T2），其CT在T1的運行間隔【ST，CT】之間，與T1對同樣的數據項進行寫操作，則T1 abort，T2 commit成功，這個特性被稱為First-committer-wins，可以保證不出現Lost update。事實上，部分資料庫會將其調整為First-write-wins，將衝突判斷提前到write操作時，減少衝突的代價。

這個過程不是某個資料庫的具體實現，事實上不同資料庫對於SI實現存在很大差別。例如，PostgreSQL會將歷史版本和當前版本一起保存通過時間戳區分，而MySQL和Oracle都在回滾段中保存歷史版本。MySQL的RC與RR級別均使用了SI，如果當前事務（T1）讀操作的數據被其他事務的寫操作加鎖，T1轉向回滾段讀取快照數據，避免讀操作被阻塞。但是RC的快照定義與以上描述不同，也包括了T1執行過程中其他事務提交的最新版本[6]。

此外，我們還有一個重要發現，時間戳是生成SI的關鍵要素。在單機系統中，唯一時間戳比較容易實現，而對於分散式系統在跨節點、跨數據中心甚至跨城市部署的情況下如何建立一個唯一時鐘就成為一個非常複雜的問題，我們暫留下一個伏筆將在後面的專題文章中進行討論。

Serializable VS SSI

SI是如此有效，甚至在TPC-C benchmark測試中也沒有出現任何異常現象[5]，但事實上SI不能保證完整的串列化效果。Critique中指出，SI還無法處理A5B（Write Skew，寫偏序），如下圖所示。

Write Skew

寫偏序（Write Skew）也是一致性約束下的異常現象，即兩個並行事務都基於自己讀到的數據集去覆蓋另一部分數據集，在串列化情況下兩個事務無論何種先後順序，最終將達到一致狀態，但SI隔離級別下無法實現。下圖的“黑白球”常常被用來說明寫偏序問題。

如何實現真正的串列化效果呢？事實上，早期的資料庫已經通過嚴格兩階段鎖協議（S2PL，Strict Two-Phase Locking）實現了完全的串列化隔離（Serializable Isolation），即正在進行讀操作的數據阻塞對應寫操作，寫操作阻塞所有操作（包括讀操作和寫操作）。如阻塞造成迴圈將構成死鎖，則需要進行rollback操作。S2PL的問題顯而易見，在競爭激烈場景下，阻塞和死鎖會造成資料庫吞吐量下降和響應時間的增加，所以這種串列化無法應用於實際生產環境。直到SSI的出現，人們終於找到具有實際價值的串列化隔離方案。

串列化快照隔離（SSI, Serializable Snapshot Isolation，也會被翻譯為序列化快照）是基於SI改進達到Serializable級別的隔離性。SSI由Michael James Cahill在他的論文"Serializable Isolation for Snapshot Databases"[3]中提出（該論文獲得2008 Sigmod Best Paper Award，文章末尾提供了該論文的2009年完整版[4]相關信息，有興趣的同學可以深入研究）。SSI保留了SI的很多優點，特別是讀不阻塞任何操作，寫不會阻塞讀。事務依然在快照中運行，但增加了對事務間讀寫衝突的監控用於識別事務圖（transaction graph）中的危險結構。當一組併發事務可能產生異常現象（anomaly），系統將通過回滾其中某些事務進行干預以消除anomaly發生的可能。這個過程雖然會導致某些事務的錯誤回滾（不會導致anomaly的事務被誤殺），但可以確保消除anomaly[3]。

從理論模型看，SSI性能接近SI，遠遠好於S2PL。2012年，PostgreSQL在9.1版本中實現了SSI[7]，可能也是首個支持SSI的商業資料庫，驗證了SSI的實現效果。CockroachDB也從Cahill的論文獲得靈感，實現SSI並將其作為其預設隔離級別。

隨著技術的發展，SI/SSI已經成為主流資料庫的隔離技術，尤其是後者的出現，無需開發人員在代碼通過顯式鎖來避免異常，從而降低了人為錯誤的概率。在分散式資料庫的相關章節中，我們將進一步對SSI實現機制進行深入探討。

參考文獻
[1]Innodb中的事務隔離級別和鎖的關係，ameng，https://tech.meituan.com/innodb-lock.html
[2]H. Berenson, P. Bernstein, J. Gray, J.Melton, E. O’Neil,and P. O’Neil. A critique of ANSI SQL isolation levels. InProceedings of the SIGMOD International Conference on Management of Data, pages1–10, May 1995.
[3]Michael J. Cahill, Uwe Röhm, and Alan D.Fekete. 2008. Serializable isolation for snapshot databases. In SIGMOD ’08:Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pages 729–738, New York, NY, USA. ACM.
[4]Michael James Cahill. 2009. Serializable Isolation for Snapshot Databases. Sydney Digital Theses. University of Sydney, School of Information Technologies
[5] A. Fekete, D. Liarokapis, E. O’Neil, P.O’Neil, andD. Shasha. Making snapshot isolation serializable. In ACM transactions on database systems, volume 39(2), pages 492–528, June 2005.
[6]薑承堯,MySQL技術內幕：InnoDB存儲引擎機, 械工業出版社, 2011
[7]https://wiki.postgresql.org/wiki/Serializable