乐趣区

关于后端:RocksDB深度解析

jiezi

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 多平台公布

退出移动版