RocksDB 是很多分布式数据库的底层存储,如 TiKV、CRDB、NebulaGraph 等等。在 DataDog 工作的 Artem Krylysov 写了一篇文章来对 RocksDB 做了一个科普,通俗易懂,在这里翻译下分享给大家。
导语
近几年,RocksDB 的采用率急速上升,俨然成为内嵌型键值存储(以下简称 kv 存储)的不二之选。
目前,RocksDB 在 Meta、Microsoft、Netflix 和 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 的形式嵌入到使用其他语言编写的应用中,例如 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 看看:
1 | db.put("chipmunk", "1") |
如上图所示,MemTable 中的键值对是按 key 有序排列的。尽管 chipmunk
是最先插入的,但由于 MemTable 是按 key 有序的,因此 chipmunk
排在 cat
之后。这种排序对于范围扫描是必须的,此外,稍后我会详细介绍,它也会让某些操作更加高效。
预写日志
无论是在进程意外崩溃退出还是计划内重启时,其内存中的数据都会丢失。为了防止数据丢失,保证数据的持久化,除了 MemTable 之外,RocksDB 会将所有更新写入到磁盘上的预写日志(WAL,Write-ahead log)中。这样,在重启后,数据库可以回放日志,进而恢复 MemTable 的原始状态。
WAL 是一个只允许追加的文件,包含一组更改记录序列。每个记录包含键值对、记录类型(Put / Merge / Delete)和校验和(checksum)。与 MemTable 不同,在 WAL 中,记录不按 key 有序,而是按照请求到来的顺序被追加到 WAL 中。
Flush
RocksDB 使用一个专门的后台线程定期地把不可变的 MemTable 从内存持久化到磁盘。一旦刷盘(flush)完成,不可变的 MemTable 和相应的 WAL 就会被丢弃。RocksDB 开始写入新的 WAL、MemTable。每次刷盘都会在 L0 层上产生一个新的 SST 文件。该文件一旦写入磁盘后,就不再会修改。
RocksDB 的 MemTable 的默认基于跳表实现。该数据结构是一个具有额外采样层的链表,从而允许快速、有序地查询和插入数据。有序性使得 MemTable 刷盘时更高效,因为可以直接按顺序迭代键值对顺序写入磁盘。将随机写变为顺序写是 LSM-Tree 的核心设计之一。
注: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。
例如,我们在查找 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:
1 | db.delete("chipmunk") |
随着我们的不断写入,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:
根据待查找的 key 的具体情况,查找过程可能在上面任意步骤提前终止。例如,在搜索 MemTable 后,key “cat” 或 “chipmunk” 的查找工作会立即结束。查找 “raccoon” 则需要搜索 L1 为止,而查找根本不存在的 “manul” 则需要搜索整个树。
Merge
RocksDB 还提供了一个同时涉及读路径和写路径的功能:合并(merge)操作。假设,你在数据库中存了一个整数列表,偶尔需要扩展该列表。为了修改列表,你需要从数据库中读取其现有值,在内存中更新该列表,最后把更新后的值写回数据库。
上面整个操作序列被称为 “Read-Modify-Write” 循环:
1 | db = open_db(path) |
上面这种方式能达到目的,但存在一些缺陷:
- 非线程安全——两个尝试更新相同的 key 的不同线程,交错执行,会出现更新丢失。
- 存在写放大——随着值变得越来越大,更新成本也会增加。例如,在含有 100 个数的列表中追加一个整数需要读取 100 个整数并将 101 个整数写回。
除了 Put
和 Delete
写操作之外,RocksDB 还支持第三种写操作 Merge
。Merge
操作需要提供 **Merge Operator**
——一个用户定义函数,负责将增量更新组合成单个值:
1 | funcmerge_operator(existing_val, updates) { |
上面的 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系列
- 每天学点数据库系列
- 系统好文推荐系列
- 读书笔记系列
- 数据密集型论文导读系列
会保证每周不低于两篇更新,订阅方式见专栏介绍,欢迎喜欢我文章的朋友们的订阅支持,激励我产出更多优质文章。