隔离性简介

先理清一些基本概念。

在数据库系统中，事务是一个程序执行单位，它访问且可能更新不同的数据项。事务通常由高级数据操纵语言（代表性的是SQL）或编程语言用对数据库的访问接口编写的用户程序执行所引起。事务具有ACID特性：

1. 原子性
   原子性保证事务的所有影响在数据库中要么全部反映出来，要么根本不反映（或描述成：要么全部执行，要么完全不执行）。一个故障不能让数据库处于事务部分执行后的状态。

2. 一致性
   一致性保证若数据库一开始是一致的，则事务（单独）执行后数据库仍处于一致状态。

3. 隔离性
   隔离性保证并发执行的事务相互隔离，使得每个事务感觉不到系统中其他事务的并发执行。

4. 持久性
   持久性保证一旦一个事务提交后，它对数据库的改变不会丢失，即使系统可能出现故障。

事务处理系统通常允许多个事务并发执行，这些事务会对数据进行读写。多个事务并发更新数据，会引起许多数据一致性的复杂问题。如果强制事务串行执行，就简单得多：一次只执行一个事务，仅当前一事务执行完之后才执行后一个事务。但是允许并发有以下好处：

• 提高吞吐量和资源利用率
  计算机部件如CPU、磁盘等可以并行运作，允许多个事务并发可以增加吞吐，提升各组件的利用率

• 减少等待时间
  串行执行事务可能会迫使短事务等待前面的长事务完成，导致难以预测的延迟。并发执行可以降低延迟，减少事务的平均响应时间

在数据库中使用并发执行的动机在本质上与操作系统中使用多道程序(multiprogramming)的动机是一样的。

当多个事务并发执行时，各个事务的中间状态可能暴露出来，从而违背事务之间的隔离性，各个事务都不能正确执行，数据库的一致性也可能被破坏。数据库系统必须控制事务之间的交互，以防止它们相互影响，破坏数据库的一致性。数据库有一套称为并发控制机制(concurrency-control scheme)的一系列机制来保证这一点。

一个事务往往会包含多个操作（或称指令）。并发控制必须要决定事务各的调度，也就是事务的各指令的执行顺序。事务调度是串行的，定义为：一个调度中，各个事务按先后顺序执行，并且同一个事务的指令紧挨在一起。在并发执行环境，如果一个调度S可以经过一系列等价指令交换转换成串行的调度S'，它就称为可串行化的。例如下面的调度2是串行调度，调度1是可串行化的。

调度1:
时间流逝方向 ->
T1：r(A) w(A)            r(B) w(B)
T2：          r(A) w(A)            r(B) w(B)

可以转换成

调度2：
T1：r(A) w(A) r(B) w(B)
T2：                    r(A) w(A) r(B) w(B)

可串行化允许用户忽略不同事务的并发，简化了并发控制相关的问题。但严格的可串行化，只允许很小的并发度，为了提升执行并发度，现代的数据库都允许采用较弱级别的一致性，允许事务在一些与其他事务非串行化的方式执行，这些方式被定义成不同的隔离级别(对应不同的一致性级别)。

一组事务之间的指令交错执行过程也称为历史(history)，在论文中的2.1节有提到，上述两种调度的结果就是两个历史。

《A Critique of ANSI SQL Isolation Levels》论文

SQL-92 隔离级别

ANSI/ISO SQL-92标准（简称SQL-92）定义了4个隔离级别：

1. 读未提交(READ UNCOMMITTED)
2. 读已提交(READ COMMITTED)
3. 可重复读(REPEATABLE READ)
4. 可串行化(SERIALIZABLE)

这4个隔离级别是用几种现象(phenomenon)来定义的，这些现象分别是：脏读(Dirty Read)，不可重复读(Non-Repeatable Read)和幻读(Phantom)。现象这个概念在SQL-92里面并没有显式的定义，但标准建议现象是可能会导致异常行为(anomalous behavior)的动作子序列。异常和现象其实有严格的技术区别，但在这个区别不影响一般性的理解。

论文的第2部分先介绍了SQL-92的隔离级别的定义。首先给出了data item和predicate的描述：

• data item：可以指数据表的一行，一个页面，整个表，消息队列中的一个消息。在论文中的各场景都可以简单理解成数据表的一行，data item操作就对应常说的点查/单点写
• Predicate: 中文翻译为谓词，指在多个data item组成的集合上的操作，对应日常说的批查/批写。举例，Predicate lock即是范围锁，SQL中条件sum(x, y) > 100即是一个predicate查询条件，它作用在两个data item x和y。

论文介绍了用来描述历史的标记法。w1[x]表示事务1对data item x的write操作，r2[x]表示对x的读操作。predicate操作用P来替代data item x，因此事务1读或写一个data item集合表示成r1[P]或w1[P]。另外，事务1的提交或回滚操作分别表示成c1和a1。

SQL-92定义了3种现象：

1. P1 (Dirty Read，脏读)

   事务T1修改了一个data item。然后另一个事务T2在事务T1提交(COMMIT)或回滚(ROLLBACK)之前读取了这个data item的值。如果T1后面回滚了，T2就读到了一个没被提交因此从不存在的值。

   上述定义可以用前面提过的标记法表示成
   (2.1) w1[x]...r2[x]...(a1 and c2 in either order)
   这个定义的问题是描述模糊。它没有坚决表明T1是不是回滚。有的人会理解成
   (2.2) w1[x]...r2[x]...((c1 or a1) and (c2 or a2) in any order)
   上面的(2.2)是一个比(2.1)更宽泛的解释，因为它包含了4种可能的T1, T2两个事务的提交或回滚的组合，而(2.1)只包含了2种组合。在(2.2)中，无论T1是提交还是回滚，T2都读到了一个未提交的数据。我们将(2.2)称为宽泛解释(broad interpretation)，而将(2.1)称为P1的严格解释(strict interpretation)，前者描述了一种可能造成异常的现象(phenomenon)，但是后者描述了实际发生的异常(anomoly)，因为用不同的标记来描述严格解释和扩大化的宽泛解释：

   P1: w1[x]...r2[x]...((c1 or a1) and (c2 or a2) in any order)
   A1: w1[x]...r2[x]...(a1 and c2 in either order)
   

2. P2 (Non-repeatable or Fuzzy Read，不可重复读)

   事务T1读一个data item。然后另一个事务T2修改或删除了这个data item并提交。如果之后T1尝试重读这个data item，它会读取一个被修改过的值，或者发现这个data item已经被删除。

   类似地可以得到宽泛解释和严格解释：

   P2: r1[x]...w2[x]...((c1 or a1) and (c2 or a2) in any order)
   A2: r1[x]...w2[x]...c2...r1[x]...c1
   

   在宽泛解释中，只要T1读过x，而不阻塞T2对x的写，就有可能导致异常。

3. P3 (Phantom，幻读)

   事务T1读一个满足某个条件(<search condition>)data item的集合。然后事务T2插入了满足此条件的data item并提交。如果之后T1用同样的条件重复它的读操作，它会读到一个与第一次读到的结果不同的data item集合。

   类似地可以得到宽泛解释和严格解释：

   P3: r1[P]...w2[y in P]...((c1 or a1) and (c2 or a2) any order)
   A3: r1[P]...w2[y in P]...c2...r1[P]...c1
   

   在宽泛解释中，只要T1进行了predicate读，而不阻塞T2对满足相同predicate条件的data item的写操作，就可能导致异常。

SQL-92定义的4个隔离级别和3个现象见表1：

表中对各个隔离级别都添加了ANSI/ANOMALY前缀，用来和后面讲的锁实现的隔离级别区分开来。

锁实现的隔离级别

很多SQL数据库都用了锁来实现并发控制，因此论文特别探讨了在锁实现中的隔离级别细节。这些实现中，锁分成两种：

• 读(Read)锁，即共享(Shared)锁
• 写(Write)锁，即排他(Exclusive)锁

对于单个data item的读写操作，锁作用在对应单个的data item。在不同事务的并发情况下，如果同一个data item有一个写锁，就会和其它锁（无论读写）出现冲突。

对于predicate类操作，锁作用范围包括所有现存的满足对应predicate条件的data item集合上，而且也包括那些被INSERT, UPDATE或DELETE操作修改的满足条件的data item，换句话说，被predicate锁锁住的对应数据集限制了INSERT, UPDATE或DELETE的修改。当两个predicate锁的范围有部分重合，并且其中一个是写锁时，会出现冲突。

良构(well-formed)的读写是指对要进行读写的每个数据进行加锁。两阶段读写是指严格按先加锁后读写一轮执行完的步骤来操作，一旦读写完释放了锁之后就不再进行加锁。事务按先来后到的顺序执行，当出现锁冲突时，只有在前一个事务释放锁后，后一个事务才能被授予锁并执行。

这里有一个重要的理论：良构的两阶段锁执行保证了串行化。反之，则不是串行化的。很多数据库都利用了这一点，无论是单机的还是分布式的，我们会在无数的数据库产品和文档中反复看到它。

本论文中提到另一个[GLPT]论文，它定义了一致性的度(degrees of consistency)，来描述锁，依赖和基于异常特性的等价性质。这个[GLPT]论文不是我们讨论的重点，这里就不展开它的相关内容。

论文总结了锁实现的隔离级别和加锁实现的关系见表2：

表中列出了，Degree一致性和锁实现隔离级别的等价关系。Degree 0一致性，可能会出现脏读和脏写。Degree 1, 2, 3分别对应锁实现隔离级别的读未提交，读已提交和串行化。

接下来，论文用较大的篇幅，先后论证了几个结论：

1. 隔离级别是有强弱区别的，锁实现的隔离级别强弱关系见Remark 1

   Remark 1: Locking READ UNCOMMITTED
               « Locking READ COMMITTED
                   « Locking REPEATABLE READ
                       « Locking SERIALIZABLE
   

2. 锁实现的隔离级别都不比SQL-92同名的隔离级别弱，因为SQL-92没排除Dirty Write

   P0 (Dirty Write，脏写)定义：

   事务T1修改了一个data item。然后另一个事务T2在T1提交或回滚之前修改了这个data item。如果之后T1或T2执行了一个回滚，那么什么值才是这个data item正确值是不明确的。

   P0: w1[x]...w2[x]...((c1 or a1) and (c2 or a2) in any order)
   

3. 所有SQL-92隔离级别都应该被修改，以包括P0的定义。即需要对应的P0, P1, P2, P3而不是严格的A1, A2, A3

4. 严格解释A1, A2, A3具有无意识的弱点。正常的解释应该是宽泛的解析。

5. 用于SQL标准的现象定义应该修改成

   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]...(c1 or a1) (Fuzzy or Non-Repeatable Read)
   P3: r1[P]...w2[y in P]...(c1 or a1) (Phantom)
   

   因此得到修正过的隔离级别与现象的关系见表3：

   

6. 表2中的锁实现隔离和表3中经过修正的基于现象描述的隔离级是等价。对于单版本历史(single version histories，区别于后面提到的snapshot isolation中，data items可以有多个版本)实现，P0, P1, P2, P3只是对应锁实现版本的变装(disguised versions)。

其它隔离级别

游标稳定性(Cursor Stability)

游标稳定性(Cursor Stability)是为了防止丢失更新(lost update)现象而设计的。

P4 (Lost Update)

丢失更新异常是指，事务T1读一个data item然后T2更新这个data item(可能基于之前的读)，接着T1(基于之前读到的值)再更新这个data item并提交。

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

经过分析，这个现象对应的隔离级别在读已提交和可重复读之间，通过在读已提交的锁实现基础上，添加扩展：添加一个游标，读时对当前data item进行加锁，写时对游标遍历过的data item进行加锁，可以防止现象P4的出现。注意论文中在给出P4时比较的是SQL-92 READ COMMITTED和游标稳定性，强调了通过多个游标会一直拥有多个data item的锁的机制，用加锁阻塞另一个进程的写，可以用MySQL里面普通不加锁读和通过select lock in share mode或select for update加锁读写来对比理解。这种加了游标的现象被重新描述为：

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

备注7梳理这几个隔离级别的关系：

Remark 7:
READ COMMITTED « Cursor Stability « REPEATABLE READ

快照隔离(Snapshot Isolation)

快照隔离是一种常见的用于实现多版本的并发控制技术。

1. 一个data item允许存在多个版本
2. 每个事务都有自身的数据库版本，以事务开始的时间Start-Timestamp来标记。写操作在提交前只对当前事务可见，对其它事务不可见。事务提交时获取一个Commit-Timestamp，当在[Start-Timestamp, Commit-Timestamp]范围内没有其它Commit-Timestamp才能成功提交，否则中止。换句话说，即对应时间段内没有其它事务提交过，这个事务才能提交成功。这个策略称为先提交者胜出(First-committer-wins)，能防止现象P4。一个事务成功提交后，它的修改对后面的Start-Timestamp大于已提交事务Commit-Timestamp的事务可见。
3. 快照隔离可以保证读数据的尝试无须等待（跟锁实现不同）。只读事务不会中止；写事务在冲突时有中止风险，因此适用于小事务，短时事务较多，冲突少的场景。在冲突较多，或者有覆盖data item范围比较大的长时间事务场景，往往会出现事务多次被迫中止的结果，对事务公平性和性能影响较大。

快照隔离提出了特有的异常。论文定义了data item约束条件和两个异常。

A5 (Data Item Constraint Violation)

指数据库中对多个data item(论文中是两个)的约束的违反。

A5A Read Skew(读偏斜)

假设事务T1读data item x，然后第二个事务T2更新x和y到一个新值并提交。如果现在T1读y，会读到一个不一致的状态。

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

需要注意的是因为 Read Skew 现象中没有重复读取同一个 key，所以不属于 Non-repeatable Read。

A5B Write Skew(写偏斜)

假设事务T1读满足约束的x和y，接着T2读x和y，写了x并提交。然后T1写y。那么x和y之间的约束可能会被违反。

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

对于写偏斜，网上很多文章经常提到写偏斜的一个例子，就是把x, y两个值交换。

接下来论文花了较大的篇幅去论证几个结论：

Remark 8. READ COMMITTED « Snapshot Isolation

Remark 9. REPEATABLE READ »« Snapshot Isolation.

Remark 10. Snapshot Isolation histories preclude
anomalies A1, A2 and A3. Therefore, in the anomaly interpretation
of ANOMALY SERIALIZABLE of Table 1:
ANOMALY SERIALIZABLE « SNAPSHOT ISOLATION.

几个结论的论证过程都比较简单，这里就不逐一展开。

最后论文总结了所有描述过的现象、异常和隔离级别的关系见图2和表4：

这个图上每条边标记了两个隔离级别之间有差异的现象。

注意上面的图表，都用了经过强化的SQL-92隔离级别定义，而不是原本的SQL-92，即用了更宽泛解释的现象P0-P3，而不是严格解释的异常A1-A3。并在此基础上添加了游标稳定性和快照隔离及它们提出的异常。

MySQL中的隔离级别

下面讨论一下常用的MySQL InnoDB引擎的特点。它支持多版本和锁机制，有如下要点：

1. 普通读写
   在事务中，普通的读是快照读(snapshot read，即用事务开始时的时间戳来生成快照，不会被锁阻塞)，普通的写(UPDATE/DELETE/INSERT/SELECT FOR UPDATE)会使用当前读(local read，即获取最新的时间戳来生成快照)。若要保证读的数据不会被修改，需要显式使用锁机制。
2. SELECT ... LOCK IN SHARE MODE
   在读取到的行上设置共享锁。其他会话可以读取行，也可以继续给行加共享锁，但是在当前事务提交之前其他会话不能修改加了共享锁的行。如果这些行中的任何一个被尚未提交的另一个事务更改，则当前查询将等待直到该事务结束，然后使用最新值。
3. SELECT ... FOR UPDATE
   用排他锁锁定行和任何关联的索引条目，就像在这些行上执行UPDATE语句一样。禁止其他事务在这些加了锁的行上进行UPDATE、执行SELECT ... LOCK IN SHARE MODE或者读取某些事务隔离级别的数据。

其中select for update在实现中用的是Next-Key Lock，即Record Lock + Gap Lock的组合。复杂的地方在于它锁的是索引，因此行为跟实现（索引怎么建，索引命中了哪些数据行）紧密相关，而且在不同的隔离级别(RR/RC)上行为表现不同。有兴趣可以读一读这个文章《Mysql「Select For Update」锁机制分析》。

TiDB中的隔离级别

最后我们浏览一下《TiDB事务隔离级别》。

要注意的几点：

1. TiDB在称它的快照隔离级别为可重复读，是为了方便宣传。实际上细分起来这是两个不同的概念，混用术语会导致混乱。
2. TiDB有乐观事务和悲观事务的区别，乐观事务(还有自动重试)是来自于Percolator模型，悲观事务的行为更接近MySQL。悲观事务从v3.0.8版本开始默认启用。
3. TiDB支持select for update加锁，与MySQL类似，写(UPDATE/DELETE/INSERT/SELECT FOR UPDATE)使用当前读，但在实现上并不是Next-Key Lock，没有Gap Lock无法锁住范围。TiDB不支持Select lock in share mode.

---

参考资料：

MySQL InnoDB官网文档：多版本
MySQL InnoDB官网文档：事务隔离级别
UNDERSTANDING MYSQL ISOLATION LEVELS: REPEATABLE-READ
隔离级别的追溯与究明，带你读懂 TiDB 的隔离级别（上篇）
隔离级别的追溯与究明，带你读懂 TiDB 的隔离级别（下篇）