ANSI SQL-92通过phenomena定义的隔离级别是基于single-version和lock的，有宽松解释和严格解释（所谓的Anomaly）。严格解释并不能描述所有隔离级别，而宽松解释是有缺陷的（缺少Dirty Write和P3），在原有的3种phenomena上扩展得到P0,P1,P2,P3，同时该新的phenomena-base的隔离级别的定义和lock-base隔离级别的定义是完全等价的。

下图总结了不同隔离级别的差异，上面的等级高于下面的等级；等级之间的连线表明不同隔离级别之间的phenomena差异；

有趣的结论：

1. snapshot isolation隔离级别比RC严格，和RR之间并没有可比性：RR会幻读，snapshot isolation不会；snapshot isolation有Write skew，而RR不会；

2. Oracle Consistent Read比RC严格，和RR相比，它又有不可重复度的异常；

3. Oracle Consistent Read并不是严格的snapshot isolation，有上面所说的不可重复度异常，有lost update的异常，oracle是first-write-wins；而snapshot isolation的实现是first-commit-wins，不会有lost update（commit时发现item被并发事务修改中或者已经修改完成，则本事务abort）；

下面正文开始：

Abstract

ANSI SQL-92通过phenomena-base（Dirty Read，Non-Repeatable Reads, Phantoms）来定义的隔离级别是不完备的。本文进行了详细的分析，并提出了更加形式化的phenomena-base的隔离级别的定义。讨论了snapshot isolation隔离级别的特点。

1. Introduction

2. Isolation Definitions

2.1 Serializability Concepts

transaction: 一组操作，使得db从一个一致的状态转移到另一个一致的状态；

history：一组事务的多个操作交替执行的序列；

conflict：在一个history中，两个事务操作同一个data item，且其中一个是写操作；

dependency graph：在history中已经提交的事务的每个operation表示一个图的节点，如果事务T1的op1和事务T2的op2发生了conflict关系，<Op1，Op2>之间就存在一条边；

两个history是等价的：有相同的committed事务集合，且dependency graph相同；

如果一个history和串行化的history等价，那么该history就符合串行化；

2.2 ANSI SQL Isolation Levels

ANSI SQL隔离级别的设计者们试图设计出适用于多种技术实现的事务系统，而不仅仅是基于锁的事务系统，通过下面3种phenomena来定义隔离：

P1（Dirty Read）：T1修改了一个data item，T2在T1commit/rollback前读到了该data item，如果T1执行rollback，那么T2就读到了没有提交过的数据；

P2（Non-repeatable or Fuzzy Read）：T1读取data item，之后，T2修改或者删除了data item且该行为commit了，然后T1再次读取时发现数据被修改，或者删除了；

P3（Phantom）：T1通过一个读取到了一批数据，T2创建了一些数据，正好符合该，T1再次读取时发现读取的数据集合和之前不同了；

事务串行化理论中上述3种phenomena都不允许出现。

一些缩写：

事务1写x -> w1[X]

事务2读x -> r2[x]

事务1读取符合条件P的数据 -> r1[P]

事务1写符合条件P的数据 -> w1[P]

事务1提交 -> c1

事务1abort -> a1

P1可以形式化表达为：

(2.1) w1[x] ... r2[x] ... (a1 and c2，顺序无关)

ANSI的P1的文本描述是不精确的，并没有指出T1会进入abort；P1仅仅描述了如果该种执行顺序发生的话，就会发生导致DB不一致的结果，因此有些学者会把P1解读为：

(2.2) w1[x] ... r2[x] ... ((c1 or a1) and (c2 or a2) 顺序无关)

不允许T1修改数据，之后T2读取数据，无论T1是commit还是abort。

2.2和2.1相比是宽松的定义，它禁止了T1和T2之间4中可能的commit-abort组合。2.2可以看做是P1的某个执行序列在未来可能会导致异常。

P1：2.2称为P1的宽松解释(loose interpretation)，描述了可能导致异常的phenomena；

A1：2.1称为P1的严格解释(strict interpretation)，描述了一定会导致异常的phenomena；

因此，

P1：w1[x] ... r2[x] ... ((c1 or a1) and (c2 or a2) 顺序无关)

A1：w1[x] ... r2[x] ... (a1 and c2，顺序无关)

P2：r1[x] ... w2[x] ...((c1 or a1) and (c1 or a2)顺序无关)

A2：r1[x] ... w2[x] ... c2 ... r1[x] ... c1

P3：r1[P] ... w2[y in P] ... ((c1 or a1) and (c1 or a2)顺序无关))

A3：r1[P] ... w2[y in P] ... c2 ... r1[P] ... c1

ANSI 定义的P1,P2,P3仅仅适用于single-version history（和multi-version相比）。ANSI SQL定义了4种隔离级别。每个隔离级别通过3种phenomena来定义，并没有具体指出SERIALIZABLE应该符合哪些执行序列，不允许P1,P2,P3发生的隔离级别称为ANOMALY SERIALIZABLE。真正的SERIALIZABLE并不等价于不发生P1,P2，P3（P3不能准确的描述SERIALIZABLE）。

2.3 Locking

有些SQL产品的隔离级别是基于锁来实现的，ANSI SQL使用锁的属于来描述隔离级别仍然是有用的，即使这种方法存在一些问题。

在基于锁的事务调度下，事务在执行期间请求Read/Write锁，如果两个事务对同一个data item上锁，且至少一个是Write锁，则发生了conflict。

Predicate lock对所有符合的item集合上锁，该集合可能是无穷大集合，因为insert或者update的item也符合条件。record lock是特殊的predicate lock：他的就是单指当前的record。

well-formed：事务的每次读写date item都严格对item（或者集合）上锁；

2PL锁：一旦开始释放锁，后续就不再请求新的锁（前面阶段申请锁，后面阶段释放锁）；

long duration：事务在成功获得锁后，只在commit/abort时才释放锁；

short duration：事务在成功获得锁后，用完即释放的锁；

基础的串行化理论：well-formed + two-phase locking。每个two-phase locking的执行序列都等价于一个串行化执行。反之，如果不遵守well-formed或者two-phase locking就不是串行化。

GLPT论文中试图建立locking, dependency, anomaly-based隔离级别的联系，定义了4种一致性。ANSI SQL定义的隔离级别实际上就是下面以locking开头的隔离级别。

当时phenomena-based和lock-base定义的隔离级别之间有比较大的差异。GLPT定义了degree-0，仅仅要有原子写。而degree 1，2，3分别是locking READ UN- COMMITTED, READ COMMITTED, 和SERIALIZABLE。但是GLPT并没有给locking REPEATABLE READ定义一个degree。

隔离级别的强弱定义

L1比L2弱，记做：L1 << L2。所有执行history满足L2的隔离级别定义时，一定满足L1的定义，同时存在一个在L1约束下面发生的history，在L2下面不会发生（通过集合的包含概念来定义）。

同理，两个级别L1和L2不可比较，记做：L1 >><< L2，互相都有一个执行history在对方的标准中不允许发生（互相没有包含的关系）。

Remark 1: 
  Locking READ UNCOMMITTE
    << Locking READ COMMITTED
        << Locking REPEATABLE READ
            << Locking SERIALIZABLE

3. Analyzing ANSI SQL Isolation Levels

Remark 2: 可以证明Table2中的lock-base隔离级别的定义至少和Table1中phenomena-base隔离级别一样强。

那么，lock-base的隔离级别是否比ANSI的隔离级别更加的具有‘隔离性’呢？答案是肯定的，即使在低级别的lock-base定义的隔离性也比ANSI低级别的隔离性要强。比如，Locking READ UNCOMMITTED要求long duration write锁，避免“dirty wirte”，而ANSI的READ UNCOMMITTED并没有排除这种异常。

P0（Dirty Write）：T1修改item，在T1执行commit/rollback之前，T2随后也修改item。后续如果T1或者T2要执行rollback，就无法确定要rollback到哪个值了。

P0：w1[x] ... w2[x] ... ((c1 or a1) and (c1 or a2)顺序无关))

Dirty Write会打破DB的一致性约束。比如：存在一个约束 x=y，如果T1和T2分别执行会时刻维护这个约束。但是当交替执行时该约束很容易被打破，比如一个执行history如下：

w1[x] ... w2[x] ... w2[y] ... c2 ... w1[y] ... c1

T1和T2对x，y的修改都成功了，但是如果T1写入1，T2写入2，那么就违背了该约束。

约束被破坏一定发生了Dirty Write。

P0的之所以重要是因为它决定了事务能否正确的rollback到事务开始前的状态，如果存在dirty write就无法rollback。

比如：w1[x] ... w2[x] ... a1，

如果T1执行rollback时，把x的值rollback到T1之前的值，就会覆盖w2刚刚写入的值，当T2commit时它写的值被覆盖了；

如果T1不把x的值rollback到T1之前的值，那么当T2也rollback时，T2无法知道之前的值是什么（T2开始时不知道T1之前的值是什么）；

这也就是为什么即使是最低级别的隔离也需要持有long duration写锁。

Remark2：ANSI SQL定义的所有隔离级别应包含了P0的语义（不允许dirty wirte）。

证明过程如下，

ANSI隔离级别的3中strict解释：

A1：w1[x] ... r2[x] ... (a1 and c2，顺序无关) (脏读)

A2：r1[x] ... w2[x] ... c2 ... r1[x] ... c1 (不可重复度)

A3：r1[P] ... w2[y in P] ... c2 ... r1[P] ... c1 (幻读)

x=50，y=50，T1从x向y转账40，其中一个执行序列如下：

H1: r1[x=50]w1[x=10]r2[x=10]r2[y=50]c2r1[y=50] w1[y=90]c1

H1是非串行化的执行序列，但是并没有违背A1,A2,A3。因此严格解释并不是ANSI的正确解释，考虑宽松解释：

P1：w1[x] ... r2[x] ... ((c1 or a1) and (c2 or a2) 顺序无关)

H1确实违背了P1，T1先更新了x，然后T2读取x。

因此：侧面佐证ANSI中phenomena-base定义的隔离级别实际上是指宽松解释中定义的各种异常。

同理ANSI中的repeatable read是指P2而非A2，比如：

H2: r1[x=50]r2[x=50]w2[x=10]r2[y=50]w2[y=90]c2 r1[y=90]c1

H2是非串行化的执行序列，没有违背P1，没有违背A2，但是违背了P2：

P2：r1[x] ... w2[x] ...((c1 or a1) and (c1 or a2)顺序无关)

T1没有像A2描述那样读取两次x，T1先读取了x，随后T2更新了x，等T1读取y时，他读取到的x已经过时。

同理，

H3: r1[P] w2[insert y to P] r2[z] w2[z] c2 r1[z] c1

H3没有违背A3，因为T1没有执行两次r1[P]，它只读取了一次，而T2则进行了插入和更新。但是违背了P3:

P3：r1[P] ... w2[y in P] ... ((c1 or a1) and (c1 or a2)顺序无关))

Remark 4：描述隔离级别的严格解释A1,A2,A3是有缺陷的，宽松解释P1,P2,P3是正确的。
    Remark 5：ANSI SQL的phenomena是不完整的，需要定义新的phenomena，另外，P3也需要修订。

修订之后的phenomena如下：

P0: w1[x]...w2[x]...(c1 or a1)             (Dirty Write)
    P1: w1[x]...r2[x]...(c1 or a1)              (Dirty Read) 
    P2: r1[x]...w2[x]...(c1ora1)                (Fuzzy 或者 Non-Repeatable Read)
    P3 : r1[P]...w2[y in P]...(c1 or a1)     (Phantom)

ANSI中的P3描述是的符合条件P的insert和update，而此处修订后的P3描述了所有符合条件P的写入（insert, update, delete）。

修订后的phenomena-base的隔离级别定义如下：

P0,P1,P2,P3的基于phenomena的描述实际上就是table2中基于锁的描述，这里做一下对比：

P0：为了阻止其他事务对x的脏写，需要long-duration的写锁，因此其他更高级别的隔离都需要long-duration写锁（对应table2中的最后一列中每个级别都有long-duration写锁）；

P1：为了阻止脏读，需要well-formed读锁；

P2：为了阻止不可重复度，需要long-duration的读锁；

P3：为了阻止幻读，需要long-duration predicat锁；

因此，table2和table3的定义是等价的。

Remark 6：table2中lock-based隔离级别的定义和table3中的phenomena-base隔离级别的定义是等价的。

4. Other Isolation Types

4.1 Cursor Stability

Cursor Stability是为了防止lost update异常。

P4（Lost Update）：T1读取item，T2根据自己之前读取的更新item，T1更新item。

P4：r1[x]...w2[x]...w1[x]...c1        (Lost Update)

下面的例子中即使T2提交了，T2的update也会丢失：

H4：r1[x=100] r2[x=100] w2[x=120] c2 w1[x=130] c1

P4可能在READ COMMITED级别下发生，因为P0,P1下H4不会发生，但是在P2下H4会发生：T1会对x上long-duration的读锁，导致T2无法在T1 commit之前更新x。

因此Cursor Stability介于RC和RR之间。

Cursor Stability隔离级别的实现通过对Read Commited锁行为扩展得到，通过cursor读item时需要在原来RC的well-formed读锁上，再加一条：在当前cursor下面该读锁不会释放，直到cursor发生了move/closed。

rc1[x]，wc1[x]和T2的w2[x]会交替执行，因此P4重新定义为：

P4C：rc1[x]...w2[x]...w1[x]...c1        (Lost Update)

Remark7：READ COMMITTED << Cursor Stability << REPEATABLE READ

大部分SQL系统的RC就是增强了的Cursor Stability。

4.2 Snapshot Isolation

基于snapshot的事务隔离系统，永远读取事务开始时刻的数据版本Start-Timestamp。事务中的读操作永远不会被阻塞。其他事务的更新会在下一次Start-timestamp中被读取到。

Snapshot Isolation是一种多本版并发控制技术，对Multiversion Mixed Method的扩展。

当事务T1提交时，申请一个Commit-timestamp，大于Start-timestamp和所有已知Commit-timstamp。T1成功commit：不存在事务T2，它的commit-stamp介于[Start-timestamp, Commit-timstamp]之间，同时T2更新的数据集，T1也更新过。

为了防止Log update，T1主动abort，即fist-commit-wins。T1的变更对所有Start-timestamp大于T1的Commit-timstamp可见。

多版本中的读操作关键是选择合适的版本来读取。

在snapshot隔离下，同样的操作序列会导致多值的序列发生（仿佛发生了时间线分叉）。

H1: r1[x=50]w1[x=10]r2[x=10]r2[y=50]c2r1[y=50] w1[y=90]c1
    H1.SI: r1[x0=50] w1[x1=10] r2[x0=50] r2[y0=50] c2 r1[y0=50] w1[y1=90] c1

上述H1.SI的执行序列和串行执行T1和T2效果相当。可以证明Snapshot isolation中任何history都可以映射到single-valued的history，而且都具有相同的dependency。

比如上述：

H1.SI.SV: r1[x=50] r1[y=50] r2[x=50] r2[y=50] c2 w1[x=10] w1[y=90] c1

把MV的执行history映射到SV执行history，是把MV放到隔离级别体系中的唯一方法。

Snapshot Isolation不是串行化的，因为它的读和写仍然是在不同的时刻会导致其他事务穿插进来，比如：

H5: r1[x=50] r1[y=50] r2[x=50] r2[y=50] w1[y=-40] w2[x=-40] c1 c2

H5是SV中的执行history，它不是串行化的隔离。该执行history在Snapshot Isolation中也对应有一个，因此MV也不是串行化。

Constraint

约束被打破是事务在并发执行时的异常。事务在开始时读取到DB已经违反了约束，该事务就观察到约束在并发时的异常，称为inconsistent analysis。

A5 (Data Item Constraint Violation)：C()是数据项x和y之间的约束，会有以下两种异常。

Read Skew

A5A Read Skew：事务T1读取x，T2更新x，y，T1读取y，对于T1读取到的x和y不符合约束。

A5A: r1[x]...w2[x]...w2[y]...c2...r1[y]...(c1 or a1)        (Read Skew)

之所以称为read skew，该异常关联两个数据项x和y，正常应该读取到x和y对等的数据，就像天平的两端，现在其中一个值被其他事务更新，导致读取到的版本不对等，天平出现了倾斜。

Write Skew

A5B Write Skew：T1读取x，T2读取y，T2更新了x，T1更新y。交叉更新。

A5B: r1[x]...r2[y]...w1[y]...w2[x]...(c1 and c2 occur)    (Read Skew)

A5和P2的关系

P2：r1[x] ... w2[x] ...((c1 or a1) and (c1 or a2)顺序无关)

P2是可重复读的隔离级别，它是A5A的特殊场景（x=y）。A5是更加普遍的场景：读取不同的有关联的item。A5B交叉更新在银行的数据模型中比较常见。

只要P2不会发生，A5A和A5B就不会发生，因为A5中的T2都更新了T1读取到的item且T1未commit（重复读的定义）。

因此，A5A和A5B可以用来衡量REPEATABLE READ的隔离级别的实现是否正确。

ANSI中REPEATABLE READ的严格定义（也就是A2）会有read skew和write skew的情况（A5），而table2中的Locking REPEATABLE READ（等价于P2）不会有A5的情况。

Snapshot Isolation和其他隔离级别的关系

下面对照隔离级别的phenonmena来逐个对比。

P0: w1[x]...w2[x]...(c1 or a1)             (Dirty Write)
    P1: w1[x]...r2[x]...(c1 or a1)              (Dirty Read) 
    P2: r1[x]...w2[x]...(c1ora1)                (Fuzzy 或者 Non-Repeatable Read)
    P3 : r1[P]...w2[y in P]...(c1 or a1)     (Phantom)

Snapshot Isolation和RC

Remark 8. READ COMMITTED << Snapshot Isolation

Snapshot Isolation的隔离级别比RC强，证明：

1. 在Snapshot Isolation中，first-commit-wins阻止了P0的发生；

2. timestamp机制阻止了P1的发生；因此Snapshot Isolation至少不比 READ COMMITTED弱；

3. 另外，A5A在RC中是可能发生的，在Snapshot Isolation中不会发生；

4. 因此，Snapshot Isolation<< Snapshot Isolation

Snapshot Isolation和RR

Remark 9. REPEA T ABLE READ >><< Snapshot Isolation.

Snapshot Isolation隔离级别和RR无可比性，证明：

1. Snapshot Isolation不会发生A2，但是会发生P2（比如：A5B），因此从A5B的角度看Snapshot Isolation比RR要弱；

2. Snapshot Isolation不会发生A3（没有幻读），而RR有A3；

3. 因此，不具有可比性。

然而，Snapshot Isolation不会发生A3但是会发生P3，比如，

约束：找到所有job，其总和不超过8小时

T1：发现当前所有job总和为7，因此T1可以插入一个新的为1的job；

T2：也发现当前所有job总和为7，因此T2可以插入一个新的job；

因为T1和T2插入不同的item，first-commit-wins没有阻止T1和T2。

因此最终约束被打破了。

Snapshot Isolation和SER级别

Snapshot Isolation最重要的特点是：没有A3。

因此，从ANSI的ANOMALY（严格解释）来说：

Remark 10. Snapshot Isolation阻止了A1, A2 and A3。因此从table1的ANSI的严格解释来说：
  ANOMALY SERIALIZABLE << SNAPSHOT ISOLATION

Snapshot Isolation的特点

Snapshot Isolation使得并发事务在读取时无需锁等待。在一个老的timestamp下更新时，如果被更新的事务（并发事务）更新了，则使用first-commit-wins，当前事务abort（PostgreSQL的实现是如果当前是RC则允许更新，存在lost update的问题；如果是RR/SSI则abort）；

first-commit-wins要求每个item记录被哪些事务更新过（更新过程上行锁），然后通过可见性判断得到更新item的事务和当前事务关系是否是并发的。

Snapshot Isolation的first-commit-wins有点类似“乐观”的事务控制技术，在长事务+短事务，且存在冲突时，会导致长事务频繁abort，导致性能回退。

对于短事务冲突很少，且长事务大部分是read-only的场景性能理论上最高。

4.3 Other Multi-Version Systems

一些DB的Snapshot Isolation只允许read only。

PostgreSQL维护数据版本且允许更新，允许长事务的快照查询。

ORACLE允许更新，但是不是first-commit-wins。Oracle Read Consistency在事务开始时分配一个最新的已提交数值（本论文中没有详细提及，猜测是SCN），在事务判断时底层会重新计算每row是否可见。insert/update/delete时被Write Lock保护（行锁），只要上锁成功就可以更新，因此是first-writer-wins而不是first-commit-wins（PG也是行锁，在拿到行锁后会去校验下当前的隔离级别，如果是RC继续更新，如果是RR/SSI则abort）。

Oracle Read Consistency隔离比RC强（不会发生P4C：cursor lost update）,但是会有P3，P4，A5A。而Snapshot Isolation不允许P4或者A5A，因此并非严格的Snapshot Isolation。

Oracle Read Consistency >> RC

SQL标准中要求事务中的每个SQL statement是原子的，每个SQL statement开启前是一个子事务（timestap），可以通过赋予不同的timestamp派生出不同的隔离级别。比如：Oracle的cursor fetch在cursor开启时分配一个timestamp。

5. Summary and Conclusions

ANSI通过phenomena-base的文本描述来定义隔离级别是存在歧义且不是完整的。Dirty Write（P0）没有显示的描述。

这里再回顾下P0：

P0（Dirty Write）：T1修改item，在T1执行commit/rollback之前，T2随后也修改item。后续如果T1或者T2要执行rollback，就无法确定要rollback到哪个值了。
  P0：w1[x] ... w2[x] ... ((c1 or a1) and (c1 or a2)顺序无关))

我们提出了如下的phenomena-base的隔离级别的定义，和lock-base的定义是等价的：

P0: w1[x]...w2[x]...(c1 or a1)             (Dirty Write)
    P1: w1[x]...r2[x]...(c1 or a1)              (Dirty Read) 
    P2: r1[x]...w2[x]...(c1ora1)                (Fuzzy 或者 Non-Repeatable Read)
    P3 : r1[P]...w2[y in P]...(c1 or a1)     (Phantom)

ANSI定义的RR排除了出幻读之外其他的异常，事实上table1中的严格解释并没有做到，而table2中lock-base的定义做到了RR的精确定义。ANSI的RR术语存在2个问题：

1. 重复读没有重复的结果集；

2. 多个商用数据库中的RR术语等同于串行化；

上图描述了不同隔离等级之间的关系：上面的等级高于下面的等级；等之间的连线表明不同隔离级别之间的phenomena；

事务隔离源远流长，此处仅仅开了个头~~~