LevelDB源码解析(12) Memtable落盘
背景
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层需要满足一下要求：
- 已经升到第level层了，且level小于kMaxMemCompactLevel。
- Key范围和level+1层的文件没有重叠。
- Key范围和level+1层的文件可以有重叠，但是有重叠的文件的总size不超过阈值。
OverlapInLevel判断和某层有无重叠，如果是level0，会遍历每个文件，如果不是level0，则使用二分查找加快执行速度（L0层的文件的key范围是无序的且可能有重叠的，所以需要遍历，非L0层是有序的无重叠的，所以可以使用二分查找）。GetOverlappingInputs返回有重叠的文件列表，TotalFileSize计算文件的总size。
源码版本
- 原文作者：胡刘郏
- 原文链接：https://www.huliujia.com/blog/124132a9b3/