LSM概念

• 一种分层，有序，面向磁盘的数据结构

组织架构：

image.png
image.png

Memory（active memtable、immutable memtable、block cache）、Disk（sstable、WAL）
active memtable：活跃的内存表
immutable memtable：不变的内存表
block cache：缓存
sstable：有序表
WAL：预写日志

• 有序性
  虽然sstable是有序的，但同一level中不同的sstable可能会出现key重叠，这取决于compaction策略。
  size-tiered compaction：同一level的sstable会出现重叠
  leveled compaction：level0以上的同一level的sstable不会出现重叠
  key重叠会导致读变大

• 写：

1. 写active memtable、WAL；2. active memtable写满后变为immutable memtable，并flush到磁盘，成为L0 sstable 3. 每L的sstable体积达到一定数量或大小，进行compaction操作, 合并到更高L去

• 读

1. 读取active memtable 2. 读取immutable memtable 3. 读取block cache 4. 前三步都是读内存，下面读磁盘；依次读取每层的sstable（读取sstable时使用二分查找）

• 如果读取一个不存在的key，开销很大，所以可以维护一个布隆过滤器。
• Compaction
  随着sstable的不断写入，系统打开的文件就会越来越多，并且对于同一个key积累的数据改变（更新、删除）操作也就越多。由于sstable是不可变的，为了减少文件数并及时清理无效数据，就要进行compaction操作，将多个key区间有重合的sstable进行合并。
  但compaction操作非常消耗CPU和磁盘IO，所以需要调整Compaction操作的启用时间。
• 空间放大
  指存储引擎的数据实际占用的磁盘空间比数据的真正大小偏多的情况。例如真实数据是10M，但实际存储耗费了25M，空间放大因子就是2.5
  为什么？
  LSM存储引擎中的数据只会增加，更改和删除操作都不是in-place的，需要等待compaction执行到对应的key才可以。所以一个key可能会对应多个value（删除标记也算一个特殊的value），而只有一个value是有效的（最新的哪个），其余的都算空间放大。
  另外，在Compaction时，原始数据在执行完成之前不能删除（防止出现意外无法恢复），所以同一份被Compaction的数据最多可能膨胀为2倍，这也算空间放大。
• 写放大
  一个数据会随着Compaction过程向更高的层重复写入，有多少层就写多少次。
• 读放大
  读放大是指：读取一次数据会产生多次的io，即为读放大
  SSL读取顺序为内存->存储0level->存储nlevel，最坏的可能要读取到n level（每一层io一次）。
  另外，如果是STCS 策略（size-tiered compaction），每一层的sstable会存在key重叠，最坏的情况要遍历所有的sst才能获得结果（每一层io次数=这一层sstable的数量）

参考：
https://blog.csdn.net/u010454030/article/details/90414063
https://www.jianshu.com/p/e89cd503c9ae?utm_campaign=hugo