背景

LevelDB源码解析(4) MemTable介绍了Memtable,LevelDB会先把key-value插入到MemTable中。如果MemTable写满了,就会新建一个MemTable进行写入。旧的Memtablex会落盘。一个Memtable会产生一个SST文件(后缀为ldb)。这个文件可能放到L0(第0层),也可能直接放到L1或L2。

DBImpl::CompactMemTable

CompactMemTable是Memtable落盘的入口,函数代码如下:

//源码文件: db/db_impl.cc
void DBImpl::CompactMemTable()
{
  BEGIN;
  mutex_.AssertHeld();
  assert(imm_ != nullptr);

  VersionEdit edit;
  Version *base = versions_->current();
  base->Ref();
  Status s = WriteLevel0Table(imm_, &edit, base);
  base->Unref();
  if ( s.ok() && shutting_down_.load(std::memory_order_acquire))
  {
    s = Status::IOError("Deleting DB during memtable compaction");
  }

  if ( s.ok())
  {
    edit.SetPrevLogNumber(0);
    edit.SetLogNumber(logfile_number_);
    s = versions_->LogAndApply(&edit, &mutex_);
  }

  if ( s.ok())
  {
    imm_->Unref();
    imm_ = nullptr;
    has_imm_.store(false, std::memory_order_release);
    RemoveObsoleteFiles();
  } else
  {
    RecordBackgroundError(s);
  }
}

CompactMemTable分为三步

Step1:调用WriteLevel0Table把Memtable落盘,并在VersionEdit存储新增的文件信息。

Step2:调用LogAndApply把VersionEdit的更新应用到LevelDB的版本库。

Step3:调用RemoveObsoleteFiles删除废弃的文件(比如Memtable的预写日志文件),RemoveObsoleteFiles会检查数据库下所有的文件,删除废弃的文件。

下面介绍WriteLevel0Table的实现逻辑。

DBImpl::WriteLevel0Table

Status DBImpl::WriteLevel0Table(MemTable *mem, VersionEdit *edit, Version *base)
{
  mutex_.AssertHeld();
  const uint64_t start_micros = env_->NowMicros();
  FileMetaData meta;
  meta.number = versions_->NewFileNumber();
  pending_outputs_.insert(meta.number);

  //遍历Memtable的迭代器
  Iterator *iter = mem->NewIterator();

  //写到"LOG"文件中,不是WAL的log文件
  Log(options_.info_log, "Level-0 table #%llu: started", (unsigned long long) meta.number);

  Status s;
  {
    mutex_.Unlock();
    s = BuildTable(dbname_, env_, options_, table_cache_, iter, &meta);
    mutex_.Lock();
  }

  Log(options_.info_log, "Level-0 table #%llu: %lld bytes %s", (unsigned long long) meta.number,
      (unsigned long long) meta.file_size, s.ToString().c_str());
  delete iter;
  pending_outputs_.erase(meta.number);

  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();
    if ( base != nullptr )
    {
      level = base->PickLevelForMemTableOutput(min_user_key, max_user_key);
    }
    edit->AddFile(level, meta.number, meta.file_size, meta.smallest, meta.largest);
  }

  CompactionStats stats;
  stats.micros = env_->NowMicros() - start_micros;
  stats.bytes_written = meta.file_size;
  stats_[level].Add(stats);
  return s;
}

Step1: 调用BuildTable完成Memtable到SST文件的转换,meta.number是文件要使用的number,最终生成的sst文件名为$number.ldb,比如000012.ldb。

Step2:调用PickLevelForMemTableOutput为新的SST文件挑选level,最低放到level 0,最高放到level 2。这里还会修改 VersionEdit,添加一个文件记录。包含文件的number、size、最大和最小key。

Step3:更新第level层的统计信息,level是Step2选出的level。

WriteLevel0Table调用BuildTable落盘Memtable,依赖PickLevelForMemTableOutput为新SST文件挑选level。我们再看看这两个函数。

BuildTable

//源码文件:db/builder.cc
Status BuildTable(const std::string &dbname, Env *env, const Options &options,
                  TableCache *table_cache, Iterator *iter, FileMetaData *meta)
{
  Status s;
  meta->file_size = 0;
  iter->SeekToFirst();

  //Step1
  std::string fname = TableFileName(dbname, meta->number);
  if ( iter->Valid())
  {
    WritableFile *file;
    s = env->NewWritableFile(fname, &file);
    if ( !s.ok())
    {
      return s;
    }
    
    //Step2
    TableBuilder *builder = new TableBuilder(options, file);
    meta->smallest.DecodeFrom(iter->key());
    Slice key;
    for ( ; iter->Valid(); iter->Next())
    {
      key = iter->key();
      builder->Add(key, iter->value());
    }
    if ( !key.empty())
    {
      meta->largest.DecodeFrom(key);
    }

    //Step3
    s = builder->Finish();
    if ( s.ok())
    {
      meta->file_size = builder->FileSize();
      assert(meta->file_size > 0);
    }
    delete builder;

    //Step4
    if ( s.ok())
    {
      s = file->Sync();
    }
    if ( s.ok())
    {
      s = file->Close();
    }
    delete file;
    file = nullptr;

    //Step5
    if ( s.ok())
    {
      Iterator *it = table_cache->NewIterator(ReadOptions(), meta->number,
                                              meta->file_size);
      s = it->status();
      delete it;
    }
  }

  //Step6
  if ( !iter->status().ok())
  {
    s = iter->status();
  }
  if ( s.ok() && meta->file_size > 0 )
  {
    // Keep it
  } else
  {
    env->RemoveFile(fname);
  }
  return s;
}

Step1:创建一个WritableFile,WritableFile是兼容不同操作系统文件操作的抽象类,可以理解为打开了一个文件。文件名由meta->number和.ldb后缀组成。

Step2:遍历Memtable,调用TableBuilder::Add把key-value写入文件。因为Memtable是有序的,所以第一个key和最后一个key分别赋值给TableBuilder的smallest和largest,即最小key和最大key。Add会把key-value分block写入文件,并在内存中构建index block等辅助块。TableBuilder是落盘的核心类,详细逻辑请见LevelDB源码解析(10) TableBuilder

Step3:调用TableBuilder::Finish完成最后的写入操作,至此整个SST文件的内容构造完成。

Step4:调用Sync把缓冲区数据强制写到磁盘上,至此Memtable完成落盘。

Step5:调用table_cache->NewIterator读取刚刚生成的sst文件,一方面检查写入是否OK,另一封面把新文件加入到leveldb的缓存中。

Step6:完成收尾工作和错误检查

Version::PickLevelForMemTableOutput

//源码文件:db/version_set.cc
int Version::PickLevelForMemTableOutput(const Slice &smallest_user_key,const Slice &largest_user_key)
{
  int level = 0;
  if ( !OverlapInLevel(0, &smallest_user_key, &largest_user_key))
  {
    InternalKey start(smallest_user_key, kMaxSequenceNumber, kValueTypeForSeek);
    InternalKey limit(largest_user_key, 0, static_cast<ValueType>(0));
    std::vector < FileMetaData * > overlaps;
    while ( level < config::kMaxMemCompactLevel )
    {
      if ( OverlapInLevel(level + 1, &smallest_user_key, &largest_user_key))
      {
        break;
      }
      if ( level + 2 < config::kNumLevels )
      {
        GetOverlappingInputs(level + 2, &start, &limit, &overlaps);
        const int64_t sum = TotalFileSize(overlaps);
        if ( sum > MaxGrandParentOverlapBytes(vset_->options_))
        {
          break;
        }
      }
      level++;
    }
  }
  return level;
}

Step1:首先检查新的SST文件和level 0的文件是否有重叠的key范围,如果有就返回level 0,如果没有重叠,进入Step2,level此时值为0.

Step2:检查level+1层是否有和新文件重叠的key范围,如果有,返回level。如果没有,进入Step3。

Step3:检查level+2层和新文件有key范围重叠的文件,如果有重叠的文件总size超过阈值(默认为文件最大size的10倍)就返回level,如果没有,level加1,如果level不小于kMaxMemCompactLevel,也返回level,否则回到Step2。

总结一下选择level的思路,初始level为0,最高放到kMaxMemCompactLevel层。每次循环就把level加1,也就是每次往上升一层,能升到第level+1层需要满足一下要求:

  1. 已经升到第level层了,且level小于kMaxMemCompactLevel。
  2. Key范围和level+1层的文件没有重叠。
  3. Key范围和level+1层的文件可以有重叠,但是有重叠的文件的总size不超过阈值。

OverlapInLevel判断和某层有无重叠,如果是level0,会遍历每个文件,如果不是level0,则使用二分查找加快执行速度(L0层的文件的key范围是无序的且可能有重叠的,所以需要遍历,非L0层是有序的无重叠的,所以可以使用二分查找)。GetOverlappingInputs返回有重叠的文件列表,TotalFileSize计算文件的总size。