浅析LSM树

简介

Log Structured Merge Tree，下面简称 LSM。

2006年，Google 发表了 BigTable 的论文。这篇论文提到 BigTable 单机上所使用的数据结构就是 LSM。

目前，LSM 被很多存储产品作为存储结构，比如 Apache HBase, Apache Cassandra, MongoDB 的 Wired Tiger 存储引擎, LevelDB 存储引擎, RocksDB 存储引擎等。

简单地说，LSM 的设计目标是提供比传统的 B+ 树更好的写性能。

LSM的思想，在于对数据的修改增量保持在内存中，达到指定的限制后将这些修改操作批量写入到磁盘中。

相比较于写入操作的高性能，读取需要合并内存中最近修改的操作和磁盘中历史的数据，即需要先看是否在内存中，若没有命中，还要访问磁盘文件。

对应于使用LSM的Leveldb来说，对于一个写操作，先写入到memtable中，当memtable达到一定的限制后，这部分转成immutable memtable（不可写），当immutable memtable达到一定限制，将flush到磁盘中，即sstable.，sstable再进行compaction操作。

LSM思想非常朴素，就是将对数据的更改hold在内存中，达到指定的threadhold后将该批更改批量写入到磁盘，在批量写入的过程中跟已经存在的数据做rolling merge。

优化写性能

如果我们对写性能特别敏感，我们最好怎么做？—— Append Only：所有写操作都是将数据添加到文件末尾。

这样做的写性能是最好的，大约等于磁盘的理论速度（200 ~ 300 MB/s）。但是 Append Only 的方式带来的问题是：

• 读操作不方便。
• 很难支持范围操作。
• 需要垃圾回收（合并过期数据）。

所以，纯粹的 Append Only 方式只能适用于一些简单的场景：

• 数据库的 WAL。
• 能知道明确的 offset，比如 Bitcask。

优化读性能

如果我们对读性能特别敏感，一般我们有两种方式：

• 有序存储，比如 B+ 树，SkipList 等。
• Hash 存储 —— 不支持范围操作，适用范围有限。

如何获得（接近） Append Only 的写性能，而又能拥有不错的读性能呢？

以 LevelDB 为代表的 LSM 存储引擎给出了一个参考答案。注意，LevelDB 实现的是优化后的 LSM，原始的 LSM 可以参考论文。

下面的讨论主要以 LevelDB 为例子。

LevelDB 的写操作主要由两步组成：

• 写日志并持久化（Append Only），这样可以保证写操作不丢失。
• Apply 到内存中的 memtable（SkipList）。

所以，LevelDB 的写速度非常快。

与前面讲的LSM基本流程类似，在memtable 写“满”后，会转换为 immutable memtable，然后被后台线程 compaction 成按 Key 有序存储的 sst 文件（顺序写）。

由于 sst 文件会有多个，所以 LevelDB 的读操作可能会有多次磁盘 IO（LevelDB 通过 table cache、block cache 和 bloom filter 等优化措施来减少读操作的磁盘 IO 次数）。

总结

基于 LSM 数据结构的 LevelDB 的适用场景：

• 写请求多。
• 写性能（吞吐+延迟）要求高。

参考

https://www.jianshu.com/p/42d9dcd4f8cd

https://www.jianshu.com/p/dd4ad9d586ec