LevelDB 之 Compaction

2019-12-18 13:38:30

好久之前为解决一个 LevelDB 数据膨胀的问题（也就是垃圾数据得不到回收），梳理过一遍 LevelDB 的源码，探究其 Compaction 的机制，以便分析出 LevelDB 垃圾数据不能得以回收的原因，也参考过很多网上的资料，但是都不够系统，所以决定再抽点时间把 LevelDB Compaction 的机制单独梳理总结出来，供学习交流。如果有任何错误和疑问，欢迎交流。

1. LevelDB Write

在分析之前，还是先简单的回顾下 LevelDB 的基本结构，如下图，为 LevelDB 的基本 write 流程。1）数据首先会被写到 log，保证持久性；2）然后写入 mutable memtable 中，返回；3）当 mutable 内存到达一定大小之后就会变成 immutable memtable；3）当到达一定的条件后，后台的 Compaction 线程会把 immutable memtable 刷到盘中 Level 0 中 sstable；4）当 level i 到一定条件后（某个 level 中的数据量或者 sstable 文件数据等）就会和 level i+1 中的 sstable 进行 Compaction，合并成 level i+1 的 sst 文件。

这里先简单的过一下 LevelDB 的基本结构，下面会详细描述每一种 Compaction 的作用和流程。

2. LevelDB Compaction

2.1. Compaction Classification

在 LevelDB 中 Compaction 从大的类别中分为两种，分别是：

MinorCompaction，指的是 immutable memtable持久化为 sst 文件。
Major Compaction，指的是 sst 文件之间的 compaction。

而Major Compaction主要有三种分别为：

（1）Manual Compaction，是人工触发的Compaction，由外部接口调用产生，例如在ceph调用的Compaction都是Manual Compaction，实际其内部触发调用的接口是：

void DBImpl::CompactRange(const Slice begin, const Slice end)

（2）Size Compaction，是根据每个level的总文件大小来触发，注意Size Compation的优先级高于Seek Compaction，具体描述参见Notes 2；

（3）Seek Compaction，每个文件的 seek miss 次数都有一个阈值，如果超过了这个阈值，那么认为这个文件需要Compact。

2.2. Priority

其中这些 Compaction 的优先级不一样（详细可以参见 BackgroundCompaction 函数），具体优先级的大小为：

Minor > Manual > Size > Seek

LevelDB 是在 MayBeScheduleCompaction 的 Compation 调度函数中完成各种 Compaction 的调度的，个判断的就是 immu_ （也就是 immutable memtable）是不是为 NULL，如果不为 NULL，那么说明有 immutable memtable 存在，那就需要优先将其转化为 level 0 的 sst 文件，否则再看是不是 Manual，否则再是PickCompaction() 函数——它的内部会优先判断是不是有 Size Compaction，如果有就优先处理。具体每一种Compact的细节，下面一一展开。

2.3. Minor Compaction

执行条件

Minor Compaction 是将 immutable memtable 持久化为 sst 文件。触发是在 Wirte（如put(key, value)）新数据进入leveldb的时候，会在适当的时机检查内存中memtable占用内存大小，一旦超过 options_.write_buffer_size (default 4M)，就会尝试 Minor Compaction。

新产生出来的sstable 并不一定总是处于level 0，尽管大多数情况下，处于level 0。新创建的出来的sstable文件应该位于那一层呢？由PickLevelForMemTableOutput 函数来计算：

从策略上要尽量将新compact的文件推至高level，毕竟在level 0 需要控制文件过多，compaction IO和查找都比较耗费，另一方面也不能推至过高level，一定程度上控制查找的次数，而且若某些范围的key更新比较频繁，后续往高层compaction IO消耗也很大。所以PickLevelForMemTableOutput就是个权衡折中。

如果新生成的sstable和Level 0的sstable有交叠，那么新产生的sstable就直接加入level 0，否则根据一定的策略，向上推到Level1 甚至是Level 2，但是高推到Level2，这里有一个控制参数：kMaxMemCompactLevel。

核心过程

第1步：将内存中的memsstable格式化成sst文件的格式；

第2步：选择这个新sst文件放置的level，规则如图 2 所示（来自文献 [2]）；

第3步：将新sst文件放置到第2步选出的level中。

2.4. Major Compaction

Major compaction 是将不同层级的 sst 的文件进行合并，目的是将

均衡各个level的数据，保证 read 的性能；
合并delete数据，释放磁盘空间，因为leveldb是采用的延迟（标记）删除；
合并update的数据，例如put同一个key，新put的会替换旧put的，虽然数据做了update，但是update类似于delete，是采用的延迟（标记）update，实际的update是在compact中完成，并实现空间的释放。

如上所述，Major Compaction主要有三种分别为，Manual Compaction，Size Compaction 和 Seek Compaction。

Notes 1:

Manual Compaction之所以被称之为Manual（人工），是因为LevelDB内部自己运行的时候，是不会自动触发调用的。

Notes 2:

Size Compaction优先级高于Seek Compaction，也就是说如果leveldb会先检查，是否有Size Compaction，如果存在，则会执行Size Compaction，并返回，不会继续判断是否存在SeekCompaction。大致的逻辑可以理解为下面的伪代码：

if (size_compaction) {
    //
} else if (seek_compaction) {
    //
} else {
    return NULL;
}

3. Major Compaction

3.1. Manual Compaction

Manual Compaction，是人工触发的Compaction，由外部接口调用产生，例如在ceph调用的Compaction都是Manual Compaction，实际其内部触发调用的接口是：void DBImpl::CompactRange(const Slice begin, const Slice end)。在 Manual Compaction 中会指定的 begin 和 end，它将会一个level 一个level 的分次的Compact 所有level 中与begin 和 end 有重叠（overlap）的 sst 文件。

执行条件

Manual Compation在levelDB的内部并不会触发，只有在外部调用 void DBImpl::CompactRange(const Slice begin, const Slice end)接口时才会触发，也就是说levelDB内部不会自己调用void DBImpl::CompactRange(const Slice begin, const Slice end)接口。这个接口目前估计是提供给外部使用的，例如在ceph中。

核心过程

第1步：遍历level 0到level 6：如果level i存在sst文件和begin和end重合，那么就更新max_level_with_files = level;

第2步：

for (int level = 0; level < max_level_with_files; level++) {
      TEST_CompactRange(level, begin, end);
 }

其中TEST_CompactRange(level, begin, end);将慢慢的Compact掉真个level中所有与begin和end存在重叠（overlap）的sst文件。

Notes 3: 当 begin 和 end 为NULL时，表示尝试 Compact 所有的文件。

3.2. Size Compaction

Size Compaction是levelDB的核心Compact过程，其主要是为了均衡各个level的数据，从而保证读写的性能均衡。

执行条件

levelDB会计算每个level的总的文件大小，并根据此计算出一个score，后会根据这个score来选择合适level和文件进行Compact. 具体的计算方式如下：

对level 0：文件个数阈值kL0_CompactionTrigger = 4，则：

score = level 0的文件总数 / 4

对其他的level，每个level所有文件的总大小的一个阈值：

第0层： 10M（level 0可以忽略，其采用的是文件个数计算score）

第1层： 10M

第2层： 100M

第3层： 1000M （ 1G）

第4层： 100000M （ 10G）

第5层： 1000000M （ 100G）

当然了Level 6就不用算了，它已经是高的层级了，不会存在Compact了。

如果超过这个值，那么：

score = 整个level所有的file size总和 / 此level的阈值

我们会选择score大的level并做标记。会在合适的时机触发。

核心过程

第1步：计算的score值，可以得出 max score，从而得出了应该哪一个 level 上进行 Compact，

第2步：假设上面选出的是 level n，那么第 2 步就是选择出需要 Compact 的文件，其包含两步，首先在 level n 中选出需要 Compact 的文件文件（对应第2.1步）；然后根据level n选出的文件的key的begin和end来选出 level n+1 层的 sst 文件（对应第2.2步）：

第2.1步：确定level n参与Compact的文件列表

2.1.1: 将begin key更新为level n 上次Compact操作的文件的largest key。然后顺序查找level的sst文件，返回个largest key > begin key的sst文件，并加入到level n需要Compact的文件列表中；

2.1.2: 如果是n==0，把sst文件都检查一遍，如果存在重叠则加入Compact文件列表中。因为level 0中，所有的文件之间都有可能存在重叠（overlap）。

第2.2步：确定level n+1参与Compact的文件列表；

2.2.1: 计算出level n参与Compact的文件列表的所有sst文件的总和key范围的begin和end；

2.2.2: 根据2.2.1计算出来的begin和end，去获取根level n+1有重叠（overlap）的sst文件列表；

2.2.3: 计算当前的level n 和 n+1参与Compact的两个文件列表的总和，如果小于阈值kExpandedCompactionByteSizeLimit=50M，那么会继续尝试在level n中选择出合适的sst文件，考虑到不影响理解，具体细节暂时省略。

3.3. Seek Compation

在levelDB中，每一个新的sst文件，都有一个 allowed_seek 的初始阈值，表示多容忍 seek miss 多少次，每个调用 Get seek miss 的时候，就会执行减1（allowed_seek--）。其中 allowed_seek 的初始阈值的计算方式为：

allowed_seeks = (sst文件的file size / 16384);  // 16348——16kb
    if ( allowed_seeks < 100 ) 
        allowed_seeks = 100;

LevelDB认为如果一个 sst 文件在 level i 中总是没总到，而是在 level i+1 中找到，那么当这种 seek miss 积累到一定次数之后，就考虑将其从 level i 中合并到 level i+1 中，这样可以避免不必要的 seek miss 消耗 read I/O。当然在引入布隆过滤器后，这种查找消耗的 IO 就会变小很多。

执行条件

当 allowed_seeks 递减到小于0了，那么将标记为需要Compact的文件。但是由于Size Compaction的优先级高于Seek Compaction，所以在不存在Size Compaction的时候，且触发了Compaction，那么Seek Compaction就能执行。

核心过程

计算 sst 的 allowed_seek 都是在 sst 刚开始新建的时候完成；而每次 Get（key）操作都会更新 allowed_seek，当allowed_seeks 递减到小于0了，那么将标记为需要 Compact 的文件。

4. Done Compaction

实际的 Compaction 执行比较简单

Minor Compaction

Minor Compaction 的 compaction 是将 immutable memtable 转化为 sst 文件。

Major Compaction

Major Compaction 主要是执行 DoCompactionWork 函数。其实就是将多个 sst 文件做归并排序来生成新的sst文件。

Notes

限于作者水平，难免有理解和描述上有疏漏或者错误的地方，欢迎共同交流；部分参考已经在正文和参考文献中列表注明，但仍有可能有疏漏的地方，有任何侵权或者不明确的地方，欢迎指出，必定及时更正或者删除；文章供于学习交流，转载注明出处

参考文献
[1]. Lu L, Arpaci-Dusseau A C, Arpaci-Dusseau R H. WiscKey: separating keys from values in SSD-conscious storage[C]// Usenix Conference on File and Storage Technologies. USENIX Association, 2016:133-148.
[2]. Tags of leveldb. http://bean-li.github.io/tags/
[3]. 那岩. Leveldb实现解析.pdf