leveldb笔记之13:minor compaction

#leveldb

level笔记开篇里,提到过Compaction这个过程,这是 leveldb 中最为复杂的一部分,从这篇笔记开始,介绍下 Compaction.

compaction 分为两种:minor compaction 和 major compaction. minor compaction 相对简单一些,对应了MemTable持久化为sstable的过程。

1. 简介

DBImpl定义了两个MemTable:

  MemTable* mem_;
  MemTable* imm_ GUARDED_BY(mutex_);  // Memtable being compacted

size of mem_ <= options_.write_buffer_size时,数据都会直接更新到mem_。超过大小后,mem_转化为imm_

      imm_ = mem_;//mem_大小超过4M,因此转化为imm_
      has_imm_.Release_Store(imm_);
      mem_ = new MemTable(internal_comparator_);//重新new一个新的mem_供更新

imm_全称是 immutable memtable,只读状态,leveldb 会有一个后台线程负责将imm_持久化到磁盘,成为 level 0 的 sst 文件,同时更新一些版本信息(版本的概念会在另外的笔记介绍)、文件清理等。

整个过程完成后,就可以重新设置imm_ = nullptr;,当mem_大小再次达到阈值,循环这个过程。

如果 minor compaction 耗时较长,会直接导致mem_过大无法写入但是又无法转化为imm_,因此对 minor compaction 最重要的原则是:

高性能的持久化

2. 源码

整个过程的入口函数

//实际Compact
void DBImpl::BackgroundCompaction() {
  mutex_.AssertHeld();

  //如果immutable memtable存在,则本次先compact,即Minor Compaction
  if (imm_ != nullptr) {
    CompactMemTable();
    return;
  }

  ...
  // major compaction

可见 minor compaction 是高优于 major 的。

2.1. 整体流程

CompactMemTable主要流程分为三部分:

  1. WriteLevel0Table(imm_, &edit, base)imm_落盘成为新的 sst 文件,文件信息记录到 edit
  2. versions_->LogAndApply(&edit, &mutex_):将本次文件更新信息versions_,当前的文件(包含新的 sst 文件)作为数据库的一个最新状态,后续读写都会基于该状态
  3. DeleteObsoleeteFiles:删除一些无用文件

2.2. WriteLevel0Table

首先顺序生成 sstable 的编号,用于文件名

meta.number = versions_->NewFileNumber()

iter用过遍历 MemTable,通过BuildTable将数据写入到 sstable,该函数实际上就是调用了TableBuilder.

    mutex_.Unlock();
    //更新memtable中全部数据到xxx.ldb文件
    //meta记录key range, file_size等sst信息
    s = BuildTable(dbname_, env_, options_, table_cache_, iter, &meta);

接下来通过meta选取合适的 level,注意虽然函数名字是WriteLevel0Table,但是新生成 sstable,并不一定总是会放到 level 0,例如如果 key range 与 level 1层的所有文件都没有 overlap,那就会直接放到 level 1。PickLevelForMemTableOutputVersion的接口,后续笔记专门介绍 leveldb 的版本,这里的作用就是返回一个该 sstable 即将放入的 level,加上meta里的文件信息,统一记录到edit.

  int level = 0;
  if (s.ok() && meta.file_size > 0) {
    const Slice min_user_key = meta.smallest.user_key();
    const Slice max_user_key = meta.largest.user_key();
    //为新生成sstable选择合适的level(不一定总是0)
    if (base != nullptr) {
      level = base->PickLevelForMemTableOutput(min_user_key, max_user_key);
    }
    //level及file meta记录到edit
    edit->AddFile(level, meta.number, meta.file_size,
                  meta.smallest, meta.largest);
  }

2.3. LogAndApply

edit应用到版本信息里记录

  // Replace immutable memtable with the generated Table
  if (s.ok()) {
    edit.SetPrevLogNumber(0);
    edit.SetLogNumber(logfile_number_);  // Earlier logs no longer needed
    //应用edit
    s = versions_->LogAndApply(&edit, &mutex_);
  }

2.4. DeleteObsoleteFiels

新的版本信息生成后,会有一些不再需要的文件,通过DeleteObsoleteFiles选出并且删除。

  if (s.ok()) {
    // Commit to the new state
    imm_->Unref();
    imm_ = nullptr;
    has_imm_.Release_Store(nullptr);
    DeleteObsoleteFiles();
  } else {
    RecordBackgroundError(s);
  }

这就是一个完整的 minor compaction过程,通过 minor compaction,内存里的 memtable 源源不断的转化为磁盘上的 sst 文件,正如前面强调的这一过程最重要的原则,就是高性能的写转化。因此并没有考虑不同文件间数据的重复和顺序,当读取数据时,总是需要读取 level 0 所有的文件,因此对读并不友好。major compaction就是为了解决这一问题,不断的把上层的 sst 文件通过二路归并转化为下层的 sst 文件。

从 compact 里,就开始引入 leveldb 里版本的概念了,minor compaction 过程相对简单一些,因此,接下来一篇笔记,开始从上面提到的版本的各个接口,介绍 leveldb 里的版本的设计思想。