RocksDB系列一：基本概念

0 引言

RocksDB 是 Facebook 基于 Google 的 LevelDB 代码库于 2012 年创建的高性能持久化键值存储引擎。它针对 SSD 的特定特性进行了优化，目标是大规模（分布式）应用，并被设计为嵌入在更高层次应用中的库组件。RocksDB应用范围很广，比如：

• 流处理：RocksDB 用于在 Apache Flink、Kafka Stream、Samza 和 Facebook 的 Stylus 中存储暂存数据。
• 日志/队列服务：RocksDB 被 Facebook 的 LogDevice（使用 SSD 和 HDD）、Uber 的 Cherami 和 Iron.io 使用。
• 索引服务：RocksDB 被 Facebook 的 Dragon 和 Rockset 使用。
• SSD 上的缓存：像 Netflix 的 EVCache 、360 的 Pika 和 Redis 这样的内存缓存服务，使用 RocksDB 将从 DRAM 的数据存储在 SSD 上
• 数据库：比如MySQL、TiDB

本文首先介绍一些基本概念。

一、重点概念

LSM tree

LSM-Tree(Log-Structured-Merge-Tree)个人认为更是一种设计思想，而非一个具体的数据结构，如下图所示：

核心点：

1. 不支持磁盘原地修改，避免磁道随机访问, 提高写入能力
2. 写入不可变文件，随着时间再做merge处理

工作原理如下：

1. 数据写入

   • 数据首先写入到内存中的 MemTable（内存表），通常使用跳表、平衡树或哈希表等数据结构实现。
   • MemTable 支持快速的写入操作，以处理高吞吐量的写入请求。

2. 数据刷新

   • 当 MemTable 达到一定大小或条件时，它会被写入到磁盘，成为一个不可变的 SSTable（Sorted String Table）文件。
   • MemTable 刷新后会被清空，并准备接收新的写入操作。

3. 合并compation

   • 磁盘上会有多个层次的 SSTable 文件。为了保持查询性能和存储效率，LSM-Tree 定期进行合并操作。
   • 合并操作将多个 SSTable 文件的数据合并到一个新的、更大的 SSTable 文件中，通常分为多个层次，每一层的大小递增。

4. 读取操作

   • 读取数据时，首先在 MemTable 中查找，如果未找到，再在最近的 SSTable 文件中查找。
   • 如果需要，还会查找更早的 SSTable 文件。通常会使用布隆过滤器（Bloom Filter）来快速判断某个键是否在特定的 SSTable 文件中。

5. 删除和更新

   • 删除操作通过插入删除标记（如删除标记的条目）来标记数据已被删除。
   • 更新操作通过插入新版本的数据来覆盖旧的数据。最终，这些删除和更新会在合并过程中得到处理。

memtable

MemTable 是一种在内存中保存数据的数据结构，用于提高写入性能和减少对磁盘的频繁访问。MemTable 在数据达到一定量时，会将其内容 flush（刷新）到磁盘上的 SST (Sorted String Table) 文件中。MemTable 支持读写操作，并且可以使用不同的数据结构实现，具体包括：

• 跳表（Skip List）：支持并发操作，适合高并发场景。它通过多层索引实现高效的插入、删除和查找操作。
• 平衡树（如 AVL 树或红黑树）：支持高效的查找、插入和删除操作，但并不一定适合高并发场景。
• 数组（Vector）：提供简单的顺序访问，但对于查找和插入的效率可能较低。
• 哈希表（Hash Table）：提供高效的查找操作，但可能不支持范围查询。
  选择不同的数据结构作为 MemTable 实现，取决于系统的性能需求和使用场景。

Flush

Flush 时机：

以RocksDB为例：

• 内存表大小超过阈值：

  • 当内存表的大小超过了 write_buffer_size 时，会触发 flush 操作。

• 全部列族的内存表总大小超过阈值：

  • 当所有列族的内存表总大小超过了 db_write_buffer_size，或者 write_buffer_manager 发出了 flush 指令时，会触发 flush 操作。在这种情况下，会选择最大的memtable进行 flush 操作。

• WAL 文件总大小超过阈值：

  • 当全部的 Write-Ahead Logging（WAL）文件的大小超过了 max_total_wal_size 时，会触发 flush 操作。在这种场景下，内存中数据最老的memtable会被选择执行 flush 操作，并且对应的 WAL 文件会被回收。

Write-Ahead Log (WAL)

概述：
Write-Ahead Log（WAL）是一种类似于数据库日志的机制，用于故障和异常恢复。在 RocksDB 中，每次数据写入都会写入到两个位置：

1. 内存表（MemTable）：

   • 内存表是一个内存中的数据结构，最终会被 flush 到磁盘上的 SST 文件中。

2. 磁盘中的 WAL：

   • 每次更新操作同时写入 WAL 文件。WAL 记录了对数据库的所有变更操作，用于在发生故障时恢复内存表中的数据。

一致性保障：

• 默认情况下，RocksDB 通过在每次用户写操作时调用 flush 操作来保证 WAL 的一致性，确保数据的持久性和可靠性。
• RocksDB 支持配置以关闭 WAL 写入，但这会影响数据的持久性和恢复能力。

结构：

• 存储顺序：WAL 记录按照写入的顺序存储变长的键值对（K-V）。
• 分组存储：为了提高读取效率，WAL 将变长的 K-V 对按照固定长度进行分组存储。这种方式可能导致一个 K-V 对跨多个分组存储，但这样做是为了便于数据的顺序读取和恢复操作。

WAL文件由一堆变长的record组成，而每个record是由kBlockSize(32k)来分组，比如某一个record大于kBlockSize的话，他就会被切分为多个record：

record的格式如下:

SST 文件存储结构

多块存储结构

• 数据块：

  • SST 文件按照多个数据块（blocks）进行存储。每个数据块中的键值对（K-V）是有序的。
  • 多个数据块之间也是有序的，确保了文件的整体有序性。

• 元数据：

  • 文件中包含与数据相关的元数据，如数据压缩字典、过滤器（例如布隆过滤器）等。
  • 这些元数据用于提高存储效率和查询性能。

• 索引创建：

  • 根据数据块中键值对的范围创建索引，以提升查询性能。
  • 索引可能会进行分片，进一步提高检索效率和减少查询延迟。

每个 K-V 存储结构

• 索引结构：

  • 这种结构的索引较为特殊，由两个主要部分组成：哈希结构和二进制查找缓存。

• 哈希结构：

  • 根据键的前缀进行哈希。如果哈希桶对应的 K-V 记录很少，则直接指向第一个键（多个键属于该桶）的记录位置。
  • 如果哈希桶中的 K-V 记录多于 16 条，或者包含多个前缀的记录，则会使用二进制查找缓存。

• 二进制查找缓存：

  • 对于包含多个记录的桶，首先进行二分查找以定位目标记录。
  • 二分查找后，会指向第一个键的记录位置，以加速查询过程。

这种存储结构通过不同的存储方式和索引机制来优化 SST 文件的读取性能和数据访问效率。

Block Cache

• 存储内容：

  • Block Cache 存储的是非压缩的数据块内容。用户可以选择另外设置一个 Block Cache 来存储压缩数据块。
  • 读取数据时，首先从非压缩数据块缓存中读取数据，如果未命中，则从压缩数据块缓存中读取。

• Direct-IO：

  • 在 RocksDB 中，当启用 Direct-IO 时，数据的读写操作可以绕过操作系统的页缓存，直接与磁盘进行交互。Block Cache可以作为系统页缓存的替代，减少内存使用并提高 I/O 性能。

• 实现方式：

  • RocksDB 中有两种主要的缓存实现方式：

    • LRUCache：基于最近最少使用（LRU）算法，管理缓存中的数据块。
    • CLockCache：基于锁的缓存实现，提供高并发性能。

  • 这两种缓存实现都会被分片以降低锁的压力。

  • 用户设置的缓存容量会平均分配给每个分片。

  • 默认情况下，每个缓存会被分片为 64 块，每块的大小不小于 512KB 字节。

Bloom Filter

• 功能：

  • Bloom Filter 是一种空间效率高的概率数据结构，用于测试某个元素是否存在于集合中。
  • 在 RocksDB 中，Bloom Filter 用于加速 SST 文件的读取操作，通过减少不必要的磁盘访问来提高查询性能。

• 实现：

  • Bloom Filter 会在 SST 文件中维护一个布隆过滤器来快速判断某个键是否存在于特定的数据块中。
  • 如果 Bloom Filter 表示键不在数据块中，RocksDB 可以避免读取该数据块，从而减少 I/O 操作。
  • Bloom Filter存在误判率，判断键不在，那一定不在；判断键存在，也可能不在

通过使用 Block Cache 和 Bloom Filter，RocksDB 能够显著提升数据读取性能和减少磁盘 I/O，提高整体系统效率。

读放大/写放大/空间放大

LSM-Tree 将离散的随机写请求都转换成批量的顺序写请求（WAL + Compaction），以此提高写性能。也带来了较多问题，比如读放大、空间放大

1. 读放大

• 定义：

  • 在 LSM-Tree 中，读操作需要从最新的层次到最旧的层次逐层查找，直到找到所需的数据。这意味着读操作可能需要多次 I/O 操作。
  • 特别是在范围查询（range query）的情况下，这种影响会更加明显。

• 计算方式：

  • 读放大可以通过每次读请求所带来的实际读盘字节数除以实际的数据量来计算。公式为：

    读放大 = 实际读取字节数 / 实际读取数据量-字节
    

2. 写放大

• 定义：

  • 写放大指的是每次写入一个字节的数据，实际写入到磁盘的数据量比写入量多的倍数。

• 计算方式：

  • 写放大可以通过每写入 1 字节数据所带来的实际写入磁盘的字节数来计算。公式为：

    写放大 = 实际写入字节数 / 实际写入数据量-字节
    

    每写1byte数据带来n bytes的数据写盘，写放大为n

3. 空间放大

• 定义：

  • 由于 LSM-Tree 是 append-only 的（追加写入），数据更新不是 in-place 更新，这导致过期的数据不会立即被清理掉。
  • RocksDB 和 LevelDB 使用后台的 compaction 过程来减少读放大（减少 SST 文件数量）和空间放大（清理过期数据）。

• 计算方式：

  • 空间放大可以通过所占用的总空间大小除以实际存储的数据量来计算。公式为：

    空间放大 = 所占空间大小 / 实际数据量
    

  • 空间放大主要与未回收的过期数据量（旧版本数据/已删除条目）相关。

4. 临时空间

• 定义：

  • 在进行 compaction 任务时，需要一定的临时空间来处理数据，compaction 完成后，旧数据才可以被删除。
  • 临时空间的需求与 compaction 任务的拆分粒度相关。

• 说明：

  • compaction 过程会生成中间数据文件，并在完成后清理过期的数据。临时空间用于存储这些中间数据，以确保 compaction 操作的顺利进行。

Compaction 机制

在 LSM-Tree中，数据写入首先会放置在内存中的 MemTable。当 MemTable 达到一定阈值时，它会被 flush 到磁盘，形成一个新的 SST 文件。这种机制对于写入操作非常友好，因为写入只涉及内存操作，减少了对磁盘的写入次数。然而，这种机制在读取时可能会面临以下挑战：

• 读取开销：

  • 为了读取一个键的值，可能需要遍历多个 SST 文件，这会导致较高的读取开销，特别是在处理大量 SST 文件时。

• 多版本机制：

  • LSM-Tree 支持多版本机制，允许同一个键存在多个版本。这意味着一个键可能会有多个版本的数据留在 LSM-Tree 中，占用更多的存储空间。

为了解决这些问题，Compaction 过程被引入用于优化存储和提升读取性能。

Compaction 是一个后台任务，其目的是整理和优化存储中的数据，以提高读取性能和减少空间占用。因此Compaction 的作用：

• 提高读取性能：

  • 通过合并 SST 文件，减少需要遍历的文件数量，降低读取开销。

• 减少空间占用：

  • 通过清理过期的和冗余的数据，减少存储的空间使用。

• 优化写入性能：

  • 通过整理数据，减少写入操作对存储的影响，提高写入效率。

通过有效的 Compaction 策略，RocksDB 可以优化数据存储和访问性能，减少读取和写入开销，提升整体系统效率。常见的 Compaction 算法有以下几种：

1. Size-Tiered Compaction（大小分层）

原理

• 数据块被组织成大小相近的集合。当一个数据块集合达到一定的大小时，会触发 compaction，将这些数据块合并成一个更大的数据块。

• 数据组织：

  • MemTable 中的数据周期性地 flush 到 SSTable，形成有序的 runs。每一层包含多个相似大小的 SSTable（runs），最底层是最大的一层。

• Compaction 过程：

  • 在 Size-Tiered Compaction 中，当某一层的数据大小达到限制时，将整层的 SSTable 合并并 flush 到下一层，形成一个更大的 SSTable。这个过程会一直进行，直到某一层的 SSTable 数量未达到限制时停止。

优点

• 可以减少写放大，因为每次 compaction 操作只涉及到相近大小的数据块。 Size-Tiered Compaction 特别适合写密集型的工作负载。由于每次 compaction 操作处理的是相同大小的 SSTable，因此写放大较低。

缺点

• 读操作：在 Size-Tiered Compaction 中，读取操作可能需要合并多个层级的数据，尤其是在范围查询（range query）中，读放大较高。

  • 点读：假设忽略 cache 和 Bloom Filter 等上层优化，大部分的点读会落在最大的层级中。由于每一层的数据大小类似，读取操作的开销与数据量成正比。
  • 范围查询：范围查询需要合并所有层的数据，这意味着所有的 SSTable 都可能被读取。随着 runs 的数量增加，读放大也会增加，导致查询性能下降。

• 空间放大：由于每层的 SSTable 都需要合并，导致存储的空间使用可能增加，特别是在频繁更新或删除操作时。

  • 重复写入：如果重复写入相同的数据（例如更新或删除），相邻层级的大小比为 T。当每个层级的 run 数量达到 T 时，会触发整层的合并操作。空间放大近似于 O(T)，实际运行中还需要考虑临时空间的使用，这要求预留足够的临时空间以应对 compaction 过程中的数据处理需求。

通过 Size-Tiered Compaction，RocksDB 能够有效地处理写密集型工作负载，但需要注意读放大和空间放大的影响。合理的配置和优化可以帮助平衡性能和资源使用。

2. Level-Based Compaction（层级）

原理

• 数据被分成多个层级，每一层的数据块按照大小递增的方式存储。
• 当一个层级的数据块数量达到一定阈值时，触发 compaction 操作，将当前层级的数据块与下一层级的数据块合并，并生成新的 SST 文件。

优点

• 减少空间放大：

  • -可以有效减少读取放大，因为每个层级的数据块之间是有序的。在 Leveled Compaction 中，每一层的 SSTable 组成一个有序的 run，每层的数据块大小有限制，当层级的数据量达到上限时，会触发与下一层级的数据块合并（merge）。这种方式可以有效地将多个较小的 SSTable 合并为一个，从而减少存储空间的使用。

• 减少读放大：

  • 提供了较好的读取性能，尤其是在层级数量较少时。由于每层的 SSTable 都保持有序关系，且层级之间的数据范围不重叠，读取时可以更快地定位到数据，减少了需要遍历的 SSTable 数量，从而降低了读放大。

• 精细化任务拆分和控制：

  • 小的 SSTable 使得任务拆分更为精细化，并可以更好地控制 compaction 任务的大小，从而优化临时空间的使用。

缺点

可能导致较大的写放大，因为数据在每次 compaction 时都需要被写入多个层级。即可能从L0层一路写到最底层。

• Worst-Case 写放大：

  • 在设定相邻层级数据量比为 10 的情况下，假设 Level A 层的数据与 Level A+1 层的所有数据都有重叠。当 Level A 层进行合并操作时，涉及 Level A+1 层的全部数据。
  • 这种情况下，合并操作会将 Level A 层的数据与 Level A+1 层的数据合并，可能会导致原数据的 11 倍大小的数据量被写入磁盘。

• 计算方式：

  • 假设：每个层级的数据量比为 10。
  • Worst-Case 写放大：Level A 层的合并操作需要处理 Level A+1 层的全量数据，导致写入的数据量为原数据量的 11 倍。因此，写放大为 Tired Compaction 的 11 倍。

• 总结：

  • 尽管 Leveled Compaction 可以显著降低读放大和空间放大，但在最坏的情况下，写放大可能会增加，因为合并操作需要处理多个层级的数据。

通过使用 Leveled Compaction，RocksDB 能够有效地优化存储和读取性能，但也需要注意在某些情况下写放大的增加。合理配置 compaction 策略可以帮助平衡读写性能。

3. Universal Compaction（通用）

原理

• 结合了上述层级和大小分层的特点，灵活地管理数据块的合并策略。
• 可以根据数据访问模式和存储情况动态调整 compaction 策略。

优先

• 提供了较好的读取和写入性能，可以根据实际情况动态调整 compaction 行为。

缺点

• 实现较为复杂，需要对数据访问模式有较好的了解和动态调整。

4. FIFO Compaction

原理

• FIFO Style Compaction：

  • FIFO（First-In-First-Out）是一种最简单的合并策略。适用于处理低开销的事件日志数据，例如查询日志。
  • 当所有的 SST 文件的总大小超过配置值 CompactionOptionsFIFO::max_table_files_size（默认值为 1GB）时，最早创建的 SST 文件将会被删除，以释放存储空间。

• 文件管理：

  • 所有的文件都被存放在 Level 0。当 SST 文件数量增加时，可能导致查询性能的急剧下降，因为 Level 0 文件数量过多。
  • FIFO Compaction 策略只关注文件的时间顺序，不考虑文件的大小或内容。

• Compaction 触发：

  • 通过设置 CompactionOptionsFIFO.allow_compaction 参数，可以触发 L0 层的 IntraCompaction。每次至少会选取 level0_file_num_compaction_trigger 个 SST 文件进行合并，从而减少 Level 0 层的文件数量。

优点

• 简单易实现：

  • FIFO Compaction 策略实现简单，适合用于处理时间序列数据或日志数据。

• 低开销：

  • 适合用于需要简单文件管理策略的场景，例如日志数据的存储。

缺点

• 查询性能下降：

  • 由于所有文件都位于 Level 0，可能会导致查询性能下降，特别是当 Level 0 文件数量过多时。

• 空间管理有限：

  • FIFO Compaction 主要关注文件的删除，可能无法有效控制空间的使用或优化读写性能。

FIFO Compaction 是一种适合简单场景的合并策略，通过删除最早的文件来管理存储空间，但在处理大量文件或复杂查询时可能面临性能问题。

二、LSM-Tree和B+ 树区别

LSM-Tree和B+ 树区别如下，本质上LSM-Tree是面向SSD等新硬件一种新的设计，对写入友好，但同时也引入了一些其他问题。一些对比如下：

特性	LSM-Tree	B+ 树
结构	内存表 + 磁盘上的分层文件	自平衡的树形结构，所有数据存储在叶子节点中
写入性能	高，写入首先在内存表中，然后批量合并到磁盘	较低，写入涉及节点插入和重新平衡
读取性能	可能较高延迟，需要在多个层次中查找数据	快速，数据直接存储在叶子节点中
存储和整理	定期合并和整理磁盘上的数据文件	自动平衡树结构，维持查询性能稳定
适用场景	写密集型应用、大规模数据存储	读密集型应用、数据索引
优点	高写入吞吐量、较低写放大	快速读取、稳定查询性能
缺点	读取延迟、复杂的合并操作	写入开销较高、存储开销大
数据库实例	RocksDB、LevelDB	MySQL（InnoDB 存储引擎中的聚簇索引和非聚簇索引）

参考资料：

1. https://github.com/facebook/rocksdb/wiki
2. https://github.com/facebook/rocksdb/wiki/Leveled-Compaction
3. https://github.com/facebook/rocksdb/wiki/Universal-Compaction
4. http://alexstocks.github.io/html/rocksdb.html