索引之LSM——compaction分类
为什么需要compaction?
LSM是一个顺序存储的结构，而且删除，修改都是追加方式存储，所以需要定时合并以减少数据冗余。
compaction的类型
- 按大小：较新和较小的SSTable被连续合并到较旧和较大的SSTable中。
- 按层级：在分层压缩中Key的范围会分裂为多个更小的SSTable，层级越大数据越旧，同层级的若干个SSTable合并成大的SSTable并且移动到下一层。
- LevelDB和RocksDB使用分层压缩，而Hbase使用大小分级，Cassandra同时支持两种策略。
a. size-tiered compaction
image.png
- 文件大小相近的进行合并
- 每一个sst是有序的，不保证每一层是有序无交集的
性能分析：
- 空间放大：
a. compaction过程中，多个小文件合并成中等文件，在生成大文件。超大文件合并是磁盘数据量几乎是两倍
原因：合并中sst不能马上删除，部分老的sst有读操作，由于文件还被引用不能立即删除。新老文件共存，需要更多磁盘空间。
b. 多次写入重复数据，合并过程中可能会空间放大多倍。因此不适合覆盖写频繁的场景 - 写入放大：
写入放大较好，因为每个层级都是多个低level合并，因此没有额外其他数据开销。 - 读放大：
因为每一层的数据无需，因此查询一个内容可能需要读取同一层级多个文件，开销相对较大。
b. leveled compaction
image.png
1. 实现原理
数据是分level的，每一个level是由多个sst组成，而每个层级的sst大小是固定的，
一个层级的文件数量或大小达到阈值，就会合并成更大的文件，依次类推。
特点：
- 每个level的sst大小固定，每个level有多个sst
-
每一层的sst数据没有交集，且都是有序排列
每层维护“唯一一个”run, 注意里面的key不仅仅sort，而且non-overlap。
有序排列
-
每层的大小是上一级的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
