1. 什么是 compaction ?

Compaction 顾名思义,就是对 SSTable 文件进行合并,分为两种:

  • Minor Compaction: 把 MemDB 写入到文件系统,生成SSTable
  • Major Compaction: 把 Level N层的一个或多个SSTable与Level N+1层的一个或多个SSTable进行合并,把合并结果写入到Level N+1层的一个或多个文件中。

2. 为什么要进行 compaction ?

2.1 数据持久化

为了提升写入速率,LevelDB 是先把数据写到内存的 MemDB,为了数据持久化,Minor Compaction 会把MemDB作为一个整体,写入 SSTable 文件,这些文件都存放在 Level 0 中。

2.3 提升读取效率

由于用户输入数据的不确定性,Level 0中的 SSTable 是可能会相互重叠的(overlap),如果不做处理的话,查询一个Key时,需要遍历所有的SSTable,这样会导致查询效率很低。因此,需要把Level 0中的数据进行整理,排序之后写入 Level 1,减少查询时需要读取的SSTable数量。

Level 1 的SSTable越来越多之后,每次将 Level 0的文件合并到 Level 1时,需要读取的SSTable 数量、数据量也会越来越大,这样会导致 compaction 越来越慢。因此需要把 Level 1 中的 SSTable 往更高 Level 合并,这样可以减少 Level 1 的数据量。另外,低 Level 的数据是最近写入的,高 Level 的数据是很久之前写入的,根据局部性原理,也可以加快查询速度。

LevelDB 最多有 7 层,Ref: kNumLevels

2.3 整理数据

Compaction 在合并有重叠的 SSTable 时,会把相同 key 的数据进行整理,在频繁修改同一个 key 的场景下,可以减少很多存储空间,也可以加快查询速度,避免读到过期的数据。

3. 什么时候触发 compaction ?

触发 compaction 有三种情况:

  • 情况1: 对于 Level 0: 当文件数大于 4 时,触发 compaction
  • 情况2:对于 Level N (N > 0): 当该 Level 的数据总大小大于 10 ** N MB 时,触发 compaction。也就是,Level 1 10 MB,Level 2 100 MB 以此类推。最后一层没有大小限制。
  • 情况3:对某个 SSTable 的查询次数过多,也就是查了很多次(相同或不同的可以),没有一次命中。

前两种情况,会在每次 compaction 结束时,通过积分的形式来表示。

  • 情况1: score = level 0 文件数量 / 4
  • 情况2:score = level i 数据总大小 / (10 ** i MB)

4. 怎么进行 compaction ?

4.1 选择输入的SSTable

对于满足compaction 的 level,会选取部分SSTable来作为初始的输入文件,优先处理情况1、情况2。

  • 对于情况1、情况2,当积分大于 1 时,就需要 compaction:
    • 对于 Level 0:输入的是第一个 SSTable 文件
    • 对于 Level N (N > 0) :会采用轮转法来选择,也就是上一次compaction处理的最后一个 SSTable的下一个文件,通过记录上一次 compaction 处理的max key来实现。
  • 对于情况3:之前已经记录了,直接将其作为输入

4.2 尝试扩大compaction范围

  1. 记选中的文件在Level i
  2. i==0(图中五角星),则会在其同一层中,找到与其有overlap的其它SSTable,一同作为输入。(图中蓝色虚线框)
  3. 然后会在Level i+1找到与其有 overlap 的其它 SSTable(图中橙色虚线框)。
  4. 最后在不改变Level i+1输入文件数量(橙色框)的前提下,尝试扩大Level i文件数量(图中红色框)。其实就是拿Level i+1被选中的文件,反向去找Level i中与其overlap的文件。

4.2.1 Trivial compaction

有一种特殊情况,就是与 level i + 1 overlap 的文件数量为0,且与level i + 2 overlap的文件数量小于 10 个,此时可以直接把输入的文件从level i 移动到 level i + 1,而不需要进行归并操作。

4.3 多路归并

对于选中的输入,做多路归并。具体实现起来,就是创建多个迭代器,按序从多个迭代器中取出数据,写入新文件,放到Level i+1层中。由于单个SSTable有大小限制,默认2MB。因此在合并过程中,可能会产生多个新的 SSTable(图中黄色部分)。

怎么处理更新数据或者是删除数据呢?其实遍历的时候都是按从大到小的seq顺序来遍历key的:

  • 对于删除:
    • 如果更高层没有相同的 key 了,则直接删了
    • 如果有,则还需要写入 del key 到 SSTable 中,等 compact 到更高层后,再从 SSTable文件中删除
  • 对于更新:
    • 直接写入新值,旧值略过

新的SSTable 写完之后,需要删除作为输入的那些SSTable,当然不是立即删除,由于Snapshot的存在,只是把这些文件的引用计数减1,待引用为0后,再进行删除。

(完)

绘图文件 goleveldb-sstable.drawio

References: