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架构中的作用。

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

• Bloom 过滤器
• 基于块的存储格式
• 压缩
• 多版本MemTable结构

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

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

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

日志结构合并树(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")

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

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

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

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

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

1. MemTable刷新

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

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

1. 排序字符串表(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中。

1. 校验和

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

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

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

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

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

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

1. 合并和压缩操作

压缩是合并多个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 triggers
db.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)

// 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]

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

为了解决这些问题，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"，并设个星标吧，如果能一键三连(转发、点赞、在看)，则能给我带来更多的支持和动力，激励我持续写下去，和大家共同成长进步！

本文由mdnice多平台发布