LSM 树(Log-Structured-Merge-Tree)的名字往往会给初识者一个错误的印象，事实上，LSM 树并不像 B+树、红黑树一样是一颗严格的树状数据结构，它其实是一种存储结构，目前HBase、LevelDB、RocksDB 这些 NoSQL 存储都是采用的 LSM 树。
LSM 树的核心特点是利用顺序写来提高写性能，但因为分层(此处分层是指的分为内存和文件两部分)的设计会稍微降低读性能，但是通过牺牲小部分读性能换来高性能写，使得 LSM 树成为非常流行的存储结构。
数据库存储有两种数据结构，一种 B+树，另外一种是 LSM。数据库，我们知道是用 B+树，但是对于 LSM，就不是所有人都知道。因为这种数据结构适用大数据的存储场景，适用于写多读少的场景。
LSM 数据结构
LSM 数据结构如上图，写入数据时：
- 先写入 WAL，用于故障恢复，如果断电，由于有 WAL Log 的存在，不会导致数据丢失。
- 再写入 MemTable 中，如果 MemTable 满，则数据被迁移到 Imutable Memtable 中。
- 后台线程发现有 Imutable Memtable，就写入到 SStable， SStable 的 key 都是有序的。
- 当 level0 的 ssTbale 满，就把数据迁移到 level1，并且和 level1 的数据进行归并排序，依次类推
各种操作
- 写入操作，写入 WAL Log 和 Memtable 就认为成功
- 读取，先到 Memtable 和 Imutable memtable 查找，如果查不到就到 SSTable 中查找，查找每个 SStable，使用布隆过滤器进行加速，指导找到数据。
- 删除，只进行标记，在合并 SSTable 时才会被真正删除
- 修改，知识插入数据，合并数据时，才会将旧值删除。数据读取时，新数据位置总是比旧数据位置高，因此总能读到最新值。
LSM 存储引擎
| 名称 | 语言 |
|---|---|
| levelDB | C++ |
| RocksDB | C++ |
| Pebble | go |
| BadgerDB | go |
| WiredTiger | C++ |
1、LSM 树的核心思想
如上图所示，LSM 树有以下三个重要组成部分：
1、MemTable
MemTable 是在内存中的数据结构，用于保存最近更新的数据，会按照 Key 有序地组织这些数据，LSM 树对于具体如何组织有序地组织数据并没有明确的数据结构定义，例如Hbase 使跳跃表来保证内存中 key 的有序。
因为数据暂时保存在内存中，内存并不是可靠存储，如果断电会丢失数据，因此通常会通过 WAL(Write-ahead logging，预写式日志)的方式来保证数据的可靠性。
2、Immutable MemTable
当 MemTable 达到一定大小后，会转化成 Immutable MemTable。Immutable MemTable 是将转 MemTable 变为 SSTable 的一种中间状态。写操作由新的 MemTable 处理，在转存过程中不阻塞数据更新操作。
3、SSTable(Sorted String Table)
有序键值对集合，是 LSM 树组在磁盘中的数据结构。为了加快 SSTable 的读取，可以通过建立 key 的索引以及布隆过滤器来加快 key 的查找。
这里需要关注一个重点，LSM 树(Log-Structured-Merge-Tree)正如它的名字一样，LSM 树会将所有的数据插入、修改、删除等操作记录(注意是操作记录)保存在内存之中，当此类操作达到一定的数据量后，再批量地顺序写入到磁盘当中。这与 B+树不同，B+树数据的更新会直接在原数据所在处修改对应的值，但是 LSM 数的数据更新是日志式的，当一条数据更新是直接 append 一条更新记录完成的。这样设计的目的就是为了顺序写，不断地将 Immutable MemTable flush 到持久化存储即可，而不用去修改之前的 SSTable 中的 key，保证了顺序写。
因此当 MemTable 达到一定大小 flush 到持久化存储变成 SSTable 后，在不同的 SSTable 中，可能存在相同 Key 的记录，当然最新的那条记录才是准确的。这样设计的虽然大大提高了写性能，但同时也会带来一些问题：
1）冗余存储，对于某个 key，实际上除了最新的那条记录外，其他的记录都是冗余无用的，但是仍然占用了存储空间。因此需要进行Compact操作(合并多个 SSTable)来清除冗余的记录。
2）读取时需要从最新的倒着查询，直到找到某个 key 的记录。最坏情况需要查询完所有的 SSTable，这里可以通过前面提到的索引/布隆过滤器来优化查找速度。
2、LSM 树的 Compact 策略
从上面可以看出，Compact 操作是十分关键的操作，否则 SSTable 数量会不断膨胀。在 Compact 策略上，主要介绍两种基本策略：size-tiered 和 leveled。
不过在介绍这两种策略之前，先介绍三个比较重要的概念，事实上不同的策略就是围绕这三个概念之间做出权衡和取舍。
1）读放大:读取数据时实际读取的数据量大于真正的数据量。例如在 LSM 树中需要先在 MemTable 查看当前 key 是否存在，不存在继续从 SSTable 中寻找。
2）写放大:写入数据时实际写入的数据量大于真正的数据量。例如在 LSM 树中写入时可能触发 Compact 操作，导致实际写入的数据量远大于该 key 的数据量。
3）空间放大:数据实际占用的磁盘空间比数据的真正大小更多。上面提到的冗余存储，对于一个 key 来说，只有最新的那条记录是有效的，而之前的记录都是可以被清理回收的。
- size-tiered 策略
size-tiered 策略保证每层 SSTable 的大小相近，同时限制每一层 SSTable 的数量。如上图，每层限制 SSTable 为 N，当每层 SSTable 达到 N 后，则触发 Compact 操作合并这些 SSTable，并将合并后的结果写入到下一层成为一个更大的 sstable。
由此可以看出，当层数达到一定数量时，最底层的单个 SSTable 的大小会变得非常大。并且 size-tiered 策略会导致空间放大比较严重。即使对于同一层的 SSTable，每个 key 的记录是可能存在多份的，只有当该层的 SSTable 执行 compact 操作才会消除这些 key 的冗余记录。 - leveled 策略
每一层的总大小固定，从上到下逐渐变大
leveled 策略也是采用分层的思想，每一层限制总文件的大小。
但是跟 size-tiered 策略不同的是，leveled 会将每一层切分成多个大小相近的 SSTable。这些 SSTable 是这一层是全局有序的，意味着一个 key 在每一层至多只有 1 条记录，不存在冗余记录。之所以可以保证全局有序，是因为合并策略和 size-tiered 不同，接下来会详细提到。
每一层的 SSTable 是全局有序的
假设存在以下这样的场景: - L1 的总大小超过 L1 本身大小限制：
此时 L1 超过了最大阈值限制 - 此时会从 L1 中选择至少一个文件，然后把它跟 L2 有交集的部分(非常关键)进行合并。生成的文件会放在 L2:
如上图所示，此时 L1 第二 SSTable 的 key 的范围覆盖了 L2 中前三个 SSTable，那么就需要将 L1 中第二个 SSTable 与 L2 中前三个 SSTable 执行 Compact 操作。 - 如果 L2 合并后的结果仍旧超出 L5 的阈值大小，需要重复之前的操作 —— 选至少一个文件然后把它合并到下一层:
需要注意的是，多个不相干的合并是可以并发进行的：
leveled 策略相较于 size-tiered 策略来说，每层内 key 是不会重复的，即使是最坏的情况，除开最底层外，其余层都是重复 key，按照相邻层大小比例为 10 来算，冗余占比也很小。因此空间放大问题得到缓解。但是写放大问题会更加突出。举一个最坏场景，如果 LevelN 层某个 SSTable 的 key 的范围跨度非常大，覆盖了 LevelN+1 层所有 key 的范围，那么进行 Compact 时将涉及 LevelN+1 层的全部数据。
3、总结
LSM 树是非常值得了解的知识，理解了 LSM 树可以很自然地理解 Hbase，LevelDb 等存储组件的架构设计。ClickHouse 中的 MergeTree 也是 LSM 树的思想，Log-Structured 还可以联想到 Kafka 的存储方式。
虽然介绍了上面两种策略，但是各个存储都在自己的 Compact 策略上面做了很多特定的优化，例如Hbase 分为 Major 和 Minor 两种 Compact，这里不再做过多介绍，推荐阅读文末的 RocksDb 合并策略介绍。
