CockRoachDB 的事务实现与优化

CockRoachDB（后文均简称 CRDB）是一款知名的工业级开源 Shared-Nothing 分布式数据库，具有高可用、跨地域水平扩展、高性能事务等特点。与大部分分布式数据库一样，CRDB 的单节点分为 SQL 层、数据分布层和支持事务的 KV 层。CRDB 依据范围分片，将存储的数据划分为一个个 64M 大小的 Ranges。数据分布层根据元信息可以确定查询请求应该由哪个或者哪些 Ranges 来处理。

CockRoachDB 兼容 PostgreSQL 协议，也支持 Online Schema Change、物理备份、JSON等数据库常用功能。底层使用基于 Raft 协议实现高可用，数据则存储在 RocksDB。

由于当今许多 Shared-Nothing NewSQL 都采用 SQL + Transactional KV 的架构，大家都比较熟悉了。本文重点描述 CRDB 分布式事务的实现与优化。

2.事务优化

总体是一个优化版本的两阶段提交

2.1 Write Pipelining

数据库事务里的 SQL 语句通常是串行执行的，既一条 SQL 语句只有在 consensus writes 后，才返回客户端，客户端继续发送下一条 SQL 请求。

CRDB 将这个流程并行化。事务中，客户端向协调者发请求，不用等上一个语句在多副本持久化（例如一个较大的更新），只要提交给 raft 模块后立即返回，然后继续发其他的语句。这样每条 SQL 语句的多副本持久化是可以并行起来的。此时客户端应当 track 所有 key 持久化是否成功。因为只有所有 key 持久化成功，事务才能提交。

事务内语句并行执行，需面对一个棘手问题：两条语句有操作的记录有重合时，如何处理冲突？CRDB 的解决方案是事务上下文 track 已经执行过的所有 key，可以据此判断新的语句是否与未完成的语句有 overlap，没有则立即执行，有的话则需要等待其执行成功。

1. CRDB 最初加 hint 的并行执行方案为什么不好？

CRDB 最初的方案时允许用户加一个 RETURNING NOTHING hint，语句不在等待执行完成直接返回用户，当然也不会返回执行结果。该方案本质上是一个伪并发执行方案，只对一部分不在乎返回结果的用户有用，并且想用该功能的用户需要手动更改 SQL。

2.CRDB为什么不 buffer 所有的写请求，提交时再一起持久化？

诚然，这样也能实行并行执行，显著减少 consensus writes 次数（只有提交的时候需要多副本复制）。但是这种方案也存在一些问题：（1）无论在协调者或者客户端 buffer 这些写请求，都需要较大的内存空间，因此很难支持大事务，只能通过限制事务大小来防止 buffer 过大。（2）CRDB 默认支持 serializable 隔离级别，因此读写需要使用同一个时间戳（SI 及更低的隔离级别，读写时间戳可以不同），本来冲突概率就较高，如果采用 buffer 写的方式，相当于加锁被延迟到提交时，那么冲突的概率会更加高。CRDB 自称根据这个方案做过一个 Demo，效果并不好。

2.2 Parallel Commits

标准的 2PC 存在的问题：当提交命令下发时，首先每个参与者的写入都完成一轮 consensus 才能保证到达可提交状态（Prepare完成），然后再将 transction record 设置为 COMMITTED 状态，这又是一轮 consensus。这时可以返回用户提交完成，后台异步做最后的提交和事务上文清理工作。

Parallel Commits 解决这个问题的方式是加入 Staging 状态，当客户端 Commit 命令下达时，表明现在已经确认了事务所有更改的 key（语句），这时的状态就被称为 Staging。持久化 Staging 状态（还需要持久化所有 track 的 keys）的一轮 consensus，可以和 Prepare 写数据 consensus 同步进行，因此被称为 Parallel Commits。只要当协调者发现，所有 track 的 key 都replicated 成功了，那么就可以提交了。

Staging 状态的本质是，标记一种状态：已经收到了 Commit 命令，虽然提交还未完全完成，但是由于记录了所有 keys，并且所有参与者都 prepare 成功了，所以它未来一定会成功。staging 状态需要记录所有 key 的原因是，确保在异常恢复场景，判断事务是否能够提交的条件是所有的 key 都已经持久化。

尽管事务会尽快异步将 Staging 状态的事务标记为 Committed(或 Aborted)，但是如果并发事务看到了 staging 状态的 key，也会帮忙去判断，staging 事务是否已完成，如果发现所有 key 都成功写入了，会帮助其将事务状态置为 Committed。

我组 KinsDB 也采用了 parallel commit 的方式，区别是我们并没有显示的引入 staging 状态，而是在 coordinator 记录了所有参与者的 id 和事务 id，在异常场景协助判断未完成事务是否可以提交。

3.原子性保证

CRDB 依靠 write intent 一次性生效来保证原子性。事务的所有写入都先写到临时的 write intent，与已经提交的数据相比，它的头部有特殊的标记，并且指向相应的 transaction record（包含了事务状态 pending, staging, committed or aborted）。如果某个参与者的 write intent 写失败，事务状态会被标记为 aborted，write intent 则会被丢弃。

读请求如果遇到 write intent ，首先查询 transaction record 的状态，

• 如果是 commit 状态，可以读之（要比较时间戳大小）。这个读请求甚至可以帮忙清理该 write intent。
• 如果是 pending/aborted 状态，则忽略之。
• 如果是 staging，事务状态和时间戳还未确定，需要等待事务完成。

4.并发控制（冲突检测）

原则：每个事务执行读写用的是同一个时间戳（commit timestamp），达到serializable execution（串行）执行的效果。以这个原则，事务冲突处理方式如下：

1.写读冲突

读请求遇到还未提交且时间戳更小的的 write intent，会等待其提交。

2.读写冲突

写请求时如果发现key上已经有时间戳更大的读请求读过，CRDB 会强制提高自己的 commit timestamp，超过上述读请求时间戳。

3.写写冲突

写请求遇到还未提交且时间戳更小的的 write intent，会等待其提交（类似写读冲突）。写请求时如果发现key上已经有时间戳更大的写请求写过，CRDB 会强制提高自己的 commit timestamp，超过上述写请求时间戳（类似读写冲突）。

需要注意一点：如果 commit timestamp 发生变化，需要保证之前的读还是有效的（更改时间戳，结果集未发生变化），否则事务需要 restart。这时，如果事务读结果未返回给用户，CRDB 内部重试 . 如果结果已经返回用户， 会通知用户丢弃结果，并重试事务。

5.Follower Read

CRDB 可以提供 Follow Read 来帮助 Leader 分担只读事务压力。为了保证在 Follower 上读到正确的结果，需要保证：

（1）Follower 响应了时间戳为 t 的读请求，那么leader就不能再接受比t更小的写了。因此 Leader 会周期性的生成 closed timestamp，并同步给 Followers，小于这个时间戳的请求不再接受。Follower read 只能接受比 closed timestamp 小的读请求。其实为了简化起见，CRDB每个 Node 维护一个，而非 range。

（2）Follower 必须回放到 raft log index I，以保障时间戳小于 t 的 log entry 肯定已经回放完了，论文没说怎么每个 range 怎么维护这个 raft log index I，一个比较简单的方式是，取了 closed timestamp 后，获取每个 range 的 raft log index。与 closed timestamp 一起同步。

笔者之前在做一款基于 TSO（中心授时） 的分布式数据库 Follower Reads 功能时，思路也基本一样。为了给用户灵活的选择，支持三种一致性的 Follower Reads：最终一致性（周期性同步），会话一致性（read ur own write）和强一致性（满足 SI 隔离级别）。强一致性需要先到 leader 上拿到 read index，然后带着 read index 和 snapshot 去 读。目的就是为了保证 follower 已经回放到 read index，snapshot 读到一个 key 时间戳为 CT，那么时间戳比他小的修改一定不会提交（SI 隔离级别保证）， follower 上已经回放了所有 snapshot 值。

6.CRDB 的一致性保证

CRDB 使用的是 HLC，显然无法保证严格的线性一致性，既事务 T1 开始的时间，晚于另一个事务 T2 提交的时间时，T1 的时间戳一定大于 T2。全局时钟（TSO）可以保证全局事务的外部一致性，和真实发生的顺序一致。TrueTime 可以保证节点之间时间误差是 bounded 的，因此借助一定的算法也可以保证线性一致性。HLC对于非因果并发事务，因为没有全局时间，顺序无法确定，但是由于这种因果特性，CRDB 可以做到操作同一个 key 事务的线性一致性。

我们首先看看 Spanner 是怎么利用 TrueTime 保证线性一致性的。

Spanner 使用的 True Time 接口提供这样一个API：TT.now() = [earliest, latest]，可以保证当前的绝对时间这这个范围内。事务 e1 获取提交时间戳（S1 = TT.Now().latest）后等待当前绝对时间一定超过 TT.Now().latest 时（需要等待 7ms），再真正提交（可以保证提交的绝对时间 tabc(e1 commit) > S1）。e1 提交后开始的事务 e2（tabc(e2 start) > tabc(e1 commit)），e2 请求到达服务器的绝对时间一定晚于开始绝对时间（tabc(e2 server) > tabc(e2 start)，基本因果关系），e2 的提交时间戳 S2 = TT.Now().latest 是当前绝对时间的上限，因此 S2 >= tabc(e2 server)。

最终传导关系：S2 >= tabc(e2 server) > tabc(e2 start) > tabc(e1 commit) > S1，线性一致性满足。

CRDB 是如何做到单 key 线性一致性的呢？

假设集群保证HLC之间的时间差不得大于 max_offset 。假设事务 T1 提交后，T2 才开始，并且它们操作了同一个key。T1 提交 key 的时间戳为 ts1，T2开始时获取的提交时间戳为 commit_ts，当提交时发现 ts1 的key：

（1）如果 commit_ts > ts1，那么完美，T1 和 T2 满足线性一致性。

（2）如果 commit_ts < ts1，由于存在 node 之间时间戳 gap 最多只有 max_offset 的限制，所以 ts1 肯定位于 [commit_ts, commit_ts + max_offset] 之间。因此为了保证在 T1 完成后才开始的 T2 commit 时间戳一定大于 ts1，应当开始一个叫 uncertainty restart 的行为：将 commit_ts 强制提升到 ts1 以上（需要重新读），但仍然小于 commit_ts+max_offset。