kudu之Compaction 策略设计原理

曾经终败给现在 2022-01-22 00:25 307阅读 0赞

本文档讲解了执行Compaction的策略。有关如何实现Compaction的详细信息，请参阅[kudu之Compaction 设计原理][kudu_Compaction]。

Compaction策略的功能是定义如何选择一组rowset进行压缩。为了减少DiskRowSets的数量，我们需要对它们进行压缩，从而提高tablet的整体性能。

良好的Compaction策略需要在以下几个目标之间做权衡：

1.  重新安排物理布局，以便更高效地进行后续操作。
2.  压缩操作本身不会占用太多资源。
3.  需要保证压缩操作能够顺利执行-随着时间做增量压缩，这样使得操作的性能可预测且稳定

以下小节将对上述目标进行分析：

# 压缩带来的好处 #

为了确定良好的压缩策略，我们需要为tablet中的一组RowSet定义一些指标。考虑以下一组RowSet：

1     2      3     4    5
    |--A--||-B--||--C--||---D----|
    |--------------E-------------|
                       |-F--|

入上图所示，key空间从左到右跨越，每个RowSet基于其第一个和最后一个包含的key绘制了一个区间。我们将在本文档中定义一些术语供以后使用：  
**宽度**  
RowSet的宽度代表它占key空间的百分比。例如，rowSet E的宽度为1，因为它跨越整个tablet。rowSet B的宽度为0.2，因为它的key 空间占整个tablet的20％。

请注意，宽度也代表随机读取落在该RowSet中的概率。

**高度**  
tablet中某个key的高度是指key范围包含该key的rowset个数。例如，key1的高度为2，因为rowset A和E都有包含该key。key4的高度为3，因为D，E和F包含该key。

key的高度代表随机读取该key时必须查阅的RowSet数。

让我们考虑tablet上各种操作的花费：

## 插入 ##

为了插入，必须检查每个rowkey的重复键。通过将rowset范围存储在区间树中，我们可以有效地确定那些可能包含要插入的key的rowset，因此插入操作的花费与包含该key的rowset个数是线性关系：

Let n = the Height of the tablet at the given key
    Let B = the bloom filter false positive rate
    Let C_bf = cost of bloom filter check
    Let C_pk = cost of a primary key lookup
    Cost = n*C_bf + n*B*C_pk
    Cost = n(C_bf + B*C_pk)

通常，B约为1％或更低，因此bloom filter 检查主导该等式。但是，在主键列非常大的某些情况下，每次主键检查都会产生磁盘搜索，这意味着C\_pk高于C\_bf（我们期望在RAM或SSD中）的数量级。因此，我们不能完全忽略由bloom filter 未命中情况的消耗。

## 随机读取 ##

随机读取的消耗与插入成本类似：给定已知key，必须查询每个可能重叠的rowset。

## 短扫描 ##

扫描无法使用bloom filter，因此成本与上述类似，只是所有重叠的rowset必须由PK查找：

Cost = n*C_pk

我们假设短扫描是在找到开始键之后的IO耗时与搜索成本相比较小的扫描。（例如，假设10ms的寻找时间，1MB或更少的连续IO）。

## 长扫描（例如全表扫描） ##

长扫描可能会从许多rowset中检索数据。在这种情况下，rowset的大小起作用。

设S =在扫描范围内rowset大小（单位MB） B =磁盘带宽（MB / sec）n =访问的rowset个数，如前所述

假设访问每个rowset需要1次搜索（相同C\_pk）。

Cost = n*C_pk + S/B

综上所述，所有操作成本在很大程度上取决于必须访问的rowset的数量。因此，为了最大限度地降低成本，我们应该遵循以下策略：

*  在查询（插入和随机读取/短扫描）的情况下，合并在key空间有重叠的rowset，从而降低tablet的平均高度。
 *  长扫描的情况下，将多个rowset合在一起以提高顺序IO与搜索的比率。

我们可以假设，只要rowset相当大，当rowset达到大约10MB左右的顺序IO（1个搜索〜= 10毫秒，10MB IO~ = 100毫秒）后，上面的目标＃2的收益递减。但是，目标＃1具有线性回报，因此我们关注目标＃1。

# 进行压实的成本 #

根据以上分析，tablet的最佳配置是跨越整个key空间的单个巨型rowset。这是直观的：完全压缩的tablet将发挥最佳性能，因为每次访问最多只需要一次bloom filter检查和一次搜索。

但是，在每次压缩中简单地压缩所有RowSet显然不是最佳选择。这将是低效的，因为每次压缩都会重写整个行集，导致巨大的写入放大和IO消耗，仅获得少量的效率增益。

因此，我们不仅要考虑生成的tablet的效率，还要考虑执行压缩的成本。只有这两者间做权衡，我们才能决定在任何给定时间点执行的最佳压缩。

出于分析的目的，我们将压缩的成本简单地视为压缩执行的IO的总和。我们假设删除很少，在这种情况下，压缩的输出数据大小大约等于输入数据大小。我们还假设压缩输入足够大，以至于IO耗时超过了所需的任何搜索。

因此，执行压缩的成本是O（输入大小）。

# 增量工作 #

压缩的第三个目标是能够增量执行。进行频繁的增量压缩而不是偶尔的大压缩，可以为最终用户提供持续的性能分析。增量工作还有利于系统更快地对工作负载的变化做出反应：例如，如果key空间的一个区域变热数据，我们希望能够在短时间内快速响应并压缩该区域的数据。

实现此目标的一种方法是限制任何给定压缩将读取和写入的数据量。将此数据限制在几百MB的范围内意味着压缩可以在10秒或更短的时间内发生，从而允许快速响应工作量的变化。

# 提出策略 #

## 限制RowSet大小 ##

压缩策略的第一个关键点是将RowSet的最大大小限制为相对较小的容量 - 例如64MB或者更小。这可以通过修改DiskRowSet的writer代码来实现，在数据量达到阈值后创建一个新的rowSet来容纳数据。因此，即使从内存中刷新较大的数据集，也可以限制磁盘上的rowkey大小。

## 刷新出来的rowset需要有大小限制 ##

例如，假设最大rowset大小设置为64MB，并且在刷新之前在MemRowSet中累积了150MB的数据。得到的刷新输出如下所示：

A       B     C
    |------||------||--|
      64MB    64MB  22MB

请注意，即使最大DiskRowSet大小为64MB，第三个刷新的行集也可能会更小。将来，我们可以估算刷新到磁盘后的数据大小，并尝试使三个RowSet大小相等，但这种做法并不是必须的。

## 压缩的输出rowset也要限制大小 ##

现在想象一下另一种场景，其中Tablet会刷新几次，每次都会产生跨越整个键space的小rowset -这种场景通常在均匀的随机插入看到。在3次刷新后，tablet看起来像：

A (50MB)
    |-------------------|
           B (50MB)
    |-------------------|
           C (50MB)
    |-------------------|

由于三个rowset范围重叠，因此对tablet的每次访问都必须查询每个rowset（即平均rowset“高度”为3）。如果压缩策略选择这三个RowSet进行压缩，则压缩结果将如下所示：

D       E     F
    |------||------||--|
      64MB    64MB  22MB

实质上，压缩将重叠rowset的数据重组为相似大小的非重叠rowset。这将平均高度从3降低到1，从而提高了tablet的性能。

## 处理大量的rowset ##

由于这些每个rowset的大小限制，正常大小的tablet（例如20GB）将具有数百个RowSets。为了有效地确定可能包含给定查询key或key范围的RowSet集，我们必须更改Tablet代码以将RowSet存储在区间树中而不是简单列表中。区间树是一种数据结构，它为与给定查询点或查询范围重叠的区间集提供有效查询。

## 压缩选择策略的思考 ##

为了方便说吗，假设现在所有RowSet都具有完全相同的大小。然后，我们可以基于一个简单的因素将RowSet分类为“好”或“坏”：跨越的key空间范围越小越好。假设现在有一批数据在插入，每个刷新的RowSet将跨越整个Tablet的key空间 - 一次这个rowset将会被每个查询访问。一旦有多个这样的RowSet（图中的A，B和C），压缩它们会产生更精细的rowsetD，E和F.

直观地说，一个好的压缩策略会找到宽且重叠的行集，并将它们压缩在一起，从而产生宽度小且不重叠的行集。

考虑到上面开发的成本因素，我们可以将压缩对象的选择视为优化问题：在给定的IO预算下尽可能地降低Tablet配置的成本。

根据上面的分析，单个读取或插入的成本与被访问的key的“高度”是线性关系的。因此，平均操作成本可以通过在key空间中整合tablet高度来计算，或者等效地累加所有RowSet的宽度。例如：

|---A----| (width 10)
         |-----B-------| (width 15)
    |-C-||-----D-------| (width 5, width 15)
    |--------E---------| (width 20)

总宽度 = 20+5+15+15+10 = 65.  
假设我们选择压缩上面的rowsetA，B和D，从而产生以下输出：

|-C-||-F-||-G-||-H-| (width 5, width 5, width 5, width 5)
    |--------E---------| (width 20)

请注意，总字节数没有改变：我们只是将字节重组为更紧凑的形式，从而降低了tablet的平均高度。

现在总计的成本是40.因此，压缩后优化了25，在3个IO单位的预算下（请记住，对于此分析，假rowset是恒定大小）。

压缩的另一个选择可能是压缩B，D和E，结果如下：

|---A----| (width 10)
    |-C-|                (width 5)
    |---F--||--G--||-H-| (width 8, width 7, width 5)

这种压缩将tablet的成本从65降低到35 - 所以它优化了30，使用了3个相同的IO预算。

由于第二个压缩选择，在使用相同的预算情况下，更多地降低了tablet的高度，因此它是更优化的解决方案。

## 数学分析 ##

压实带来的成本降低是很容易计算：

成本变化=总和（原始rowset宽度） - 总和（输出rowset宽度）

我们知道输出rowset根本不会重叠，并且它们的总宽度将跨越输入rowset范围的并集。因此：

成本变化=总和（原始rowset宽度） - （原始rowset的并集宽度）

请注意，对于此分析，key范围被视为整数。通过将字符串数据视为无符号整数，可以以简单的方式将其扩展为字符串key。

## 压缩选择策略的算法 ##

For each pair of rowsets (A, B):
      Evaluate BestForPair(A, B):
    
    BestForPair(A, B):
      Let union width = max(A.max_key, B.max_key) - min(A.min_key, B.min_key)
      Determine the subset R of rowsets that are fully contained within the range A, B
      Evaluate PickRowsetsWithBudget(R, N):
      Set objective = sum(rowset width) - union width
      If objective > best objective:
        best solution = this set
    
    PickRowsetsWithBudget(R, N):
     Choose the N rowsets in R which which maximize sum(rowset width)

这个算法没看懂，比较疑惑的地方是A,B表示什么？后续如果在kudu源码中得到答案会回来补充，或者哪位大神可以在评论中指导一下。

[kudu_Compaction]: https://blog.csdn.net/qqqq0199181/article/details/90770378