日志结构合并树(LSM-Tree)
简介
LSM-Tree全称 Log Structured Merge Tree，是 Google 在 2006 年开源其 BigTable 中引入的一种数据结构。
一种分层，有序，面向磁盘的数据结构；
其核心思想是充分了利用了磁盘批量的顺序写要远比随机写性能高出很多的特性；
LSM-Tree 大大提升了数据的写入能力，却是以牺牲部分读取性能为代价，故此这种结构通常适合于写多读少的场景;
SSTable
LSM-Tree 核心的数据结构是 SSTable，全称是 Sorted String Table；
SSTable 是一种拥有持久化，有序且不可变的的键值存储结构，它的 key 和 value 都是任意的字节数组，并且了提供了按指定 key 查找和指定范围的 key 区间迭代遍历的功能。SSTable 内部包含了一系列可配置大小的 Block 块，典型的大小是 64KB，关于这些 Block 块的 index 存储在 SSTable 的尾部，
整体结构
LSM-Tree 里，SSTable 有一份在内存里面，其他的多级在磁盘上，如下图是一份完整的 LSM-Tree 图示
写流程
当收到一个写请求时，会先把该条数据记录在 WAL Log 里面，用作故障恢复；
当写完 WAL Log 后，会把该条数据写入内存的 SSTable 里面（删除是墓碑标记，更新是新记录一条的数据），也称 Memtable。注意为了维持有序性在内存里面可以采用红黑树或者跳跃表相关的数据结构；
当 Memtable 超过一定的大小后，会在内存里面冻结，变成不可变的 Memtable，同时为了不阻塞写操作需要新生成一个 Memtable 继续提供服务；
把内存里面不可变的 Memtable 给 dump 到到硬盘上的 SSTable 层中，此步骤也称为 Minor Compaction，这里需要注意在 L0 层的 SSTable 是没有进行合并的，所以这里的 key range 在多个 SSTable 中可能会出现重叠，在层数大于 0 层之后的 SSTable，不存在重叠 key；
当每层的磁盘上的 SSTable 的体积超过一定的大小或者个数，也会周期的进行合并。此步骤也称为 Major Compaction，这个阶段会真正 的清除掉被标记删除掉的数据以及多版本数据的合并，避免浪费空间，注意由于 SSTable 都是有序的，我们可以直接采用 merge sort 进行高效合并。
读流程
当收到一个读请求的时候，会直接先在内存里面查询，如果查询到就返回；
如果没有查询到就会依次下沉，知道把所有的 Level 层查询一遍得到最终结果。
优化
压缩
SSTable 是可以启用压缩功能的，并且这种压缩不是将整个 SSTable 一起压缩，而是根据 locality 将数据分组，每个组分别压缩，这样的好处当读取数据的时候，我们不需要解压缩整个文件而是解压缩部分 Group 就可以读取。
缓存
因为 SSTable 在写入磁盘后，除了 Compaction 之外，是不会变化的，所以我可以将 Scan 的 Block 进行缓存，从而提高检索的效率
索引，Bloom filters
正常情况下，一个读操作是需要读取所有的 SSTable 将结果合并后返回的，但是对于某些 key 而言，有些 SSTable 是根本不包含对应数据的，因此，我们可以对每一个 SSTable 添加 Bloom Filter，因为布隆过滤器在判断一个 SSTable 不存在某个 key 的时候，那么就一定不会存在，利用这个特性可以减少不必要的磁盘扫描。
合并
这个在前面的写入流程中已经介绍过，通过定期合并瘦身， 可以有效的清除无效数据，缩短读取路径，提高磁盘利用空间。但 Compaction 操作是非常消耗 CPU 和磁盘 IO 的，尤其是在业务高峰期，如果发生了 Major Compaction，则会降低整个系统的吞吐量，这也是一些 NoSQL 数据库，比如 Hbase 里面常常会禁用 Major Compaction，并在凌晨业务低峰期进行合并的原因。
LSM-Tree vs B+Tree
传统关系型数据采用的底层数据结构是 B+树，那么同样是面向磁盘存储的数据结构 LSM-Tree 相比 B+树有什么异同之处呢？
LSM-Tree 的设计思路是，将数据拆分为几百 M 大小的 Segments，并是顺序写入。
B+Tree 则是将数据拆分为固定大小的 Block 或 Page, 一般是 4KB 大小，和磁盘一个扇区的大小对应，Page 是读写的最小单位。
在数据的更新和删除方面，B+Tree 可以做到原地更新和删除，这种方式对数据库事务支持更加友好，因为一个 key 只会出现一个 Page 页里面，但由于 LSM-Tree 只能追加写，并且在 L0 层 key 的 rang 会重叠，所以对事务支持较弱，只能在 Segment Compaction 的时候进行真正地更新和删除。
因此 LSM-Tree 的优点是支持高吞吐的写（可认为是 O（1）），这个特点在分布式系统上更为看重，当然针对读取普通的 LSM-Tree 结构，读取是 O（N）的复杂度，在使用索引或者缓存优化后的也可以达到 O（logN）的复杂度。
而 B+tree 的优点是支持高效的读（稳定的 OlogN），但是在大规模的写请求下（复杂度 O(LogN)），效率会变得比较低，因为随着 insert 的操作，为了维护 B+树结构，节点会不断的分裂和合并。操作磁盘的随机读写概率会变大，故导致性能降低。
还有一点需要提到的是基于 LSM-Tree 分层存储能够做到写的高吞吐，带来的副作用是整个系统必须频繁的进行 compaction，写入量越大，Compaction 的过程越频繁。而 compaction 是一个 compare & merge 的过程，非常消耗 CPU 和存储 IO，在高吞吐的写入情形下，大量的 compaction 操作占用大量系统资源，必然带来整个系统性能断崖式下跌，对应用系统产生巨大影响，当然我们可以禁用自动 Major Compaction，在每天系统低峰期定期触发合并，来避免这个问题。
阿里为了优化这个问题，在 X-DB 引入了异构硬件设备 FPGA 来代替 CPU 完成 compaction 操作，使系统整体性能维持在高水位并避免抖动，是存储引擎得以服务业务苛刻要求的关键。