[GitHub] [incubator-doris] ZhangYu0123 edited a comment on issue #4164: [Proposal] Compaction rules optimization

[GitBox <gi...@apache.org>]

ZhangYu0123 edited a comment on issue #4164:
URL: https://github.com/apache/incubator-doris/issues/4164#issuecomment-663071982


   ### 问题描述
    目前，在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：
   - 当前rowset是非overlap类型，
   - rowset磁盘空间大于base版本的2%或大于等于2G，
   ### 2.2 选取Cumulative Compaction要合并的Rowset
   ### 2.2.1 候选集candidate_rowsets收集，(与原流程一致)
   - 候选集选择先大于等于Cumulative Point所有版本。并进行排序。
   - 从候选集中收集要合并rowset版本，当compaction_score大于等于1000或遍历到最后时停止收集。
   - 当candidate_rowsets存在删除条件时，收集删除之前的版本。将Cumulative Point移动到删除rowset之后。
    ### 2.2.2 创建input_rowsets (调整部分)
    **定义：**
   - 当候选集candidate_rowsets磁盘总数s_total，
   - 候选集candidate_rowsets中第一个版本的磁盘空间s1。
   - level_size（n）表示n到能够映射到的磁盘大小分段[1G~2G) , [512m~1G), [256m~512m), [128m~256m), [64m~128m)
   
   **执行过程：**
   - 当s_total大于等于base版本的2% 或者大于等于2G或者s_total <= 64m，candidate_rowsets直接赋值给input_rowsets，退出。
   - 当level_size (s_total - s1) >= level_size (s1) 时，candidate_rowsets直接赋值给input_rowsets，退出。
   - 当level_size (s_total - s1) < level_size (s1)  时，candidate_rowsets去掉第一个版本后，回到第一步，循环该流程。
   
   ### 2.2.3 检查input_rowsets，(与原流程一致)
   - 当input_rowsets的compaction_score小于最小分数5时，input_rowsets清空，不合并。
   - 检查input_rowsets为空时，按时间补充检查，大于1天未执行合并，并且candidate_rowsets中有overlap类型的rowset时，candidate_rowsets直接赋值给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的对数个文件。如下表所示
   ![image](https://user-images.githubusercontent.com/67053339/88304370-bfed0400-cd3a-11ea-840d-1b9d66042a75.png)
   
   ### 3 前后对比
   这里包括了base compaction和cumulative compaction。假设每次导入文件大小为d，经过q轮导入后执行一次cumulative compaction，经过k次cumulative compaction后执行一次base compaction。共执行n次d的导入。这里假设k大于4
   
   ### 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次数 p = n / (k * q)
          Base IO 写入数据量 = d * q * k * p * (p + 1) / 2 = d * n * (n + k * q) / k * q
   
   这种情况下，Base Compaction IO与之前的Compaction IO情况整体基本相同，
   
   b)	当d * q * k < 8G，数据量小于100G时：
   
          Base Compaction次数 p = log(1 + 8%)(n) ，这里不依赖于次数k
          Base IO 写入数据量 = d(1-n/1.08) / (1-1.08) = 18.51 * n * d – 20d
   
   这种情况下，Base Compaction IO是O(n) 级别的，明显优于之前的O(n2)的情况。这里的8% 是由于base compaction限制当大于5个版本(包括了base)时进行合并，这里按最坏情况评估。
   
   c)	当d * q * k < 8G，数据量大于100G时：
   
          Base Compaction次数 p = n * d / 8G
          Base IO写入数据量 = 8G * p (p + 1) / 2 = d * n * (n+ d/8G) / 2 * (d / 8G)
   
   这种情况下，Base Compaction IO与之前的Compaction IO情况整体基本相同。会带来8G/(d * q * k) 倍的提升。
   
   ### 3.2.3 Cumulative IO写入放大情况：
   q*d > 2G时：
   	
              Cumulative IO写入数据量 = n * d
   
   q*d < 2G时：
   	
              Cumulative IO写入数据量 =（log（2G / q * d）+ 1）* n * d
   
   
   ### 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时，与之前效果一样。 
   
   
   


----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org