What is LSM

前言：最近在了解学习 Rocksdb，在学习过程中发现里面挺多东西的，LSM树就是其中一环，于是乎就有了这篇文章。接下来会再写几篇，直到学习完 rocksdb，敬请期待啊～希望大家看完了也可以评论一下，给些反馈哈哈

什么是 LSM

虽然大家都是叫它 LSM 树，听着很像是一个树状的数据结构，但严格意义上，它是一种存储结构，全称 Log-Structured-Merge-Tree，即日志结构合并树

很多 NoSQL 存储都是采用 LSM 树进行支撑的，如 HBase、LevelDB、RocksDB 等

它的核心其实是牺牲部分读性能（存储分层设计），追求更好的写性能（顺序写）

那么问题来了，LSM 树究竟是要解决什么问题而提出的呢？

LSM 使用场景

知道了 LSM 树的特点后，基于 LSM 的存储引擎会用来做什么，其实并不难猜出来，即写多读少（相对而言）的场景，比如说：

• 日志系统
• 推荐系统
• 海量数据存储
• 数据分析
• ......

这些场景都是会有一定规模的数据量写入，同时对于数据读取的实时性要求并不高

接下来我们继续来了解一下 LSM 的核心原理吧～

LSM 的核心原理

这部分要分两块来讲，第一块是它如何保证顺序写？第二块是它有哪些东西组成？

LSM 如何保证顺序写

与 InnoDB 不同，LSM 就是围绕追加写来展开的。因为追加写就是一种典型的顺序IO，将所有的用户操作，都像写日志一样，不断的追加记录写到磁盘中，而不是记录覆盖

如图中所示，不管操作是数据插入，还是更新删除，都会往磁盘文件中的尾部追加操作的记录，而不是去磁盘中找到之前的数据记录，然后覆盖或删除，通过这种方式保证了 LSM 树的顺序写，从而大大地提高了写入的性能

至于为啥都说要保证顺序 IO 以及为啥顺序 IO 可以提高性能其实是跟磁盘的结构有关，实际上说的就是顺序 IO 符合磁盘的扫描读取的行为模式，相比随机 IO 而言更高效，保证顺序 IO 的目的也是为了减少寻址的次数

这是摘自网上的一张图，主要展示的是磁盘、SSD、内存这三者对于随机写和顺序写的一些性能比较，我们可以看到磁盘顺序写的吞吐量甚至能够超过内存随机写的吞吐量！

更多关于磁盘 IO 的知识，这里就不再展开了，感兴趣的可以自己再去了解一下

LSM 的核心模块

要想理解 LSM 树的读写原理，要先了解它的一些核心模块。数据库都离不开内存和磁盘的交换，而 LSM 树也是一样的，我们可以从内存和磁盘两部分去看它的组成原理，如下图：

内存模块由三个部分组成：

• memtable：内存中的数据结构，保存最近写入的数据，并按key有序地组织数据
• immutable memtable：中间状态，当 memtable 的大小到一个阈值时，会转为此状态，同时新建一个 memtable 用于处理新的写操作，避免了阻塞数据更新的操作
• block cache：缓存块，缓存了近期频繁使用的数据块解压缩之后的内容，用于提高读效率

磁盘模块由两个部分组成：

• WAL：Write-ahead-logging，预写式日志，在写入更新数据前先写日志，保证数据可靠性
• SSTable：磁盘中的数据结构，持久化在磁盘的有序键值对集合

除了上面说的这几个模块，图中还有几个数据流向也是很关键的：

• full：memtable 满了之后就会转换成 immutable memtable
• flush：immutable memtable 定期刷盘到磁盘里，与 level 0 的 SST 进行合并，在这个过程也会保证数据有序性
• compaction：压缩操作，这里涉及到分层压缩和分级压缩策略，下面会讲到

LSM 写入流程及读取流程

上面提到了 LSM 的核心其实就是通过顺序写来解决大量写时的性能问题，又因为分层设计牺牲了部分读取性能，那么接下来就从“增删改查”的角度去理解它的读写流程及原理

从“增删改”来看写入流程

要预先说明的是，LSM 对所有数据的插入、修改、删除操作都是先写入 log，再保存到内存中，待数据量到达某个值后再批量顺序地写入到磁盘中，这样也会提高写的效率

以插入数据为例，它的数据流向如下图

更新数据、删除数据时依然是上面的流程，只不过是操作的记录有所变化，并且是追加写入，与之前的同个 key 的写入记录是可以同时存在的，最终形成类似的日志形式

从“查”来看读取流程

现在来看一下读数据的流程，如下图所示

1. 收到 get 指令时，会先从 memtable 中查找是否存在，如果不存在则继续向下查找，依次顺序为 immutable memtable、block cache（如果开启了缓存）、level 0 SST、level 1 SST....level n SST，需要反序遍历所有的集合
2. 序号小的集合中的数据一定会比序号大的集合中的数据新（level0比level1新）
3. 一旦匹配到要读取的数据，一定是最新的数据，直接返回即可

实际上，为了提高随机读取的性能，一般会在 SSTable 上加入布隆过滤器判断数据是否存在达到避免不必要的数据遍历，同时也会对数据建立索引，加快查找速度

引申出来的“三大问题”

如果仔细看的话，通过上面的读写流程可以发现读写操作流程可能会很长，而这就引申出了 LSM 树的三大经典问题：写放大、读放大、空间放大，下面提到的合并策略其实就是对这三个问题的权衡与取舍

• 写放大：在写入数据时，触发了 Compact 操作导致写入的数据量远大于该 key 的数据量
• 读放大：读取数据时发现 key 不存在于 Memtable、Immutable Memtable，只能继续从 SSTable 往下查找
• 空间放大：冗余数据，key 从创建、修改、删除的记录可能会同时存在于磁盘，只有最新的那条记录才是有效的，之前的记录都可以被清理（在合并时）

LSM Compact 合并策略

为了解决上面提到的“三大问题”，就要用到合并策略了

LSM 树中有两种合并策略：size-tiered（分层策略），leveled（分级策略）

size-tiered 策略

我们先来看下 size-tiered 分层策略是怎样的

每层限制 SSTable 为 N，当每层 SSTable 数量达到 N 后，则触发 Compact 操作合并这些 SSTable，并将合并后的结果写入到下一层成为一个更大的 SSTable，这就是分层合并策略，即

• 限制每一层SSTable的数量
• 保证每层SSTable的大小相近

合并过程

假设 N 为 4，也就是每层 SSTable 数量最多为 4 个，一旦 SSTable 在这一层中数量到达 4，则会触发合并生成下一层的 SSTable

这种策略会有什么问题呢？

• 当层数达到一定数量时，最底层的单个 SSTable 的大小会变得非常大
• 导致空间放大比较严重：即使对于同一层的 SSTable，每个 key 的记录是可能存在多份的，只有当该层的 SSTable 执行 compact 操作才会消除这些 key 的冗余记录

leveled 策略

我们再来看一下 leveled 分级策略是怎样的，其实也跟名字含义一样，每一层都有一个层级 level 的概念

• 每一层限制总文件大小
• 将每一层切分成多个大小相近的 SSTable

• 每一层的 SSTable 是全局有序的，即一个 key 在每一层至多只有1条记录，不存在冗余记录

合并过程

1. 当 level 0 的总大小超过本身大小限制

1. 从 level 0 中选择至少一个文件，然后把它跟 level 1 有交集的部分进行合并，合并生成的 SSTable 文件会放在 level 1

假设此时 level 0 中有两个 SSTable 的 key 的范围与 level 1 的前两个有重合，则这几个 SSTable 触发 Compact 操作

需要注意的是：多个不相干的合并是可以并发进行的

如果 level 1合并后也超出 level 1的容量大小，重复上面的操作，于是乎...

既然说到合并策略是对读写、空间放大的问题的权衡与取舍，那它肯定也不是十全十美的，这种策略有什么样的问题呢？

• 空间放大问题会减缓：每层的 key 本身是不会重复的，即使是最坏的情况，除开最底层外，其余层都是与下一层重复的 key，按照相邻层大小比例为10来算，冗余占比也很小（如 3GB:30GB）
• 写放大问题会更突出：如果 level 1 触发合并了，其中的某个 SSTable 的 key 范围（如 key1~key100，个数为50）与下一层所有 SSTable 的范围都有交集（如key1～key100，个数为100），这时候 Compact 操作就会涉及 level 2 所有的数据

总结

LSM 树是一种利用磁盘顺序 IO 写入高性能的存储结构模型，它以牺牲了一定的读性能为代价，大幅度提升了写性能，适用于写多读少的特定应用场景，是一种兼顾成本及性能的存储解决方案。

很多数据库也是基于 LSM 树实现的，如 leveldb、rocksdb、hbase，大家可以去看一下理论演化成工程化实践落地具体会有什么不一样的地方或改进的地方

这篇文章主要讲解了 LSM 的结构组成、读写流程、三大问题以及合并策略，关于 LSM 树在内存、磁盘中数据的具体写入细节由于篇幅问题没有提及，感兴趣的可以去了解一下，数据是怎样顺序写入到内存的数据结构中，然后又如何持久化到磁盘的数据结构中，合并后读取对应的数据又是如何遍历这些数据结构的等等

最后留一个问题：你觉得分层合并与分级合并的区别是什么？什么情况选择哪一种策略更好？

Reference

1. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.44.2782&rep=rep1&type=pdf
2. https://blog.csdn.net/jinking01/article/details/105377370
3. https://zhuanlan.zhihu.com/p/181498475
4. https://www.jianshu.com/p/e89cd503c9ae?utm_campaign=hugo
5. https://xonlab.com/2021/01/10/%E8%AE%BA%E6%96%87%E7%BF%BB%E8%AF%91The%20Log-Structured%20Merge-Tree%EF%BC%88LSM-Tree%EF%BC%89/