Serializable隔離級(jí)別

事務(wù)的一致性和隔離性是事務(wù)的兩個(gè)重要的特性，從隔離級(jí)別的角度看代咸，兩者是息息相關(guān)的蹈丸，更高的隔離級(jí)別代表更嚴(yán)格的一致性。

在ANSI SQL標(biāo)準(zhǔn)中，事務(wù)有4個(gè)隔離級(jí)別逻杖，Read Uncommitted奋岁，Read Committed，Repeatable Read荸百，Serializable闻伶，其中Serializable是最高的隔離級(jí)別」换埃可以說(shuō)蓝翰，在傳統(tǒng)數(shù)據(jù)庫(kù)中，只有Serializable的事務(wù)才能完全滿足ACID的特性女嘲，因?yàn)榈透綦x級(jí)別的事務(wù)之間還是有可感知的互相影響畜份，比如幻讀，嚴(yán)格來(lái)說(shuō)欣尼，這既破壞原子性又破壞隔離性爆雹。

現(xiàn)實(shí)中，即使是面向OLTP的數(shù)據(jù)庫(kù)愕鼓，大部分也沒(méi)有實(shí)現(xiàn)Serializable隔離級(jí)別钙态，或沒(méi)有采用Serializable作為默認(rèn)隔離級(jí)別，見(jiàn)下表

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

在表中册倒，比較重要的沒(méi)有實(shí)現(xiàn)Serializable的數(shù)據(jù)庫(kù)有Oracle 11g，身為商業(yè)數(shù)據(jù)庫(kù)的霸主谋旦，沒(méi)有提供Serializable隔離級(jí)別剩失，不能不說(shuō)是一種遺憾屈尼。

隔離級(jí)別是在一致性和并發(fā)性之間的一次權(quán)衡册着，對(duì)于互聯(lián)網(wǎng)應(yīng)用，Serializable往往是不必要的脾歧，相較之下甲捏，吞吐量更為重要，這是nosql鞭执，newsql司顿，sharding中間件能夠流行的一個(gè)重要原因。但對(duì)于金融領(lǐng)域的某些場(chǎng)景兄纺，Serializable的重要性就凸顯出來(lái)了大溜。

如何實(shí)現(xiàn)Serializable

悲觀方案-加鎖

最簡(jiǎn)單的方法，當(dāng)然是加數(shù)據(jù)庫(kù)鎖估脆，讀加共享鎖钦奋，寫(xiě)加排它鎖。

但是在tp類型的數(shù)據(jù)庫(kù)，這種方法顯然不可行付材，這會(huì)導(dǎo)致數(shù)據(jù)庫(kù)所有事務(wù)的讀寫(xiě)和寫(xiě)寫(xiě)行為全部串行化朦拖。為了提高并發(fā)性，可以采用加表鎖的方式厌衔，但是璧帝，這種方法也不能滿足并發(fā)性的要求。對(duì)于數(shù)據(jù)庫(kù)事務(wù)富寿，行是修改的最小單位睬隶。因此采用行加鎖的方式實(shí)現(xiàn)串行化，是并發(fā)性最高的方案页徐。

樂(lè)觀方案-SSI

在SIGMOD 2008理疙，論文《Serializable Isolation for Snapshot Databases》提出了一個(gè)使用樂(lè)觀機(jī)制實(shí)現(xiàn)Serializable的方法。
事務(wù)的有害依賴可以分為：

1. rw-dependency泞坦，代表事務(wù)T1讀取了元素X窖贤，事務(wù)T2隨后修改了元素X；
2. wr-dependency贰锁，代表事務(wù)T1修改了元素X赃梧，事務(wù)T2隨后讀了元素X；
3. ww-dependency豌熄，代表事務(wù)T1修改了元素X授嘀，事務(wù)T2隨后再次修改了元素X；

由于MVCC機(jī)制的特殊性锣险，對(duì)于snapshot隔離級(jí)別蹄皱，當(dāng)事務(wù)T1，T2并行執(zhí)行時(shí)芯肤，是互相讀不到對(duì)方修改后的結(jié)果的巷折，因此任何事務(wù)讀取了對(duì)方修改的數(shù)據(jù)，一定是前一個(gè)版本（或者前幾個(gè)版本）崖咨，即使讀操作是發(fā)生在寫(xiě)之后锻拘，這會(huì)形成一個(gè)rw-dependency，而不是wr-dependency击蹲。

顯然署拟，對(duì)于任何一個(gè)非串行化的調(diào)度，那么一定有多個(gè)事務(wù)組成的讀寫(xiě)關(guān)系形成了環(huán)歌豺。

這篇論文證明了推穷，對(duì)于snapshot隔離級(jí)別，任何一個(gè)成環(huán)的調(diào)度必然包含連續(xù)的兩個(gè)rw-dependency类咧，這是一個(gè)充分不必要條件馒铃。以write skew為例：

write-skew.png

事務(wù)T1和T2分為讀取了對(duì)方修改前的數(shù)據(jù)谴咸，形成了兩個(gè)rw-dependency，如下圖：

RW conflict.png

也就是說(shuō)骗露，只要破壞這兩個(gè)rw-dependency岭佳，既可以實(shí)現(xiàn)串行化。同時(shí)萧锉，這個(gè)方案會(huì)帶來(lái)一定誤判珊随，并不是所有包含兩個(gè)rw-dependency的事務(wù)都構(gòu)成了環(huán)。

常見(jiàn)數(shù)據(jù)庫(kù)Serializable隔離級(jí)別的實(shí)現(xiàn)

MySQL(innodb)如何實(shí)現(xiàn)Serializable

MySQL是通過(guò)gap lock的方式實(shí)現(xiàn)了Serializable柿隙，簡(jiǎn)單來(lái)說(shuō)叶洞，在snapshot讀的基礎(chǔ)上，對(duì)讀操作加鎖禀崖。

1. 如果查詢包括索引衩辟，在索引上使用gap lock，鎖下一個(gè)key波附；
2. 如果查詢不包含索引艺晴，使用表鎖；

考慮一下掸屡，對(duì)于上圖中的write skew會(huì)發(fā)生什么封寞？

事務(wù)T1讀X的時(shí)候加鎖，事務(wù)T2讀Y的時(shí)候加鎖仅财，事務(wù)T1修改Y的時(shí)候被阻塞狈究，事務(wù)T2修改X的時(shí)候被阻塞，形成死鎖盏求。死鎖檢測(cè)導(dǎo)致其中一個(gè)事務(wù)回滾抖锥，環(huán)被打破，實(shí)現(xiàn)Serializable碎罚。

見(jiàn)下面這個(gè)例子磅废，id是主鍵。

mysql serilizable-write skew.png

為什么這種加鎖的方式可以實(shí)現(xiàn)SSI魂莫？

讀寫(xiě)操作都加鎖之后还蹲，無(wú)論兩個(gè)事務(wù)之間如何發(fā)生沖突，都不可能形成環(huán)耙考，至于為什么鎖下一個(gè)key，這是一種謂詞鎖的實(shí)現(xiàn)方式潭兽，代表對(duì)滿足條件但是尚未插入的數(shù)據(jù)加鎖（幻讀）倦始。

PostgreSQL如何實(shí)現(xiàn)Serializable

PostgreSQL在版本9.2之后根據(jù)論文《Serializable Isolation for Snapshot Databases》提出的算法實(shí)現(xiàn)了Serializable隔離級(jí)別，可以說(shuō)是這篇論文的開(kāi)源實(shí)現(xiàn)山卦。

回想一下《Serializable Isolation for Snapshot Databases》論文中的內(nèi)容鞋邑，為了實(shí)現(xiàn)Serializable诵次，我們需要追蹤rw-dependency，這不僅需要記錄每行的修改事務(wù)枚碗，同時(shí)也要記錄每行的讀取事務(wù)逾一。

PostgreSQL是行級(jí)MVCC機(jī)制的，這點(diǎn)和MySQL相同肮雨。行級(jí)MVCC機(jī)制表示該行的每個(gè)版本都記錄了是由哪個(gè)事務(wù)的修改的遵堵，由此可見(jiàn)，我們?nèi)鄙俚木褪窃撔械淖x取事務(wù)的信息怨规。

PostgreSQL通過(guò)predicate lock維護(hù)事務(wù)的讀取信息陌宿，以記錄物理時(shí)間上讀后寫(xiě)產(chǎn)生的rw-dependency。和MySQL的gap lock不同波丰，predicate lock并不會(huì)阻塞任何其他事務(wù)壳坪，僅僅用于生成rw-dependency，并在生成rw-dependency時(shí)和事務(wù)提交時(shí)判斷是否以事務(wù)為中心構(gòu)成了兩個(gè)連續(xù)的rw-dependency掰烟，以此判斷事務(wù)是否需要回滾爽蝴。

PostgreSQL通過(guò)對(duì)整個(gè)index page加鎖的方式實(shí)現(xiàn)了類似MySQL next key lock的效果，這同樣是為了解決讀操作發(fā)生后有滿足條件的數(shù)據(jù)插入纫骑。

見(jiàn)下面這個(gè)例子霜瘪，同樣，id是主鍵（不過(guò)惧磺，pg是heap表颖对，不是IOT表）

pg serializable-write skew.jpg

雖然是同樣的語(yǔ)句，一樣是write skew的例子磨隘，但是pg的事務(wù)行為和MySQL不同缤底，只有在提交時(shí)，后提交的事務(wù)（右邊）顯式的回滾了番捂，這是樂(lè)觀機(jī)制和悲觀機(jī)制的不同个唧。

Cockroach如何實(shí)現(xiàn)Serializable

Cockroach是跨數(shù)據(jù)中心部署的分布式數(shù)據(jù)庫(kù)，全局?jǐn)?shù)據(jù)結(jié)構(gòu)的維護(hù)代價(jià)要遠(yuǎn)遠(yuǎn)高于單機(jī)數(shù)據(jù)庫(kù)设预，因此無(wú)法像MySQL和PostgreSQL一樣維護(hù)全局鎖表徙歼，也就無(wú)法使用MySQL和PostgreSQL的方式實(shí)現(xiàn)Serializable，同時(shí)鳖枕，Cockroach是純樂(lè)觀機(jī)制魄梯，實(shí)現(xiàn)上并沒(méi)有鎖，也不可能為了實(shí)現(xiàn)Serializable推翻自己的根本設(shè)計(jì)基礎(chǔ)宾符。

那Cockroach是如何實(shí)現(xiàn)的Serializable隔離級(jí)別酿秸？Cockroach lab有一篇文章，介紹了他們是如何實(shí)現(xiàn)的Serializable隔離級(jí)別魏烫，見(jiàn)Serializable, Lockless, Distributed: Isolation in CockroachDB

想想PostgreSQL實(shí)現(xiàn)Serializable隔離級(jí)別時(shí)需要解決的幾個(gè)問(wèn)題：

1. 實(shí)現(xiàn)類似next key lock的機(jī)制（索引頁(yè)面加鎖）辣苏，解決讀后插入數(shù)據(jù)的問(wèn)題肝箱；
2. 讀加鎖，解決讀后修改的問(wèn)題稀蟋；

Cockroach為了實(shí)現(xiàn)Serializable煌张，提供了兩個(gè)關(guān)鍵的機(jī)制：

1. Cockroach允許snapshot隔離級(jí)別的事務(wù)在提交時(shí)使用一個(gè)更新的timestamp，這是符合snapshot隔離級(jí)別的語(yǔ)義的退客，但是不允許Serializable隔離級(jí)別的事務(wù)使用更新的timestamp骏融，Serializable隔離級(jí)別的事務(wù)會(huì)用一個(gè)timestamp讀取數(shù)據(jù)，同時(shí)也用這個(gè)timestamp提交數(shù)據(jù)井辜，因此Serializable隔離級(jí)別的事務(wù)邏輯上等價(jià)在這個(gè)時(shí)間瞬時(shí)完成绎谦，雖然物理上并非如此。
2. Cockroach內(nèi)所有的key都是按照range組織的粥脚，而非hash窃肠，這為serializab的實(shí)現(xiàn)提供了極大的便利，類似PostgreSQL的predicate lock刷允，Cockroach維護(hù)了一個(gè)單獨(dú)的timestamp cache冤留，記錄了讀寫(xiě)指定范圍內(nèi)的key的timestamp。在寫(xiě)操作發(fā)生時(shí)树灶，會(huì)檢查這個(gè)范圍的最大read timestamp纤怒。如果read timestamp > 事務(wù)的timestamp，那么這兩個(gè)事務(wù)之中就有一個(gè)需要回滾天通。

結(jié)合這兩點(diǎn)泊窘，我們可以發(fā)現(xiàn)，在Cockroach中像寒，Serializable隔離級(jí)別的實(shí)現(xiàn)有兩個(gè)關(guān)鍵點(diǎn)：

1. 通過(guò)固定timestamp烘豹，將所有Serializable隔離級(jí)別的事務(wù)按照Serializable隔離級(jí)別進(jìn)行串行化排序；
2. 通過(guò)timestamp cache诺祸，進(jìn)行讀寫(xiě)沖突的判斷携悯，同時(shí)，cache以range的形式維護(hù)筷笨，也避免了幻讀的問(wèn)題憔鬼；

同樣的，我們分析一下為什么Cockroach的這種方法可以實(shí)現(xiàn)Serializable胃夏？

Cockroach中轴或，每個(gè)Serializable隔離級(jí)別的事務(wù)他們的讀寫(xiě)行為都在另一個(gè)發(fā)生沖突的Serializable隔離級(jí)別的事務(wù)之前或之后，按照timestamp的順序嚴(yán)格排序构订，沒(méi)有任何交叉的可能侮叮，因此一定是Serializable的；

同樣悼瘾，舉一個(gè)Cockroach處理write skew的例子囊榜。

cockraoch-write skew.png

總結(jié)

Mysql使用gap lock的實(shí)現(xiàn)和PostgreSQL使用SSI的實(shí)現(xiàn)更像是悲觀機(jī)制和樂(lè)觀機(jī)制之間的比較。Cockroach則使用了最嚴(yán)格的方式亥宿，但他的并發(fā)性也是這三個(gè)數(shù)據(jù)庫(kù)中最差的卸勺。看下面這個(gè)例子

-- 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;

明顯烫扼，這兩個(gè)事務(wù)可等價(jià)于Tx2->Tx1的串行調(diào)度曙求。但是在不同的數(shù)據(jù)庫(kù)中，他們的行為就各不相同映企。

1. 在MySQL中悟狱，事務(wù)Tx1需要等待事務(wù)Tx2提交后才能提交；
2. 在PostgreSQL中堰氓，兩個(gè)事務(wù)可以無(wú)阻塞的并發(fā)執(zhí)行下去挤渐；
3. 在Cockroach中，左邊的事務(wù)會(huì)回滾双絮；

當(dāng)然浴麻，這并不能說(shuō)明PostgreSQL的實(shí)現(xiàn)方式就優(yōu)于MySQL，在上面write skew的例子中囤攀，PostgreSQL會(huì)繼續(xù)執(zhí)行注定失敗的update软免，如果其后有一些其他的語(yǔ)句，那么無(wú)用操作的開(kāi)銷更多焚挠，而MySQL在update發(fā)生時(shí)就會(huì)立刻回滾膏萧，避免后續(xù)空耗資源。很明顯蝌衔，這還是樂(lè)觀機(jī)制和悲觀機(jī)制的差別榛泛。當(dāng)沖突較多時(shí)，悲觀機(jī)制更優(yōu)胚委，當(dāng)沖突較少時(shí)挟鸠，樂(lè)觀機(jī)制更優(yōu)。

而cockroach亩冬，采用了串行化事務(wù)的所有操作的方式艘希，有最差的并發(fā)性，但也避免了實(shí)現(xiàn)全局鎖的巨大工程開(kāi)銷硅急。

參考文檔

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