RocksDB 深度解析

RocksDB 是被广泛采用的内存嵌入式键值存储引擎，本文介绍了 RocksDB 的架构、技术原理、性能优化，帮助读者深入了解 RocksDB，从而更好的使用这项技术。原文: RocksDB — A Deep Dive into the Internals of an Embedded Key-Value Storage Engine

目标读者： 有兴趣深入了解亚马逊 DynamoDB、Cassandra 等 NoSQL 数据库以及 LevelDB 和 RocksDB 等嵌入式键值存储的内部原理，并熟悉数据库管理系统(DBMS)的基本组件(尤其是存储引擎)的读者。

导言

RocksDB 是领先的嵌入式键值存储引擎，已在各行各业得到广泛应用。Meta、微软、Netflix 和 Uber 等知名公司都已将 RocksDB 集成到生产环境。这些公司高度依赖 RocksDB 来管理和存储大规模数据，为消息传送、用户活动跟踪和内部系统等关键应用提供动力。

Meta 广泛使用 RocksDB 来处理海量数据的管理和存储，支持消息传递、用户活动跟踪和内部系统等基本功能。此外，LinkedIn 利用 RocksDB 高效处理其消息平台中的高写入和高读取工作负载。通过 RocksDB，LinkedIn 可确保为用户提供流畅可靠的性能。

Airbnb 依赖 RocksDB 来管理用户数据和会话存储，优化整体性能，提升用户体验。通过使用 RocksDB，Airbnb 提高了数据管理和会话处理能力，从而在其平台上实现了更加完美的用户体验。

Netflix 依靠 RocksDB 进行会话管理和元数据存储，并获益于其性能和可靠性。这使 Netflix 能够向数百万用户提供不间断的流媒体服务，确保流畅可靠的娱乐体验。

Uber 依靠 RocksDB 保证快速可靠的访问关键数据，实现实时决策，促进顺利运营。通过利用 RocksDB 的功能，Uber 增强了高效处理和检索重要信息的能力。

这些知名企业对 RocksDB 的采用进一步巩固了 RocksDB 作为强大、多功能存储引擎的声誉。RocksDB 久经考验的性能和可靠性使其成为处理大规模数据和高要求工作负载的首选。

RocksDB 是什么

RocksDB 是一种嵌入式数据库，2012 年基于谷歌的 LevelDB 分叉而来，最初由 Dhruba Borthakur 在 Facebook 创建，目的是提高服务器工作负载性能。目前，RocksDB 由 Meta 开发和维护。

RocksDB 以 C++语言编写，支持通过С绑定嵌入到以 C、C++、Rust、Go 和 Java 等多种语言编写的应用程序中。这种灵活性使得开发人员可以将 RocksDB 集成到自己的应用程序，而无需考虑使用的编程语言。

数据模型

• 基于键值对存储数据，任意字节数组可作为键，并可存储相关值。字节数组可以是字符串、整数、序列化对象或自定义数据结构。任何类型的数据都可以作为值存储。

• 键和值都是任意长度的字节数组，没有任何预定义数据类型。

主要操作

• Put(Key, Value) - 插入新的键值对或更新现有键值。

• Merge(Key, Value) - 将新值与给定键的现有值合并。

• Delete(Key) - 从 RocksDB 中删除与指定键值相关的键值对。

检索值

• Get(Key) - 获取与特定键相关的值。

范围扫描和迭代器

• Seek(key_prefix) - 匹配指定键的前缀或大于键的前缀。

• Value() - 检索与当前键相关的值。

• Next() - 将迭代器移动到指定范围内的下一个键值对。

高级操作

• filter.set_expiration_time(1)，然后 compact(filter) - 当运行压缩过滤器时，任何超过 1 秒的数据都将从数据库中删除。

• snapshot.take(database) - 创建特定时间点的数据库副本，可用于备份数据或测试对数据库的更改，而不会影响实时数据。

开发人员可以利用 RocksDB 的键值数据模型来构建更复杂的系统，如反转索引、文档数据库、SQL 数据库、缓存系统和消息代理，这些系统需要在 RocksDB 的基础上实现更多层次的逻辑和功能。

• 反向索引 - 根据术语或关键词检索文档。

• 文档数据库 - 将文档存储为值，并使用唯一标识符或其他特定于文档的键来有效检索和处理数据。

• SQL 数据库 - 实现 SQL 查询解析、执行和索引。

• 缓存系统 - 通过在内存中存储经常访问的数据，提高应用程序性能。

• 消息代理 - 促进分布式系统之间的通信和数据交换。

例如，要用 RocksDB 建立反向索引系统，开发人员需要:

• 设计存储反向索引的数据模式

• 执行标记化和索引逻辑

• 开发查询处理机制

例如，要创建文档数据库，开发人员需要:

• 定义文档数据模式

• 处理索引和查询操作

• 管理文件级操作

嵌入式数据库是集成到应用程序中的数据库，没有独立程序，有一些主要特点。

• 与应用程序集成 - 避免跨进程通信开销

• 共享资源 - 避免跨进程通信开销

• 无内置服务 - 无法通过网络远程访问

• 缺乏分布式功能 - 没有容错、冗余或分片机制

• 轻便高效

RocksDB 架构原则

RocksDB 是 Meta 开发的一种广泛使用的嵌入式数据库库，实现了日志结构合并树(LSM-tree，log-structured merge-tree)数据结构。RocksDB 架构的原理可以通过以下方面来理解：

1. 存储引擎和架构 - 不同于分布式事务键值数据库(TiKV)，RocksDB 使用 LSM 树作为主要数据结构，将数据组织成多个层次，包括

• MemTable

• 不可变 MemTable

• SSTables(分类静态表文件，sorted static table)

• 预写式日志(WAL，write-ahead log)文件

下面会深入了解每个组件及其在 RocksDB 架构中的作用。

2. 调整和优化 - 提供控制读取放大、写入放大和空间放大选项，支持各种功能和优化，包括

• Bloom 过滤器

• 基于块的存储格式

• 压缩

• 多版本 MemTable 结构

下面会详细了解这些优化功能。

3. 可插拔架构 - 用户更换特定组件时不会影响整个系统架构。

后面会详细介绍可插拔架构和可更换组件。

日志结构合并树(LSM-Tree)

RocksDB 采用日志结构合并树(LSM tree)结构来有效组织和存储数据。LSM 树由多个层次组成，每个层次都有特定用途。

LSM 树的顶层是 MemTable，称为第 0 层(L0)。MemTable 位于内存中，保存最近插入的数据。此外，还可以选择将数据记录到磁盘上的预写式日志(WAL)文件中，以持久化数据。

当数据在 MemTable(L0)中积累时，会定期刷新到磁盘。这一过程会将数据转换为不可变 MemTable，然后进行排序并转换为排序字符串表(SSTables)。SSTable 存储在从第 1 级(L1)开始的后续级中，并驻留在磁盘上。

LSM 树中的每一级通常都比前一级大，这种设计可实现高效的数据压缩和合并。当某一级数据过大时，就会触发压缩过程，将其与下一级数据合并。在压缩过程中，多余和过时的条目会被删除，压缩后的 SSTable 会存储在下一级中。

值得注意的是，虽然本文主要关注 RocksDB，但这里讨论的与日志结构合并树(LSM-Tree)相关的原理和概念也适用于许多其他使用这种技术作为底层结构的数据库，包括 Bigtable、HBase、Cassandra、ScyllaDB、LevelDB 以及 MongoDB WiredTiger。

算法和优化

在 RocksDB 架构中，采用了各种算法和优化手段来确保高效的写入操作、数据持久化和压缩过程。下面介绍写入路径中涉及的关键组件。

写入路径

1. MemTable

MemTable 充当内存缓冲区和缓存，在键值对写入磁盘前暂时存储，可以处理插入、更新和删除操作。插入或更新键值对时，会将其写入 MemTable。删除操作使用墓碑记录将键标记为已删除。

MemTable 的大小可配置，通常设置为 64MB。一旦达到这个限制，MemTable 就会被冻结，变成只读，并创建新的 MemTable，随后的写入操作将指向新的 MemTable。同时对冻结的 MemTable 进行处理，将其数据持久化到磁盘上。

其中涉及两个关键部分：

• MemTable

• 预写式日志(WAL)文件

当 MemTable 达到其容量时，其内容会被刷新到 LSM 树第 0 层(L0)的 SSTable 文件中，并存储在持久化存储中，相应的 WAL 文件会被删除。在刷新过程中，会删除 MemTable 中重复和被覆盖的键。

RocksDB 的整个数据库都存储在 SSTable 文件中。在断电或系统崩溃的情况下，WAL 文件可以用来完全恢复 MemTable 中的数据，确保数据库可以恢复到原始状态。

我们先在数据库中添加几个键：

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

如你所见，键值对是按键排序的。这种排序方式可以实现高效的范围扫描，即可以更高效的访问特定键值范围内的数据。

2. 预写式日志(WAL)文件

RocksDB 采用了预写式日志(WAL)技术来确保数据持久化，并将意外进程崩溃或重启时数据丢失的风险降到最低。WAL 可作为对数据库所做所有修改的可靠、持久的日志。

WAL 文件的主要目的是通过基于磁盘的日志文件捕获所有更新来防止数据丢失。在将任何更改应用到实际数据库之前，首先会记录在 WAL 文件中。WAL 文件是一种只支持添加数据的结构，包含了修改的有序序列。WAL 中的每条记录都包括键值对、执行的操作类型(插入/合并/删除)和校验和。

WAL 文件中的记录并不像 MemTable 那样根据键来排列。相反，是按照接收请求的顺序附加到日志中的。这样可以确保修改被安全的记录下来，即使系统崩溃，也能在修改被刷新到磁盘或应用到 MemTable 之前恢复。

3. MemTable 刷新

当内存中的 MemTable 已满并被冻结时，RocksDB 会使用后台线程定期将内存中的 MemTable 刷新到磁盘上。在刷新过程中，不可变的 MemTable 及其对应的 WAL 的内容会被写入磁盘。一旦刷新完成，不可变的 MemTable 和 WAL 就会被丢弃，然后 RocksDB 开始写入新的 MemTable 和 WAL。每次刷新操作都会在 L0 层生成一个新的 SST(sorted string table)文件。这些 SST 文件是不可变的，也就是说，一旦写入磁盘，就永远不会被修改。这种设计确保了数据变化的持久性，即使系统崩溃或重启也能恢复。

备注: RocksDB 默认的 MemTable 实现是基于跳表(skip lists)，这是一种高效的数据结构，可用于有序查询和插入。基于跳表的 MemTable 可以更快刷新到磁盘，键值对可以按顺序写入，从而优化了从随机写入到按序写入的写入操作。

4. 排序字符串表(SST, Sorted String Table)

当 RocksDB 把数据从 MemTable 刷新到磁盘时，会把数据组织成 SST 文件，这是为了高效查询而设计的。SST 文件是基于块的文件，通常每个块的固定大小为 4KB，可以使用 Zlib、BZ2、Snappy、LZ4 或 ZSTD 等各种算法进行压缩。

SST 文件中的每个块都包含校验和，以确保数据的完整性，并检测任何潜在的损坏。每次从磁盘读取数据时，RocksDB 都会验证这些校验和，为存储数据提供额外的可靠性。SST 文件中的数据块结构分为若干部分，第一部分是数据部分。在数据部分，键值对按序顺序存储，这样就能对键进行高效的 Delta 编码。Delta 编码意味着不存储完整键值，而只存储相邻键值之间的差异，从而降低了总体存储需求。

虽然 SST 文件中的键值对是经过排序的，但直接在压缩块上执行二进制搜索可能并不高效。为了优化查找过程，RocksDB 在 SST 文件中加入了索引部分，紧接在数据部分之后。索引将每个数据块中的最后一个键映射到磁盘上的相应偏移量。索引中的键也是有序的，便于通过二进制搜索快速查找键。例如，在搜索关键字"lynx"时，由于"lynx"位于"chipmunk"之后而在"raccoon"之前，因此索引有助于确定它可能位于数据块 2 中。

5. 校验和

这是一种确保数据完整性和检测数据损坏的机制。

RocksDB 利用预写式日志(WAL)来存储记录序列。WAL 中的每条记录都由"Type(类型)"字段和"Payload(有效载荷)"组成。类型字段用于处理大的键值对，而有效载荷则包含一个或多个键值对。

RocksDB 计算校验和时，会将类型和有效载荷字段合并在一起，并在整个有效载荷和其他相关字段上计算校验和。这种统一的表示方法可确保数据完整性，并检测数据损坏。

在早期版本中，RocksDB 使用 CRC32 算法作为默认校验和算法。CRC32 在检测常见错误方面很有效，但可能不是最佳选择。

从 v7.8 版开始，RocksDB 改用 kXXH3 算法作为默认校验和算法。kXXH3 基于 XXH3 哈希算法，与 CRC32 相比，速度和效率都有所提高。

当数据被写入 RocksDB 时，校验和会和数据一起被保存在 WAL 文件中。在读取操作过程中，RocksDB 会使用与初始写入时相同的算法来重新计算检索数据的校验和。重新计算的校验和会与存储在 WAL 文件中的校验和进行比较，以验证数据的完整性。校验和不匹配表示存在潜在的数据损坏，可以采取适当措施来解决。

6. 合并和压缩操作

压缩是合并多个 SSTable 并优化其存储的过程，包括将多个 SSTable 的数据合并和重写到数量较少的新 SSTable 中，消除冗余数据，提高读写性能。

因此，空间放大、读取放大和写入放大等术语通常用来描述其性能特征的不同方面。

空间放大(Space amplification) 指的是用于存储数据的实际磁盘空间与逻辑数据大小之间的比率。例如，如果一个数据库需要 2MB 的磁盘空间来存储逻辑键值对，而逻辑键值对只占用 1MB，那么空间放大率就是 2。这表明存储利用效率低下，占用的磁盘空间大于逻辑数据大小。空间放大率越高，表明存储利用效率越低，即数据库占用的磁盘空间大于逻辑数据大小的比率越大。导致空间放大的因素主要是已删除或更新的键仍占用磁盘空间。RocksDB 中的压缩功能可以通过合并 SST 文件和丢弃不必要的键来减少空间放大。

读取放大(Read amplification) 衡量的是逻辑读取操作所需的 I/O 操作次数。在一次读取操作中，RocksDB 需要搜索多个 SST 文件来查找特定的键值，访问 SST 文件数量会导致读取放大，读取放大的增加会影响系统的读取性能。

写入放大(Write amplification) 是指写入存储的字节数与写入数据库的字节数之间的比率，量化了存储系统为适应用户写操作而产生的额外 I/O 操作。写入放大率反映了数据写入底层存储的效率，写入放大率过高会增加存储设备的磨损，影响系统性能。

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

RocksDB 利用压缩技术来应对数据存储和检索方面的挑战。当数据被持续写入时，MemTable 最终会被刷新，从而在 LSM 树的第 0 层(L0)创建 SST 文件。然而，这可能会导致删除或更新的键占用空间等问题。压缩可通过合并不同层级的 SST 文件和回收被不必要的键占用的磁盘空间来解决这些问题。

其中一个挑战是 L0 上 SST 文件中已删除或更新的键所占用的空间。例如，同一键存在多个副本，占用磁盘空间。压缩可以消除不必要的键和副本，优化存储利用率。

另一个挑战是随着 L0 上 SST 文件数量的增加对读取性能的影响。每次键查找时，都需要检查 L0 上的所有 SST 文件，从而导致读取放大和读取操作变慢。压缩可通过合并 SST 文件减少读取放大，从而加快键查找操作。

压缩过程在后台通过专用线程池运行，可以并发处理用户读写请求，确保数据库在压缩过程中的响应速度和可操作性。

RocksDB 的默认压缩策略是"分级压缩"，将 SST 文件组织成不同级别，并对每个级别的压缩过程进行独特的管理。L0 级别允许键值范围重叠，而较低的级别(L1 及以上)则按顺序整理 SST 文件，不允许键值范围重叠。每个级别内的 SST 文件都按键值顺序排序。

在压缩过程中，某个层级的 SST 文件会与下一层级的 SST 文件有选择的合并，同时考虑重叠的键范围。例如，当压缩从 L0 开始到 L1 结束，而 L0 上的 SST 文件覆盖了整个键范围时，就会对 L0 和 L1 上的所有文件进行压缩。

在 L1 层和 L2 层的压缩过程中，L1 层的输入文件只与 L2 层的两个 SST 文件重叠，意味着在这种情况下只需要压缩一部分文件。

根据特定条件和配置会触发压缩。例如当 L0 上的 SST 文件数量达到指定阈值(默认情况下通常为 4 个)，或某一级别的大小超过配置的目标大小时，就会触发压缩。可能会对较低级别的文件进行级联压缩，以保持数据的最佳组织和存储。

压缩过程完成后，RocksDB 会更新元数据，并从磁盘中删除压缩后的文件，从而释放磁盘空间。

RocksDB 提供不同的压缩策略，允许在空间利用率、读取放大和写入放大之间进行权衡。这些策略可以根据特定工作负载和需求，灵活优化数据库性能。

RocksDB 的 SST 文件是按词序排序的，可以使用 k-way 合并算法对多个文件进行增量合并。该算法与合并排序的合并阶段类似，有助于高效合并 SST 文件。

读取路径

在 LSM-Tree 结构中，读取路径比写入路径更简单。

1. 键查询过程

在磁盘上持久保存不可变 SST 文件的 LSM 树中查找键的过程，需要从上到下遍历树。

• 搜索从检查活跃 MemTable 开始，MemTable 位于内存中，保存最近插入的数据。

• 如果在 MemTable 中没有找到键，则继续搜索 L0 层。在这一层，最近刷新的 MemTable 会被转换为不可变 SST 文件。

• 如果在 L0 中没有找到键，则继续搜索 LSM 树的较低层次，查找可能包含键的单个 SST 文件，然后在该文件中进行搜索。

搜索 SST 文件的过程包括:

• 探测布隆过滤器(可选) - 确定特定 SST 文件是否可能包含键，从而减少磁盘 I/O。如果布隆过滤器显示可能匹配，则搜索进入下一步。

• 查询索引 - 搜索会查询索引，以找到 SST 文件中可能包含键的区块位置。

• 读取区块文件 - 读取包含潜在键的区块文件，并尝试在该区块中查找键。

搜索以顺序的方式进行，通过向下读取树状结构并检查相应的 SST 文件来查找键，直到找到键或检查完所有 SST 文件为止。

查找操作可以在任何阶段提前结束，取决于正在查找的键。例如，如果我们正在查找键"cat"或"chipmunk"，查找过程会在检查活跃 MemTable 后结束。但是，如果我们要查找的键是"raccoon"，而这个键只存在于数据结构的第 1 层，在 LSM 树中根本不存在，那么查找必须在整个树中持续进行，直到找到或确定不存在这个键为止。总之，查找操作的持续时间取决于查找的特定键及其在数据结构中的位置。

合并

RocksDB 的合并(Merge)操作简化了"读取-修改-写入"循环，允许直接对与键相关的值进行修改。这种操作无需读取、修改和写回整个值，从而提高了效率，减少了开销。可以定义自定义合并函数，以指定如何应用修改，并根据定义的逻辑将现有值和修改结合起来。

• 读取 - 从数据库中读取现有值

• 修改 - 在内存中对其进行必要的修改

• 写入 - 将更新值写入数据库

db = open_db(path)
// Readold_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]
// Modifynew_list = old_list.extend([4, 5, 6]) // new_list: [1, 2, 3, 4, 5, 6]new_val = serialize_list(new_list)
// Writedb.put(key, new_val)
db.get(key) // deserialized value: [1, 2, 3, 4, 5, 6]

不过，这种方法也存在缺陷。首先，不是线程安全的，这意味着不同线程对同一键的并发更新可能会导致数据覆盖或不一致。此外，由于更新操作的成本会随着更新值的大小而增加，因此会出现写放大现象。

为了解决这些问题，RocksDB 引入了合并操作和合并操作符。合并操作将增量更新合并为一个值，从而减少并发更新时数据被覆盖的几率。合并操作符(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})// 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]

合并操作的一个问题是读取成本增加。读取过程中执行的工作不会被保存，意味着对相同键的重复查询将重复相同的工作，直到触发刷新和压缩过程。为了缓解这个问题，RocksDB 提供了一些调整行为的选项，比如限制 MemTable 中合并操作数的数量，或者减少 L0 中 SST 文件的数量。

挑战

配置 RocksDB 以获得最佳性能是一项极具挑战性的任务，尤其是当性能对应用程序至关重要时。RocksDB 提供了广泛的配置选项，但调整这些选项需要深入了解数据库内部结构，并深入研究源代码。

通过监控三个放大因子(写入放大、空间放大和读取放大)，可以深入了解不同配置对性能的影响。

RocksDB Advisor 命令行工具可以帮助用户找到最佳配置参数，可以根据具体需求和工作负载特征，帮助用户确定最合适的配置设置。利用这一工具，用户可以减轻在配置 RocksDB 获得最佳性能时的复杂性。

此外，RocksDB 的性能还受到多种因素的影响，包括硬件性能、操作系统性能、数据读写模式和并发过程。对 CPU 使用情况和系统整体性能进行监控，可以帮助我们深入了解潜在的性能问题。

参考资料

RocksDB Basic

RocksDB Overview

How Intel Optimized RocksDB Code for Persistent Memory with PMDK

RocksDB: Evolution of Development Priorities in a Key-value Store Serving Large-scale Applications

Under the Hood: Building and Open-sourcing RocksDB

What is an LSM Tree?

Per Key-Value Checksum

RocksDB Tuning Guide

How RocksDB works

The log-structured merge-tree (LSM-tree)

你好，我是俞凡，在 Motorola 做过研发，现在在 Mavenir 做技术工作，对通信、网络、后端架构、云原生、DevOps、CICD、区块链、AI 等技术始终保持着浓厚的兴趣，平时喜欢阅读、思考，相信持续学习、终身成长，欢迎一起交流学习。为了方便大家以后能第一时间看到文章，请朋友们关注公众号"DeepNoMind"，并设个星标吧，如果能一键三连(转发、点赞、在看)，则能给我带来更多的支持和动力，激励我持续写下去，和大家共同成长进步！