一文科普 RocksDB 工作原理-技术圈

本篇文章来自我的小报童专栏，初步规划有以下几个系列：

图数据库101系列

每天学点数据库系列

系统好文推荐系列

读书笔记系列

数据密集型论文导读系列

源码阅读系列

会保证每周不低于两篇更新，订阅方式见👉这里，欢迎喜欢我文章的朋友们的订阅支持，激励我产出更多优质文章。

RocksDB 是很多分布式数据库的底层存储，如 TiKV、CRDB、NebulaGraph 等等。在 DataDog 工作的 Artem Krylysov 写了一篇文章（原文链接：https://artem.krylysov.com/blog/2023/04/19/how-rocksdb-works/）来对 RocksDB 做了一个科普，通俗易懂，在这里翻译下分享给大家。

导语

近几年，RocksDB 的采用率急速上升，俨然成为内嵌型键值存储（以下简称 kv 存储）的不二之选。

目前，RocksDB 在 Meta、Microsoft、Netflix 和 Uber 等公司的生产环境上运行。在 Meta，RocksDB 作为 MySQL 部署的存储引擎，为分布式图数据库（TAO）提供支持存储服务。

大型科技公司并非 RocksDB 的仅有用户，像是 CockroachDB、Yugabyte、PingCAP 和 Rockset 等多个初创企业都构建在 RocksDB 基础之上。

我在 Datadog 工作了 4 年时间，在生产环境中构建和运行了一系列基于 RocksDB 的服务。本文将就 RocksDB 的工作原理进行概要式讲解。

RocksDB 是什么

RocksDB 是一种可持久化的、内嵌型 kv 存储。它是为了存储大量的 key 及其对应 value 设计出来的数据库。可以基于这种简单 kv 数据模型来构建倒排索引、文档数据库、SQL 数据库、缓存系统和消息代理等复杂系统。

RocksDB 是 2012 年从 Google 的 LevelDB fork 出来的分支，并针对跑在 SSD 上的服务器进行了优化。目前，RocksDB 由 Meta 开发和维护。

RocksDB 使用 C++ 编写而成，因此除了支持 C 和 C++ 之外，还能通过 С binding 的形式嵌入到使用其他语言编写的应用中，例如 Rust、Go 或 Java。

如果你之前用过 SQLite，你肯定知道什么是内嵌式数据库。在数据库领域，特别是在 RocksDB 的上下文中，“内嵌”意味着：

该数据库没有独立进程，而是被集成进应用中，和应用共享内存等资源，从而避免了跨进程通信的开销。
它没有内置服务器，无法通过网络进行远程访问。
它不是分布式的，这意味着它不提供容错性、冗余或分片（sharding）机制。

如有必要，需依赖于应用层来实现上述功能。

RocksDB 以 kv 对集合的形式存储数据， key 和 value 是任意长度的字节数组（byte array），因此都是没有类型的。RocksDB 提供了很少的几个用于修改 kv 集合的函数底层接口：

put(key, value)：插入新的键值对或更新已有键值对
merge(key, value)：将新值与给定键的原值进行合并
delete(key)：从集合中删除键值对

通过点查来获取 key 所关联的 value：

get(key)

通过迭代器可以进行范围扫描——找到特定的 key，并按顺序访问该 key 后续的键值对：

iterator.seek(key_prefix); iterator.value(); iterator.next()

Log-structured merge-tree

RocksDB 的核心数据结构被称为日志结构合并树 （LSM-Tree）。它是一种树形的数据结构，由多个层级组成，每层的数据按 key 有序。LSM-Tree 主要设计用来应对写入密集型工作负载，并于 1996 年在同名论文 The Log-Structured Merge-Tree (LSM-Tree) 被大家所知。

LSM-Tree 的最高层保存在内存中，包含最近写入的数据。其他较低层级的数据存储在磁盘上，层数编号从 0 到 N 。第 0 层 L0 存储从内存移动到磁盘上的数据，第 1 层及以下层级则存储更老的数据。通常某层的下个层级在数据量上会比该层大一个数量级，当某层数据量变得过大时，会合并到下一层。

注：虽然本文主要讨论 RocksDB，但涉及 LSM-Tree 的概念适用于大多数底层采用此技术实现的数据库（例如 Bigtable、HBase、Cassandra、ScyllaDB、LevelDB 和 MongoDB WiredTiger）。

为了更好地理解 LSM-Tree 的工作原理，下面我们将着重剖析它的写 / 读路径。

写路径

MemTable

LSM-Tree 的顶层被称为 MemTable。MemTable 是一个内存缓冲区，在键值对写入磁盘之前，Memtable 会缓存住这些键值对。所有插入和更新操作都会过 MemTable。当然也包括删除操作：不过，在 RocksDB 中，并不会直接原地修改键值对，而是通过插入墓碑记录（tombstone ）来进行标记删除。

MemTable 具有可配置的字节数限制。当一个 MemTable 变满时，就会切到一个新的 MemTable，同时原 MemTable 变为不可修改状态。

注：MemTable 的默认大小为 64 MB。

现在，我们往数据库写入点 key 看看：

      db.put("chipmunk", "1")
db.put("cat", "2")
db.put("raccoon", "3")
db.put("dog", "4")

MemTable：内存中的一个有序查找表

如上图所示，MemTable 中的键值对是按 key 有序排列的。尽管 chipmunk 是最先插入的，但由于 MemTable 是按 key 有序的，因此 chipmunk 排在 cat 之后。这种排序对于范围扫描是必须的，此外，稍后我会详细介绍，它也会让某些操作更加高效。

预写日志

无论是在进程意外崩溃退出还是计划内重启时，其内存中的数据都会丢失。为了防止数据丢失，保证数据的持久化，除了 MemTable 之外，RocksDB 会将所有更新写入到磁盘上的预写日志（WAL，Write-ahead log）中。这样，在重启后，数据库可以回放日志，进而恢复 MemTable 的原始状态。

WAL 是一个只允许追加的文件，包含一组更改记录序列。每个记录包含键值对、记录类型（Put / Merge / Delete）和校验和（checksum）。与 MemTable 不同，在 WAL 中，记录不按 key 有序，而是按照请求到来的顺序被追加到 WAL 中。

WAL：为了应对宕机的写前日志

Flush

RocksDB 使用一个专门的后台线程定期地把不可变的 MemTable 从内存持久化到磁盘。一旦刷盘（flush）完成，不可变的 MemTable 和相应的 WAL 就会被丢弃。RocksDB 开始写入新的 WAL、MemTable。每次刷盘都会在 L0 层上产生一个新的 SST 文件。该文件一旦写入磁盘后，就不再会修改。

RocksDB 的 MemTable 的默认基于跳表实现。该数据结构是一个具有额外采样层的链表，从而允许快速、有序地查询和插入数据。有序性使得 MemTable 刷盘时更高效，因为可以直接按顺序迭代键值对顺序写入磁盘。将随机写变为顺序写是 LSM-Tree 的核心设计之一。

Flush：将不可变内存表刷到磁盘的过程

注：RocksDB 高度可配，因此你可以给 MemTable 配置其他的实现方案，RocksDB 中大部分组件都是如此。在其他的一些基于 LSM 实现的数据库中，使用自平衡二叉搜索树来实现 MemTable 并不鲜见。

SST

SST 文件包括从 MemTable 刷盘而来的键值对，并且使用一种对查询友好的数据格式来存储。SST 是 Static Sorted Table 的缩写（其他数据库中也称为 Sorted String Table）。它是一种基于块（ block）的文件格式，会将数据切成固定大小的块（默认为 4KB）进行存储。RocksDB 支持各种压缩 SST 文件的压缩算法，例如 Zlib、BZ2、Snappy、LZ4 或 ZSTD 算法。与 WAL 的记录类似，每个数据块中都包含用于检测数据是否损坏的校验和。每次从磁盘读取数据时，RocksDB 都会使用这些校验和进行校验。

SST 文件由几个部分组成：首先是数据部分，包含一系列有序的键值对。key 的有序性可以让我们对其进行增量编码，也即，对于相邻的 key ，我们可以只存其差值而非整个 key。

尽管 SST 中的 kv 对是有序的，我们也并非总能进行二分查找，尤其是数据块在压缩过后，会使得查找很低效。RocksDB 使用索引来优化查询，存储在紧邻数据块之后的索引块。Index 会把每个 block 数据中最后一个 key 映射到它在磁盘上的对应偏移量。同样地，index 中的 key 也是有序的，因此我们可以通过二分搜索快速找到某个 key。

SST：带有索引的外存查找文件

例如，我们在查找 lynx，索引会告诉我们这个键值对可能在 block 2，因为按照字典序，lynx 在 chipmunk 之后，但在 raccoon 之前。

但其实 SST 文件中并没有 lynx，但我们仍然需要从磁盘加载 block 以进行搜索。RocksDB 支持启用布隆过滤器，一种具有高效空间利用率的概率性数据结构，可以用来检测某个元素是否在集合中。布隆过滤器保存在 SST 文件中过滤器部分，以便能够快速确定某个 key 不在 SST 中（从而省去摸硬盘上的数据块的开销）。

此外，SST 还有其他几个不太有趣的部分，比如元数据部分。

Compaction

到现在为止，一个功能完备的键值存储引擎讲完了。但如果这样直接上生产环境，会有一些问题：空间放大（space amplifications）和读放大（read amplifications）。空间放大是存储数据所用实际空间与逻辑上数据大小的比值。假设一个数据库需要 2 MB 磁盘空间来存储逻辑上的 1 MB 大小的键值对是，那么它的空间放大率是 2。类似地，读放大用来衡量用户执行一次逻辑上的读操作，系统内所需进行的实际 IO 次数。作为一个小练习，你可以尝试推演下什么是写放大。

现在，让我们向数据库添加更多 key 并删除当中的一些 key：

      db.delete("chipmunk")
db.put("cat", "5")
db.put("raccoon", "6")
db.put("zebra", "7")
// Flush triggers
db.delete("raccoon")
db.put("cat", "8")
db.put("zebra", "9")
db.put("duck", "10")

随着我们的不断写入，MemTable 不断被刷到磁盘，L0 上的 SST 文件数量也在增长：

删除或更新 key 所占用的空间永远不会被回收。例如，cat 这个 key 的三次更新记录分别在 SST1，SST2 和 SST3 中，而 chipmunk 在 SST1 中有一次更新记录，在 SST2 中有一次删除记录，这些无用的记录仍然占用额外磁盘空间。
随着 L0 上 SST 文件数量的增加，读取变得越来越慢。每次查找都要逐个检查所有 SST 文件。

RocksDB 引入了压实（ Compaction ）机制，可以降低空间放大和读放大，但代价是更高的写放大。Compaction 会将某层的 SST 文件同下一层的 SST 文件合并，并在这个过程中丢弃已删除和被覆盖的无效 key。Compaction 会在后台专用的线程池中运行，从而保证了 RocksDB 可以在做 Compaction 时能够正常处理用户的读写请求。

Leveled Compaction 是 RocksDB 中的默认 Compaction 策略。使用 Leveled Compaction，L0 层中的不同 SST 文件键范围会重叠。L1 层及以下层会被组织为包含多个 SST 文件的序列，并保证同层级内的所有 SST 在键范围上没有交叠，且 SST 文件之间有序。Compaction 时，会选择性地将某层的 SST 文件与下一层的 key 范围有重叠 SST 文件进行合并。

举例来说，如下图所示，在 L0 到 L1 层进行 Compaction 时，如果 L0 上的输入文件覆盖整个键范围，此时就需要对所有 L0 和 L1 层的文件进行 Compaction。

而像是下面的这种 L1 和 L2 层的 Compaction，L1 层的输入文件只与 L2 层的两个 SST 文件重叠，因此，只需要对部分文件进行 Compaction 即可。

当 L0 层上的 SST 文件数量达到一定阈值（默认为 4）时，将触发 Compaction。对于 L1 层及以下层级，当整个层级的 SST 文件总大小超过配置的目标大小时，会触发 Compaction 。当这种情况发生时，可能会触发 L1 到 L2 层的 Compaction。从而，从 L0 到 L1 层的 Compaction 可能会引发一直到最底层级联 Compaction。在 Compaction 完成之后，RocksDB 会更新元数据并从磁盘中删除已经被 Compcated 过的文件。

注：RocksDB 提供了不同 Compaction 策略来在空间、读放大和写放大之间进行权衡。

看到这里，你还记得上文提过 SST 文件中的 key 是有序的吗？有序性允许使用 K 路归并算法逐步合并多个 SST 文件。K 路归并是两路归并的泛化版本，其工作方式类似于归并排序的归并阶段。

读路径

使用持久化在磁盘上不可变的 SST 文件，读路径要比写路径简单很多。要找寻某个 key，只需自顶而下遍历 LSM—Tree。从 MemTable 开始，下探到 L0，然后继续向更低层级查找，直到找到该 key 或者检查完所有 SST 文件为止。

以下是查找步骤：

检索 MemTable。
检索不可变 MemTables。
搜索最近 flush 过的 L0 层中的所有 SST 文件。
对于 L1 层及以下层级，首先找到可能包含该 key 的单个 SST 文件，然后在文件内进行搜索。

搜索 SST 文件涉及：

（可选）探测布隆过滤器。
查找 index 来找到可能包含这个 key 的 block 所在位置。
读取 block 文件并尝试在其中找到 key。

这就是全部所需步骤了！看看这个 LSM-Tree：

!https://-website-cn.oss-cn-hangzhou.aliyuncs.com/-blog/how-rocksdb-works/rocksdb-lookup.png

根据待查找的 key 的具体情况，查找过程可能在上面任意步骤提前终止。例如，在搜索 MemTable 后，key “cat” 或 “chipmunk” 的查找工作会立即结束。查找 “raccoon” 则需要搜索 L1 为止，而查找根本不存在的 “manul” 则需要搜索整个树。

Merge

RocksDB 还提供了一个同时涉及读路径和写路径的功能：合并（merge）操作。假设，你在数据库中存了一个整数列表，偶尔需要扩展该列表。为了修改列表，你需要从数据库中读取其现有值，在内存中更新该列表，最后把更新后的值写回数据库。

上面整个操作序列被称为 “Read-Modify-Write” 循环：

      db = open_db(path)

// 读取 Read
old_val = db.get(key) // RocksDB stores keys and values as byte arrays. We need to deserialize the value to turn it into a list.
old_list = deserialize_list(old_val) // old_list: [1, 2, 3]

// 修改 Modify
new_list = old_list.extend([4, 5, 6]) // new_list: [1, 2, 3, 4, 5, 6]
new_val = serialize_list(new_list)

// 写回 Write
db.put(key, new_val)

db.get(key) // deserialized value: [1, 2, 3, 4, 5, 6]

上面这种方式能达到目的，但存在一些缺陷：

非线程安全——两个尝试更新相同的 key 的不同线程，交错执行，会出现更新丢失。
存在写放大——随着值变得越来越大，更新成本也会增加。例如，在含有 100 个数的列表中追加一个整数需要读取 100 个整数并将 101 个整数写回。

除了 Put 和 Delete 写操作之外，RocksDB 还支持第三种写操作 Merge。Merge 操作需要提供 Merge Operator——一个用户定义函数，负责将增量更新组合成单个值：

      funcmerge_operator(existing_val, updates) {
        combined_list = deserialize_list(existing_val)
        for op in updates {
                combined_list.extend(op)
        }
        return serialize_list(combined_list)
}

db = open_db(path, {merge_operator: merge_operator})
// key's value is [1, 2, 3]

list_update = serialize_list([4, 5, 6])
db.merge(key, list_update)

db.get(key) // deserialized value: [1, 2, 3, 4, 5, 6]

上面的 merge_operator 将传递给 Merge 调用的增量更新组合成一个单一值。当调用 Merge 时，RocksDB 仅将增量更新插入到 MemTable 和 WAL 中。之后，在 flush 和 compaction 时，RocksDB 调用 merge_operator() ，在条件允许时，将若干更新合并成单个更新或者单个值。在用户调用 Get 或扫描读取数据时，如果发现任何待 merge 的更新，也会调用 merge_operator 向用户返回一个经过 merge 而得到的值。

Merge 非常适合于需要持续对已有值进行少量更新的写入密集型场景。那么，代价是什么？读将变得更加昂贵——读时的合并值没有写回。对该 key 的查询需要一遍又一遍地执行相同的合并过程，直到触发 flush 和 compaction 为止。与 RocksDB 其他部分一样，我们可以通过限制 MemTable 中 merge 对象的数量、降低 L0 中 SST 文件数量来优化读行为。

挑战

如果你的应用对性能非常敏感，那么使用 RocksDB 面临的最大挑战是需要针对特定工作负载来进行配置调优。RocksDB 提供了非常多的可配置项，但对其进行合理调整通常需要理解数据库内部原理并深入研究 RocksDB 源代码：

“不幸的是，对 RocksDB 进行配置调优并不容易。即使作为 RocksDB 开发人员的我们，也不能完全理解每个配置更改的所造成的影响。如果你想针对你的工作负载充分调优，我们建议你进行实验和基准测试，并时刻注意三个放大因素。”

-- RocksDB 官方调优指南

总结

从零开始写一个生产级别的 kv 存储是非困难的：

硬件和操作系统随时都有可能丢失或损坏数据。
性能优化需要大量时间投入。

RocksDB 解决了上述两个问题，从而让你可以专注于上层业务逻辑实现。这也使得 RocksDB 成为构建数据库的优秀模块。

题图故事

喀什老城的一个巷子里，各种鲜艳颜色的搭配LSM-Tree 更多文章推荐阅读：漫谈 LevelDB 数据结构（一）：跳表（Skip List）
漫谈 LevelDB 数据结构（二）：布隆过滤器（Bloom Filter）
漫谈 LevelDB 数据结构（三）：LRU 缓存（ LRUCache）

点击“阅读原文 ”可以跳转我的小报童专栏，欢迎订阅支持我的持续创作。