# Universal Compaction

## 数据分布和安置

### Sorted Runs

Level 0: File0_0, File0_1, File0_2
Level 1: (empty)
Level 2: (empty)
Level 3: (empty)
Level 4: File4_0, File4_1, File4_2, File4_3
Level 5: File5_0, File5_1, File5_2, File5_3, File5_4, File5_5, File5_6, File5_7


### Placement of Compaction Outputs

File0_0
File0_1
File0_2
Level 4: File4_0, File4_1, File4_2, File4_3
Level 5: File5_0, File5_1, File5_2, File5_3, File5_4, File5_5, File5_6, File5_7


Level 5: File5_0', File5_1', File5_2', File5_3', File5_4', File5_5', File5_6', File5_7'


Level 0: File0_0
Level 1: (empty)
Level 2: (empty)
Level 3: (empty)
Level 4: File4_0', File4_1', File4_2', File4_3'
Level 5: File5_0, File5_1, File5_2, File5_3, File5_4, File5_5, File5_6, File5_7


Level 0: (empty)
Level 1: (empty)
Level 2: (empty)
Level 3: File3_0, File3_1, File3_2
Level 4: File4_0, File4_1, File4_2, File4_3
Level 5: File5_0, File5_1, File5_2, File5_3, File5_4, File5_5, File5_6, File5_7


Level 0: File0_0', File0_2
Level 1: (empty)
Level 2: (empty)
Level 3: (empty)
Level 4: File4_0, File4_1, File4_2, File4_3
Level 5: File5_0, File5_1, File5_2, File5_3, File5_4, File5_5, File5_6, File5_7


## Compaction Picking Algorithm

    R1, R2, R3, ..., Rn


R1的数据最新更新的，Rn 的数据是最旧的。 sorted runs 是根据其中包含的数据的新旧排序的，而不是 sorted run 自己的更新时间。 这样，合并输出保存的位置和输入的位置一样的。

#### Precondition: n >= options.level0_file_num_compaction_trigger

(Note although the option name uses word “file”, the trigger is for “sorted run” for historical reason. For the names of all options mentioned below, “file” also means sorted run for the same reason.)

#### 1. 通过空间放大率触发合并

    size amplification ratio = (size(R1) + size(R2) + ... size(Rn-1)) / size(Rn)


If options.compaction_options_universal.max_size_amplification_percent = 25, which means we will keep total space of DB less than 125% of total size of live data. Let’s use this value in an example. Assuming compaction is only triggered by space amplification, options.level0_file_num_compaction_trigger = 1, file size after each mem table flush is always 1, and compacted size always equals to total input sizes. After two flushes, we have two files size of 1, while 1/1 > 25% so we’ll need to do a full compaction:

1 1  =>  2


After another mem table flush we have

1 2   =>  3


Which again triggers a full compaction becasue 1/2 > 25%. And in the same way:

1 3  =>  4


But after another flush, the compaction is not triggered:

1 4


Because 1/4 <= 25%. Another mem table flush will trigger another compaction:

1 1 4  =>  6


Because (1+1) / 4 > 25%.

And it keeps going like this:

1
1 1  =>  2
1 2  =>  3
1 3  =>  4
1 4
1 1 4  =>  6
1 6
1 1 6  =>  8
1 8
1 1 8
1 1 1 8  =>  11
1 11
1 1 11
1 1 1 11  =>  14
1 14
1 1 14
1 1 1 14
1 1 1 1 14  =>  18


#### 2. 单个文件大小比例

size ratio trigger 使用下列公式计算：

     size_ratio_trigger = 1 + options.compaction_options_universal.size_ratio / 100


1 1  =>  2


After another mem table flush,

1 2  (no compaction triggered)


which doesn’t qualify a flush because 2/1 > 1. But another mem table flush will trigger a compaction of all the files:

1 1 2  =>  4


This is because 1/1 >=1 and 2 / (1+1) >= 1.

The compaction will keep working like this:

1 1  =>  2
1 2  (no compaction triggered)
1 1 2  =>  4
1 4  (no compaction triggered)
1 1 4  =>  2 4
1 2 4  (no compaction triggered)
1 1 2 4 => 8
1 8  (no compaction triggered)
1 1 8  =>  2 8
1 2 8  (no compaction triggered)
1 1 2 8  =>  4 8
1 4 8  (no compaction triggered)
1 1 4 8  =>  2 4 8
1 2 4 8  (no compaction triggered)
1 1 2 4 8  =>  16
1 16  (no compaction triggered)
......


Compaction is only triggered when number of input sorted runs would be at least options.compaction_options_universal.min_merge_width and number of sorted runs as inputs will be capped as no more than options.compaction_options_universal.max_merge_width.

#### 3. sorted sorts 的个数触发合并

See Universal Style Compaction Example as an example of how output sorted run sizes look like for a common setting.

Parallel compactions are possible if options.max_background_compactions > 1. Same as all other compaction styles, parallel compactions will not work on the same sorted run.

## Subcompaction

Subcompaction is supported in universal compaction. If the output level of a compaction is not “level” 0, we will try to range partitioned the inputs and use number of threads of options.max_subcompaction to compact them in parallel. It will help with the problem that full compaction of universal compaction takes too long.

## Options to Tune

Following are options affecting universal compactions:

• options.compaction_options_universal: various options mentioned above
• options.level0_file_num_compaction_trigger the triggering condition of any compaction. It also means after all compactions’ finishing, number of sorted runs will be under options.level0_file_num_compaction_trigger+1
• options.level0_slowdown_writes_trigger: if number of sorted runs exceed this value, writes will be artificially slowed down.
• options.level0_stop_writes_trigger: if number of sorted runs exceed this value, writes will stop until compaction finishes and number of sorted runs turn under this threshold.
• options.num_levels: if this value is 1, all sorted runs will be stored as level 0 files. Otherwise, we will try to fill non-zero levels as much as possible. The larger num_levels is, the less likely we will have large files on level 0.
• options.target_file_size_base: effective if options.num_levels > 1. Files of levels other than level 0 will be cut to file size not larger than this threshold.
• options.target_file_size_multiplier: it is effective, but we don’t know a way to use this option in universal compaction that makes sense. So we don’t recommend you to tune it.

Following options DO NOT affect universal compactions:

• options.max_bytes_for_level_base: only for level-based compaction
• options.level_compaction_dynamic_level_bytes: only for level-based compaction
• options.max_bytes_for_level_multiplier and options.max_bytes_for_level_multiplier_additional: only for level-based compaction
• options.expanded_compaction_factor: only for level-based compactions
• options.source_compaction_factor: only for level-based compactions
• options.max_grandparent_overlap_factor: only for level-based compactions
• options.soft_rate_limit and options.hard_rate_limit: deprecated
• options.hard_pending_compaction_bytes_limit: only used for level-based compaction
• options.compaction_pri: only supported in level-based compaction