CockroachDB（以下简称 CRDB）底层集成的 RocksDB 存储引擎，是一个基于 LSM-Tree结构设计的、为快速存储而生的高性能 KV 存储引擎。相较于基于传统的 update-in-place的树状结构的存储引擎，RocksDB 更能够充分发挥硬盘顺序写的性能优势，在面向写优化的参数配置下轻松地达到硬盘数据写入的吞吐上限。
在具体的 RocksDB LSM 实现中，用户插入的数据会先写 WAL 日志（Write-Ahead-Log）并落盘，然后将数据或数据操作以键值对的形式添加到内存当中的 Memtable 结构，并在随后某个时刻点 Flush 到硬盘生成内部有序的、不可变的 SSTable 文件。适时触发的后台Compaction 任务会选取多个数据范围重叠的 SSTable 文件，合并多版本内容生成新的有序的 SSTable 文件，回收多余的存储空间。
在接下来内容中，将介绍 RocksDB 跟数据写入密切相关的 WriteBatch 的实现细节，以及 CRDB 如何利用 DBBatch 封装 RocksDB 的 Batch 操作。
TIPS：
以下内容基于 CockroachDB v2.0.3版本，集成的 RocksDB 版本为 v5.13.4。
WriteBatch 简介
WriteBatch 存储的是一系列的键值对，在提交的时候通过 MemtableInserter 对象将 WriteBatch 所有键值对所对应的数据更新操作，应用到内存中的 Memtable 当中，通过一致的SeqNumber 保证了内部所有的更新操作对于整个 DB 来说是 All-or-nothing 的。这些键值对根据具体的 ValueType 类型对应为20种不同的数据操作，目前 CRDB 涉及到的主要有：
kTypeDeletion：用于单个键值对的删除。
kTypeValue：用于键值对实际数据的写入。
kTypeMerge：用于单个键值对 Merge 写入。
kTypeLogData：用于写入特定数据到 WAL 日志当中，不对应任何实际数据。
kTypeRangeDeletion：用于删除指定起始和终止 Key 值的范围内的所有键值对。
本文涉及到的数据写入操作主要为 KTypeValue 类型的操作。在 RocksDB 中写入该类型的键值对，用户可以显式地创建 WriteBatch 对象并在最后一次性提交所有写入操作，也可以一个一个地使用 Put 操作写入数据库。后者在底层实现上会转化为只有一个键值对的 WriteBatch 对象，执行与前者一致的底层处理逻辑。
Writer & BatchGroup
在数据写入方面，RocksDB 采取的是 Single-Writer 的设计，任何时刻只有一个线程去执行数据的 WAL 日志的写操作。
数据结构
如下图，一个 Writer 对象封装一个 WriteBatch 任务以及其对应的一些配置信息，如分配到的 SeqNumber、线程状态信息、是否写 WAL 日志、是否写入 Memtable 等。Writer 对象之间组成一个双向链表，新插入 WriteBatch 将封装为 Writer 结构插入到链表末尾，等待编入 WriteGroup 进行处理。
WriteGroup 由一组相邻的 Writer 构成，分为一个 Leader 和多个 Follower 。在一个 WriteGroup 里面，重要部分（WAL 日志写）甚至是所有的写操作（包括 WAL 日志写和Memtable 写）都由 Leader 完成。Leader 可以是第一个插入到空链表的 Writer，也可以是上一个 WriteGroup 执行结束以后获取到的链表头部的 Writer。Leader 将负责协调 WriteGroup 内写操作的有序执行，适时地唤醒 Follower，并在 WriteGroup 执行结束唤醒新的Leader 执行新一轮的 WriteGroup 写。
执行流程
在默认情况下：
一个 WriteBatch 封装为 Writer 对象，插入等待链表当中。插入的同时判断是否插入空链表而被选为起始 Leader：若是，则执行步骤2；否则 Writer 线程进入等待状态等待唤醒，执行步骤6。
Leader 从等待链表中获取一批 Writer 组成 BatchGroup，其他 Writer 作为 Follower。
Leader 合并 BatchGroup内所有 Writer 的数据，设置 seqNumber，写 WAL 日志。
Leader 遍历 WriteGroup 的所有 Writer，通过 MemtableInserter 对象将所有数据插入到Memtable。
Leader 修改 Follower 的状态并唤醒 Follower，更新等待链表，尝试唤醒下一个 Leader 。
Follower 检查状态，确认 Leader 执行结果并退出 WriteGroup。
实际上根据存储引擎的配置参数的不同，上述流程存在多种变化：
disableWAL：是否需要写 WAL 日志，一般只在 Bulkload 模式下使用；
allow_concurrent_Memtable_write：Memtable 是否允许并发写，目前只有 Skiplist 类型的 Memtable 支持并发写。
enable_pipelined_write：Memtable 写和 WAL 写是否分离，能够提高写的速率，降低时延。
two_write_queues：是否分离不需要写 Memtable 的负载和需要写 Memtable 的负载，该配置能够加速 2PC 提交。
例如，假设存储引擎采用 Skiplist 类型的 Memtable 并允许 Memtable 并发写，则上述步骤中：
步骤4修改为 Leader 修改 Follower 的状态，唤醒 Follower，只执行自己的数据写入操作。
步骤5修改为 Leader 等待 Follower 退出 WriteGroup，更新等待链表，尝试唤醒下一个Leader。
步骤6修改为 Follower 检查状态，执行自己的数据写入操作并退出 WriteGroup。
Batch in CRDB
Go 语言编写的 CRDB 与 C++ 语言版本的 RocksDB，通过 CGO 进行混合编程。参阅参考资料[3]可知，开发者在享受 CGO 带来的便捷性的同时，也需要明白其潜在的编程开销以及复杂度。在 CRDB 实现中，特别是对于 BatchPut 场景，不经过任何优化往往意味着数以千万次的 CGO 调用以及 GB 级别以上的隐式内存拷贝，其所带来的开销不容小觑。此外倘若调用 CGO 接口的线程在 RocksDB 底层遇到线程阻塞的情况（例如，同一个 WriteGroup 中 Follower 与 Leader 之间可能存在的相互等待的情况），阻碍 Go 语言层 goroutine 轻量级线程的切换，加重为系统级的线程切换，将会较大地影响并发性能。为此 CRDB 针对性地设计了自己的一套为了更高性能而生的 Batch 实现，同时兼容 RocksDB 底层实现的 WriteBatch 或是 WriteBatchWithIndex（继承自 WriteBatch 并进行了读优化）。
如上图，在 Go 语言层中 CRDB 声明了 Batch 接口并实现了“继承”了该接口的 rocksdbBatch 结构体。根据具体的数据特征和业务需求，rocksdbBatch 实现上分为读写模式、只写模式以及 Distinct 模式：读写模式在 RocksDB 底层使用了基于跳表索引的 WriteBatchWithIndex，引入了维护索引的开销，提供了数据快速读取的能力；只写模式则在底层使用了最基础的 WriteBatch，屏蔽了任何读操作；Distinct 模式针对的是 Key 值不重复的业务场景，避免了跳表索引检查重复 Key 值的开销。
而在 C++ 语言层，CRDB 在libroach.h中声明了 DBBatch 相关的接口并在 batch.cc 中实现接口，封装了 WriteBatch 或 WriteBatchWithIndex、迭代器创建等内容。
如上图，CRDB 实现了类似 RocksDB 的 Writer&WriteGroup 的简化模型。rocksdbBatch封装了 RocksDBBatchBuilder 对象，所有 Put 操作的数据直接插入到 RocksDBBatchBuilder 对象的缓冲区当中，尽可能地避免了直接调用底层 RocksDB 的 Put 接口，从而减少了 CGO 的调用开销。
在 Commit 阶段，所有 rocksdbBatch 都将添加到 pending 数组当中并确定角色：如果是Leader线程，则获取 BatchGroup 中的其他 rocksdbBatch 的数据，通过 DBApplyBatchRepr 接口将其他数据合并到自己的 WriteBatch 当中，再通过 DBCommitAndCloseBatch 接口向 RocksDB 一并提交并执行所有的数据写入操作，任务完成后唤醒 Follower线程；如果是 Follower 线程则在提交后进入等待状态，等待 Leader 线程完成任务后唤醒自己。此时除了 Leader 以外的所有线程完全由 goroutine 并发模型管理，能够有效减少 C++ 层阻塞带来的系统级线程切换带来的性能影响。
值得注意的是图中的 Repr 代表的是一个内存段，CRDB 的 RocksDBBatchBuilder 和RocksDB 的 WriteBatch 对于缓存的数据，拥有一致的数据编码格式，如下图所示。这意味无论是 C++ 语言层与 GO 语言层对于彼此之间缓存的数据内容都能够直接解析，之间的数据交互只需要交换内存段起始地址和长度的信息，这样能够有效地避免 C++ 与 GO 之间的隐式内存拷贝的开销。
结 语
本文在第一章和第二章主要讲解了 RocksDB 基于 WriteBatch 的数据写入操作，同时在第三章介绍了 CRDB 在 C++ 语言层对 RocksDB WriteBatch 进行高度封装，Go 语言层对部分逻辑进行了上推与重写，优化混合编程模型。
CRDB 是一款分布式的、能够承载 EB 级别数据规模的开源 NewSQL 数据库，其所具有高并发、弹性拓展、多活高可用的特性，在轻度冲突的情况下性能与集群规模成比例，对数据写入的性能有较高的要求。而在 CRDB 开发者一直致力于 RocksDB 存储引擎的研究，积极参与 RocksDB 开源社区的交流与建设，同时在实际应用中根据自身负载特性进行深度的定制，以追求单点更快的存储性能，使得集群整体的性能表现更为优秀。
参考资料：
[1] https://github.com/facebook/rocksdb
[2] https://github.com/cockroachdb/cockroach
[3] https://www.cockroachlabs.com/blog/the-cost-and-complexity-of-cgo/
[4] https://github.com/cockroachdb/cockroach/issues/6739
[5] http://www.leviathan.vip/2018/02/27/Rocksdb%E7%9A%84Put/
[6] http://kernelmaker.github.io/Rocksdb_Study_1
关于我们：我们是百度 DBA 团队，团队有两位 CockroachDB PMC Member 及一位 Contributor, 目前正积极推动 NewSQL 在百度内部以及外部的发展。除了NewSQL, 我们在MySQL, PostgreSQL, GreenPlum 有多年的内核开发经验及实践经验，对数据库和大数据领域有疑问或者需求欢迎联系我们，同时欢迎有志青年加入我们！
关注我们
