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 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"，并设个星标吧，如果能一键三连(转发、点赞、在看)，则能给我带来更多的反对和能源，激励我继续写下去，和大家独特成长提高！

本文由mdnice多平台公布