LevelDB的compaction操作

leveldb源码分析4

对于leveldb来说，写入记录操作很简单，删除记录仅仅写入一个删除标记就算完事了，但是读取记录比较复杂， 需要在内存以及个层级文件中依照新鲜程度依次查找，代价很高。为了加快读取速度，leveldb采取了 compaction的方式对已有记录进行整理压缩，通过这种方式，来删除掉一些不再有效的KV数据，减小数据规模，减少文件数量等

leveldb的Compaction机制和过程与Bigtable的基本一致，Bigtable中讲到三种类型的Compaction：minor，major和full。所谓minor Compaction，就是把MemTable中的数据导出到SSTable文件中；major Compaction就是合并不同层级的SSTable文件，而full Compaction就是将所有SSTable进行合并。

leveldb包括其中的两种：minor和major。

先看minor Compaction，当内存中的MemTable大小到了一定值时，将内容保存到磁盘文件中：

major Compaction：

DBImpl::MaybeScheduleCompaction()

这是主线程主动触发compact，db_impl.cc652行：

void DBImpl::MaybeScheduleCompaction() {
  mutex_.AssertHeld();
  if (background_compaction_scheduled_) {
    // Already scheduled
  } else if (shutting_down_.Acquire_Load()) {
    // DB is being deleted; no more background compactions
  } else if (!bg_error_.ok()) {
    // Already got an error; no more changes
  } else if (imm_ == nullptr &&
             manual_compaction_ == nullptr &&
             !versions_->NeedsCompaction()) {
    // No work to be done
  } else {
    background_compaction_scheduled_ = true;
    env_->Schedule(&DBImpl::BGWork, this);
  }
}
  1. 如果compact已经运行或者db正在退出，直接返回
  2. 检查当前的运行状态，确定是否需要进行compact，如果需要，则触发后台调度compact(Env::Schedule())，否则直接返回
  3. 做实际的compact逻辑(DBImpl::BackgroundCompaction())，完成后，再次触发compact(主线程将任务如队列即返回)

主动触发compact的情况

  • db启动时，恢复完毕，会主动触发compact
  • 直接调用compact相关的函数，会把compact的key-range指定在manual_compaction中
  • 每次进行写操作检查时(DBImpl::MakeRoomForWrite())，如果发现MemTable已经写满并且没有immutable MemTable，会将MemTable置为immutable MemTable，生成新的MemTable，同时触发compact
  • get操作时，如果有超过一个SSTable文件进行了IO，会检查做IO的最后一个文件是否达到了compact的条件(allowed_seek用光)，达到条件，则主动触发compact

需要compact的运行状态

  • 存在immutable MemTable
  • 函数直接调用了compact相关的接口，manual_compaction中指定了要compact的key-range
  • level存在不均衡或者有明确需要compact的SSTable文件(VersionSet::NeedsCompaction VersionSet::current_::compaction_score >= 1 || VersionSet::current_::file_to_compact != NULL)

compact的流程

  1. 如果存在immutable MemTable，将其dump成SSTable(DBImpl::CompactMemTable())，完成返回
  2. 如果存在外部触发的compact，根据manual_compaction指定的level/start_key/end_key选出Compaction(VersionSet::CompactionRange())。为了避免外部指定的key-range过大，一次compact过多的SSTable文件，manual_compaction可能不会一次做完，所以有done来标识是否已经完成，tmp_sotrage保存上一次compact到的end-key，即下一次的start-key
  3. 根据db当前的状态，选出Compaction(VersionSet::PickCompaction())
  4. 如果不是manual compact并且选出的SSTable都处于level-n且不会造成过多的GrandparentOverralp(Compaction::IsTrivialMove())，简单处理，将这些SSTable推到level-n+1，更新db元信息即可(VersionSet::LogAndApply())
  5. 否则，根据确定出的Compaction，做具体的compact处理(DBImpl::DoCompactionWork())，最后做异常情况的清理(DBImpl::CleanupCompaction())

总结

compact操作是比较复杂的操作，也是leveldb唯一的后台操作。