RocksDB 运行原理

RocksDB 是很多分布式数据库的底层存储,如 TiKV、CRDB、NebulaGraph 等等。在 DataDog 工作的 Artem Krylysov 写了一篇文章来对 RocksDB 做了一个科普,通俗易懂,在这里翻译下分享给大家。

导语

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

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

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

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

作者:木鸟杂记 https://www.qtmuniao.com/2023/06/05/how-rocksdb-works 转载请注明出处

RocksDB 是什么

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

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

RocksDB 使用 C++ 编写而成,因此除了支持 C 和 C++ 之外,还能通过 С binding 的形式嵌入到使用其他语言编写的应用中,例如 RustGo 或 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 层及以下层级则存储更老的数据。通常某层的下个层级在数据量上会比该层大一个数量级,当某层数据量变得过大时,会合并到下一层。

blog_how-rocksdb-works_rocksdb-lsm.png

注:虽然本文主要讨论 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 看看:

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

how-rocksdb-works-memtable.png

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

预写日志

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

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

how-rocksdb-works-wal.png

Flush

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

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

how-rocksdb-works-flush.png

注: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。

how-rocksdb-works-sstable.png

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

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

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

Compaction

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

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

1
2
3
4
5
6
7
8
9
10
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")

blog_how-rocksdb-works_rocksdb-compaction1.png

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

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

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

blog_how-rocksdb-works_rocksdb-compaction2.png

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

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

blog_how-rocksdb-works_rocksdb-compaction3.png

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

blog_how-rocksdb-works_rocksdb-compaction4.png

当 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 文件为止。

以下是查找步骤:

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

搜索 SST 文件涉及:

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

这就是全部所需步骤了!看看这个 LSM-Tree:

blog_how-rocksdb-works_rocksdb-lookup.png

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

Merge

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 还支持第三种写操作 MergeMerge 操作需要提供 **Merge Operator**——一个用户定义函数,负责将增量更新组合成单个值:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 成为构建数据库的优秀模块。

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

  • 图数据库101系列
  • 每天学点数据库系列
  • 系统好文推荐系列
  • 读书笔记系列
  • 数据密集型论文导读系列

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


我是青藤木鸟,一个喜欢摄影、专注大规模数据系统的程序员,欢迎关注我的公众号:“木鸟杂记”,有更多的分布式系统、存储和数据库相关的文章,欢迎关注。 关注公众号后,回复“资料”可以获取我总结一份分布式数据库学习资料。 回复“优惠券”可以获取我的大规模数据系统付费专栏《系统日知录》的八折优惠券。

我们还有相关的分布式系统和数据库的群,可以添加我的微信号:qtmuniao,我拉你入群。加我时记得备注:“分布式系统群”。 另外,如果你不想加群,还有一个分布式系统和数据库的论坛(点这里),欢迎来玩耍。

wx-distributed-system-s.jpg