基于LSM树的存储引擎

发表于 | 分类于

使用 LSM 树提升写入性能

在了解 LSM 树存储引擎之前，我们先来说说磁盘的随机IO、顺序IO。通常数据库的数据最终都是持久化到磁盘上，而对磁盘的访问方式有两种，即：

  • 随机IO
    随机 IO 就需要花费时间做昂贵的磁盘寻道，一般来说，它的读写效率要比顺序 IO 小好几个数量级，所以我们想要提升写入的性能就要尽量减少随机 IO
  • 顺序IO
    以 MySQL 的 InnoDB 存储引擎来说，更新 binlog、redolog、undolog 都是在做顺序 IO，而更新 datafile 和索引文件则是在做随机 IO，而为了减少随机 IO 的发生，关系数据库已经做了很多的优化，比如说写入时先写入内存，然后批量刷新到磁盘上，但是随机 IO 还是会发生。
    索引在 InnoDB 引擎
    中是以 B+ 树（上一节课提到了 B+ 树，你可以回顾一下）方式来组织的，而 MySQL 主键是聚簇索引（一种索引类型，数据与索引数据放在一起），既然数据和索引数据放在一起，那么在数据插入或者更新的时候，我们需要找到要插入的位置，再把数据写到特定的位置上，这就产生了随机的 IO。而且一旦发生了页分裂，就不可避免会做数据的移动，也会极大地损耗写入性能。

目前很多 NoSQL 数据库都在使用基于 LSM 树的存储引擎，例如 RocksDB、LevelDB、HBase 以及 Prometheus 等，这也是为什么这些数据库的写入性能很高的原因。

什么是 LSM 树

LSM 树（Log-Structured Merge Tree）牺牲了一定的读性能来换取写入数据的高性能，这种方式全部都是以追加的形式将数据写入，不存在直接对数据删除和修改，所以这种结构很适合在写多读少的情况下。

它的思想很简单，数据首先会写入到一个叫做 MemTable 的内存结构中，在 MemTable 中数据是按照写入的 Key 来排序的。为了防止 MemTable 里面的数据因为机器掉电或者重启而丢失，一般会通过写 Write Ahead Log 的方式将数据备份在磁盘上。

MemTable 在累积到一定规模时，它会被刷新生成一个新的文件，我们把这个文件叫做 SSTable（Sorted String Table）。当 SSTable 达到一定数量时，我们会将这些 SSTable 合并，减少文件的数量，因为 SSTable 都是有序的，所以合并的速度也很快。SSTable 会以多个层级的方式保存在磁盘上。

当从 LSM 树里面读数据时，我们首先从 MemTable 中查找数据，如果数据没有找到，再从 SSTable 中按层级往下一层层查找数据。因为存储的数据都是有序的，所以查找的效率是很高的，只是因为数据被拆分成多个 SSTable，所以读取的效率会低于 B+ 树索引。

LSM

写数据

  1. 当有数据写入时，会先把数据记录在 WAL Log 中用来进行故障恢复。
  2. 将数据写入内存 MemTable 中，为了维持有序性可以采用红黑树或者跳跃表相关的数据结构。
  3. 当 MemTable 超过一定大小后会把它写到磁盘 SSTable 层中，此时会生成一个新的 MemTable 提供数据写入。
  4. SSTable 在 L0 层中是没有进行合并的，所以会出现重复的 key，当每层的磁盘上的 SSTable 大小或个数到达阈值时则会进行合并，避免浪费空间，在 L0 层之后的数据不存在重复的 Key。

常见问题

  1. 数据都是以追加写的形式进行增删改，所以存在冗余数据，因此通常会进行 compact 操作合并多个 SSTable 来清除冗余数据。
  2. 如果查找的数据不存在，最坏的情况是会扫描所有 SSTable 文件，所以可以使用索引、布隆过滤器来优化查询速度。