介绍

LSM Tree 是一种存储结构

起源于 1996 年的一篇论文《The Log-Structured Merge-Tree (LSM-Tree)》

HBase、Cassandra、LevelDB、RocksDB

写数据流程

当收到一个写请求时，会先把该条数据记录在 WAL Log 里面。可用作故障恢复。
当写完 WAL Log 后，会把该条数据写入内存的 SSTable （删除是 墓碑标记，更新是新添加一条数据），也称 Memtable。
注意：根据Key有序地组织数据，为了实现排序，在内存里面采用红黑树或者跳跃表相关的数据结构。
当 Memtable 超过一定的大小后，会在内存里面冻结，变成不可变的 Memtable ，同时为了不阻塞写操作需要新生成一个 Memtable 继续提供服务。
把内存里面不可变的 Memtable 中的数据，写到硬盘上的 SSTable 层中，此步骤也称为 Minor Compaction
注意：在L0层的SSTable是没有进行合并的，所以这里的key range在多个SSTable中可能会出现重叠。在层数大于0层之后的SSTable，不存在重叠key。
当每层的磁盘上的 SSTable 的体积超过一定的大小或者个数，也会周期的进行合并。
此步骤也称为 Major Compaction ，这个阶段会 真正的清除标记为删除的数据，多版本数据的合并，避免浪费空间

如果SSTable的分层较多，把所有的分层扫描一遍，效率低，性能差

压缩。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，并在凌晨业务低峰期进行合并的原因。