A Critique of ANSI SQL Isolation Levels
先叙述一下 A Critique of ANSI SQL Isolation Levels 这篇 paper 在说什么。
在摘要里，这篇 paper 首先介绍了 ANSI SQL-92 是基于“异象”（Anomaly，Phenomena ）来定义的，也就是 Dirty Read、Non-Repeatable Read 和 Phantom。之后这篇 paper 指出这个定义会 fail to characterize several popular isolation levels，包括用锁实现的隔离级别。此外对于异象的定义会导致歧义。所以这篇文章给出了隔离级别更清楚的定义，此外还定义了一些新的异象来将 ANSI 里不能区分的隔离级别分类。最后还给出了多版本的隔离界别，也就是 Snapshot Isolation。
下面我们来详细看看这篇文章是如何介绍上面的这几点的。
Secion 2 介绍了 Isolation Definitions。
Section 2.1 首先给出了 History 的概念，指的是将事务里的操作转换成线性的执行顺序。之后给出了 Dependency Graph 的定义。基于依赖图又给出了两个 History 相等的概念，也就是它们的依赖图完全一致。最后，如果一个事务历史是可串行化（Serializable）的，则意味着这个事务历史的依赖图和一个线性历史（Serial History）的完全相同的。
Section 2.2 则是介绍 ANSI SQL Isolation Levels并指出了里面的两点不足。
其一是对于“异象”的定义过于“strict”，也就是只有错误发生了才定义为异象。因此给出了一个 “broad” 的定义，只要执行历史是 broad 定义的，就可能出现异常。其二是 ANSI SQL 没有准确地给出 Serializable 的定义。另外，Isolation Matrix 最后一行的是 “Amonoly Serializable” ，这个概念只是“不出现上面三种异象”，而并不是 Serializable。所以就会给人造成一种误导：“只要保证不出现这三种异象，就会保证 Serializable ”。因为隔离级别是由“避免异象”定义的，所以如果我们用更 “broad” 的异象定义，就能过滤更多的 history，也就是说我们对于隔离级别的定义是更“strict”的。但即使是使用更严格的定义，避免这三种异象也不能保证 Serializable。Section 3 会详细讨论。
section 2.3 则是在介绍锁相关的概念。因为大多数的数据库都是基于锁来实现的隔离，所以将 ANSI SQL 的隔离级别按照锁来分类是有用的，虽然会引出一些问题。首先，事务在执行的过程中会申请读（共享）锁和写（独占）锁。如果两个锁是两个事务在同一个记录上的，并且其中至少一个是写锁，那么这两个锁就是冲突的。接下来说到谓词锁，谓词锁包括所有满足谓词的记录和所有 INSERT、DELETE、UPDATE 时会包含在谓词里的记录。两个谓词锁的冲突则是至少一个记录同时存在于两个锁的谓词范围内并且至少其中一个锁是写锁。记录锁可以看成是只有一条记录的谓词锁。接下来定义了什么叫做 well-formed、two-phase 和 long/short duration。Well-formed 是指在读（写）记录前都会在对应的记录和谓词上加读（写）锁。Two-phase 则是指在释放读（写）锁之后不会再加读（写）锁。Long duration 是指锁会被事务持有直到事务 commit 或是 abort。而 short duration 则是在读（写）这个“动作”结束后会被立刻释放掉。之后抛出了一个重要的理论：Well-formed two-phase locking guarantees serializability。然后，作者夹杂了一篇自己之前的 paper [GLPT]，没看里面具体的内容。大意是说 ANSI SQL 的定义太模糊了，只有更加数学的定义，也就是以依赖图的历史或是锁，才能 stand the test of time。所以，接下来就引出了以锁的形式来定义的 isolation types。锁的形式包括 scope（记录锁还是谓词锁）、mode（读锁还是写锁）和 duration（长锁还是短锁）。用锁定义的 Isolation Types 就是 ANSI SQL 的隔离级别前面加上 Locking 。但是事实上和 ANSI SQL 的却不太相同。之后，定义了隔离级别之间的 weaker 和 stronger 的关系。如果 L1 is weaker than L2，记做 L1 << L2，说明 L2 允许的非序列化历史 L1 都允许，而且至少存在一个 L1 允许的非序列化历史是 L2 所不允许的。如果 L1 和 L2 的非序列化历史是相同的，那么 L1 == L2。如果 L1 和 L2 都分别存在至少一个历史是对方不允许的，则说明 L1 >< L2，也就是两者不可比较。最后，这个地方只去比较非可序列化历史（non-serializable history）
section 3 是 Analyzing ANSI SQL Isolation Levels。所以看一下作者是怎么分析的。
section 4 主要是讲，在 READ COMMITTED 和 REPEATABLE READ 之间还有许多其它的商业实现的隔离级别。我们来看看都有哪些。
4.1 讲的是 Cursor Stability，一种为了避免 Lost Update 的隔离级别。首先 Lost Update 是什么呢，就是下面这种情况。w2 的更新会被 w1 覆盖掉。
P4: r1[x]...w2[x]...w1[x]...c1
很明显，如果禁止 P0 和 P1，P4 依然可以存在；但是如果禁止 P2 的话，P4 就不会存在了。所以 Lost Update 在 Read Committed 时会发生，但是在 Repeatable Read 下会被禁止。换言之，禁止了 Lost Update 的 Cursor Stability 比 RC 要强但是比 RR 要弱。
RC << Cursor Stability << RR
接下来看 Cursor Stability 是如何避免 Lost Update 的。在从 cursor 上读的时候加一个（读）锁，直到 cursor 移动或是关闭；同样，如果要写 cursor 的记录的话，就要加一个整行的（写）锁并且持有这个锁直到事务提交，即使 cursor 移动了。其实就是一个 short term 的 cursor 读锁加一个 long term 的 cursor 写锁。这两个动作分别对应 rc 和 wc。一个 rc1[x] 和一个之后的 wc1[x] 会排除掉中间的 w2[x]。因此也就防止了 P4 和 P4C。
P4C: rc1[x]...w2[x]...w1[x]
之后说的是很多 RC 的事实标准都实现了 CS。
最后说 CS 可以在多条记录上实现，只要放多个 cursor 就可以了。因此如果在一个事务要 access 的所有记录上放置 cursor，就可以将 CS 进化成 RR。但是这种方法并不是很方便和普遍。因此会有一些历史记录满足 P4（因此也满足更普遍的 P2）并没有被 CS 排除掉。Thus there are always histories fitting the P4 (and of course the more general P2) phenomenon that are not precluded by Cursor Stability.
挖个坑，SI 过段时间来补上。
Reference
A critique of ansi sql isolation levels 先介绍了 sql 锁机制下的隔离级别以及怎么实现，之后提到了 MVCC 的 snapshot isolation 与 write skew，最后对隔离级别进行了一个排序。
A critique of ansi sql isolation levels 上面那篇博客提到的 paper
隔离级别的一些 tips 上面两篇的补充，还提到了解决 write skew 的方法：serializable snapshot isolation
