本文是我對最近讀的幾篇論文的總結(jié)，沒有太多引用原文，純靠自己的理解和印象串聯(lián)起來。主要是為日后深入了解相關(guān)知識做個簡單“索引”。

本文描述得不是很嚴謹，也不保證完全正確，建議有興趣的同學(xué)去閱讀論文——根據(jù)論文名稱搜索就可以找到。

ACID

事務(wù)是關(guān)系數(shù)據(jù)庫操作的邏輯單位。
事務(wù)的存在，是為從數(shù)據(jù)庫層面保證數(shù)據(jù)的安全性，減輕應(yīng)用程序的負擔。

說起“事務(wù)”，總會先想起 “ACID” 四個字母。

• A：Atomicity，原子性。
• C：Consistency，一致性。
• I：Isolation，隔離性。
• D：Durability，持久性。

原子性、一致性和持久性都比較好理解。

一個事務(wù)可能包含一個或多個操作，原子性保證這些操作要么全部被生效，要么全部不被生效。
數(shù)據(jù)庫的一致性是指數(shù)據(jù)庫中的數(shù)據(jù)都滿足“完整性約束”，如主鍵的唯一約束。

事務(wù)提交后，要永久保存到數(shù)據(jù)庫中，這就是持久性。簡單地說就是數(shù)據(jù)要落盤。為了提高系統(tǒng)的可用性，數(shù)據(jù)還應(yīng)該通過某種算法復(fù)制到其它機器。

隔離性是這幾個特性里面比較不好理解的。單個事務(wù)的場景下，談隔離性是沒意義的——事務(wù)之間有并發(fā)才有隔離的必要。簡單地說，隔離性指的就是數(shù)據(jù)庫在并發(fā)事務(wù)下的表現(xiàn)。權(quán)衡安全和性能，數(shù)據(jù)庫一般會有多個隔離級別。

隔離級別

SQL 標準里定義了四個隔離級別：

• 讀未提交（Read Uncommitted）：會出現(xiàn)臟讀（Dirty Read）—— 一個事務(wù)會讀到另一個事務(wù)的中間狀態(tài)。
• 讀已提交（Read Committed）：會出現(xiàn)不可重復(fù)讀（Unrepeatable Read） —— 事務(wù)只會讀到已提交的數(shù)據(jù)，但是一行數(shù)據(jù)讀取兩遍得到不同的結(jié)果。
• 可重復(fù)讀（Repeatable Read）：會出現(xiàn)幻讀（Phantom Read） —— 一個事務(wù)執(zhí)行兩個相同的查詢語句，得到的是兩個不同的結(jié)果集（數(shù)量不同）。
• 可串行化（Serializable）：可以找到一個事務(wù)串行執(zhí)行的序列，其結(jié)果與事務(wù)并發(fā)執(zhí)行的結(jié)果是一樣的。

SQL 標準定義的的這四個隔離級別，只適用于基于鎖的事務(wù)并發(fā)控制。后來有人寫了一篇論文 A Critique of ANSI SQL Isolation Levels 來批判 SQL 標準對隔離級別的定義，并在論文里提到了一種新的隔離級別 —— 快照隔離（Snapshot Isolation，簡稱 SI）。

Snapshot Isolation

在 Snapshot Isolation 下，不會出現(xiàn)臟讀、不可重復(fù)度和幻讀三種讀異常。并且讀操作不會被阻塞，對于讀多寫少的應(yīng)用 Snapshot Isolation 是非常好的選擇。并且，在很多應(yīng)用場景下，Snapshot Isolation 下的并發(fā)事務(wù)并不會導(dǎo)致數(shù)據(jù)異常。所以，主流數(shù)據(jù)庫都實現(xiàn)了 Snapshot Isolation，比如 Oracle、SQL Server、PostgreSQL、TiDB、CockroachDB（關(guān)于 MySQL 的隔離級別，可以參考這篇文章）。

雖然大部分應(yīng)用場景下，Snapshot Isolation 可以很好地運行，但是 Snapshot Isolation 依然沒有達到可串行化的隔離級別，因為它會出現(xiàn)寫偏序（write skew）。Write skew 本質(zhì)上是并發(fā)事務(wù)之間出現(xiàn)了讀寫沖突（讀寫沖突不一定會導(dǎo)致 write skew，但是發(fā)生 write skew 時肯定有讀寫沖突），但是 Snapshot Isolation 在事務(wù)提交時只檢查了寫寫沖突。

為了避免 write skew，應(yīng)用程序必須根據(jù)具體的情況去做適配，比如使用SELECT ... FOR UPDATE，或者在應(yīng)用層引入寫寫沖突。這樣做相當于把數(shù)據(jù)庫事務(wù)的一份工作扔給了應(yīng)用層。

Serializable Snapshot Isolation

后來，又有人提出了基于 Snapshot Isolation 的可串行化 —— Serializable Snapshot Isolation，簡稱 SSI（PostgreSQL 和 CockroachDB 已經(jīng)支持 SSI）。

為了分析 Snapshot Isolation 下的事務(wù)調(diào)度可串行化問題，有論文提出了一種叫做 Dependency Serialization Graph (DSG) 的方法（可以參考下面提到的論文，沒有深究原始出處）。通過分析事務(wù)之間的 rw、wr、ww 依賴關(guān)系，可以形成一個有向圖。如果圖中無環(huán)，說明這種情況下的事務(wù)調(diào)度順序是可串行化的。這個算法理論上很完美，但是有一個很致命的缺點，就是復(fù)雜度比較高，難以用于工業(yè)生產(chǎn)環(huán)境。

Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions 證明在 Snapshot Isolation 下, DSG 形成的環(huán)肯定有兩條 rw-dependency 的邊。

Making snapshot isolation serializable 再進一步證明，這兩條 rw-dependency 的邊是“連續(xù)”的（一進一出）。

后來，Serializable Isolation for snapshot database 在 Berkeley DB 的 Snapshot Isolation 之上，增加對事務(wù) rw-dependency 的檢測，當發(fā)現(xiàn)有兩條“連續(xù)”的 rw-dependency 時，終止其中一個事務(wù)，以此避免出現(xiàn)不可串行化的可能。但是這個算法會有誤判——不可以串行化的事務(wù)調(diào)用會出現(xiàn)兩條“連續(xù)”的 rw-dependency 的邊，但是出現(xiàn)兩條“連續(xù)”的 rw-dependency 不一定會導(dǎo)致不可串行化。

Serializable Snapshot Isolation in PostgreSQL 描述了上述算法在 PostgreSQL 中的實現(xiàn)。

上面提到的 Berkeley DB 和 PostgreSQL 的 SSI 實現(xiàn)都是單機的存儲。A Critique of Snapshot Isolation 描述了如何在分布式存儲系統(tǒng)上實現(xiàn) SSI，基本思想就是通過一個中心化的控制節(jié)點，對所有 rw-dependency 進行檢查，有興趣的可以參考論文。