LevelDB剖析(5): Compaction

Compaction是LevelDB的特色所在,其本质是一种内部数据重整机制,而非外部功能接口(用户也可以主动要求发起). 在本系列开篇文章中已经介绍过了Compation操作的背景和分level组织数据的原因,本文就LevelDB中考虑的其他细节问题再来集中整理下.

一、Compaction的目的
1) memtable dump,是table文件的最初来源,并且也相对独立,因此也归到Compaction线程的工作里.
2) 顾名思义,进行冗余数据的合并,控制数据量. 例如某个key更新了10次后最后delete,那么最终这11条记录都可清理掉.
3) 除最高level外,控制每个level_n下的文件大小和数量,防止其过大导致level_n-1的table与其有太多交集文件.

二、何时进行Compaction
首先如果memtable满了则要尽快dump到level_0,否则可能会阻塞后续Write操作.

对level_0的文件来说,由于最坏情况下所有文件都有相互有交集,查询level_0时最多要查所有文件,因此必须严格控制文件数量,比如level_0的table到了4个就启动Compaction,这样level_0一般不会超过4个.

对level_1及以上来说,Get最多只会到1个sstable中进行查找,因而主要问题转为考虑Compaction本身的IO开销控制(与Get查索引不同,Compaction要遍历所有输入文件的内容并做归并输出),例如我们期望控制level_n的某个tableA文件在与level_n+1中的文件进行合并时,level_n+1的输入文件总大小最多不超过10倍tableA本身的大小,为了保证这一点,我们可以在生成tableA的时候就进行控制,在tableA与level_n+1有过多交集之前就提前Finish,影响就是tableA可能写不满2M的阈值大小,level内文件数也会变多. 再认规定level_1最大10M,那么按照10倍的关系,level_2最大100M, level_3最大1G... 从而导出这样一条规则:对level_n(n>=1),当文件总大小超过(10^n) M时,意味着该level容量已满,应启动Compaction.

所以对level_1及以上可以定期检查每个level的总大小,超过阈值则触发Compaction. 但事实上level_n唯一增长的来源是来自level_n-1的Compaction归并,所以可以在每次Compaction完成之后再重新做检查即可,如果仍然有超过阈值的level则发起下一轮Compaction.

至此看上去都较为合理的,但假如完全按照阈值条件触发,那么数据将严格逐level下沉,即只有当level_n满时,level_n+1才会开始产生数据,而且此时level_1到level_n都是满的,这时假设level_0触发了新的Compaction,则从level_1到level_n全部都要做一次Compaction,因为大家都满了,而数据只能逐层流动,所以导致集中大量IO,影响系统性能. 1个优化是如果level_0产生的新数据与level_1到level_n都没有交集的话,可以直接移到level_n+1,不需要任何IO,但这个条件比较苛刻. 更根本的解法是,不用严格按照逐level填充的方式,即使level_n未达到阈值,只要其中某个文件tableA与level_n+1的部分文件存在key范围交集,就可以考虑在合适的时机触发tableA的Compaction,达到错峰、在时间上均摊IO的目的(多个level同时满的概率大大减小了). 从而又引出了下面2个问题:
a) 怎样发现适合做Compaction的文件
b) 具体在什么时机对此文件进行Compaction.

对问题 a)我们可以对单个key进行取样探测,例如每次Get(key)完成后,假如最终是在某个sstable文件中查到的,那么我们拿着这个key去next level的各个文件看下是否相交(在其key域值范围内)即可. 因为DB元数据中保存了每个level每个文件的beginKey和endKey,而且level0以上文件之间又是有序的,因而该操作开销很小;类似的在用户做Iterate遍历操作时也可以做类似的采样. 对问题 b),LevelDB通过平衡Compaction操作和读取操作的开销来决定这个时机点,即假如发现了这么一个文件A,但A的实际读取次数比较小,那么专门针对其做Compaction的必要性不大,反而因为Compaction带来了额外的开销;假如统计到A的读取次数比较大,那么就有必要考虑了,因为Compaction至少可以在当前level消除掉A,从而消除因A与下层level相交这一事实带来的潜在综合开销,因此LevelDB这样决定:假如读取A文件M次的开销相当于对A做Compaction的开销,那么当统计到A被读取了M次后,就启动对A的Compaction. 因此table文件信息中除了基本的文件大小、keyspace等字段,还有一个allowed_seek字段,就是用于计算并存储M值. 我们来看该字段赋值的地方:


struct FileMetaData {
  int refs;
  int allowed_seeks;          // Seeks allowed until compaction
  uint64_t number;
  uint64_t file_size;         // File size in bytes
  InternalKey smallest;       // Smallest internal key served by table
  InternalKey largest;        // Largest internal key served by table
}

...
{
    // Add new files
    for (size_t i = 0; i < edit->new_files_.size(); i++) {
      const int level = edit->new_files_[i].first;
      FileMetaData* f = new FileMetaData(edit->new_files_[i].second);
      f->refs = 1;

      // We arrange to automatically compact this file after
      // a certain number of seeks.  Let's assume:
      //   (1) One seek costs 10ms
      //   (2) Writing or reading 1MB costs 10ms (100MB/s)
      //   (3) A compaction of 1MB does 25MB of IO:
      //         1MB read from this level
      //         10-12MB read from next level (boundaries may be misaligned)
      //         10-12MB written to next level
      // This implies that 25 seeks cost the same as the compaction
      // of 1MB of data.  I.e., one seek costs approximately the
      // same as the compaction of 40KB of data.  We are a little
      // conservative and allow approximately one seek for every 16KB
      // of data before triggering a compaction.
      f->allowed_seeks = (f->file_size / 16384);
      if (f->allowed_seeks < 100) f->allowed_seeks = 100;

      levels_[level].deleted_files.erase(f->number);
      levels_[level].added_files->insert(f);
    }
}

该段代码在每次Compaction完成后更新DB元数据时被调用,主要目的之一就是为Compaction产生的新文件的allowed_seek赋值,推导过程见注释,最后得出结论:seek一次相当于Compact 16K数据,故allowed_seeks = file_size / 16K. 那么还需要一种统计更新机制,只要seek一次并且有交集就--allowed_seeks,当其为0时便触发Compaction,前面说的读后取样机制正好可以用上,即Get(key)、Iterate等操作有可能触发Compaction.

综上,总结下Compaction的时机,并按照优先级排序:
1) memtable满,立即dump为level_0文件
2) level_0文件数量超过某个阈值如4个
3) level_n(n>=1) 的总大小达到(10^n)M
4) 某个与下层level有交集的文件达到了最大seek次数限制 (allowed_seek == 0)

对于2)和3),还存在具体选择哪个table进行Compaction的问题,LevelDB的策略是在整个level的keyspace内轮转,记录了上一次Compact的文件的最大key,下一次则选择在此key之后的首个文件.

三、Compaction过程和优化
对于memtable dump的情况比较简单,遍历SkipList直接落地为单个level_0 table即可.

对某level_n内某table文件 A进行Compaction的基本过程如下:
1) 将A加入输入文件列表
2) 如果n==0,则获取level_0中所有与A相交的其他文件,加入输入文件列表
3) 在level_n+1中找出与现有输入列表中的文件有交集的文件,并加入输入文件列表.
4) 打开输入列表的每个文件,按key顺序遍历key-value记录并合并输出到新table文件,在以下条件满足时结束当前table,并新建另一个table继续输出:
a) 当前输出table达到了sstable大小阈值如2M
b) 当前输出table与level_n+2的数据交集达到了20M (即10倍于A自身)
5) 所有输入文件遍历完成,得到一系列新的level_n+1 table列表.
只有一个Compaction线程,如果存在多个Compaction任务则需排队等待.

基于上述流程框架,LevelDB做了以下几点优化:
1) 扩充输入集合,即在上述3)完成后反过来看下level_n还有没有文件可以加入到输入列表而不影响level_n+1的输入文件.
2) 如果level_n+1中没有相交的文件,则不用真正发起IO,而仅需简单更新一下元数据指向将A归到level_n+1即可.
3) memtable dump时,如果发现level_0中与新数据无交集,则试图直接dump到level_1甚至level_2.
4) 由于memtable dump的优先级最高,但普通Compaction的过程可能比较长,因此在普通Compaction过程中允许随时插入memtable的dump,保证其优先响应. 具体就是每遍历一个key就去检查下当前是否存在待dump的immutable memtable.
5) 对userKey相同的冗余数据进行清理,但要保留当前用户还有在使用的旧的SnapShot数据.

3)的理由:

// Maximum level to which a new compacted memtable is pushed if it
// does not create overlap.  We try to push to level 2 to avoid the
// relatively expensive level 0=>1 compactions and to avoid some
// expensive manifest file operations.  We do not push all the way to
// the largest level since that can generate a lot of wasted disk
// space if the same key space is being repeatedly overwritten.
static const int kMaxMemCompactLevel = 2;

优化2)示意图:

leveldb_trivialmove

相关代码较多这里就不展开了,里面涉及较多计算key相交范围的操作,关键的一点就是尽量利用key的有序性,能二分查找的地方就不遍历查找,以提高效率;另一点是对record的遍历操作使用了组合Iterator的模式,使得代码结构清晰,后面会专门介绍LevelDB中Iterator的使用.

四、Compaction收场
一轮Compaction结束后还有些重要的收尾工作:
1) Compaction带来的元数据变更信息写入manifest.log,同时更新内存中元数据信息.
2) 删除无用文件. 不能直接删除所有旧的table因为用户可能还在使用(如正在遍历某个Snapshot).
3) 通知可能正在等待Compaction完成的其他对象,如数据库关闭例程.

五、用户写行为的影响
从Compaction和Level的数据组织可以看到,用户写入key的模式对DB整体性能都有较大影响,具体来说就是Locality原则,如果可能,尽量按照key的顺序来更新DB,即把相近的key集中在一起提交,这样产生的table文件keyspace比较紧凑,无论查询还是Compaction过程中涉及的文件数量和数据量都比随机写产生的LevelDB要小很多。

例如,假设有一批初始数据需要导入DB,我们可以先按key排序再写入DB,这样在导入过程中Compaction过程每次都是Trival Move,因为后写入的数据与前面的数据没有key交集;如此导入完成后DB的整体紧凑程度很高,无论是后续查询还是写入或者合并等操作产生的IO都比较小,性能高.

发表评论

电子邮件地址不会被公开。