crdb 两阶段提交过程

06 Sep 2021 by fleuria

之前只了解一点 percolator,对它的印象是可以在一个普通的分布式 KV 存储上面实现事务能力,但是 2PC + raft 流程的开销很可观。前几天听说 cockroachdb 相对于 percolator 有搞了一些工程上的优化,学习一下这部分的实现思路。

和 percolator 一样的地方是,crdb 也是按照去中心化事务管理器实现多行事务的管理,难点在于每行操作都有可能存在并发竞争条件,事务提交协议为了实现原子的多行事务提交,会借助单机的原子事务能力对并发操作进行仲裁,针对不同阶段的异常,也同样借助单机的原子事务推进异常恢复。

和 percolator 的不同在于,percolator 基于现有的下层通用 KV 存储,使事务元信息嵌入到普通的 KV 中,而 crdb 可以更加端对端地设计,对事务元信息做一些自己的存储形式。

本文大致上按以下几部分进行组织:

  • 事务元信息与常规事务过程
  • 并发控制
  • Parallel Commit 优化

TransactionRecord 和 WriteIntent

crdb 将数据分片为 range,类似 tidb 中的 region,每个 range 大约 64mb 大小,每个 range 内部可以执行单机事务。

crdb 会在每个 range 中划单独的区域来分别保存 TransactionRecord 和 WriteIntent,它们两个是事务相关的主要元信息:

  • TransactionRecord 会用来保存事务的状态(PENDING、COMMITTED、ABORTED),有一个超时时间;
  • WriteIntent 相当于写锁与新数据的暂存区,同一个 Key 同一时刻最多只能有一个 WriteIntent 存在,用于悲观互斥,事务中的每个 WriteIntent 均会指向同一个 TransactionRecord;

回忆一下 percolator 中会选择事务中第一个写入的行作为 Primary Row,然后使其他 Row 指向 Primary Row,其他 Key 的并发操作均对齐到 Primary Row,按 Primary Row 中保存的提交状态作为事务总体状态的判断依据。

crdb 中也同样选取事务第一行使它扮演特殊角色,将 TransactionRecord 保存在第一行的同一 range,使事务中的所有 WriteIntent 指向 TransactionRecord。这是与 percolator 第一眼看上去比较不同的地方:

Coordinator Node 是用户访问 crdb 集群时连到的节点,它会使自己扮演 Coordinator 角色,推动事务过程的推进。

当所有 Key 都完成一阶段写入后,就会由 Coordinator 驱动进入两阶段提交的提交阶段:使 Transaction Record 标记为 COMMITTED 状态,作为 Commit Point,可以向用户返回提交成功,随后由 Coordinator 驱动异步地清理 Write Intent。期间如果有用户访问到 WriteIntent,会查询 Transaction Record 的状态,执行清理收敛操作:

最终 WriteIntent 与 TransactionRecord 均被清理,事务完成。

与 percolator 不同,crdb 作为 Serializable 隔离级别,整个事务只有一个提交时间戳,而非 startTs 和 commitTs 两个时间戳。这里的时间戳应该只用于 MVCC,并发控制层面就都靠上锁的悲观并发控制了。这种单一时间戳也是 Serializable 在逻辑上的体现:Serializable 等价于所有的事务依次执行,事务的开始和结束在一个原子的时间中完成。

Coordinator 挂了怎么办

每个 range 已经有了 Raft,上层可以大致认为它们是可靠的。但是 Coordinator 是一个单点,中途挂掉的概率并不低,不能依赖它来保障事务的可靠性。在设计上,crdb 会安排 Coordinator 来驱动事务的完整生命周期,但当 Coordinator 挂掉时,其他访问者若碰到遗留的 WriteIntent,仍可以通过访问者驱动的清理过程使事务正常走完。这里与 percolator 是相同的思路:

  • Commit Point 之前如果事务执行中断,由相关键的访问者驱动 Rollback 流程,标记事务状态为中断,清理键上的事务元信息;
  • 若 Commit Point 之后中断,访问者驱动 Roll Forward 流程,使事务写入的最新值生效,并清理事务元信息;

与 percolator 的每个锁都有超时时间不同,crdb 中的超时维护在 TransactionRecord 中,WriteIntent 是没有超时的。Coordinator 会定期地给 TransactionRecord 心跳续命,其他访问者如果发现 TransactionRecord 超时,会认为 Coordinator 死亡而发起清理过程,使 TransactionRecord 进入 ABORTED 状态。

当访问一个 Key 发现有 Write Intent 存在时,会顺着 Write Intent 的引用找到 TransactionRecord,结合其状态进行不同的处理:

  • 如果发现是 COMMITTED 状态,则直接读取 WriteIntent 中的值,同时发起 WriteIntent 的清理;
  • 如果处于 ABORTED 状态,这个 WriteIntent 中的值会被忽略,并发起清理 WriteIntent;
  • 如果遇到 PENDING 状态,则认为碰到了一个进行中的事务:
    • 如果发现事务已过期,则标记为 ABORTED 状态;
    • 如果事务未过期,则结合时间戳进行冲突检测;

关于冲突检测的逻辑在后面详细看。

Timestamp Cache 和 Read Refreshing

Write Intent 可以用于跟踪写入的冲突,但是 crdb 是 Serializable 隔离级别,也需要跟踪读取的记录,对读取操作和写入操作都进行冲突检测。

crdb 的做法是在每个 range 保存一段 Timestamp Cache,用于保存 range 中的 Key 最近一次读取操作的时间戳。顾名思义,Timestamp Cache 是保存在 range 中的一段内存数据,并不经过 raft 复制。

每当有写入发生,都会检测当前事务的时间戳是否小于 Timestamp Cache 中该 Key 的最新值。如果存在,则表示当前事务的写入操作会使最近一次其他事务读取到的内容失效。按常规的 Serializable 事务过程的话,到这里就应该宣告事务冲突失败了:

不过 crdb 这里并没有直接事务冲突退出,仍挽留了一把。思路大致上是:当前事务与其他事务发生Write after Read 冲突,我可不可以将事务的时间戳推后(push)到当前时间,再跑一次 Write After Read 冲突检查就没问题了。

但是执行 Push Timestamp 时也需要满足一定前置,就是当前事务读取的键,在 [原时间戳,新时间戳] 范围内是否存在新的写入操作。如果不幸存在新的写入,就无法挽救了,只能认为事务冲突失败。这项检查称作 Read Refreshing。

Push Timestamp 相比于直接报错事务冲突然后用户上层对整个事务进行重试,更轻量,也对用户会更友好,我们平时在业务代码中其实很少对事务做重试,挽回一个有救的事务,sentry 上就少一个异常出现。我想这也是悲观并发控制相比乐观并发控制更好的一个地方。

事务冲突

事务冲突有几个场景:

Read after Write:读到一个未提交事务的 Write Intent,其时间戳小于当前事务,这时当前事务需要等待此事务完成后再读取键值。crdb 会将当前事务加入到 TxnWaitQueue 队列用于等待依赖的事务完成。如果读到的 Write Intent 的时间戳大于当前事务,则不需要等待,按 MVCC 直接读取键值就可以,相当于读取当前事务时刻的快照。

Write after Read:写操作时,当前事务的时间戳必须大于等于该 Key 最近一次被读取的时间戳,若存在冲突,则尝试 Push Timestamp 继续事务执行。

Write after Write:写操作时,如果遇到更早的未完成 Write Intent,则需要等待该事务先完成。如果遇到更新的时间戳,则按 Push Timestamp 推后自身的时间戳。

总结一下,事务遇到冲突有两种策略:

  1. 等待:主要用于其他事务的开始时间早于当前事务时,遇到依赖关系,当前事务等待其他事务完成再执行;
  2. Push Timestamp:主要用于当前事务的开始时间早于其他事务时,遇到依赖关系,先尝试使当前事务的时间戳推后,使之变得比其他事务更晚,不过推后时间戳需要经过 Read Refreshing 前置检查,确保当前事务读取集没有被修改,不然也要使事务中断;

Parallel Commit

原始的 percolator 的性能会很感人:对每行数据的 Prewrite 均需要走一趟复制,然后每行数据 Commit 再走一趟复制。假如下层使用 Raft 做复制的条件下,N 行数据,就等于跑 2 * N 趟 Raft 共识,每趟 Raft 共识又至少 fsync() 一趟。反观单机 DB 不管多少行事务也就一次 fsync()。

为了优化提交的性能,crdb 首先做了 Write Pipelining,一个事务中写入的多行数据,会排进流水线中并行地发起共识过程,这一来等待时间就从 O(N) 降到了 O(2),Prewrite 和 Commit 分别经历两轮共识过程。

有没有可能对提交过程做进一步优化呢?crdb 引入了新的提交协议 Parallel Commit,能够实现一轮共识过程完成提交。大致上的思路是:在两阶段提交中,只要所有预写入均已完成,提交就已经不会失败了,能够安全地返回用户提交成功。

那么,怎样判断所有写入处于完成状态?这里对 Transaction Record 做了两项修改:1. 引入 STAGING 状态,表示事务已进入提交;2. 增加 InFlightWrites 字段,记录当前事务写入的 Key 列表。此外,Transaction Record 不再是事务开始时创建,而是在用户 Commit() 时创建,这时才能知道事务修改了哪些 Key。

按官方文档中的例子,一个事务的过程大致上的步骤:

  1. 客户端联系 Transaction Coordinator 创建事务;
  2. 客户端尝试写入键为 K1 值为 “Apple” 的 Write Intent,这时会生成 Transaction Record 的 ID 并使 Write Intent 指向它,但并不真正创建 Transaction Record;
  3. 客户端尝试写入键为 K2 值为 “Berry” 的 Write Intent,同样使它指向 Transaction Record 的 ID,这时 Transaction Record 也同样未存在;
  4. 客户端发起 Commit(),这时创建 Transaction Record,使它的状态为 STAGING,使其 InFlightWrites 中指向 [“Berry”, “Apple”] 两个 WriteIntents。
  5. 等待 Write Intent 和 Transaction Record 的并发写入完成,即可向用户返回成功;
  6. Coordinator 发起提交阶段,使 Transaction Record 为 COMMITTED 状态,并使 Write Intent 刷入主存储;

如果 Coordinator 在提交后挂掉,访问者读到 Write Intent 的 Key 时,会首先读取相应的 Transaction Record,继而通过 InFlightWrites 访问每个 Key 判定是否已写入成功:

  • 如果未成功且 Transaction Record 已超时,则访问者驱动使 Transaction Record 进入 ABORTED 状态;
  • 如果所有 Key 均已写入成功,则认为已处于 Implicit Committed 状态,由访问者驱动使 Transaction Record 进入显式的 COMMITTED 状态,并使相关的 Write Intent 刷入主存储;

可见 Parallel 虽然显著的减少了提交过程的等待时间,但是访问者驱动的异常恢复过程变得更加昂贵。crdb 在正常流程中,仍希望通过 Coordinator 驱动提交的过程尽快完成,使访问者驱动的恢复过程只作为最后的兜底保障。

References