A Critique of Snapshot Isolation论文阅读
A Critique of Snapshot Isolation
摘要
对事物的支持是DBMS的一个重要组成部分。缺少这一支撑的话,开发人员不仅会面临尽管同时访问数据库可能出现故障也需要确保事务操作具有原子性的困扰,而且还会遭遇大量并发操作时可能出现不可恢复性问题等挑战。最理想的状况是,一个事务管理系统能够提供串行化处理,即所有并发事务的操作结果都能按照它们的实际执行顺序进行公正分配。然而,基于锁机制的经验表明,串行化处理会导致较高的开销和较低的并行效率。因此,商业数据库系统通常采用串行化处理的方式来实现像隔离快照这样的较弱一致性保证,但这样做的代价就是开发人员仍然无法摆脱由于缺乏串行化而导致的各种异常问题的影响。近年来,人们已经尝试通过丰富事务支持来提升大规模数据存储能力,例如HBase和BigTable等系统正是沿袭了传统数据库管理系统的思路以提高效率而牺牲了某些一致性保障功能。然而我们发现，在无锁实现下无需采用这种折中方案我们引入了一种独特的隔离级别——"写快照隔离"(write-sanpshot isolation),它既具有独特的特性又实现了串行化的高效执行
引言
一个事务由一系列连续执行的操作组成，并可能涉及数据库中的多个读写操作。该系统通过满足以下四个ACID特性来实现可靠性：原子性确保操作不可分割；一致性和持久性保证数据的一致性和长期可用；隔离级别决定了在处理多个事务时系统的响应方式。然而，在串行化模式下可能会遇到一些挑战
（1）较高的实现开销。
（2）较低的并发性。
写写冲突(write-write conflict)：
两个同时发生的事务修改相同的数据项。
快照隔离（snapshot isolation）的优点:
仅检测插入删除冲突。基于锁的实现相当直接：事务修改数据项之前必须先获取锁；如果该数据项已处于被锁定状态，则需等待或进行重滚。
- 在只读事务中无需锁开销。
- 实现串行化的一个缺点是需要检测快照隔离机制未提供的对防止读写冲突的保护能力。这意味着使用锁定机制时会带来较高的性能代价。
该论文探讨了两种类型的并发问题：writer-writer 冲突与 reader-writer 冲突。阐述了即使在允许 writer-writer 冲突的情形下，系统仍能实现严格的事务性行为。证明 read-write 冲突检测对于实现串行化是足够的，并提出了一种新的隔离级别——write-snapshot isolation（WSI）。这种 WSI 通过将 write 短截隔离（基于 read-write 冲突检测）替代传统的 writer-writer 冲突检测来提高系统的容错能力并减少资源竞争程度
- 主要贡献：
- 我们深入探讨了快照隔离与串行化的本质内涵。
- 我们开发出了 write-isolation 技术。
- 我们证实了 write-isolation 方法具备保障一致性的作用。
- 我们开发出一种基于 HBase 平台的安全并发机制。证实尽管该方法确保数据一致性但在性能表现方面与传统方案具有可比性。
2. 快照隔离
部分主要是快照隔离基于锁与无锁机制的概述。快照隔离设计旨在防止并发操作对数据一致性的影响。为了达成这一目标，在数据服务端数据库需维护多个数据版本以供客户端事务引用。通过起始时间戳区分的不同版本的数据供客户端事务访问。隔离快照方案的一个优势是单个事务写操作不会阻碍其他事务执行读操作。
- 两个事务会在下面的情况下产生冲突：
- 区域重叠（Spatial overlap）：在同一时间段处理行r。
- 时间重叠（Temporal overlap）：Ts在txn_i时小于Tc在txn_j时，并且Ts在txn_j时小于Tc在txn_i时。
2.1 基于锁的快照隔离实现
Percolator新增了两个字段：lock字段用于检测锁定情况，并引入了write字段来记录事务提交的时间戳。其中write字段则用于维护提交的时间戳值。通过双重确认协议（2PC）机制，在所有受到影响的数据项上更新相应的字段值。然而，在这种机制下，尽管使用锁来简化同步操作确实提高了检测冲突的能力，但当一个事务因性能不佳或长时间挂起而持有锁时，在回滚过程中可能会导致其他正在等待解锁的事务无法继续推进。
2.2 无锁的快照隔离实现
图中展示了事务txni处理提交请求的过程：首先系统会遍历存储库R中的每一行数据r，并对每一条记录进行分析。具体而言，在每条记录被处理时需要判断其最新的修改时间是否晚于当前事务启动的时间点。如果是，则该事务将发生回滚；否则该事务可以顺利提交至数据库系统中。接着系统会获取该行r的修改时间信息，并将其保存为当前最新的修改 timestamp值。最后会将这一更新结果反馈至存储库R中。
3. 串行化
历史记录用以表示事务交错执行的行为序列。其中w₁[x]与r₁[x]分别标记事务txn₁在数据项x上的写入与读取操作，“c₁”与“a₁”则分别代表该事务的有效提交及失败回滚过程。
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中实现对读写冲突的有效检测与处理。
- 然而，在这种情况下运行中的事务无法对其自身的write操作产生影响。
- （其write阶段也被阻塞）
4.1 写隔离快照
事务会观察它自己的所有更改以及在txni开始之前提交的事务的修改。
如果在写快照隔离下有下列情况两个事务txni和txnj会产生冲突：
- RW-spatial overlap（读写空间重叠）：
txnj写入行r并且txni从行r读取。
- RW-temporal overlap（读写时间重叠）：
Ts(txni) < Tc(txnj) < Tc(txni)
这表明事务在txni的时间周期内不应修改其已读取的数据以完成提交。
仅读事务（Read-only transaction）：
称其为仅读事务的为那些写集为空的事务。常见于日常业务流程中的仅读事务占比相对较高且具有重要意义。
- 写事务（write transaction）：
写集非空的事务称为写事务。
因此确保一下几点是非常重要的：
- 使用隔离快照技术执行只读事务时的开销应尽量降低至最低水平。
- 采用快照隔离策略时进行的只读事务具有不可恢复性。
无修改操作的只读事务不影响其他事务的读取数据值，并因而在处理过程中不影响同时进行的任务。
- 非只读（Not read-only）：
事务txni和txnj都不是只读。
只读事务不会进行冲突检测，因此也不会回滚。
4.2 对于串行化来说避免读写冲突是足够的吗？
- 证明写快照隔离是串行化的
为了解决这个问题，在采用快照隔离策略时的每一个历史事件h都需要与其对应的串行化的序列化历史记录serial(h)保持一致的状态变化过程。
为了避免混淆，
我们需要明确区分这两种情况：
(1) 指同一事务内部的所有操作
(2) 指该事务的整体提交流程。
- 我们通过以下几点组成历史记录serial(h):
- 当提交时遵循与历史记录h相同的写事务使用顺序。
- 确保每个事务内的操作按照规定的执行顺序。
- 将所有属于只读事务的操作在其启动之后的位置向右调整。
- 将其所有操作在其提交前的位置向右调整。
引理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，因为txn2在事务txn1的生命周期中提交了对txn2已经读取的x的修改操作。
下面的历史记录是串行化的：
H7. r1[x] w1[y] c1 r2[z] w2[x] c2
结果和H6相同。
5. 写隔离快照的无锁实现
这部分详细阐述了写隔离快照所采用的一种非锁机制，在无锁运行状态下，其隔离快照与其对应的写入操作所消耗的时间资源具有可比性。
每个提交请求包含两个集合：
已修改行的标识符集合Rw;
已读行的标识符集合Rr。
该系统能够识别事务中的读写冲突；只有在不存在读写冲突的情况下才能提交事务，并将修改后的数据集合记录到状态列表中。
算法2具体说明了执行事务txni提交请求的过程。首先，在Rr中核查是否存在行r的最新提交时间戳大于事务txni的开始时间戳。如果是，则需要将事务txni进行回滚处理。如果核查结果是没有，则允许事务txni被提交成功。随后，在Rw中记录并更新每个行r的时间戳为当前事务txni的提交时间戳。
因为包含集合Rr,在写隔离快照中提交请求开销更大。
5.1 只读事务
基于算法1, 一个事务将在与其他事务无并发修改的情况下被提交至系统.为体现该特性, 在算法2中, 该事务将向状态Oracle提交一个空的读集.由此可见, 当读集与写集皆为空时, 状态Oracle将不会执行任何计算.
5.2 分析流量
数据流量（涵盖复杂且高负载的操作）超出了本文探讨的范围。为了探讨未来可能的研究方向，我们进一步阐述了如何扩展当前方案以更好地应对偶尔出现的数据流分析需求。
- 读集合规模迅速扩大，并且通过 Oracle 状态机制处理时会带来较高的代价。
- 随着读集合规模增大, 发生读写冲突的概率会增加, 这会导致回滚率上升。
6. 评估
该部分论文对比了在隔离快照（包括集中式隔离快照和无锁实现）下提供的并发级别。该研究者开发了两个原型系统，并将写快照隔离技术（WSI）、快照隔离技术（SI）与HBase进行了整合。该评估的主要目标是解答以下问题：
- 采用快照隔离策略时，在读操作与写的冲突检测所需的时间（即开销）以及在相同策略下进行的写操作之间的冲突检测所需的时间（即另一类开销）之间进行对比分析。
- 快速映射机制不仅支持较高的并发处理能力，并且能够有效降低资源竞争带来的性能消耗。
6.1 Benchmark
测试基准采用的是YCSB。定义了两种事务类型：
在Read-only事务中所执行的所有操作均为只读性质的操作。
复杂事务由一半数量的读操作和一半数量的写操作组成。
每个事务在n(0-20)行操作。
6.2 微测试基准(Microbenchmarks)
在本研究中，我们采用一个客户端运行架构，并将事务处理过程中的操作划分为多个阶段进行分析：首先，在事务处理过程中涉及的操作被划分为不同的阶段；（1）生成时间戳请求记录；（2）读取数据；（3）执行数据操作；（4）提交最终确认请求。
6.3 状态Oracle的开销
在分析快照隔离与写快照隔离中的状态oracle提交算法复杂度时发现两者基本相同。为了评估开销，在现有状态下运行时对状态oracle进行了最新版本测试。通过施加高负载压力进行压力测试，并按照指数级增长的方式将客户端数量从1增加到26个节点后，在图5中绘制了平均延迟与平均吞吐量的关系曲线。
如图5所示，在正常负载条件下，写快照隔离与快照隔离之间的性能差异几乎可以忽略不计。在该场景下运行时，在写快照隔离模式下达到80K TPS的速度（即每秒传输80千兆数据），此时系统的平均延迟为10.7毫秒（ms）。随后吞吐量略微增加但伴随显著提升的延迟值表明系统存在瓶颈现象：这是因为状态oracle组件内部产生了缓冲延迟。而更为关键的是，在当前状态下运行时的核心逻辑执行冲突检测机制导致的状态oracle最终采用write snapshot isolation模式能够更快地达到饱和效果。
主要源于当前状态下运行时的核心逻辑执行冲突检测机制。
- 未来工作：考虑使用更小的关键部分去缓解这个问题。
6.4 在HBase上的开销
如图6所示，在HBase系统中进行快照隔离操作时所消耗的资源（即开销）大致相当
6.5 并发性
这部分实验使用了zipfian和zipfianLatest分布。
如图7所示，写快照隔离和快照隔离的性能是相当的。
通过查看图8的数据可以看出，在写快照隔离的情况下，回滚率略高于快照隔离（仅高出约一个百分点），这一差异在Zipfian分布的混合负载场景下可以忽略不计。由此可知，在Zipfian分布的混合负载下，无论是采用哪种策略（即写快照隔离还是普通快照隔离），其提供的并发能力都是相同的。
图9展示了它们在zipfianLatest分布下的性能，两者性能基本一致。
从图10中可以看出，在ZipfianLatest分布模式下，回滚速率相较于Zipfian分布呈现出更快的增长速度。当采用快照隔离机制时（write snapshot isolation），其回滚速率略高于普通快照隔离方法（fast snapshot isolation）。尽管这种开销会产生一定的成本 overhead（overhead），但它所带来的可序列化收益却相对更高。
7. 相关工作
相关工作主要有以下几部分：
- 比较了我们工作与相关领域的快照隔离研究。
- 综述了最新实现的快照隔离技术。
- 详细介绍了基于序列化的大型数据库设计与实现。
7.1 隔离级别
该论文的主要贡献在于探讨了读写冲突检测在序列化中的充分性，并可以在无锁方法中高效地完成
- 以下几个是对序列化隔离快照的尝试：
- 利用程序源码的数据分析方法用于检测快照隔离下的潜在冲突事务，并在程序中展示以防止冲突。
该方法对开发者具有较高的技术门槛。仅需对快照隔离进行少量的修改即可在事务系统中实现序列化。
- 通过在运行时验证图实现异常的动态检测，但是实际实现代价会比较高。
在评估无锁实现时发现，在线快照隔离与隔离快照两种方法所导致的性能消耗相吻合；在现有技术研究中发现的所有序列化快照隔离方案均存在避免自写字冲突而产生的不必要的回滚风险；
相较于本研究提出的读操作与写操作之间的冲突检测方法而言，在本研究中所设计的方法是一种实用的方法；它无需事务系统构建全局依赖图，在一定程度上减少了不必要的回滚问题，并与基于快照隔离方案下的 write-write 冲突检测方法具有相似性。
7.2 大规模数据存储中的快照隔离实现
Percolater采用基于锁的分布式架构来实现快照隔离机制。为了提高系统的并发处理能力，在表结构中新增了lock和write两组特殊元数据字段。其中(write)字段用于存储事务提交的时间戳信息；(lock)字段则通过双拍机制（2PC算法）来防止在同一时间对已被锁定的数据行进行无效更新操作。当读取操作访问到被锁定的数据行时，系统会自动检查该事务是否处于封锁状态并采取相应措施
尽管采用基于锁的方法较为直观易懂,但其开销较大且会对系统性能造成显著影响.相比之下无锁快照隔离方案能够规避这些问题的同时还实现了操作序列化功能,在功能与效率之间找到了更为平衡的设计方案
7.3 大规模数据存储中序列化的实现
为了扩展功能，MegaStore、ElasTras和GStore基于数据存储划分区域，并在每个区域内支持ACID。
8. 结论
- 揭示了读写冲突检测能够体现序列化的优势，并指出其独特性在于超越隔离快照的能力。
- 写快照隔离同样无法回滚单读事务。
- 提出了新的隔离等级——写快照隔离。
- 一个显著优势是通过少量修改基于无锁快照实现序列化提升。
- 在混合负载下 write-witholation isolation 与 fast isolation 的并发性保持一致。