为什么需要compaction?

LSM是一个顺序存储的结构，而且删除，修改都是追加方式存储，所以需要定时合并以减少数据冗余。

compaction的类型

• 按大小：较新和较小的SSTable被连续合并到较旧和较大的SSTable中。
• 按层级：在分层压缩中Key的范围会分裂为多个更小的SSTable，层级越大数据越旧，同层级的若干个SSTable合并成大的SSTable并且移动到下一层。
• LevelDB和RocksDB使用分层压缩，而Hbase使用大小分级，Cassandra同时支持两种策略。

a. size-tiered compaction

image.png

1. 文件大小相近的进行合并
2. 每一个sst是有序的，不保证每一层是有序无交集的

性能分析：

1. 空间放大：
   a. compaction过程中，多个小文件合并成中等文件，在生成大文件。超大文件合并是磁盘数据量几乎是两倍
   原因：合并中sst不能马上删除，部分老的sst有读操作，由于文件还被引用不能立即删除。新老文件共存，需要更多磁盘空间。
   b. 多次写入重复数据，合并过程中可能会空间放大多倍。因此不适合覆盖写频繁的场景
2. 写入放大：
   写入放大较好，因为每个层级都是多个低level合并，因此没有额外其他数据开销。
3. 读放大：
   因为每一层的数据无需，因此查询一个内容可能需要读取同一层级多个文件，开销相对较大。

b. leveled compaction

image.png

1. 实现原理

数据是分level的，每一个level是由多个sst组成，而每个层级的sst大小是固定的，
一个层级的文件数量或大小达到阈值，就会合并成更大的文件，依次类推。

特点：

1. 每个level的sst大小固定，每个level有多个sst

2. 每一层的sst数据没有交集，且都是有序排列
   每层维护“唯一一个”run, 注意里面的key不仅仅sort，而且non-overlap。

   
   有序排列

3. 每层的大小是上一级的T（图里是10） 倍，层数越高，data越多但是也越旧.每层都有target size。

   
   image.png

2. 流程：

compaction的过程可以简化成：in memory的table写满了，那么就flush到第一级的Disk SStable并且做compaction，要是第一级又满了，就又开始flush到第二级做compaction，以此类推直到max level。
Level compaction目标就是维持每个level都保持住one data sorted run，所以每个level都可以和下一个level做compaction，同时很有可能会被上一个level做compaction。这样做好处就是level之间的compaction可以multithread来做（除了memory到level0），提高效率。

image.png

3. 性能分析

• a. 空间放大：同时共存多份结果
  具有一定空间放大，在合并过程中如果有读取操作，会保留之前的数据。但相比STCS性能会好很多，因为合并过程中SST大小有限。

• b. 读放大： 查询时需要查询多次，才能获取到结果
  相比STSC性能会好些，因为每个level中都是有序的且没有交集，所以查询效率相对较高。

• c. 写放大：实际写入数据量比原始数据大很多，主要指 io 写带宽的放大
  有写放大，在写入过程中，有多次合并，即从0-max下沉过程中都需要io写，有大量无关数据写开销。

  
  image.png

总结： 降低空间放大，改善读放大，负面影响是写放大。

总结& 对比图

两种算法的主要差别在于，leveled合并倾向于更加频繁的把小的排序结果合并到大的里面，而“tiered”等待多个大小接近的排序结果，然后把它们合并到一起。

image.png

对比	Tiered LSM-Tree	Leveled LSM-Tree
优点	降低了写放大	降低了空间放大，读放大
缺点	严重的空间放大，读放大。不适合数据重复写入场景	合并过程中具有严重的写放大

image.png

参考：https://zhuanlan.zhihu.com/p/462850000
https://zhuanlan.zhihu.com/p/112574579?utm_id=0
https://zhuanlan.zhihu.com/p/462850000