Pebble：一个受RocksDB启发用Go编写的键值存储

工程设计从一开始，CockroachDB就依赖于RocksDB作为其键值存储引擎。选择RocksDB对我们很有帮助。RocksDB经过了战斗测试，具有很高的性能，并且提供了丰富的功能集。我们是RocksDB的忠实粉丝，当被问及为什么不选择另一个存储引擎时，我们经常对它赞不绝口。

今天我们将介绍Pebble：一个受RocksDB启发的兼容RocksDB的键值存储，专注于CockroachDB的需求。Pebble带来了更好的性能和稳定性，避免了穿越CGO边界的挑战，并使我们能够更好地控制针对CockroachDB需求量身定做的未来增强功能。在我们即将在今年秋天发布的20.2版本中，Pebble将取代RocksDB作为默认存储引擎。这就是我们编写Pebble的原因，以及我们如何更改CockroachDB的基础组件的故事。

存储引擎是数据库的关键组件，为性能和稳定性提供基础。传统的SQL和NoSQL数据库通常是使用它们自己的专有存储引擎构建的。MySQL使用InnoDB，Postgres附带内部B-tree、哈希和堆存储系统，Cassandra附带LSM树实现。最近，其中一些数据库增加了RocksDB后端(例如MyRock和Rocksandra)。从远处看，这给人一种感觉，RocksDB正在蚕食低级别的存储生态系统。仔细检查就会发现，这些现有系统的RocksDB后端都有重要的注意事项。

在构建任何复杂的软件时，不可能从头开始构建每个组件。重用现有组件可以更快地将产品推向市场，而且往往是更好的产品，因为领域专家已经花费时间来制作和调整各个组件。对于我们选择使用RocksDB来说，这当然是正确的，但随着时间的推移，计算结果发生了变化。RocksDB被许多不同的系统使用。这种广泛的使用意味着大量的测试和性能调优，但这也意味着RocksDB正在为许多主服务器提供服务。我们可以在RocksDB非常大的功能集和配置表面积中看到这一点的影响。随着时间的推移，RocksDB代码库不断扩展，从LevelDB最初的30k行代码增长到目前的350k多行代码。代码行数是一个不充分的度量标准，但是这些大小确实提供了相对复杂的粗略感觉。

RocksDB一直是CockroachDB构建的坚实基础。不幸的是，随着CockroachDB的成熟，我们在RocksDB中遇到了严重的错误。例如，RocksDB在与压缩相关的代码中有一个bug，导致特定稳定的压缩无限循环，导致LSM树的其他部分无法压缩。虽然我们在RocksDB中遇到的错误的绝对数量不多，但它们的严重性通常很高，修复它们的紧迫性经常是House is Fire。这需要蟑螂实验室的工程师深入研究RocksDB代码库，作为缺陷调查的一部分。浏览350k+行的外国C++代码是可行的(我们已经做到了)，但很难说是一段美好的时光。CockroachDB主要是一个围棋代码库，Cockroach实验室的工程师在围棋方面已经开发出了广泛的专业知识。C++的专业知识要稀少得多，Go和C++之间的障碍在心理上是真实的。该障碍阻止使用本机GO配置文件工具自省C++或查看C++堆栈跟踪。我们必须用C++编写大量的逻辑，以避免频繁从Go到C++的性能开销，有时会重复Go中已经存在的逻辑。

RocksDB通常具有很高的性能，但我们也遇到了严重的性能问题。CockroachDB是范围删除的早期采用者，但我们也很早就发现了第一个实现中的一些性能缺陷。我们增加了范围删除的性能修复，并帮助设计了v2实现。

RocksDB功能齐全，但有时功能会有不足。有时，我们选择解决CockroachDB代码中的这些缺陷，而不是在RocksDB中修复它们。这些决定不一定是有意识地做出的(参见上面关于Go和C++之间的心理障碍的内容)。这种解决方法的一个示例是CockroachDB压缩器。压缩器用于强制压缩RocksDB中最近通过DeleteRange操作删除的部分数据。与我们什么也不做的情况相比，这样可以更快地恢复磁盘空间。之所以需要压缩器，是因为RocksDB在其压缩决策中没有考虑范围删除操作。撇开低层细节不谈，可以得出的结论是，存储引擎对CockroachDB的功能和行为有重要影响。拥有存储层允许CockroachDB更直接地控制其命运。

一种判断力

最后一种选择是使用另一个存储引擎，比如Badger或BoltDB(如果我们想继续使用Go)。由于几个原因，这一替代方案没有得到认真考虑。这些存储引擎没有提供我们需要的所有功能，因此我们需要对其进行重大增强。运行RocksDB的CockroachDB集群的迁移情况会变得非常复杂，这使得我们可能需要在相当长的时间内同时支持这两个存储引擎。支持多个存储引擎本身就是一项巨大的努力：它极大地增加了测试表面积，而且替代存储引擎通常带有重要的警告(例如，MyRock不支持SAVEPOINT)。最后，各种RocksDB-ISM已经加入到CockroachDB代码库中，例如使用stable格式在节点之间发送数据快照。移除这些RocksDB-ISM或提供适配器，要么是一项巨大的工程工作，要么会带来不可接受的性能开销。

更换像RocksDB这样大的组件是一项艰巨的任务。我们确实有几个有利因素：

我们非常了解CockroachDB对RocksDB的使用。Pebble的目标并不是完全替代RocksDB，而只是替代CockroachDB使用的RocksDB中的功能。一个大致的估计是，这将使替换任务的范围减少至少50%。Pebble代码库目前包含超过45k行的代码和另外45k行的测试。这只是RocksDB代码大小的一小部分，一个很大的原因是我们没有复制所有的RocksDB功能。

我们不是从零开始的。LevelDB的Go移植几年前就开始了，但从未完成。Pebble中只剩下很少的起点，但它确实展示了最初的框架，并提供了读取和写入低级文件格式的早期代码。

我们可以将RocksDB的代码作为实现模板。例如，虽然没有正式指定低级RocksDB文件格式，但是RocksDB代码提供了足够的文档来说明这些格式。重用RocksDB文件格式从Pebble设计中移除了一定程度的自由度，但这并不是一个繁重的约束。不过，这一点不仅仅是关于文件格式。我们可以从RocksDB代码的各个部分获取灵感和想法。

Pebble的API和内部结构类似于RocksDB。Pebble是一个LSM键值存储，它提供Set、Merge、Delete和DeleteRange操作。可以将操作分组为原子批处理。可以通过GET单独读取记录，也可以使用迭代器按键顺序迭代记录。轻量级时间点只读快照提供数据库的稳定视图。在内部，Pebble中的数据存储在预写日志(WAL)和排序字符串表(Sstables)的组合中。最近写入的数据缓冲在内存中的一系列Memtable中，这些Memtable由Arena支持的并发Skiplist在幕后实现。Memtable被刷新到磁盘以创建稳定表。稳定器在后台定期压缩。Pebble中的压缩机制和启发式方法都与RocksDB中的类似(至少对于CockroachDB使用的配置是这样)。

熟悉RocksDB内部结构的任何人都会在Pebble代码中看到许多相似之处。也有很多不同之处。我们已经记录了一些较大的。例如，范围删除实现与RocksDB中的实现有很大的不同，后者支持更多的优化，以便在迭代期间跳过大量删除的键。对索引批的处理是完全不同的，这使得Pebble实现能够支持所有突变操作的索引，而RocksDB目前不支持(例如，RocksDB不支持批量索引范围删除)。这些例子并不是要批评RocksDB。我们完全期待Pebble中的一些好点子会被RocksDB采纳，就像我们会继续从RocksDB中收集好点子一样。

Pebble实现了CockroachDB使用的RocksDB功能的子集。我们不希望最终包含RocksDB中的所有功能。事实上，情况恰恰相反。我们打算通过是否对CockroachDB有用的标准来过滤每一个特性添加和性能改进。对于通用键值存储引擎来说，这是一个苛刻的过滤器，但这不是Pebble的目标。那么Pebble包括哪些功能呢？

上面的一些项目可能会让你大吃一惊。既然CockroachDB提供了对备份或事务的支持，Pebble怎么会不包括对备份或事务的支持呢？CockroachDB的备份和事务实现从未使用过RocksDB中的备份和事务功能。实现分布式事务不需要本地键值存储上的事务。相反，CockroachDB使用批处理作为构建分布式事务的基础，批处理为一组操作提供原子性。

我们很早就决定让Pebble在初始版本中实现与RocksDB的双向兼容性。更确切地说，对于CockroachDB使用的RocksDB功能子集，Pebble目前与RocksDB 6.2.1(CockroachDB当前使用的RocksDB版本)是双向兼容的。双向兼容意味着Pebble可以读取RocksDB生成的DB，而RocksDB可以读取Pebble生成的DB。与RocksDB的兼容性支持无缝迁移到Pebble，只需使用新的命令行标志重新启动Cockroach节点：--storage-engine=pebble。双向兼容性提供了额外的安全级别：如果在使用Pebble时遇到问题，我们可以切换回使用RocksDB。双向兼容性还可以提高测试的严格性，测试部分将对此进行详细讨论。

请注意，与RocksDB的双向兼容性将在某个时候消失。永远保持这样的兼容性与我们希望在CockroachDB服务中增强Pebble的愿望是不一致的。维护与新的RocksDB功能的兼容性将是一个巨大的持续负担。

存储引擎是数据库的组件，其任务是持久地将数据写入磁盘。存储引擎中的错误往往很严重，例如数据损坏和数据不可用。存储引擎的测试需要健壮。

第一层测试是大量的Pebble单元测试。这些单元测试旨在测试所有正常情况和转角情况。列出所有的角落案例是一项具有挑战性的工作。即使是一个勤奋的工程师也可能错过一个转折点的案例。更有问题的是，对代码的微小更改可能会引入新的死角情况。相信我们会在做出任何改变时识别出这些新的角落案例，这会很好，但我们的经验表明并非如此。

随机化测试是近年来流行的角例问题的一种解决方案。模糊测试是随机测试的一个示例，通常用于检查解析器和协议解码器。对于Pebble，我们可以编写一个随机生成操作的测试，而不是尝试显式地枚举所有的角点情况。自然出现的问题是：我们如何知道操作结果是否正确？使用模糊测试，我们只需查找程序崩溃。这也是Pebble随机测试中的第一行检查，我们通过对某些关键内部数据结构的不变检查进一步增强了这一功能。简单地寻找崩溃和不变违规有点不能令人满意。我们想知道手术结果是否真的是正确的。为预期的操作结果维护单独的模型是一项艰巨的任务，因为Pebble实现的数据模型不仅仅是键和值的有序映射，这是因为存在快照(隐式和显式)和范围删除。解决办法是变质测试。我们随机生成一系列操作，然后针对不同配置的Pebble多次执行这些操作。对不同运行的输出进行了比较，任何差异都值得关注。我们调整的Pebble配置旋钮包括块缓存的大小、内存表的大小和稳定的目标大小。更改这些配置操作会导致执行Pebble内的不同内部代码路径。例如，更改稳定表的目标大小会导致在处理范围删除时出现不同的情况。在编写本文时，针对19个预定义配置和10个随机生成的配置运行变形测试的每个实例。

我们实际上已经实现了两个不同版本的变形测试。第一个完全在Pebble API上操作，并且只对Pebble本身进行测试。您可能会想：为什么不也针对RocksDB进行测试呢？我们也有同样的想法。不幸的是，与RocksDB相比，Pebble API有一些细微的差异和概括，这使得这一点具有挑战性。相反，我们实现了第二个变形测试，该测试在CockroachDB内的Pebble/RocksDB集成层工作。第二个变形测试不仅验证Pebble和RocksDB产生相同的结果，而且验证CockroachDB内的Pebble和RocksDB特定的胶水代码产生相同的结果。

如前所述，Pebble的目标是与RocksDB双向兼容。为了测试这种相容性，再次延长了变质试验。“重新启动”操作被更改为在Pebble和RocksDB之间随机切换。这项测试发现了Pebble和RocksDB之间的几个不兼容之处，例如Pebble错误地设置了sstables上的属性，导致RocksDB解释这些sstables的方式与Pebble不同。除了变形测试中的兼容性测试之外，我们还实现了一个CockroachDB级集成测试，该测试模拟用户可能执行的验证双向兼容性的操作。此测试启动一个CockroachDB集群，然后随机终止并重新启动集群中的节点，切换正在使用的存储引擎。

在此测试中发现的错误类型各不相同，从微小的差异到最严重的数据损坏类型不等。后者的一个示例是布隆过滤器代码使用的散列函数中极其细微的差异：将有符号8位整数扩展到32位会产生与将无符号8位整数扩展到32位不同的值。这导致Pebble的Bloom Filter哈希函数为键子集(即包含高位设置的字节的密钥)生成与RocksDB的Bloom Filter哈希函数不同的值。这个错误的起源本身就很有趣。Pebble的Bloom Filter散列函数继承自从LevelDB继承的go-level db。LevelDB的散列函数的原始实现具有依赖于C字符类型是有符号的还是无符号的行为(这是通过GCC/clang的标志来控制的)。这种微妙的依赖关系在几年前就在LevelDB和RocksDB中得到了修复，但这种依赖关系在转换过程中又滑回了某个地方。

Pebble测试的最后几层利用了现有的CockroachDB单元测试和夜间测试。我们添加了一个环境变量(ROKROACH_STORAGE_ENGINE)来控制CockroachDB单元测试使用Pebble还是RocksDB。我们还实现了另一个存储引擎来进行额外级别的测试。Tee存储引擎顾名思义就是这样做的：它将所有写操作都提交给Pebble和RocksDB。读取操作将定向到两个底层存储引擎并进行比较，以确保返回相同的结果。

CockroachDB每晚运行一套称为roachtest的集成测试。Roachtest在AWS或GCP上启动群集，并执行群集级别测试。使用相同的ROACH_STORAGE_ENGINE环境变量来允许在Pebble上运行这些测试。

如果不考虑性能，任何新存储引擎的发布都是不完整的。如果性能受到严重影响，用RocksDB替换Pebble将是不可能的。RocksDB的性能很高，我们必须花费大量精力才能赶上或超过它的性能。存储引擎的性能表面积是巨大的，而这篇文章只能触及其中的一小部分。性能不仅与原始吞吐量和延迟有关，还与资源消耗有关，例如CPU和内存使用率。归根结底，我们最关心的是Pebble与RocksDB在CockroachDB级别工作负载上的性能。

YCSB是检查存储引擎性能的标准基准。它运行六个工作负载：工作负载A混合了50%的读取和50%的更新。工作负载B混合了95%的读取和5%的更新。工作负载C为100%读取。工作负载D是95%的读取和5%的插入。工作负载E是95%的扫描和5%的插入。工作负载F是50%的读取和50%的读取-修改-写入。Pebble和RocksDB配置了类似的选项(在有重叠的地方相同)。所有工作负载的数据集大小都适合。

.