lxkaka
所有文章 标签 分类 友链 关于
lxkaka

目录

以 RocksDB 为代表的 LSM tree 的学习和总结

lxkaka 收录于 存储 原理
   约 3360 字   预计阅读 7 分钟 

在公司最近组织的一次 OceanBase 的分享中我再次听到了 LSM-tree。为什么说是再呢？那不得不先介绍一下 RocksDB

RocksDB 是由 Facebook 基于 LevelDB 开发的一款提供键值存储与读写功能的 LSM-tree 架构引擎。用户写入的键值对会先写入磁盘上的 WAL (Write Ahead Log)，然后再写入内存中的跳表（SkipList，这部分结构又被称作 MemTable）。LSM-tree 引擎由于将用户的随机修改（插入）转化为了对 WAL 文件的顺序写，因此具有比 B 树类存储引擎更高的写吞吐。 在这篇文章里我们提到过 Pulsar 使用了 bookkeeper 来作为存储组件，其中 RocksDB 是 bookkeeper 的依赖组件之一。国内比较有名的开源存储 TiDB 把 RocksDB 作为了存储引擎。可以看到 RocksDB 的在存储界的地位之高了吧。而 RocksDB 和 OceanBase 都用到了 LSM tree(Log-Structured Merge-tree):一种分层、有序、面向磁盘的数据结构或者说是存储结构。在这篇文章里我们就学习一下 LSM tree 的设计思想。

LSM tree 简介

相比于传统的 in-place updates(原地更新)索引结构比如 B+ tree，LSM tree 将第一次写入都缓存到内存中，并通过后台的 flush 来顺序写入到磁盘中，也就是out-of-palce updates。 LSM tree 这样的实现方式有非常多的优点，包括写性能的提升、较高的空间利用率、简单的并发控制和异常恢复等。所以我们可以看到在大量写的场景下很多著名软件 BigTable, Dynamo, HBase, Cassandra, LevelDB, RocksDB 等都用到了 LSM tree。

今天我们以 RocksDB 中的 LSM tree 实现为目标来学习 LSM tree 的设计思想。

核心组成

下图是 RocksDB 的核心组成, 了解了核心的组成是掌握 LSM tree 设计思想的基础。

lsm01

MemTable

MemTable 是一个内存数据结构，保存了落盘到 SST 文件前的数据。它同时服务于读和写——新的写入总是将数据插入到memtable，读取在查询 SST 文件前总是要查询memtable，因为 memtable 里面的数据总是更新的。一旦一个 memtable 被写满，它会变成不可修改的，并被一个新的 memtable 替换。一个后台线程会把这个memtable 的内容落盘到一个 SST 文件，然后这个 memtable 就可以被销毁了。并且在flush的过程中，会完成数据的压缩。RocksDB 默认实现方式是 SkipList，适用于范围查询和插入。

Immutable Memtable

所有的写操作都是在 memtable 进行，当 memtable 空间不足时，会创建一块新的 memtable 来继续接收写操作，原先的内存将被标识为只读模式，等待被刷入 sst。刷入时机有以下三个条件来确定： write_buffer_size 设置一块 memtable 的容量,一旦写满，就标记为只读，然后创建一块新的。 max_write_buffer_number 设置 memtable 的最大存在数(active 和 immutable 共享)，一旦active memtable 被写满了，并且 memtable 的数量大于max_write_buffer_number, 此时会阻塞写操作。当flush操作比写入慢的时候，会发生这种情况 min_write_buffer_number_to_merge 设置刷入sst之前，最小可合并的 memtable 数，例如，如果设置 2，只有当 immutable memtable 数量达到2的时候，会被刷入 sst，数量为1的时候，则永远不会被刷入。

WAL(write-ahead log)

每次数据被更新时，会同时写入内存表和 WAL，WAL 可用于发生故障后，恢复内存的数据。
在以下情况下会创建一个WAL：

  • 新打开一个DB
  • flush 了一个 column family。一个 WAL 文件只有当所有的列族数据都已经 flush 到SST file 之后才会被删除，或者说，所有的 WAL 中数据都持久化到SST file 之后，才会被删除。归档的WAL文件会 move 到一个单独的目录，后续从磁盘中删除。
SSTable(soretd string table)

SSTable 全称是 Sorted String Table，是一个持久化的、有序的、不可更改的 Map 结构，Key 和 Value 都是任意的 Byte 串。
下图是 SSTable 的组成示意图，了解各个 block 能帮助我们快速理解 LSM tree 的读写过程。

sstable

  • DataBlock
    data block 顺序存储key/value，为了节省存储空间，并不会为每一对key-value对都存储完整的key值，而是存储与上一个key非共享的部分，避免了key重复内容的存储
  • MetaBlock 为了方便我们理解，我们只说明其中的 filter block 为了加快 sstable 中数据查询的效率，在直接查询 datablock 中的内容之前，首先根据 filter block 中的过滤数据判断指定的 datablock 中是否有需要查询的数据，若判断不存在，则无需对这个 datablock 进行数据查找。(使用的是 Bloom Filter)
  • MetaIndexBlock 对于只有 FilterBlock 的情况下，meta index block 用来存储 filter block 在整个 sstable 中的索引信息。
  • IndexBlock 与 meta index block 类似，index block 用来存储所有 data block 的相关索引信息。indexblock 包含若干条记录，每一条记录代表一个 data block 的索引信息。
  • Footer
    Footer 是定长的，读取 SST文件的时候，就是从文件末尾，固定读取字节数，进而得到了 Footer 信息。 Footer 中的信息，指明了 MetaIndexBlock 和 IndexBlock的位置，进而找到 MetaBlock 和 DataBlock。

读写过程

  • 读

    • 在 MemTable 中查找，无法命中转到下一步；
    • 在 immutable_memtable 中查找，查找不中转到下一步；
    • 在第0层 SSTable 中查找，无法命中转到下一流程； 对于L0 的文件，RocksDB 采用遍历的方法查找，所以为了查找效率 RocksDB 会控制 L0 的文件个数。每个 Memtable 跟 SST 都会有相应的 Bloom Filter 来加快判断 Key 是否可能在其中，当判断 Key 可能在其中时，就会在 Memtable 或者 SST 中进行查找。
    • 在剩余SSTable中查找。对于 L1 层以及 L1 层以上层级的文件，每个 SSTable 没有交叠，可以使用二分查找快速找到 key 所在的 Level 以及 SSTfile。

  • 写

    • 循环检查 DB 状态;
    • 如果当前 memtable 的 size 未达到阈值 write_buffer_size(默认4MB)，则允许写入; 如果 memtable 的 size 已经达到阈值，但 immutable memtable 仍然存在，则等待 compaction 将其 dump 完成；
    • memtable 已经写满，并且 immutable memtable 不存在，则将当前 memetable 置成 immutable memtable，产生新的 memtable 和 log file，主动触发 compaction，允许该次写。
    • 数据先写入 WAL，成功后转到下一步；
    • 数据写入 memetable

Compaction 策略

在上面的介绍中我们看到 RocksDB 有非常重要的操作就是 compaction。随着 sstable 的不断写入，系统打开的文件就会越来越多，并且对于同一个 key 积累的数据改变（更新、删除）操作也就越多。由于 sstable 是不可变的，为了减少文件数并及时清理无效数据，就要进行 compaction 操作，将多个 key 区间有重合的sstable 进行合并。

Leveled Compaction

磁盘的文件组合成多个 Level。Level 0 保存了最新的数据，越高 level 的 block 保存了越旧的数据。在 L0,不同的文件可能会出现相同的 key（因此，每次Get()需要遍历L0的每个文件）,但是 L1 和更高 level 的文件中，不同的文件不会出现相同的 key。除 L0 外，每个 Level 的数据按 key 的顺序分为一个个SST file。每个 SST file 内部的 key 都是有序的。 流程总结：

  1. 找到 score 最高的 level；(compact 流程的 Compaction Score，不同 level 的计算方法不一样)
  2. 根据一定策略从 level 中选择一个 sst 文件进行 compact，L0 的各个 sst 文件之间 key range 【minkey， maxkey】 有重叠，所以可能一次选取多个；
  3. 获取 sst 文件的 minkey 和 maxkey;
  4. 从 level + 1 中选取出于 (minkey, maxkey) 用重叠的 sst 文件，有重叠的文件则把文件与 level 中的文件进行合并（merge - sort）作为目标文件，没有重叠文件则把原始文件作为目标文件；
  5. 对目标文件进行压缩后放入 level + 1 中。 示意图如下

lsm-compaction

Universal Compaction

Univesal Compaction 主要针对 L0。当 L0 中的文件个数多于 level0_file_num_compaction_trigger，则启动 compact。 L0 中所有的 sst 文件都可能存在重叠的 key range，假设所有的 sst 文件组成了文件队列 R1,R2,R3,…,Rn，R1 文件的数据是最新的，R2 其次，Rn 则包含了最老的数据，其 compact 流程如下：

  1. 如果空间放大超过 max_size_amplification_percent，则对所有的 sst 进行 compaction（full compaction）；
  2. 如果前 size(R1)小于size(R2)在一定比例，默认 1%，则与 R1 与 R2 一起进行 compaction，如果（R1+R2)*(100+ratio)%100<R3，则将 R3 也加入到 compaction 任务中，依次顺序加入 sst 文件；
  3. 如果第1和第2种情况都没有 compaction，则强制选择前 N 个文件进行合并。
FIFO Compaction

FIFO 顾名思义就是先进先出，这种模式周期性地删除旧数据。在 FIFO 模式下，所有文件都在 L0，当 sst 文件总大小超过阀值 maxtablefiles_size，则删除最老的 sst 文件。对于 FIFO 来说，它的策略非常的简单，所有的 SST 都在 Level 0，如果超过了阈值，就从最老的 SST 开始删除，其实可以看到，这套机制非常适合于存储时序数据。

总结

在这篇文章里主要是对以 RocksDB 为代表的 LSM tree 设计思想进行学习和总结，希望能对大家认识和学习 LSM Tree 及 RocksDB 带来帮助。文章里很多细节比如核心组成部分数据机构的细节；读写流程的具体实现；compaction 的细节都没有展开，有兴趣的同学可以针对具体的点进一步探究。
关于 RocksDB 的问题

  • 读写放大严重
  • 应对突发流量的时候削峰能力不足
  • 压缩率有限
  • 索引效率较低 业界也有对应的改进措施，我们可以去选取对应的 topic 去看看别人的改进方案来拓宽我们的视野。
更新于 2021-06-26
阅读原始文档
 RocksDB, LSM tree
返回 | 主页