以RocksDB为存储引擎的MyRocks是近几年流行起来的MySQL分支，在Facebook等公司广泛使用，网易杭研的数据库内核团队从2018年初开始系统研究MyRocks，目前已在内部进行小范围推广使用，效果比较理想。

在调研、测试和试用期间，积累了一些经验，包括技术实现等。本系列想跟大家分享我们组内小伙伴做的LevelDB调研输出，这是第四篇，详细介绍LevelDB Compaction机制。

第三篇链接：

温正湖：LevelDB设计与实现 - 缓存机制zhuanlan.zhihu.com

Compaction

LevelDB Compaction分两种：

minor compaction
major compaction

以下三个条件满足一个即可发起Compaction：

imm_ != NULL 表示需要将Memtable dump成SSTable，发起Minor Compaction。
manual_compaction_ != NULL 表示手动发起Compaction。
versions_->NeedsCompaction函数返回True。

先介绍minor compaction，minor compaction即immutable memtable dump成sstable文件。无论是哪一种compaction,入口点都是：

  DBImpl::MaybeScheduleCompaction()

minor compaction主要做两件事情：1、构造sstable2、新的sstable文件写入哪一层。主要函数调用流程如下图：

新产生出来的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。判断sstable文件之间key是否有重叠要用到前面介绍的数据结构FileMetaData。

除了minor compaction,另外一种compaction就是major compaction。那什么情况下发起major compaction呢？看下面这个函数：

  bool NeedsCompaction() const {
    Version* v = current_;
    return (v->compaction_score_ >= 1) || (v->file_to_compact_ != NULL);
  }

文件数目太多或者某一层级文件总大小过大，会触发compaction

如果某一层级文件的个数太多（指的是level0），或者某一层级的文件总大小太大，超过门限值，则设置v->compaction_score为一个大于1的数。如果存在某个或者某几个层级的score大于等于1，选择score最高的那个level。

seek次数太多，触发compaction

还有一种情况也可能会引起Compaction，就是某个文件seek的次数太多。除了level 0以外，任何一个level的文件内部是有序的，文件之间也是有序的。但是level（n）和level（n＋1）中的两个文件的key可能存在交叉。正是因为这种交叉，查找某个key值的时候，level（n）的查找无功而返，而不得不去level(n＋1)查找。

我们考虑寻找某一个key，如果查找level(n) ,但是没找到，然后去level(n+1)查找，结果找到了，那么对level (n)的某个文件而言，该文件就意味着有一次未命中。

我们可以很容易想到，如果查找了多次，某个文件不得不查找，却总也找不到，总是去高一级的level，才能找到。这说明该层级的文件和上一级的文件，key的范围重叠的很严重，这是不合理的，会导致效率的下降。因此，需要对该level 发起一次major compaction，减少 level 和level ＋ 1的重叠情况。

这就是所谓的 Seek Compaction。

对于seek触发的compaction, 哪个文件无效seek的次数到了阈值，那个文件就是level n的参与compaction的文件。而size 触发的compaction稍微复杂一点，它需要考虑上一次compaction做到了哪个key，什么地方，然后大于该key的第一个文件即为level n的参与compaction的文件。

对于n >0的情况，初选情况下level n的参与compaction文件只会有1个，如果n＝0，因为level 0的文件之间，key可能交叉重叠，因此，根据选定的level 0的该文件，得到该文件负责的最小key和最大key，找到所有和这个key 区间有交叠的level 0文件，都加入到参战文件。

未完待续。。。

ITPub博客

LevelDB设计与实现 - Compaction

最新文章