LSM树(Log-Structured-Merge-Tree )的名称通常会给初学者留下错误的印象。 实际上，LSM树不像b树和红色黑树那样是严密的树数据结构，实际上是存储结构，被称为现在的HBase、LevelDB、RocksDB
LSM树的核心特征是利用顺序写入来提高写入性能，但由于分层(这里分层分为内存和文件两部分)的设计，读取性能略有下降，但以牺牲读取性能较小的部分为代价，实现了高性能
1、LSM树的核心思想
如上图所示，LSM树具有以下三个重要组件：
1) MemTable
MemTable是位于内存的数据结构，用于存储最近更新的数据，并根据Key组织数据。 LSM树对于具体如何组织数据没有明确的数据结构定义。 例如，Hbase使用跳转表来保证内存中Key的有序性。
由于数据是临时存储在内存中的，因此内存不是可靠的存储器，通常会通过写操作记录(wal )来保证数据的可靠性，因为关闭电源时会丢失数据。
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个更新记录来完成。 这样设计的目的是为了顺序写入，不修改以前的SSTable的key，连续将Immutable MemTable flush保存在持久化存储中就可以了，保证了顺序写入。
因此，在MemTable达到固定大小的flush且持久化存储变为SSTable之后，不同的SSTable上可能会存在相同的密钥记录。 当然，最新的记录是正确的。 通过这样的设计，写入性能得到了很大的提高，但也存在一些问题。
1 )冗馀存储占用了某些key的存储空间，但实际上最新的记录除外，其他记录都是冗馀且浪费的。 因此，为了清除冗馀记录，需要进行Compact操作(合并多个SSTable )。
2 )在找到某个key的记录之前，需要从最新的相反方向进行调查。 在最坏的情况下，需要查询所有的SSTable。 在此，您可以使用上面提到的索引/布隆过滤器优化搜索速度。 2、LSM树的Compact策略从上面可以看出，Compact操作是一个非常重要的操作，否则SSTable的数量会不断膨胀。 Compact策略主要介绍两种基本策略： size-tiered和leveled。
但是，在介绍这两种战略之前，我先介绍三个比较重要的概念。 实际上，不同的策略是在这三个概念之间进行权衡和取舍。
1 )在用读取放大部：读取数据时，实际读取的数据量比真正的数据量大。 例如，在LSM树中，首先需要在MemTable中调查是否存在当前的密钥，如果不存在，则需要从SSTable开始继续搜索。
2 )在写入放大：的写入数据时，实际写入的数据量大于真实数据量。 例如，写入LSM树时可能会触发Compact操作，导致实际写入的数据量明显大于key的数据量。
3 )容量扩展：数据实际占用的磁盘空间大于数据的真实大小。 对于一个key，上述冗馀存储只有最新的记录有效，所有以前的记录都将被清理并回收。1) size-tiered 策略
size-tiered策略确保每层SSTable的大小相近，并限制每层SSTable的数量。 如上图所示，每层的限制SSTable为n，当每层的SSTable达到n时，它将触发Compact操作来合并这些SSTable，并将合并结果写入下一层，从而生成更大的SSTable。
由此可知，当层数达到一定数量时，最下层的各个SSTable的大小变得非常大。 另外，由于size-tiered战略，空间扩大变得严重。 对于同一个层次的SSTable，每个key都可能有多个记录，只有在该层次的SSTable执行了compact操作时，才会消除这些key的冗馀记录。
2) leveled策略
每天
一层的总大小固定，从上到下逐渐变大leveled策略也是采用分层的思想，每一层限制总文件的大小。
但是跟size-tiered策略不同的是，leveled会将每一层切分成多个大小相近的SSTable。这些SSTable是这一层是全局有序的，意味着一个key在每一层至多只有1条记录，不存在冗余记录。之所以可以保证全局有序，是因为合并策略和size-tiered不同，接下来会详细提到。
每一层的SSTable是全局有序的
假设存在以下这样的场景:
1) L1的总大小超过L1本身大小限制：
此时L1超过了最大阈值限制
2) 此时会从L1中选择至少一个文件，然后把它跟L2有交集的部分(非常关键)进行合并。生成的文件会放在L2:
如上图所示，此时L1第二SSTable的key的范围覆盖了L2中前三个SSTable，那么就需要将L1中第二个SSTable与L2中前三个SSTable执行Compact操作。
3) 如果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合并策略介绍。
参考来源：
https://rocksdb.org.cn/doc/Leveled-Compaction.html
https://www.jianshu.com/p/e89cd503c9ae?utm_campaign=hugo