Repository navigation
Description
Describe problems
At present, the Compaction in BE is divided into two parts: Base and Cumulative. For the incremental overlap rowsets, the Cumulative Compaction process is merged first, and then in Base Compaction process nonoverlap rowsets are merged. When there are frequent small batches of continuous writing, a large number of small nonoverlap rowsets to Base Compaction process. This will cause the following problems:
(1) In Base Compaction, each time a small batch file data is merged, the merge efficiency of Base Compaction is very low (it takes a long time to merge many small files, the number of merges of Base is more, and the write amplification is serious).
(2) There are too many small files at the same time, and too many files will be read during query, which affects the query efficiency.
Solution
base compaction process
The base compaction process is unchanged, the existing process is maintained, and the versions from Base to Cumulative Point are merged.
comulative compaction process
1 Cumulative Point calculation (changing part)
Cumulative Point calculation will be executed once when it is initialized.
Traverse the rowsets collection in version order. If the following conditions are satisfied, the Cumulative Point moves down, otherwise it breaks:
- The current rowset is a non-overlap type.
- The rowset disk space is greater than base_compaction_delta_ratio(2%) of the base version or greater than or equal to min_base_compaction_promotion_size(2G).
2 Select the Rowset to be merged by Cumulative Compaction
2.1 Candidate_rowsets collection of candidate sets, (consistent with the original process)
- The candidate set is selected to be greater than or equal to all versions of Cumulative Point. And sort.
- Collect rowset versions from the candidate set, and stop collecting when compaction_score is greater than or equal to 1000 or when the traversal reaches the end.
- When there is a deletion condition for candidate_rowsets, the previous version is collected and deleted. Move Cumulative Point after deleting rowset.
2.2 Create input_rowsets (changing part)
(1) Definition:
- When the total number of disks in the candidate set candidate_rowsets s_total,
- The disk space s1 of the first version in candidate_rowsets.
- level_size(n) represents n to the disk size segment that can be mapped to [1G-2G), [512m-1G), [256m-512m), [128m-256m), [64m-128m), this segments can be calculated by min_base_compaction_promotion_size.
(2) Implementation process:
- When s_total is greater than or equal to base_compaction_delta_ratio(2%) of the base version or greater than or equal to min_base_compaction_promotion_size(2G) or s_total <= smallest_compaction_limit(64m), candidate_rowsets is directly assigned to input_rowsets and exits.
- When level_size (s_total-s1) >= level_size (s1), candidate_rowsets are directly assigned to input_rowsets and exit.
- When level_size (s_total-s1) <level_size (s1), after removing the first version of candidate_rowsets, return to the first step and loop the process.
(3) Check input_rowsets (consistent with the original process)
- When the compaction_score of input_rowsets is less than the minimum score of 5, input_rowsets are cleared and not merged.
- Check that input_rowsets is empty, and supplement the check according to time. If the merge is not performed for more than 1 day, and there is an overlap type rowset in candidate_rowsets, candidate_rowsets is directly assigned to input_rowsets and exits.
3 Execute compaction (consistent with the original process)
4 Cumulative Point update (changing part)
When the disk space of the newly generated rowset is greater than base_compaction_delta_ratio(2%) of the base version rowset or greater than or equal to min_base_compaction_promotion_size(2G), the Cumulative Point moves forward, otherwise it does not move.
Evaluation of merger effect
1. Configuration variable selection
smallest_compaction_limit: 64m
min_base_compaction_promotion_size: 2G
base_compaction_delta_ratio: (2%)
2. File num growth trend
3. Comparison of two strategy
This includes base compaction and cumulative compaction. Assuming that the file size of each import is d, a cumulative compaction is performed after q rounds of data load, and a base compaction is performed after k cumulative compactions. The import of d is executed n times. It is assumed that k is greater than 4.
Base IO write amplification can be understood as the number of Base Compaction execution times during the n-time import process. Because every Base Compaction must be completely rewritten to Base. The situation of write amplification can be clearly seen by comparing the times of Base Compaction.
3.1 old strategy
Maximum number of existing files = k + q
Base Compaction times p = n / (k * q)
Base IO write data volume = d * q * k * p * (p + 1) / 2 = d * n * (n + k * q) / k * q
Cumulative IO write data volume = d*n
3.2 this new strategy
3.2.1 The number of files:
a) when q * d> 2G:
Maximum number of existing files = k + 6
b) when q * d <2G:
Maximum number of existing files = k * q * d / 2G + 6
Can avoid too many files caused by too many small batches
3.2.2 Base IO write amplification situation:
a) When d * q * k >= 8G:
Base Compaction times p = n / (k * q)
Base IO write data volume = d * q * k * p * (p + 1) / 2 = d * n * (n + k* q) / k * q
In this case, Base Compaction IO is basically the same as the previous Compaction IO situation.
b) When d * q * k <8G:
Base Compaction times p = log(1 + 8%)(n), here does not depend on the times k
Base IO write data volume = d(1-n/1.08) / (1-1.08) = 18.51 * n * d – 20d
In this case, Base Compaction IO is at the O(n) level, which is significantly better than the previous O(n2) situation. The 8% here is due to the base compaction limit when more than 5 versions (including base) are merged, and the worst-case evaluation is here.
3.2.3 Cumulative IO write amplification situation:
When q * d> 2G:
Cumulative IO write data volume = n * d
When q * d <2G:
Cumulative IO write data volume = (log (2G / q * d) + 1) * n * d
3.4 In conclusion:
When q * d <2G, Cumulative IO wastes log (2G / q * d) write amplification and reduces
k - k * q * d / 2G number of files.
When k * q * d <= 8G, Base IO greatly reduces write amplification.
When q * d> 2G, the effect is the same as before.

Activity
ZhangYu0123 commentedon Jul 23, 2020
问题描述
目前,在BE的Compaction分为Base和Cumulative两个部分。对于增量的overlap的Rowset先由Cumulative Compaction流程合并,合并完之后交由Base Compaction流程进行合并。当有频繁的小批量不断写入时,会产生大量Rowset直接交给Base合并。这样会引发如下问题:
(1)Base Compaction时,每次由Base合并一堆小文件数据,Base的合并效率较低(用时较长合并了很多小体积文件,Base的合并次数较多,写放大严重)。
(2)同时存在的小文件过多,查询时会读取过多的文件进行合并,影响查询效率。
解决方案
为兼顾合并效率(减少合并过程中IO操作)和减少文件数量提升查询效率。提出了如下改进方案:
1、base compaction流程
base compaction流程不变,保持现有流程,合并从Base到Cumulative Point的版本。
2、cumulative compaction流程
2.1 Cumulative Point计算
这里新创建或初始化的时候会执行一次。按版本顺序遍历rowset。满足如下条件,Cumulative Point向下移动,否则break:
2.2 选取Cumulative Compaction要合并的Rowset
2.2.1 候选集candidate_rowsets收集,(与原流程一致)
2.2.2 创建input_rowsets (调整部分)
定义:
执行过程:
2.2.3 检查input_rowsets,(与原流程一致)
2.3 执行合并
2.4 Cumulative Point更新(调整部分)
新产生rowset的磁盘空间大于base版本rowset的2%或者大于等于2G时,Cumulative Point向前移动,否则不移动。
合并效果评估
1 配置参考
smallest_compaction_limit: 64m
min_base_compaction_promotion_size: 2G
base_compaction_delta_ratio: (2%)
2 文件增长情况
根据算法流程的描述,在最坏情况下,经过Cumulative Compaction各个文件都达到临界值没有合并的情况是log2的对数个文件。如下表所示

3 前后对比
这里包括了base compaction和cumulative compaction。假设每次导入文件大小为d,经过q轮导入后执行一次cumulative compaction,经过k次cumulative compaction后执行一次base compaction。共执行n次d的导入。这里假设k大于4
Base IO 写放大情况可以理解成在n次导入的过程中,Base Compaction执行次数。 因为每次的Base Compaction都要对Base进行完全重新写入一次。通过比较Base Compaction次数可明显看出写放大的情况。
3.1 之前流程
最大存在文件数量 = k + q, // k具有不确定性
Base Compaction次数 p = n / (k * q)
Base IO写入数据量 = d * q * k * p * (p + 1) / 2 = d * n * (n + k* q) / k * q
Cumulative IO写入数据量 = d*n
3.2 改后流程
3.2.1 文件数量是相同的,不用分情况讨论:
q * d > 2G时:
最大存在文件数量 = k + 6
q * d < 2G时:
最大存在文件数量 = k * q * d / 2G + 6
可以避免太多小批量导致的文件数过多
3.2.2 Base IO写入放大情况:
a) 当d * q * k >= 8G时:
这种情况下,Base Compaction IO与之前的Base Compaction IO情况整体基本相同,
b) 当d * q * k < 8G:
这种情况下,Base Compaction IO会有明显减少,
3.2.3 Cumulative IO写入放大情况:
q*d > 2G时:
q*d < 2G时:
3.4 整体结论:
在 q * d < 2G时,Cumulative IO牺牲了log(2G / q * d)次的写放大,缩减了k - k * q * d / 2G个文件数。
在 k * q * d <= 8G时,Base IO大量减少了写放大。
在 q * d > 2G时,与之前效果一样。
chaoyli commentedon Jul 31, 2020
Sorry, I am not very understand the point of rule and the algorithm.
Can you add me WeChat to discuss it?
WeChat : 15652918147
ZhangYu0123 commentedon Aug 5, 2020
Self-test performance data
base rowset size 10G
Optimized version
Import 2m files every 5s, total 1000 times:
base compaction times = 2, cumulative times = 115
max number of files after cumulative point = 4
max number of files before cumulative point = 16
Import 42m files every 5s, total 100 times:
base compaction times = 2, cumulative times = 80
max number of files after cumulative point = 6
max number of files before cumulative point = 9
original version
Import 2m files every 5s, total 1000 times:
base compaction times = 5, cumulative times = 125
max number of files after cumulative point = 74
max number of files before cumulative point = 12
Import 42m files every 5s, total 100 times:
base compaction times = 3, cumulative times = 100
max number of files after cumulative point = 95
max number of files before cumulative point = 2
morningman commentedon Aug 5, 2020
Nice job. I think this test result can be put into the code comment directly.
[Compaction]Compaction rules optimization (#4212)
[UT][Bug-Fix] Resolve UT memory leak problem (#4406)
[Compaction]Compaction rules optimization (apache#4212)
[UT][Bug-Fix] Resolve UT memory leak problem (apache#4406)