农历新年的最后一天,趁着假期看看代码,顺便做点笔记。时间上比较仓促,如有问题/疑问,欢迎指出。
LevelDB 的写操作是 Append-Only 的,新的数据写入后,相应的旧数据就过期了。过期的数据需要被 Garbage Collection,不然数据文件的体积会持续膨胀,这是不可接受的。
LevelDB 通过后台线程的 compation 来对过期数据进行 Garbage Collection。
LevelDB 在执行读操作和写操作的时候都有可能会调用 MaybeScheduleCompaction
函数,MaybeScheduleCompaction
有可能触发 compaction。
MaybeScheduleCompaction
(相关代码) if (have_stat_update && current->UpdateStats(stats)) {
MaybeScheduleCompaction();
}
have_stat_update
为 true
。(相关代码 )stats
。(相关代码)UpdateStats
函数根据步骤 2 记录下的 SST 文件, allowed_seeks
(一开始初始化为 2^30)减 1。当 allowed_seeks <= 0
且当前没有其它文件等待 compaction 时,记录当前文件为待 compaction 的文件,并返回 true ,否则返回 false。(相关代码)浏览代码的时候,上面 2 和 3 的逻辑让我不是很好理解。自己思考了一下,现在来尝试回答一下(不一定完全准确)。
LevelDB-多级缓存结构.PNG
LevelDB 的结构,其实就是一个多级缓存的结构。看看读操作的顺序就是很好理解这个多级缓存结构。
从 SST 文件进行查找时,首先根据要查找的 Key 从文件的元数据(记录着每一个 SST 文件 Key 范围)找出每个 Level 对应的文件(某些 Level 可能没有对应的文件,Level0 可能有多个对应文件)。按照文件的新旧排序,就组成这个 Key 对应的一个多级缓存。查找的时候也是按照这个顺序,如果最新的 SST_n 文件命中目标,则直接返回结果,否则继续查找 SST_n-1、SST_n-2 ...
Level-SST-Cache.PNG
这种情况下,我们自然希望大部分请求都能在第一个 SST 文件命中,这样效率最高。 如果有很多请求不能从第一个查找的文件命中目标,说明,这个文件的 Key 并没有缓存的价值,应该把这个文件向下一级 Level 合并掉,这样可以减少无效的文件查找。
MaybeScheduleCompaction
写操作会调用 MakeRoomForWrite
为即将写入数据准备空间。整个逻辑由下面几个分支组成。(相关代码)
!bg_error_.ok()
:后台任务有错误,直接返回错误。allow_delay && versions_->NumLevelFiles(0) >= config::kL0_SlowdownWritesTrigger
:正常的写操作都 allow_delay
都为 true
。Level0 的文件数量超过了 config::kL0_SlowdownWritesTrigger
,说明有可能写入太多了,后台线程来不及 Compaction,需要减慢写操作。LevelDB 减慢写操作的方法是,每个写操作 sleep 1ms。!force && (mem_->ApproximateMemoryUsage() <= options_.write_buffer_size)
:MemTable 还有足够的空间支持这次写入,直接返回。imm != NULL
: 来到这里说明 MemTable 的空间不够了,且 Immutable MemTable 还存在(没被 compaction 或 正在被 compaction),需要等到compaction 完成。versions_->NumLevelFiles(0) >= config::kL0_StopWritesTrigger
: Level0 的文件实在太多了,停止写入操作,等待 compaction 完成。MaybeScheduleCompaction
。MaybeScheduleCompaction
的实现(相关代码 )MaybeScheduleCompaction
函数的实现比较简单:判断几个分支的情况,最后确定需要 Compaction 则将任务交交给后台线程。
bg_compaction_scheduled_
: 后台线程已经在进行 compaction。shutting_down_.Acquire_Load()
:正在关闭数据库。!bg_error_.ok()
: 后台任务错误。imm_ == NULL && manual_compaction_ == NULL && !versions_->NeedsCompaction()
:不需要 compaction。DBImpl::BGWork
进行compaction。DBImpl::BGWork
直接调用了 DBImpl::BackgroundCall
。 (相关代码)DBImpl::BackgroundCall
的实现(相关代码)BackgroundCompaction
执行 compaction 。MaybeScheduleCompaction
尝试再触发 compaction。DBImpl::BackgroundCompaction
的实现 (相关代码)CompactMemTable
进行 compaction。一个 Immutable MemTable 被持久化为 Level0 的一个 SST 文件。(相关代码)VersionSet::PickCompaction
,获得一个 Compaction
对象。class Compaction
封装了本次要进行 compaction 的信息。( class Compaction
的相关代码 )。人工触发的 compaction 走另一个分支,暂不讨论。 VersionSet::PickCompaction
选择要进行 compaction 的文件的策略有两种(相关代码):
1)size compaction,某一 Level 的数据太多了;
2)seek compaction,太多查询没有命中第一个 SST 文件。
另外还有一点要注意的就是 Level0 需要特殊处理,因为每个文件的 Key 范围可能是相交的。DoCompactionWork
, 执行 compaction。
2)调用 CleanupCompaction
,清理已经完成的 compaction 完成。
3)调用 DeleteObsoleteFiles
, 删除无效文件。MaybeScheduleCompaction
函数触发的。allowed_seeks
小于等于 0)会触发 compaction。MaybeScheduleCompaction
。因为有可能 level_n 的这次 compaction 导致 level_n+1 的 size 太大,需要进行 compaction。