A Critique of Snapshot Isolation

摘要

对事物的支持是DBMS的一个重要部分。没有这个支持的话，开发人员会受到尽管同时访问数据库会出现失败也要确保事务的原子执行的困扰。最理想的是，一个事务系统提供串行化，也就是意味着同时发生的事务的输出对于他们的串行执行是公平的。然而，基于锁实现的经验来说，串行化会带来高开销和低并行。 因此商业系统通过串行化这种来实现像隔离快照这样更弱的保证。但是开发人员仍然受到由于缺少串行化而出现的异常的困扰。
近期已经尝试通过事务支持里丰富大规模数据存储，例如HBase和BigTable。不足为奇的是，受传统数据库管理系统的启发，为了提高效率，串行化通常会受到影响。我们在这篇论文中展示了这种折中在无锁实现的事务支持中是没有必要的。我们介绍了写隔离级别(write-sanpshot isolation)，一个独一无二的隔离级别，并且提供了串行化。不同于快照隔离(snapshot isolation)中禁止谢谢冲突，写快照隔离是禁止读写冲突。

引言

一个事务是一个原子执行操作的集合，也许会包含对数据库的多个读写操作。一个可靠的事务系统提供ACID保证：原子性、一致性、隔离性和持久性。隔离性定义了存在同时发生的事务时系统的行为。 最理想化的隔离级别是提供串行化。但是串行化会带来一些缺点：

（1）较高的实现开销。
（2）较低的并发性。

• 写写冲突(write-write conflict)：
  两个同时发生的事务修改相同的数据项。

• 快照隔离（snapshot isolation）的优点:

1. 只检测写写冲突。
   基于锁的实现非常直接：事务在修改数据项前先上锁，如果该数据项已经被锁了，那么久等待或者回滚。
2. 对于只读事务，不需要锁开销。
3. 缺点是实现串行化需要检测快照隔离没有提供的读写冲突。在基于锁的情况下，开销比较大。

这篇论文分析了写写冲突和读写冲突。解释了系统在允许写写冲突的情况下也能实现串行化。证明了读写冲突检测对于实现串行化是足够的。提出了写快照隔离（write-snapshot isolation），一个用读写冲突检测代替写写冲突检测的新的隔离级别。

• 主要贡献：

1. 我们分析了快照隔离和串行化的核心思想。
2. 我们提出了写快照隔离。
3. 我们证明了写快照隔离能提供串行化。
4. 我们提出了一个在HBase上写快照隔离无锁的实现。展示了虽然写快照隔离能够提供串行化，但是在实现开销和并发性级别上和快照隔离是可比较的。

2. 快照隔离

这部分主要是快照隔离基于锁和无锁实现的概述。
快照隔离能够保证事务的读不被同时发生的事务所影响。为了实现快照隔离，数据库需要在数据服务端维持数据的多个版本，客户端的事务通过它们的起始时间戳来查找不同版本的数据。隔离快照实现的优点是一个事务的写操作不会阻塞其他事务的读操作。

• 两个事务会在下面的情况下产生冲突：

1. 空间重叠（Spatial overlap）：同时修改行r。
2. 时间重叠（Temporal overlap）：T_s(txn_i) < T_c(txn_j) and T_s(txn_j) < T_c(txn_i).

2.1 基于锁的快照隔离实现

Percolator增加了两列：lock和write。write用来维持提交时间戳。通过2PC算法在所有被修改的数据项上更新这个列。虽然使用锁简化了写写冲突检测，但是失败或缓慢事务持有的锁会阻止其他事务在恢复过程中取得进展。

2.2 无锁的快照隔离实现

上图描述了一个事务txn_i提交请求的处理过程：先检查R中的每一个行r，如果r的最新提交时间戳大于txn_i开始时间戳，则事务回滚，否则可以提交事务txn_i。txn_i获取提交时间戳。更新R中r的最新提交时间戳。

3. 串行化

历史记录将事务的交错执行表示为其操作的线性顺序。使用“w1[x]”和"r1[x]"表示事务txn₁在数据项x上的读写操作，"c1"和"a1"表示提交和回滚操作。

3.1 避免写写冲突对于串行化是足够的吗？

不是足够的，会出现写偏斜异常。

快照隔离不是串行化的。例如H1：

H1. r1[x] r2[y] w1[y] w2[x] c1 c2

H1会导致写偏斜（write skew）异常。写偏斜异常的出现是因为数据之间存在约束，即使每个事务在提交前验证这个约束，两个同时发生的事务依然可能违反这个约束。例如H2：

H 2. r1[x] r1[y] r2[x] r2[y] w1[x] w2[y] c1 c2

假设约束为x + y > 0;H2有可能将数据变成x = y = 0，那么久违反了约束。

3.2 避免写写冲突对于串行化是必要的吗？

快照隔离的写写冲突避免，除了允许一些不可序列化的历史记录之外，通过阻止一些有效的、可序列化的历史记录，不必要地降低了事务的并发性。

4. 读写和写写

• 隔离快照在MVCC中增加了写写冲突检测。事实上，隔离快照也可以被称为读隔离快照（read-snapshot isolation），因为一个事务的读阶段不会被同时进行的事务所打断。（读阶段是被隔离的）
• 写隔离快照在MVCC中增加了读写冲突检测，意味着如果一个事务在其读集合被一个同时进行的事务修改的情况下不会提交。然而，运行在写隔离快照下事务的写阶段不会被同时进行的事务所打断。（写阶段是被隔离的）

4.1 写隔离快照

事务会观察它自己的所有更改以及在txn_i开始之前提交的事务的修改。

如果在写快照隔离下有下列情况两个事务txn_i和txn_j会产生冲突：

1. RW-spatial overlap（读写空间重叠）：
   txn_j写入行r并且txn_i从行r读取。

2. RW-temporal overlap（读写时间重叠）：

T_s(txn_i) < T_c(txn_j) < T_c(txn_i)
也就是说事务在txn_i的周期中不应该修改它读取的数据才能提交。

• 只读事务（Read-only transaction）：
  写集为空的事务称为只读事务。日常事务中只读事务比例较高，非常重要。
• 写事务（write transaction）：
  写集非空的事务称为写事务。

因此确保一下几点是非常重要的：

1. 在写隔离快照中运行只读事务的开销要接近最小。
2. 在写快照隔离下只读事务不会回滚。

只读事务不会执行任何修改操作，不会影响到其他事务读取这个数据值，因此也不会影响同时进行的其他事务。

3. 非只读（Not read-only）：
   事务txn_i和txn_j都不是只读。

只读事务不会进行冲突检测，因此也不会回滚。

4.2 对于串行化来说避免读写冲突是足够的吗？

• 证明写快照隔离是串行化的

我们需要证明在写快照隔离下的每个历史记录h是等同于串行化历史记录serial(h)的。为了是两个历史记录相等，我们对以下保持相同的顺序（1）一个事务内部的操作（2）事务的提交。

• 我们通过以下几点组成历史记录serial(h):

1. 对于写事务使用和历史记录h相同的提交顺序。
2. 维护每个事务内部的操作顺序。
3. 将只读事务的所有操作在其启动后向右移动。
4. 将只读事务的所有操作在其提交前向右移动。

引理1. 历史记录serial(h)是串行的。

证明：因为每个事务分配的时间戳都是独一无二的，在serial(h)中没有同时进行的事务，因此它是串行的。

引理2. 历史记录serial(h)是等同于历史记录h的。

证明：在历史记录serial(h)中写事务的提交顺序是被保护的，只要每个写事务读取的值是相同的，其输出和历史记录h也是相同的。

• 理论1.写快照隔离是串行化的

根据引理1和引理2，对于运行在写快照隔离下的每个历史记录h，我们能够组成一个等同于历史记录h的串行的历史记录serial(h)。

4.3 对于串行化来说避免读写冲突检测是必要的吗？

写快照隔离相对于快照隔离的一个优点是对于一个写写冲突同时进行的事务是不需要回滚的。

• H6.r1[x] r2[z] w2[x] w1[y] c2 c1
  写快照隔离会组织历史记录6，因为txn₂在事务txn₁的生命周期中提交了对txn₂已经读取的x的修改操作。
  下面的历史记录是串行化的：

H7. r1[x] w1[y] c1 r2[z] w2[x] c2

结果和H6相同。

5. 写隔离快照的无锁实现

这部分介绍了写隔离快照的无锁实现和在无锁模式下，隔离快照和写隔离快照的开销是可比较的。

每个提交请求包含两个集合：

已修改行的标识符集合R_w;
已读行的标识符集合R_r。

会检测事务的读写冲突，无读写冲突才能提交事务并把写集合更新到状态列表里。

算法2描述了执行事务txn_i提交请求的过程。先检查R_r中是否存在行r的最新提交时间戳是否大于事务的开始时间戳，如果是，则回滚。如果不存在则提交该事务。然后更新R_w中每个行r的最新时间戳为该事务的提交时间戳。

因为包含集合R_r,在写隔离快照中提交请求开销更大。

5.1 只读事务

在算法1中，一个事务会在和其他事务没有写写冲突的情况下提交请求。为了在写快照隔离下实现这个特点，对于只读事务客户端会提交一个空的读集给状态Oracle。因此，在算法2中，如果读集和写集都是空的，那么状态Oracle的提交不会执行任何计算。

5.2 分析流量

分析流量（可能包括具有非常大的读取集的事务）超出了本文的讨论范围。为了说明未来可能的工作，这里我们提到了扩展此实现以有效支持偶尔分析流量的两个主要挑战：

1. 读 集合可能变得很大，并且提交到状态Oracle代价很高。
2. 读集合越大，读写冲突的可能性越高，因此回滚率也会越高。

6. 评估

这部分论文比较了写隔离快照和隔离快照集中式、无锁实现下提供的并发级别。作者实现了两个原型并且把写快照隔离(WSI)和快照隔离(SI)和HBase整合在一起。这个评估主要目的是回答以下问题：

1. 写快照隔离下读写冲突检测的开销和快照隔离下写写冲突检测的开销比较。
2. 写快照隔离提供的并发级别和快照隔离提供的并发级别的比较。

6.1 Benchmark

测试基准采用的是YCSB。定义了两种事务类型：

1. 只读（Read-only）事务：所有的操作都是只读操作。
2. 复杂(Complex)事务:包含50%的读操作和50%的写操作。

每个事务在n(0-20)行操作。

6.2 微测试基准(Microbenchmarks)

在这里，我们使用一个客户端运行系统，并分解事务中涉及的不同操作的延迟：(1)开始时间戳请求，(2)读，(3)写，(4)提交请求。

6.3 状态Oracle的开销

快照隔离和写快照隔离中状态oracle的提交算法复杂度是非常相似的。为了测量开销，论文在状态oracle的最新实现上评估了快照隔离和写快照隔离。论文使用大流量来给状态oracle做压力测试。论文中以指数方式将客户端数量从1增加到26，并在图5中绘制平均延迟与平均吞吐量的关系图。
如图5所示，正常负载下写快照隔离和快照隔离的不同是可忽略不计的。在写快照隔离中，吞吐量为80K TPS，平均延迟为10.7ms，之后吞吐量略微增加，延迟却快速增加，这是因为状态oracle的缓冲延迟。状态oracle最终使用写快照隔离比使用快照隔离更快地饱和。原因主要是当前状态oracle的实现在关键部分执行冲突检测算法，因为写快照隔离需要加载两倍于快照隔离的内存像。

• 未来工作：考虑使用更小的关键部分去缓解这个问题。

6.4 在HBase上的开销

通过图6能够发现，写快照隔离和快照隔离在HBase上的开销基本相同，也就说它们性能基本相同。

6.5 并发性

这部分实验使用了zipfian和zipfianLatest分布。

如图7所示，写快照隔离和快照隔离的性能是相当的。

从图8中我们能够发现写快照隔离的回滚率要比快照隔离高一点，但基本可忽略不计。因此可以得到写快照隔离和快照隔离在zipfian分布的混合负载下提供了相同的并发性。

图9展示了它们在zipfianLatest分布下的性能，两者性能基本一致。

从图10我们能够发现，在zipfianLatest分布下，回滚率要比zipfian分布下增加的更快。写快照隔离的回滚率要比快照隔离高一点。这个小小的开销使我们通过写快照隔离提供的可序列化获益的代价。

7. 相关工作

相关工作主要有以下几部分：

1. 对比我们的工作和在隔离级别相关的研究。
2. 回顾了快照隔离最新的实现。
3. 列出了提供某种序列化级别的大规模数据存储。

7.1 隔离级别

这篇论文的一个主要贡献就是展示了读写冲突检测对于序列化是足够的，能够在无锁的方法下高效实现。

• 以下几个是对序列化隔离快照的尝试：

1. 基于程序源码的统计分析来检测快照隔离下的潜在冲突事务,并且在程序上显示以避免冲突。

上面的方法对开发者要求较高，而写隔离快照只需要对快照隔离做出很的修改就能在事务系统中增加序列化。

2. 通过在运行时验证图实现异常的动态检测，但是实际实现代价会比较高。

写快照隔离的无锁实现和隔离快照的无锁实现有着相同的开销。
以上所有尝试序列化快照隔离的方法都继承了避免写写冲突的不必要的回滚问题。

相比之下，本文的读写冲突检测是一种实用的方法，它不需要事务的全局依赖图，因此可以不必要地回滚一些事务，类似于快照隔离的写写冲突检测。

7.2 大规模数据存储中的快照隔离实现

Percolater是基于锁的分布式实现快照隔离。在列族中增加了lock和write列。write列存储提交时间戳。lock列通过2PC算法来避免事务对一个被锁住的列执行写操作。如果读事务读取被锁住的列，需要去检查锁住这个列事务的状态。
虽然使用锁比较简单，但是开销和对系统性能影响比较大。写快照隔离的无锁实现则不需要面对这些问题，并且还能提供序列化，这是快照隔离所不具有的。

7.3 大规模数据存储中序列化的实现

为了实现扩展，MegaStore、ElasTras和GStore依赖于对数据存储进行分区，并且在分区内提供ACID。

8. 结论

1. 证明了读写冲突检测能够实现序列化的优点，这是隔离快照所没有的。
2. 写快照隔离和快照隔离一样也不会回滚只读事务。
3. 提出了新的隔离级别，写快照隔离。
4. 写快照隔离的一大优点是它通过很小的改变就能基于无锁的快照隔离实现有效地增加序列化。
5. 在混合负载下写快照隔离和快照隔离的并发性是一样的。