介绍

在过去的几年里，RocksDB的使用率大大提高，已经成为了内嵌键值存储的标准。

如今，RocksDB在Meta、微软、Netflix、优步等公司的生产环境中都有运行。在Meta，RocksDB作为存储引擎服务于分布式图数据库的MySQL部署。

大型科技公司并非RocksDB的唯一用户。有几家围绕RocksDB建立的初创公司，如CockroachDB、Yugabyte、PingCAP、Rockset。

在这篇文章中，我将给出一个如何运作的RocksDB高级概述。

RocksDB是什么

RocksDB是一个嵌入式持续的键值存储。它是一种设计用来存储大量唯一键与值相关联的数据库。简单的键值数据模型可以用来构建搜索索引、面向文档的数据库、SQL数据库、缓存系统和消息经纪人。

RocksDB在2012年从谷歌的LevelDB里分离出来，并优化了在带有SSD驱动器的服务器上运行。目前，RocksDB由Meta开发和维护。

RocksDB是用C++编写的，因此除了C和C++，C语言的绑定允许将库嵌入到用其他语言如Rust、Go或Java编写的应用程序中。

如果你曾经使用过SQLite，那么你就已经知道什么是嵌入式数据库了。在数据库的上下文中，尤其是在RocksDB的上下文中，“嵌入式”意味着：数据库没有一个独立的进程；相反，它直接嵌入到你的应用程序中，共享其资源和内存，消除了昂贵的进程间通信的需求。

• 它没有内置的服务器，可以通过网络访问。

• 它不是分布式的，说明它不提供容错、复制或分片机制。

• 如果需要这些功能，那么由应用程序来实现。

RocksDB将数据存储为键值对的集合。键和值都不是类型化的，他们只是任意的字节数组。数据库提供了一个低级界面，包含一些用于修改集合状态的函数：

• put(key, value)：存储一个新的键值对或更新一个现有的。
• merge(key, value)：将新值和给定键的现有值合并。
• delete(key)：从集合中删除一个键值对。

可以用点查找来获取值：

• get(key)

迭代器可以实现"范围扫描" - 寻找一个特定的键并按顺序访问接下来的键值对：

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

日志结构合并树

RocksDB背后的核心数据结构叫作日志结构合并树（LSM-Tree）。它是一个树状结构，按键值排序进入多级。LSM-Tree主要设计用于高写入负载，并在1996年以同样的名字介绍出来。

LSM-Tree的顶级存储在内存中，包含最新输入的数据。较低的级别存储在硬盘上，从0到N级。 0级（L0）存储了从内存移到硬盘上的数据，1级和以下的级别存储了更早的数据。当一个级别变得过大时，它将会和下一级合并，后者通常比前者大一个数量级。

注意：我将具体谈吃RocksDB，但大部分涵盖到的概念适用于许多使用LSM-Tree作为核心的数据库（如Bigtable，HBase，Cassandra，ScyllaDB，LevelDB，MongoDB WiredTiger）。为了更好地理解LSM-Tree的运行原理，我们将仔细研究写入和读取路径。

写路径

MemTable

LSM-树的顶级被称为MemTable。它是一个内存缓冲区，保存键和值在被写入磁盘之前。所有的插入和更新总是经过memtable。对于删除操作也是如此 -- RocksDB通过插入一个墓碑记录来标记已删除的键，而不是就地修改键值对。

MemTable被配置为具有特定的字节大小。当MemTable满了后，它会和一个新的MemTable进行交换，旧的MemTable变为不可变的。

注意：MemTable的默认大小是64MB。

让我们通过向数据库中添加一些键来开始：

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

如你所见，MemTable中的键值对是按键排序的。虽然chipmunk是第一个被插入的，但是在MemTable中，由于排序的原因，它在cat后面。排序是支持范围扫描的要求，而且它使得一些后面我会提到的操作更加高效。

预写日志?

?在进程崩溃或规划应用程序重启的情况下，存在进程内存中的数据将会丢失。为了防止数据丢失并确保数据库更新是持久的，除了在MemTable中，RocksDB也将所有更新写入磁盘上的预写日志（WAL）中。这样，数据库可以在启动时回放日志并恢复MemTable的原始状态。

WAL是一个附加文件，由一系列的记录组成。每一条记录包含一个键值对，一种记录类型（Put/Merge/Delete）和一个校验和。在回放日志时，校验和用于检测数据损坏或者部分写入的记录。不像在MemTable中，WAL中的记录不是按键排序的。相反，它们按着到达的顺序进行附加。

Flush

?RocksDB运行一个专门的后台线程，将不可变的MemTables持久化到磁盘。一旦Flush完成，不可变的MemTable和相应的WAL就会被丢弃。RocksDB开始写入一个新的WAL和一个新的MemTable。每次Flush在L0产生一个单一的SST文件。生成的文件是不可变的 -- 他们一旦被写入磁盘就永远不会被修改。

RocksDB默认的MemTable实现是基于跳表的。这个数据结构是一个带有额外层的链接列表，允许快速查找和插入排序顺序。这个排序使Flush变得高效，允许通过迭代键值对将MemTable的内容顺序写入磁盘。将随机插入转化为顺序写入是LSM-Tree设计背后的关键思路之一。

注意：RocksDB是高度可配置的。就像其他许多组件一样，MemTable的实现可以和替代方案进行交换。在其他基于LSM的数据库中使用自平衡二叉查找树来实现MemTable是很常见的。

SST?

?SST文件包含了被从MemTable刷新到磁盘上的键值对，文件格式已经为查询进行优化。SST代表静态排序表（在一些其他的数据库中被称为排序字符串表）。这是一种基于块的文件格式，组织数据成块（默认的大小目标是4KB）。个别块可以使用RocksDB支持的各种压缩算法进行压缩，如Zlib，BZ2，Snappy，LZ4，或ZSTD。就像WAL中的记录一样，块包含校验和来检测数据损坏。每次RocksDB从磁盘读取时，它都会验证这些校验和。

SST文件中的块分为几部分。第一部分，数据部分，包含一个键值对的有序序列。这个排序允许对键进行delta编码，意味着我们只需要存储相邻键之间的差异，而不再需要存储完整的键。

虽然SST文件中的键值对是存储在有序的，但是二进制搜索并不总是可以应用的，特别是当块被压缩后，使得搜索文件效率低下。RocksDB通过添加一个索引来优化查找，索引存储在数据部分之后的单独的部分中。索引将每个数据块的最后一个键映射到其在磁盘上对应的偏移量。再次，索引中的键是有序的，这允许我们通过执行一个二进制搜索来快速地找到一个键。例如，如果我们正在查找lynx，索引告诉我们键可能在块2中，因为lynx在chipmunk之后，但在raccoon之前。

实际上，在上面的SST文件中没有lynx，但是我们必须从磁盘读取块并搜索它。RocksDB支持启用Bloom filter—一种空间效率高的概率数据结构，用来测试一个元素是否属于一个集合。它储存在一个可选的Bloom filter部分并加快了对不存在的键的搜索。

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

排序?

?

到目前为止我描述的已经是一个功能性的键值存储。但是有一些挑战会阻碍它在生产系统中的使用：空间和读放大。空间扩展测量存储空间与储存逻辑数据大小的比率。比如说，如果一个数据库需要2MB的磁盘空间储存占用1MB的键值对，空间增益就是2。类似地，读扩展测量执行逻辑读操作所需的IO操作数量。我将留给你作为一个小练习去理解什么是写放大。

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

db.delete("chipmunk")
db.put("cat", "5")
db.put("raccoon", "6")
db.put("zebra", "7")
// 刷新的触发
db.delete("raccoon")
db.put("cat", "8")
db.put("zebra", "9")
db.put("duck", "10")

当我们继续写入，MemTables被刷新，L0上的SST文件数量继续增长:

被删除或更新的键占用的空间永远不会被回收。例如，键cat有三个复制品，尽管它们已经不再需要，chipmunk和raccoon仍然在磁盘上占据空间。

?

随着L0上的SST文件数量的增加，读取变慢了。每个键查找都需要检查每一个SST文件来找到所需的键。

一个叫作整理的机制有助于减少空间和读放大，以换取增加的写放大。整理选择一级上的SST文件并将它们与下一级的SST文件合并，丢弃被删除和被重写的键。整理在一个专用的线程池的后台运行，这使RocksDB可以在整理进行时继续处理读写请求。

级别整理（Leveled Compaction）是RocksDB中的默认整理策略。通过级别整理，L0上的SST文件的键范围是重叠的。1级和以下则被组织为包含一个单一的排序的键范围，被划分为多个SST文件，据保证同一级别内键范围不会有重叠。整理选择一级的文件并将它们与下一级中重叠范围的文件合并。例如，在一个L0到L1的整理中，如果L0的输入文件包含整个键范围，那么整理就必须选择L0和L1的所有文件。

?

在下面的L1到L2的整理中，L1上的输入文件与L2上的两个文件重叠，所以整理只限制在一部分文件。

?整理触发器会在L0达到一定的SST文件数量时激活（默认为4）。对于L1及以下，当整个级别的大小超过配置的目标大小时，就会触发整理。当这种情况发生时，它可能会触发一个L1至L2的整理。这样，一个L0至L1的整理可能会一直级联到最底层。整理结束后，RocksDB更新它的元数据并从磁盘中移除已经整理的文件。

注意：RocksDB提供了其它的整理策略，为空间、读和写扩展提供不同的权衡。
记住SST文件中的键是有序的吗？这个排序保证允许我们通过k路合并算法的帮助来增量合并多个SST文件。k路合并算法是一个通用版本的二路合并算法，它的工作方式类似于归并排序的归并阶段。

读取路径

有了在磁盘上持久化的不可变SST文件，相比写路径，读取路径就简单多了。一个键查找从LSM-tree的顶部开始遍历至底部。它从活动的MemTable开始，下降到L0，然后继续到更低的级别，直到它找到键或者检查完所有的SST文件。

下面是查找的步骤：

1. 搜索活动的MemTable。
2. 搜索不可变的MemTables。
3. 从最近刷新的开始，搜索L0上的所有SST文件。
4. 对于L1及以下，找到可能包含键的单一SST文件并搜索这个文件。
5. 搜索一个SST文件包括：
6. 可选的对Bloom filter进行探测。
7. 搜索索引以找到键可能所在的块。
8. 读取块并试图在那里找到键。

考虑这个LSM-tree

?根据键的不同，一个查找可能在任何步骤结束。例如，查找cat或chipmunk在搜索活动的MemTalbe后结束。搜索raccoon，只存在于1级，或manul，根本就不存在于LSM-tree，需要检查整个树。

合并

RocksDB提供了另一个特性，影响读写路径：合并操作。设想你在数据库中储存一个整数列表。偶尔你需要扩展这个列表。为了修改列表，你从数据库中读取现有的值，更新它在内存中，然后写回更新的值。这就叫做“读－修改－写”循环。

db = open_db(path)

// 读取
old_val = db.get(key) // RocksDB以字节数组形式存储键和值。我们需要反序列化值以将其转化为列表。
old_list = deserialize_list(old_val) // old_list: [1, 2, 3]

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

// 写入
db.put(key, new_val)

db.get(key) // 反序列化值: [1, 2, 3, 4, 5, 6]

这种方法是有效的，但有一些缺点：

• 它不是线程安全的 - 两个不同的线程可能会试图更新相同的键，从而覆盖对方的更新。
• 写放大 - 随着值变得越来越大，更新的代价也在增加。例如，向长度为100的列表追加一个整数，需要读取100个整数并写回101个整数。

除了Put和Delete写操作，RocksDB还支持第三种写操作，Merge，目的是解决这些问题。Merge操作需要提供一个Merge Operator - 一个用户定义的函数，用于把增量更新合并成一个单一的值：

func merge_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})
// 键的值是 [1, 2, 3]

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

db.get(key) // 反序列化值: [1, 2, 3, 4, 5, 6]

以上的merge操作符将增量更新合并成一次调用Merge操作时插入的单一的值。当Merge被调用时，RocksDB只插入增量更新到MemTable和WAL。稍后，在Flush和合并时，RocksDB调用merge操作符函数，尽可能地将更新合并成单一的大更新或单一的值。在对Get调用或迭代时，如果还有任何尚未压缩的更新，同样的函数会被调用以返回单一的合并值给调用者。

Merge非常适合需要频繁对现有值进行小更新的写重型流应用。所以，哪里有陷阱呢？读取变得更加昂贵 - 读的工作并未被保存。反复的查询获取同样的键不得不反复进行相同的工作，直到触发Flush和合并。就像RocksDB中的几乎所有其它一样，这种行为可以通过限制MemTable中的合并操作数或减少L0中的SST文件数量进行调优。

面临的挑战

如果性能对你的应用程序至关重要，那么使用RocksDB最具挑战性的方面就是根据特定的工作负载适当地配置它。RocksDB提供了数以百计的配置选项，调整它们经常需要理解数据库的内部运行和深入研究RocksDB的源代码：

"不幸的是，为RocksDB进行最优配置并不是那么简单。即使作为RocksDB的开发者，我们也没有完全理解每一项配置更改的影响。如果你想为你的工作负载完全优化RocksDB，我们建议进行实验和基准测试，同时关注这三个扩展因子。"

—官方RocksDB调优指南

最后的想法

从头开始编写一个生产级别的键值储存库是很难的：

• 硬件和操作系统会在任何时候背离你，丢弃或损坏数据。
• 性能优化需要大量的时间投资。

RocksDB解决了这个问题，让你可以专注于业务逻辑，这使得RocksDB成为数据库的一个优秀构建块。

今天分享RocksDB的有些过于专业，可能受众面不高，权当一个科普文吧，喜欢我文章的朋友可以点个关注，或者进入我的技术专栏了解更多干货。