并发控制概述

并发控制模型

每个事务包含多个读写操作，这些操作针对的是数据库中的不同数据。最简单的并发控制方法是串行（serial）执行，即一个进程在另一个进程执行完一个操作并收到回应之前，不会触发下一个操作。然而，这种方式显然不适应高并发的需求。因此，学者们提出了一种可串行化（serializable）的方法，即可以并行（非串行）地执行事务内的多个操作，但最终结果与串行执行相同。

通过事务中的读写操作，我们可以为事务建立依赖关系（代表事务被串行化后执行次序的关系）。以下是三种主要的依赖关系：

• 写写冲突（Write Dependency）：当事务 A 修改数据 X 后，事务 B 再修改同一数据 X，事务 B 依赖于事务 A。
• 写读冲突（Read Dependency）：当事务 A 读取数据 X 后，而此数据 X 由事务 B 修改，则事务 A 依赖于事务 B。
• 读写冲突（Anti Dependency）：当事务 A 读取数据 X 后，事务 B 再修改同一数据 X，则事务 B 依赖于事务 A。

通过这些冲突定义的可串行化，称为冲突可串行化（conflict serializable）。当事务间的冲突关系没有形成环时，就能保证冲突可串行化。常见的实现机制有两阶段锁和乐观锁机制。两阶段锁通过排它锁限制冲突的修改，并通过死锁检测机制回滚产生循环的事务，确保无环。乐观锁则在提交时进行检测，回滚所有可能导致环的事务。

但引入可串行化隔离级别在实际商业数据库中的应用较少，主要因为其性能代价较大。因此通常会允许某些可接受的异常以增加事务的性能和可扩展性。常见的隔离级别包括快照读和读已提交。快照读依赖于维护多版本数据，通过固定的读版本号读取对应版本的数据，从而产生读写冲突导致的环状结构，如事务 A 读取版本 1 的数据 X 并修改数据 Y，事务 B 读取版本 1 的数据 Y 并修改数据 X，最终产生写偏斜（Write Skew）。读已提交隔离级别则会暴露不可重复读（事务内部两次读取结果不同）。定义隔离级别的抽象，使其在性能和易用性上达到平衡感，是设计事务隔离级别的关键之一。

OceanBase 数据库的并发控制模型

OceanBase 数据库支持快照读和读已提交两种隔离级别，并在分布式环境中保证外部一致性。

多版本数据与事务表

为了支持读写操作不互斥，OceanBase 数据库从设计开始就选择了多版本存储，并维护两个全局版本号：读版本号和提交版本号，如图中的 本地最大读时间戳 和 最大提交时间戳。每次更新在内存中记录一个新的版本，从而实现读写不互斥。

如图所示，在内存中有三行数据 A、B 和 C；其中每次通过版本（ts）、值（val）和事务 id（txn）来维护更新，并将多次更新同时维护来保持多版本；其次，内存中存在一个事务表，事务表中记录了每个事务的 id、状态以及版本。事务开始和提交时会通过全局时间戳缓存服务（Global Timestamp Cache）获取时间戳作为读时间戳和作为提交时间戳参考的一部分。

由图中可知，全局时间戳获取服务维护了最大遇到的事务的读时间戳和最大在已经提交的事务的提交时间戳，分别为 120 与 100（之后会提到这两个时间戳的作用）。在内存中，数据 A 包含 100 版本已经提交的数据 a。其对应的事务为事务 10；类似数据 B 包含未决定版本的数据 j 以及对应事务 12 以及数据 C 包含未决定版本的数据 x 以及对应事务 15。事务表中包含了对应事务以及其对应状态，如事务 15 正在以 130 版本进入两阶段提交状态。

提交请求处理

OceanBase 数据库的分布式事务有三个状态：RUNNING、PREPARE 和 COMMIT。由于事务状态在分布式场景下无法原子确认，PREPARE 阶段通过两阶段提交引入。因此，我们维护一个本地提交版本号（local commit version，亦称 prepare version），事务的 全局提交版本号（global commit version，亦称 commit version）由所有分区的本地提交版本号的最大值决定。每个分区保证事务的 全局提交版本号 大于等于本地分区的 本地提交版本号。这是实现读写请求并发控制的关键之一。

事务提交时会进行两阶段提交。每个分区取本地 最大读时间戳 作为本地提交时间戳，第一个参与者通过全局时间戳获取服务获取全局时间戳，并取最大值作为本地提交时间戳，以防止丢失更新。如下图，事务 12 进入提交阶段，并设置状态为 PREPARE，设置本地事务版本号为最大读时间戳（120）和全局时间戳（150）中的最大值（150）。

当事务提交时，我们会走对应的两阶段提交，我们对于参与者中的每一个分区取本地 最大读时间戳 作为本地提交时间戳，对于第一个参与者还通过全局时间戳获取服务获取全局时间戳，并取最大值作为本地提交时间戳。这个保证是为了做单值的读写冲突(anti dependency)，由于我们之前的保证，可以得到我们的提交时间戳一定大于之前所有的读取，因此我们在串行执行中可以在这些之前的读取后面，那么前面的事务没读到本事务就是当然的了。如图所示，事务12进入提交阶段，并设置状态为 PREPARE，设置本地事务版本号为本地 最大读时间戳 120 与(假设为第一个分区)取 全局时间戳 为 150 的最大值 150 作为 本地事务版本号。

在两阶段提交结束前，我们保证全局提交时间戳 大于等于本地提交时间戳。一旦收到提交消息，就能确定 全局提交时间戳，如图所示，状态回填为提交，时间戳为 160，并异步回填到更新数据上，后续不再需要查询事务表。此外，更新最大提交事务时间戳以优化后续读请求，并唤醒锁队列中的事务。

写请求处理

在写入数据的时候，为了保证写写冲突（write dependency），修改会使用两阶段锁协议，当触发写入请求时，若发现本行的多版本有正在执行的事务，就会把这次请求放入锁管理器中等待，OceanBase 数据库在锁管理器中，实现了等待队列，通过锁或超时来唤醒这个写请求。如图所示当准备更新数据 B 时，由于存在活跃事务 12 正在修改数据 B，因此会将这次的写入请求放到锁队列中，等待事务 12 的唤醒。

为了防止读写冲突（anti dependency）和写读请求（read dependency）导致环状结构以及避免丢失更新（lost update），在快照读隔离级别下，当写操作成功加锁后，会将读时间戳与该行上的 最大提交事务时间戳 进行比较。如果读时间戳小于行上的最大提交事务时间，则会回滚该事务。例如，如果写操作的读时间戳为 100，而事务 12 以时间戳 160 提交，这将触发写操作事务的回滚，并报错（TRANSACTION_SET_VIOLATION）。

在不同隔离级别下，写操作的读时间戳处理方式有所不同。

• 在读已提交（RC）隔离级别下，写操作的读时间戳是语句开始时获取的时间戳，遇到 TRANSACTION_SET_VIOLATION 报错时，无需回滚整个事务，仅需重做语句并重新获取读时间戳即可。
• 在快照隔离（SI）级别下，写操作的读时间戳是事务开始时获取的时间戳，遇到 TRANSACTION_SET_VIOLATION 报错时，需要回滚整个事务以避免“丢失更新”。

读请求处理

读取时使用读版本号读取对应的数据，并更新本地 最大读时间戳。根据之前的保证，可以优雅地在分布式场景下处理读请求。

在实际读取时，可分几种情况讨论。当读取到提交或回滚的事务时，根据 全局提交时间戳 和状态简单判断是否需要读取对应数据。如图所示，读取请求 r1 以 90 作为读版本号进行读取，根据快照读策略，读取版本号为 80，数据为 b 的数据。

当读取到 RUNNING 状态的事务时，推高了 本地最大读时间戳，确保之后的 RUNNING 状态事务以更大的 本地时间戳 进入两阶段提交，从而安全地跳过该数据。如图所示，读取请求 r2 以 130 作为读版本号进行读取，推高 最大读事务时间戳 后跳过未进入两阶段提交的事务 12，读取版本号为 100 的数据 b。

当读取到 PREPARE 状态的事务时，若 本地时间戳 大于读时间戳，可以安全地跳过；若 本地时间戳 小于读时间戳，则无法确定 全局提交时间戳 与读时间戳的关系，解决方案是优雅地等待（锁读）。如图所示，读取请求 r3 以 140 作为读版本号进行读取，推高 最大读事务时间戳 后，等待两阶段提交的状态且 本地提交时间戳 为 130 的事务确定 全局提交时间戳 与读时间戳 140 的关系。