文档目录Compaction算法用于分层分层分层rocks数据库的compactionleveledcompactionwhichleveltocompactsubcompactionuniversalcompactioncompactionwhiond 通过Space Amplification合并2、通过Individual Size Ratio合并3、通过sorted runs number合并4、通过age of data合并FIFOcompactionfifocompaction
Compaction (称为合并或压缩) LSM是指将数据从Ln层合并到Ln 1层，并删除重复的旧数据。
压缩算法
主要两种类型的LSM树合并算法
高级集成，这是RocksDB数据库的默认策略
leveled算法的特点是以读取放大和写入放大为代价，以最小化空间放大
LSM-tree可以被认为是包含多个level的序列，其中每个level只包含一个sorted run。 相邻level的大小之比通常称为fanout，如果不同level之间的fanout相同，则LSM-tree的写入扩展最小。 compaction选择l(n )数据，并将其与原始l ) n1 )的数据合并以获得新的l ) n1 )数据。 每个compaction的最大大小写放大率与fanout相同。
分层是合并战略的替代，有时称为“大小分层”或“分层”
Tiered合并通过增加读取和空间扩展实现最小化写放大
LSM-tree仍可以被视为包含若干个level的序列，每个level包括n个受保护的run。 L(N )的sorted run的大小是L(N-1 )的n倍。 compaction通常选择l(n )的数据合并，得到新的sorted run并输出到l ) n1 )，但不与l ) n1 )的现有数据合并。 每个compaction的最大大小写放大率为1。
两种算法的主要区别在于，高级合并倾向于更频繁地将较小的排序结果合并到较大的中，而分层则等待多个大小相近的排序结果，然后合并它们。
分层级别
分层指示灯具有比分层指示灯小的写放大和比分层指示灯小的空间放大。
分层封装方式为混合封装，小层使用分层，大层使用分层。 在分层和分层之间切换的级别非常灵活。
RocksDB数据库的分层集成也是分层的。 memtable放弃过程类似于tiered将——memtable的输出合并以在L0中创建新的排序结果，而不需要读取/重写L0中已经存在的排序结果。 L0是Teired，因为根据leveL0_ file _ num _ compaction _ trigger的配置，l0可以具有多个sort run。 其他层是Leveled。
RocksDB的Compaction Rocksdb中常用的Compaction模式有两种： Leveled和universal (分层算法)。
所有分层压缩的非零层都有目标大小。 合并的目的是限制这些层次的数据大小。 target sizes通常指数增加。
当L0的文件数达到leveL0_ file _ num _ compaction _ trigger时，将触发“合并”，l0的文件将合并到L1中。 通常，我们需要选择所有L0文件。 因为他们通常是交叉的：
合并后，L1的大小可能超过目标大小。
此时，至少选择一个文件并合并与L2相交的部分。 生成的文件将放置在L2中：
如果结果仍超过下一层的目标大小，请重复上一个操作——以选择文件，并将其合并到下一层：中
然后呢
如果需要，将同时进行多个合并。
最大并发合并数由max_background_compactions控制。
which level to compact如果多个层触发合并条件，则RocksDB必须选择先合并哪个层。 使用以下方法为每个层生成分数：
如果不是0级，则分数是当前级别的总大小除以目标大小。 如果已有文件选择合并到下一层，则这些文件的大小将很快消失，因此不会包含在总大小中。 如果为level0，则分数为文件总数，除以level0_file_n
um_compaction_trigger，或者总大小除以max_bytes_for_level_base，这个数字可能更大一些。（如果文件的大小小于level0_file_num_compaction_trigger，level 0 不会触发合并，不管这个分数有多大）我们比较每一层的分数，分数高的合并优先级更高。
subcompaction
level 0 由memtable flush而来， 每个文件的key range会有重叠，不同于其他level，无法并行compaction。因此提出 subcompaction（次合并）来实现另一种并行。
通过一系列操作，将level 0到level 1的一次compaction按照合理的key range划分成为互不覆盖，互不影响的多个subcompaction，并交给多个子线程并行去做，不同的子线程compaction结果输出到不同的文件中，等所有子线程完成自己的compaction后，主compaction线程进行结果整理合并，最终完成本次compaction。
https://blog.51cto.com/u_15057819/2647639
Universal合并方式是一种合并方式，面向那些需要用读放大和空间放大，来换取更低的写放大的场景。
通常认为 tiere 算法提供更好的写放大表现，但是读放大会变糟糕。凭直觉来看：在tiered存储，每当一个更新被合并，他倾向于从小的sorted run移动到一个大很多的sorted run。每次合并都可能会指数级接近最后那个最大的sorted run。然而在leveled合并，一次更新更加可能通过一个小的排序结果，被合并进一个更大的排序结果，而不是直接作为一个较小的排序结果的一部分保存起来。
最坏的情况下，sorted run数量会比leveled多很多。这会导致读数据的时候有更高的IO和更高的CPU消耗。
尽管如此，RocksDB仍旧提供了“tiered”家族的算分，Universal合并。用户可以再leveled合并无法处理想要的写速率的时候，可以尝试这种合并方式。
使用 Universal Compaction 的 RocksDB 实例，可以看作是在时间上将数据划分到不同的 sorted run，每个 sorted run 在时间上互不交叠。compaction 仅仅针对在时间上相邻的 sorted run 进行，其输出的时间范围是原输入的时间范围的组合。
假设我们有 sorted run
R1, R2, R3, ..., RnR1有DB最新的更新，而Rn有最老的DB更新。 sorted run 按照数据时间顺序排序。由于 compaction 输出与输入的时间范围相同，compaction 操作不会改变 sorted run 的排序。
Compaction 触发前置条件：n >= options.level0_file_num_compaction_trigger，即 sorted run 的数量达到阈值options.level0_file_num_compaction_trigger。 （参数中的file并不准确，应该为sorted run）
如果前置条件满足了，还有四个条件。满足其中任意一个都可以触发一个合并：
如果预计的空间放大比例（size amplification ratio）大于options.compaction_options_universal.max_size_amplification_percent / 100，所有的文件会被合并为一个sorted run。
计算公式如下：
size amplification ratio = (size(R1) + size(R2) + ... size(Rn-1)) / size(Rn)以 options.compaction_options_universal.max_size_amplification_percent = 25，options.level0_file_num_compaction_trigger = 1 的配置参数为例：
11 1 => 21 2 => 31 3 => 41 41 1 4 => 61 61 1 6 => 81 81 1 81 1 1 8 => 111 111 1 111 1 1 11 => 141 141 1 141 1 1 141 1 1 1 14 => 182、由Individual Size Ratio触发的合并 size_ratio_trigger = (100 + options.compaction_options_universal.size_ratio) / 100
我们从R1开始，如果size(R2) / size(R1) <= size_ratio_trigger, 那么（R1，R2）被合并到一起。我们以此继续决定R3是不是可以加进来。如果size(R3) / size(R1+r2) <= size_ratio_trigger，R3应该被包含，得到(R1,R2,R3)。然后我们对R4做同样的事情。我们一直用所有已有的大小总和，跟下一个排序结果比较，直到size_ratio_trigger条件不满足。
以 options.compaction_options_universal.size_ratio = 0，options.level0_file_num_compaction_trigger = 5 参数配置为例：
1 1 1 1 1 => 51 5 (no compaction triggered)1 1 5 (no compaction triggered)1 1 1 5 (no compaction triggered)1 1 1 1 5 => 4 51 4 5 (no compaction triggered)1 1 4 5 (no compaction triggered)1 1 1 4 5 => 3 4 51 3 4 5 (no compaction triggered)1 1 3 4 5 => 2 3 4 53、由 number of sorted runs 触发的合并
如果sorted runs的数量达到了options.level0_file_num_compaction_trigger，但是没有触发前面提到的size amplification 或者space amplification trigger。那么RocksDB将尝试进行 sorted run 数量不超过options.compaction_options_universal.max_merge_width 的 compaction，以使得 sorted run 数量少于 options.level0_file_num_compaction_trigger。
对于Universal Compaction,基于时间的compaction策略是最高优先级的，如果我们尝试compaction，一定会先检查时间条件，如果有文件存在的时长大于options.periodic_compaction_seconds，RocksDB将会从旧到新来挑选sorted runs 来compaction，直到某个更新的sorted runs 正在被compaction，这些文件将会被合并到最底层。
FIFO Style Compaction 是最简单的合并策略。很适合用于保存低开销的事件日志数据（例如查询日志）。当文件总大小超过配置值 CompactionOptionsFIFO::max_table_files_size （默认值为 1GB) 时，最早的 SST 文件将会被删除。
使用FIFO时，所有的文件都位于 L0，因此SST文件过多，导致查询性能急剧下降。
开启 CompactionOptionsFIFO.allow_compaction 参数，可以触发 L0 IntraCompaction，每次至少选取 level0_file_num_compaction_trigger 个 SST 文件进行合并，从而减少文件数量。
FIFO Compaction with TTL 在 FIFO compaction 的基础之上，提供 SST 文件级别的过期删除功能。当 SST 的最新的 key 存在时间超过 mutable_cf_options.ttl，则该 SST 文件将会在 TTL compaction 中被删除。
参考：
https://github.com/facebook/rocksdb/wiki/Compaction
https://www.jianshu.com/p/333ec61051f0
https://zhuanlan.zhihu.com/p/165137544
https://github.com/johnzeng/rocksdb-doc-cn/blob/master/doc/Compaction.md