Serializable隔離級別

事務的一致性和隔離性是事務的兩個重要的特性，從隔離級別的角度看，兩者是息息相關的，更高的隔離級別代表更嚴格的一致性。

在ANSI SQL標準中，事務有4個隔離級別，Read Uncommitted，Read Committed，Repeatable Read，Serializable，其中Serializable是最高的隔離級別?？梢哉f，在傳統(tǒng)數據庫中，只有Serializable的事務才能完全滿足ACID的特性，因為低隔離級別的事務之間還是有可感知的互相影響，比如幻讀，嚴格來說，這既破壞原子性又破壞隔離性。

現實中，即使是面向OLTP的數據庫，大部分也沒有實現Serializable隔離級別，或沒有采用Serializable作為默認隔離級別，見下表

? (摘自 When is "ACID" ACID? Rarely.，有增刪)

在表中，比較重要的沒有實現Serializable的數據庫有Oracle 11g，身為商業(yè)數據庫的霸主，沒有提供Serializable隔離級別，不能不說是一種遺憾。

隔離級別是在一致性和并發(fā)性之間的一次權衡，對于互聯網應用，Serializable往往是不必要的，相較之下，吞吐量更為重要，這是nosql，newsql，sharding中間件能夠流行的一個重要原因。但對于金融領域的某些場景，Serializable的重要性就凸顯出來了。

如何實現Serializable

悲觀方案-加鎖

最簡單的方法，當然是加數據庫鎖，讀加共享鎖，寫加排它鎖。

但是在tp類型的數據庫，這種方法顯然不可行，這會導致數據庫所有事務的讀寫和寫寫行為全部串行化。為了提高并發(fā)性，可以采用加表鎖的方式，但是，這種方法也不能滿足并發(fā)性的要求。對于數據庫事務，行是修改的最小單位。因此采用行加鎖的方式實現串行化，是并發(fā)性最高的方案。

樂觀方案-SSI

在SIGMOD 2008，論文《Serializable Isolation for Snapshot Databases》提出了一個使用樂觀機制實現Serializable的方法。
事務的有害依賴可以分為：

1. rw-dependency，代表事務T1讀取了元素X，事務T2隨后修改了元素X；
2. wr-dependency，代表事務T1修改了元素X，事務T2隨后讀了元素X；
3. ww-dependency，代表事務T1修改了元素X，事務T2隨后再次修改了元素X；

由于MVCC機制的特殊性，對于snapshot隔離級別，當事務T1，T2并行執(zhí)行時，是互相讀不到對方修改后的結果的，因此任何事務讀取了對方修改的數據，一定是前一個版本（或者前幾個版本），即使讀操作是發(fā)生在寫之后，這會形成一個rw-dependency，而不是wr-dependency。

顯然，對于任何一個非串行化的調度，那么一定有多個事務組成的讀寫關系形成了環(huán)。

這篇論文證明了，對于snapshot隔離級別，任何一個成環(huán)的調度必然包含連續(xù)的兩個rw-dependency，這是一個充分不必要條件。以write skew為例：

write-skew.png

事務T1和T2分為讀取了對方修改前的數據，形成了兩個rw-dependency，如下圖：

RW conflict.png

也就是說，只要破壞這兩個rw-dependency，既可以實現串行化。同時，這個方案會帶來一定誤判，并不是所有包含兩個rw-dependency的事務都構成了環(huán)。

常見數據庫Serializable隔離級別的實現

MySQL(innodb)如何實現Serializable

MySQL是通過gap lock的方式實現了Serializable，簡單來說，在snapshot讀的基礎上，對讀操作加鎖。

1. 如果查詢包括索引，在索引上使用gap lock，鎖下一個key；
2. 如果查詢不包含索引，使用表鎖；

考慮一下，對于上圖中的write skew會發(fā)生什么？

事務T1讀X的時候加鎖，事務T2讀Y的時候加鎖，事務T1修改Y的時候被阻塞，事務T2修改X的時候被阻塞，形成死鎖。死鎖檢測導致其中一個事務回滾，環(huán)被打破，實現Serializable。

見下面這個例子，id是主鍵。

mysql serilizable-write skew.png

為什么這種加鎖的方式可以實現SSI？

讀寫操作都加鎖之后，無論兩個事務之間如何發(fā)生沖突，都不可能形成環(huán)，至于為什么鎖下一個key，這是一種謂詞鎖的實現方式，代表對滿足條件但是尚未插入的數據加鎖（幻讀）。

PostgreSQL如何實現Serializable

PostgreSQL在版本9.2之后根據論文《Serializable Isolation for Snapshot Databases》提出的算法實現了Serializable隔離級別，可以說是這篇論文的開源實現。

回想一下《Serializable Isolation for Snapshot Databases》論文中的內容，為了實現Serializable，我們需要追蹤rw-dependency，這不僅需要記錄每行的修改事務，同時也要記錄每行的讀取事務。

PostgreSQL是行級MVCC機制的，這點和MySQL相同。行級MVCC機制表示該行的每個版本都記錄了是由哪個事務的修改的，由此可見，我們缺少的就是該行的讀取事務的信息。

PostgreSQL通過predicate lock維護事務的讀取信息，以記錄物理時間上讀后寫產生的rw-dependency。和MySQL的gap lock不同，predicate lock并不會阻塞任何其他事務，僅僅用于生成rw-dependency，并在生成rw-dependency時和事務提交時判斷是否以事務為中心構成了兩個連續(xù)的rw-dependency，以此判斷事務是否需要回滾。

PostgreSQL通過對整個index page加鎖的方式實現了類似MySQL next key lock的效果，這同樣是為了解決讀操作發(fā)生后有滿足條件的數據插入。

見下面這個例子，同樣，id是主鍵（不過，pg是heap表，不是IOT表）

pg serializable-write skew.jpg

雖然是同樣的語句，一樣是write skew的例子，但是pg的事務行為和MySQL不同，只有在提交時，后提交的事務（右邊）顯式的回滾了，這是樂觀機制和悲觀機制的不同。

Cockroach如何實現Serializable

Cockroach是跨數據中心部署的分布式數據庫，全局數據結構的維護代價要遠遠高于單機數據庫，因此無法像MySQL和PostgreSQL一樣維護全局鎖表，也就無法使用MySQL和PostgreSQL的方式實現Serializable，同時，Cockroach是純樂觀機制，實現上并沒有鎖，也不可能為了實現Serializable推翻自己的根本設計基礎。

那Cockroach是如何實現的Serializable隔離級別？Cockroach lab有一篇文章，介紹了他們是如何實現的Serializable隔離級別，見Serializable, Lockless, Distributed: Isolation in CockroachDB

想想PostgreSQL實現Serializable隔離級別時需要解決的幾個問題：

1. 實現類似next key lock的機制（索引頁面加鎖），解決讀后插入數據的問題；
2. 讀加鎖，解決讀后修改的問題；

Cockroach為了實現Serializable，提供了兩個關鍵的機制：

1. Cockroach允許snapshot隔離級別的事務在提交時使用一個更新的timestamp，這是符合snapshot隔離級別的語義的，但是不允許Serializable隔離級別的事務使用更新的timestamp，Serializable隔離級別的事務會用一個timestamp讀取數據，同時也用這個timestamp提交數據，因此Serializable隔離級別的事務邏輯上等價在這個時間瞬時完成，雖然物理上并非如此。
2. Cockroach內所有的key都是按照range組織的，而非hash，這為serializab的實現提供了極大的便利，類似PostgreSQL的predicate lock，Cockroach維護了一個單獨的timestamp cache，記錄了讀寫指定范圍內的key的timestamp。在寫操作發(fā)生時，會檢查這個范圍的最大read timestamp。如果read timestamp > 事務的timestamp，那么這兩個事務之中就有一個需要回滾。

結合這兩點，我們可以發(fā)現，在Cockroach中，Serializable隔離級別的實現有兩個關鍵點：

1. 通過固定timestamp，將所有Serializable隔離級別的事務按照Serializable隔離級別進行串行化排序；
2. 通過timestamp cache，進行讀寫沖突的判斷，同時，cache以range的形式維護，也避免了幻讀的問題；

同樣的，我們分析一下為什么Cockroach的這種方法可以實現Serializable？

Cockroach中，每個Serializable隔離級別的事務他們的讀寫行為都在另一個發(fā)生沖突的Serializable隔離級別的事務之前或之后，按照timestamp的順序嚴格排序，沒有任何交叉的可能，因此一定是Serializable的；

同樣，舉一個Cockroach處理write skew的例子。

cockraoch-write skew.png

總結

Mysql使用gap lock的實現和PostgreSQL使用SSI的實現更像是悲觀機制和樂觀機制之間的比較。Cockroach則使用了最嚴格的方式，但他的并發(fā)性也是這三個數據庫中最差的?？聪旅孢@個例子

-- run in serialzable isolation level
start transaction; --Tx1               |             start transaction; --Tx2
select * from t1 where id=0;           |
                                       |             select * from t1 where id=0;
update t1 set id2=id2+1 where id=1;    |
commit;                                |             
                                       |             commit;

明顯，這兩個事務可等價于Tx2->Tx1的串行調度。但是在不同的數據庫中，他們的行為就各不相同。

1. 在MySQL中，事務Tx1需要等待事務Tx2提交后才能提交；
2. 在PostgreSQL中，兩個事務可以無阻塞的并發(fā)執(zhí)行下去；
3. 在Cockroach中，左邊的事務會回滾；

當然，這并不能說明PostgreSQL的實現方式就優(yōu)于MySQL，在上面write skew的例子中，PostgreSQL會繼續(xù)執(zhí)行注定失敗的update，如果其后有一些其他的語句，那么無用操作的開銷更多，而MySQL在update發(fā)生時就會立刻回滾，避免后續(xù)空耗資源。很明顯，這還是樂觀機制和悲觀機制的差別。當沖突較多時，悲觀機制更優(yōu)，當沖突較少時，樂觀機制更優(yōu)。

而cockroach，采用了串行化事務的所有操作的方式，有最差的并發(fā)性，但也避免了實現全局鎖的巨大工程開銷。

參考文檔

1. A Critique of ANSI SQL Isolation Levels
2. 《Highly Available Transactions: Virtues and Limitations》
3. When is "ACID" ACID? Rarely.
4. 《Serializable Isolation for Snapshot Databases》
5. PostgreSQL SSI README
6. PostgreSQL-wiki Serializable
7. 《Serializable Snapshot Isolation in PostgreSQL》
8. MySQL Phantom Rows
9. Cockroach design doc
10. How CockroachDB Does Distributed, Atomic Transactions
11. Serializable, Lockless, Distributed: Isolation in CockroachDB