本文介绍LevelDB的SSTable之间的Compaction。Compaction分两种:
- Minor Compaction
对应Memtable到SSTable的过程。 - Major Compaction
对应SSTable文件之间的归并。涉及到两个Level的SSTable文件。
Major Compaction中还可以细分,比如是否Manual等。对于非Manual,还有seek compaction和size compaction。
在本文中,还会介绍Version和VersionEdit概念,它们有助于理解LevelDB对MVCC的实现。
同样的,文章中的【Q】表示我在阅读源码的过程中产生的疑问,有的我找到的解答,或者自己产生了思考,有的则未必清楚。
我们首先来回顾一下LevelDB的整体架构
之前提到过,当一个Memtable满了之后,会转化为Immutable Memtable。Immutable Memtable会被Dump成SSTable文件,SSTable文件是不可变的。
这里GUARDED_BY(m)
实际上是__attribute__(guarded_by(m))
这个线程安全注解,方便编译器帮助检查有没有遗漏掉加锁的情况。
1 | class DBImpl : public DB { |
前置知识
LCS和STCS
有两种Compacton方案:Size-Tiered Compaction Strategy(STCS)和Leveled Compaction Strategy(LCS)。
STCS
Memtable刷成小sstable。当这些小的sstable达到一定个数时,会被compact成一个稍大些的sstable。当稍大些的sstable又达到一定个数时,又会被一起compact成更大的sstable。当然,如果说某些Key的更新频率比较高,那么在Compact的时候只会取最新的Sequence Number,这种情况下,可能不会增加太多。
下图是STCS的一个示意,可以看到,每层的SSTable数量不变,但是大小越来越大。
LCS(Classic Leveled)
STCS存在一些问题,是可以被优化的:
- 存储放大1
因为Compaction时,在新SSTable生成前,旧的SSTable不能删除(当然LevelDB中有Version的概念,其实更复杂点),所以可能会造成额外一倍的开销。
于是我们临机一动,我们增加SSTable数量,而控制大小不变,不就能控制这额外一倍开销的绝对数量么? - 存储放大2
如果Key更新频繁,可能导致同一个Level以及不同Level中的SSTable中存在相同的Key。这里的Key实际上就是LevelDB里面的user key,而不是带有Sequence Number的InternalKey。
【Q】为什么不同Level会存在呢?
为此,我们就得到了LCS:
- 当Level0层数量达到Level0层阈值时,将这些SSTable和L1层的所有SSTable做Compaction。
实际上,具体涉及哪些SSTable,在LevelDB中控制更为精细。并且Compaction的条件也更复杂。 - 如果Level1层的SSTable数量还是超过L1层的阈值,再把这些超出的SSTable向上做Compaction。
- 除了Level0,其他层的所有SSTable中的key都是不重叠的。
下图是LCS的一个示意
我们注意到,LCS中,SSTable的大小不变,但是数量会增多,Level N+1的文件数量是Level N的10倍。【Q】这里看上去和LevelDB的实现还有区别,LevelDB里面的MaxBytesForLevel
函数更多的是计算了10倍的大小,Why?这个我们在“Major Compaction流程”章节中讨论过了,每个文件大小是固定的,LevelDB通过限制每层的总大小来间接限制文件数量。这是因为我们dump的时候更方便统计大小而不是文件数量。
所以,假如Level1有10个文件,Level2就有100个文件。但是key在两个level中都是均匀分布的,因此我Level1拿出一个文件出来,Level2中估计只会有10个文件和它重叠,所以我们只需要合并重叠的这些文件就行了。
当然,Level0彼此重叠,所以还是emmmm。。。
LCS的缺点是写放大会比STCS显著提高。
【Q】既然LCS的写放大高了很多,为什么说基于LSM的写性能很好呢?可能是因为下面几点
- SSTable是顺序写,性能好【Q】
- 根据RocksDB的文档,在一些情况下写放大不是很严重
首先是按key顺序的写,对于这种情况RocksDB可以优化。
其次是有skew的写,会导致只有小部分的key被更新。
Level-N
相比LCS(Classic Leveled)有更高的读放大,和更小的写放大。
Tiered+Leveled
常见文件
需要注意的是,LevelDB是一个单机的数据库,所以实际承载的SSTable文件都位于一台机器上。
文件类型
1 | enum FileType { |
- kLogFile:WAL日志文件,文件名数字.log
- kDBLockFile:db锁文件,文件名LOCK
- kTableFile:SSTable文件,文件名数字.sst
- kDescriptorFile:Manifest文件,存储VersionEdit信息,文件名为MANIFEST-数字
对应descriptor_file_
这个字段。
Manifest文件中维护了所有的SSTable的key范围,层级,以及其他的元信息。 - kCurrentFile:记录当前的Manifest文件,文件名为CURRENT
- kTempFile:临时文件,db在修复【?】过程中会产生临时文件,文件名为数字.dbtmp
- kInfoLogFile:日志文件,文件名为LOG
Manifest
每一个VersionEdit对应Manifest里面的一个Entry,称为Session Record。
其中第一条Session Record包含当时LevelDB的全量版本信息,这个应该是通过WriteSnapshot
来实现的,可以看下面的介绍。
如下所示,每个Entry包含
- 增加的SSTable
kNewFile - 删除的SSTable
kDeletedFile - 当前Compaction的下标
kCompactPointer - 日志文件编号
kLogNumber - 数据库已经持久化数据项中最大的Sequence Number
kLastSequence
对应的代码如下
1 | enum Tag { |
写Manifest的代码应该是Writer::AddRecord
。
读Manifest的代码,例如VersionSet::Recover
。
Current
记录当前的Manifest文件名。
MVCC介绍
Version机制
大前提,Compaction过程是通过独立线程异步并发执行的。因此可能出现压缩前后的新老SSTable并存的情况。同时,我们不能立即删除老的SSTable文件,这可能是因为这个SSTable还在被读取,而要等到老SSTable的引用计数为0才行。因此Version机制可以用来辨别这些SSTable的版本。借助于Version机制,也能实现MVCC。
新版本New-Version由Version
类和VersionEdit
类来描述。即VersionEdit
是New-Version相对于Version的改动。
1 | New-Version = Version + VersionEdit |
LevelDB将所有的Version置于一个双向链表之中,因此所有的Version组成一个名为VersionSet的集合。这个集合也代表了当前DB的状态,包含了最新的Version,以及其他正在服务的Version。
VersionEdit
介绍作为桥梁作用的VersionEdit
类。这个类里面的方法大部分是用来读写里面的私有成员的,所以只介绍私有成员。
std::string comparator_;
uint64_t log_number_;
包含1
void SetLogNumber(uint64_t num)
log文件的file number,也就是
000003.log
的这个3。
小于这个值的Log是可以被删除的
【Q】这个字段的作用是什么呢?
目前来看,在Recover的时候会用到。
【Q】为什么VersionSet里面也有?
其实VersionSet里面的才是主要的,VersionEdit里面的这个字段,是在LogAndApply的时候,由VersionSet设置过来的。
【Q】这个number,和版本的关系是什么,是一一对应的么?比如一次Compaction之后就要换个log?因为在实现上,可以看到NewFileNumber
会产生log(DB::Open
)和SSTable(WriteLevel0Table
)文件的序列号。uint64_t prev_log_number_;
/bool has_prev_log_number_;
包括void SetPrevLogNumber(uint64_t num)
这个函数。
这篇文章说prev_log_number_
已经废弃了,出于兼容性才保留的。uint64_t next_file_number_;
/bool has_next_file_number_;
下一个可用的file number。VersionSet里面也有类似字段,详细介绍见VersionSet。
包含1
void SetNextFile(uint64_t num)
SequenceNumber last_sequence_;
/bool has_last_sequence_;
SSTable 中的最大的Sequence Number。VersionSet里面也有个平行的。bool has_comparator_;
bool has_log_number_;
std::vector<std::pair<int, InternalKey>> compact_pointers_;
主要用于Major Compaction的时候选择文件。first表示每个level。
【Q】在Compaction
类和VersionSet
类里面也有一个这个字段。它们的作用是什么呢?DeletedFileSet deleted_files_;
1
typedef std::set<std::pair<int, uint64_t>> DeletedFileSet;
pair存储了level和file。表示将第level层中的file删除。
std::vector<std::pair<int, FileMetaData>> new_files_;
FileMetaData
存储了文件大小,以及文件中最小的Key和最大的Key。
Version
相关字段
VersionSet相关
指向这个Version所属的VersionSet,以及双向链表和引用计数。
所以说每个Version只能属于一个VersionSet,这个也是很好理解的,1
2
3
4VersionSet* vset_; // VersionSet to which this Version belongs
Version* next_; // Next version in linked list
Version* prev_; // Previous version in linked list
int refs_; // Number of live refs to this versionSSTable相关
files_
表示LevelDB中每一层中所有的SSTable的文件信息。
file_to_compact(_level)_
标记下一个要Compact的文件以及属于的Level。1
2
3
4
5
6// List of files per level
std::vector<FileMetaData*> files_[config::kNumLevels];
// Next file to compact based on seek stats.
FileMetaData* file_to_compact_;
int file_to_compact_level_;根据
SaveTo
函数的论述,**files_[level]
是有序的**。其他字段
compaction_score_
计算最迫切需要Compaction的Level,所以可以决定是否需要发起Major Compaction。这个分数取决于某一层所有SSTable的大小。
NeedsCompaction
会读取这个字段,计算是否需要根据Version的情况来Compaction,并呈递给MaybeScheduleCompaction
。1
2
3
4// Level that should be compacted next and its compaction score.
// Score < 1 means compaction is not strictly needed.
double compaction_score_;
int compaction_level_;
相关函数
int PickLevelForMemTableOutput(const Slice& smallest_user_key, const Slice& largest_user_key);
给定一个Memtable里面的Key的范围,返回这个Memtable被Dump的话要放到第几层。Compaction* PickCompaction();
用来处理size compaction和seek compaction。
这个函数,在“Compaction主函数”这个章节介绍。Compaction* CompactRange(int level, const InternalKey* begin, const InternalKey* end);
Version::PickLevelForMemTableOutput
OverlapInLevel
先介绍辅助函数OverlapInLevel
,作用是判断范围[smallest_user_key,largest_user_key]
和level中的文件有没有Overlap。
1 | bool Version::OverlapInLevel(int level, const Slice* smallest_user_key, |
SomeFileOverlapsRange
SomeFileOverlapsRange返回files
中有没有在范围[smallest_user_key,largest_user_key]
中的key,是OverlapInLevel
的辅助函数。disjoint_sorted_files
表示传入的files
里面的key是不是不相交的,一般除了Level0,其他都是不相交的。AfterFile
和BeforeFile
都比较FileMetaData里面的largest
/smallest
的user_key()
字段。他们的类型是InternalKey
,也就是不带Sequence Number和Value Type的。
对于普通情况,对于一个文件f
,如果smallest_user_key
大于该文件中的最大值,或者largest_user_key
小于最小值,那么认为是不重叠的。
1 | bool SomeFileOverlapsRange(const InternalKeyComparator& icmp, |
如果是不相交的文件,就可以基于FindFile
对files
集合二分查找,所以我们看到,在某一个Level找SSTable的时候是可以二分的。
可以思考一下我们用什么做二分的key呢?答案是每个file的largest。我们要找到第一个largest大于等于smallest_user_key
的文件。
1 | ... |
二分法找到可能存在的文件files[index]
后,不要忘了在判断下这个文件实际有没有overlap。这是二分法的基本规则。
1 | ... |
主流程
1 | int Version::PickLevelForMemTableOutput(const Slice& smallest_user_key, |
首先判断我们要加入的文件的[smallest_user_key,largest_user_key]
和Level0有没有交叠。如果有交叠,就进不了这个if,直接放到第一层,等后面Major Compaction了。
如果没有交叠,我们尝试能否将它下放到config::kMaxMemCompactLevel
之前的层。【Q】为什么我们要设置上限kMaxMemCompactLevel
呢?
1 | ... |
判断level + 2层情况的分支详解
这里需要着重讲解一下level + 2 < config::kNumLevels
这个分支的含义。
作为普通人呢,我觉得判断完OverlapInLevel(level + 1,...
就可以直接level++
了啊,但是大佬肯定是不平凡的。
大佬觉得现在我们想把文件放到level + 1层,但是要先打住,看看level + 2层是什么情况,也就对应到下面的代码。我们要计算所有重叠的文件的总大小,如果这个大小超过了阈值,那么我们就不把这个SSTable进行下放。
这是防止level + 1和level + 2的重叠范围太大,导致这两层进行Compaction时涉及的SSTable过多,耗时过长。
1 | // PickLevelForMemTableOutput中的片段代码 |
于是,先要用GetOverlappingInputs
这个函数,计算level + 2层中到底有哪些文件和[smallest_user_key,largest_user_key]
有交叠,这些文件会放到overlaps
里面。
而TotalFileSize
这个函数就是对FileMetaData::file_size
求和。
然后,我们和MaxGrandParentOverlapBytes
返回的阈值进行比较。
GetOverlappingInputs/MaxGrandParentOverlapBytes
GetOverlappingInputs
的目标是找到level中和[begin,end]
重叠的所有文件,并放到inputs
里面。这个函数对Level0有特殊的处理。
1 | // Store in "*inputs" all files in "level" that overlap [begin,end] |
user_begin
和user_end
是从InternalKey中提取出的user key。如果传入nullptr,表示在比较时begin
永远小于任何key。
【Q】这里为什么去找的user key而不是InternalKey呢?貌似很多地方都是找user key。在这篇文章中,作者指出了一个其实我们很容易注意到的性质,就是除了Level0,每一层Level都是有序的。进一步地,由于LevelDB使用leveled策略(LCS),即强调一个key在每一层至多只有1条记录,不存在冗余记录。
1 | ... |
默认,我们遍历这一层的所有的文件。前面两个if分别处理文件和range完全不重叠的情况。
1 | ... |
否则就是有重叠的,我们把这个文件加入到inputs
里面作为结果返回。对于PickLevelForMemTableOutput
的逻辑而言,这里就到此为止了。
但是GetOverlappingInputs
这个函数还会在CompactRange
、SetupOtherInputs
这些函数中用到。此时,需要处理Level0的逻辑。【Q】且慢,我们已经逐文件遍历了啊,还会有什么问题呢?
1 | ... |
在这篇文章中,详细解释了原因。这是因为我们认为Level1的文件是比Level0要旧的,所以如果要把Level0中的某个文件f
移动到Level1中,我们要把Level0中所有和f
Overlap的文件都放到Level1里面。这样,实际上保证了如果我有一个Key在Level0里面,那么inputs里面会包含所有包含这个Key的文件。
进一步想,在Level0往Level1归并的时候,其实也应该看到这个过程。事实上观看PickCompaction
的代码实现,我们也能看到在最后有个if (level == 0)
的判断。
这个应当同样解决我们在IsTrivialMove
的一个疑问,也就是为什么Level层有两个的时候,我们不能简单把其中一个文件移动到下层。
所以,当检查到user_begin
在文件[file_start,file_limit]
中后,需要将user_begin
调整为文件的开头file_start
。对user_end
也是同理的。
VersionSet
成员介绍
Status VersionSet::LogAndApply(VersionEdit* edit, port::Mutex* mu)
这个函数接受一个VersionEdit。
首先,函数将VersionEdit应用在current_
,并借助于VersionSet::Builder
生成一个新的Version。Builder类的实现是比较巧妙的,我们会在稍后来讲解。
此后,它会调用Finalize
函数更新compaction_level_
和compaction_score_
。
此后,更新Manifest文件。主要是把VersionEdit中的内容EncodeTo
到Manifest文件里面。
此后,调用AppendVersion
将新版本添加到VersionSet的双向链表中,并且设置新的current_
。std::string compact_pointer_[config::kNumLevels];
这个字段在Major Compaction过程中被用到。表示每一层上,下一次Compaction需要开始的key的位置。它要么是一个空串,要么是一个InternalKey。
【Q】在什么时候被设置呢?
根据文章,这个compact_pointer_
实际上表示这一层上一次Compact时文件的largest。Status Recover(bool* save_manifest);
关于Recover机制,我们不在这篇文章中介绍。详见“LevelDB之流程概览”这篇文章。
有关Sequence:
uint64_t LastSequence() const { return last_sequence_; }
还有个对应的SetLastSequence
方法。
返回最近的Sequence Number。这个是在写入记录的时候会使用并且更新。
【Q】VersionEdit里面也有个平行的,他们之间的关系是什么呢?
首先VersionSet的last_sequence_
会随着DBImpl::Write
操作更新。
当需要进行Compact的时候,会在LogAndApply
中赋给VersionEdit中的对应字段。而VersionEdit的目的,似乎只是持久化这个信息。
有关日志:
prev_log_number_
/log_number_
【Q】和VersionEdit里面同名字段的关系是什么?见VersionEdit的解释。
有关文件编号:
next_file_number_
包含1
2
3
4
5
6uint64_t NewFileNumber() { return next_file_number_++; }
void ReuseFileNumber(uint64_t file_number) {
if (next_file_number_ == file_number + 1) {
next_file_number_ = file_number;
}
}这个字段用来生成系统中下个文件的编号。VersionEdit需要在LogAndApply时传入,以persist。
【Q】这里的file number指的是SSTable的file number么?看起来并不是的,而是Manifest文件、SSTable文件啥的共用一个编号,这也是为什么一开始Log文件是0,Minifest文件是1,SetNextFile是2的原因。manifest_file_number_;
表示Manifest文件的编号,主要在Recover时用到
疑问:
- VersionSet和DBImpl是一一对应的么?
应该是的,DBImpl持有一个VersionSet*
。
VersionSet::LogAndApply
在前面已经简单介绍过这个函数的功能了。这个函数主要在下面几个地方用到:
DB::Open
当DB启动的时候,可能需要从通过DBImpl::Recover
从log中恢复一部分数据。这些数据会以VersionEdit的方式被Apply。DBImpl::CompactMemTable
Minor Compaction。
一般在下面的地方调用:- BackgroundCompaction
- DoCompactionWork:也就是在Major Compaction的过程中也要有限处理Minor Compaction。
BackgroundCompaction
的非manual情况(平凡情况)
这种情况只是将某个SSTable移动到别的层。BackgroundCompaction
的manual情况(一般情况)
需要归并。
下面这里讲解一下源码。__attribute__((exclusive_locks_required))
表示检查在调用LogAndApply
函数之前就要持有锁mu
。因此同时只会有一个线程执行LogAndApply
。
1 | Status LogAndApply(VersionEdit* edit, port::Mutex* mu) |
下面是把VersionSet的LogNumber传给VersionEdit。
1 | Status VersionSet::LogAndApply(VersionEdit* edit, port::Mutex* mu) { |
我们要把VersionSet的last_sequence_
传给edit,在对VersionSet::Builder
的论述中已经推断过这里的作用了。
1 | ... |
下面的descriptor_file_
就是一个Manifest文件。
如果此时descriptor_log_
是NULL,根据注释,这个对应到首次打开数据库的状态。我们要新建一个Manifest文件,此时DescriptorFileName
产生一个"/MANIFEST-%06llu"
格式的文件名字。
通过WriteSnapshot
把descriptor_log_
写到新的Manifest文件里面,这个实际上就是Current Version的快照。WriteSnapshot
里面也会调用EncodeTo
和AddRecord
。
【Q】为什么有这个函数?本文之前介绍了Manifest文件的构造,里面提到第一条Session Record记录了当前数据库的全量数据,我认为这里就是实现这个性质的。
【Q】注意,VersionSet::ReuseManifest
也会修改这个descriptor_log_
,有什么影响呢?
1 | ... |
下面,是把VersionEdit中的内容EncodeTo
到Manifest文件里面。这里不是写快照了,而是写一条Log。其实Manifest文件的格式就是Log。
在这里,将写文件的操作都集中在一起,期间是不要加锁的。
1 | ... |
EncodeTo
将信息按照下面的Tag分类
1 | enum Tag { |
AddRecord
将信息编码到文件中,对应的读取函数是Reader::ReadRecord
1 | ... |
我们现在得到了一个新的Version即v
,调用AppendVersion
将它设置为current_
。这个函数还会将v
添加到VersionSet里面的那个双向链表里面。
文章中有疑问这里遇到多线程怎么办,但LevelDB中Compact只有一条后台线程,并且这里是持有锁的。
1 | ... |
VersionSet::AppendVersion
这里dummy_versions_
是VersionSet维护的环状链表头,dummy_versions_.prev_
就是current_
。
1 | void VersionSet::AppendVersion(Version* v) { |
可以通过下面的图清晰看出
VersionSet::Builder
VersionSet* vset_;
在构造时传入的VersionSet。Version* base_;
在构造时传入的,一般为current_
LevelState levels_[config::kNumLevels];
LevelState里面记录了增加和删除的文件。void Apply(VersionEdit* edit)
将edit
里面的变动应用到current_
。例如要加些什么文件,写到levels_[level].added_files
这个列表里面。但是我们不实际加,而是到SaveTo
里面再一次性加。
【Q】为什么要这样子呢?原因有2:v->files_[level]
这个是有序存储的。
void SaveTo(Version* v)
注意,从VersionSet::Recover
可以看出,Applt和SaveTo并不是一对一的关系。例如我们从一个文件中多个记录里面恢复,那么每读取一个记录就要Apply一次,但最后再SaveTo。
VersionSet::Builder::Apply
这个函数设置诸如levels_[level].added_files
的字段,表示我们需要做什么改变。
首先将VersionEdit记录的compact_pointers_
应用到VersionSet。
1 | // Apply all of the edits in *edit to the current state. |
然后把要增加和删除的文件记录到自己的levels_
字段里面。
1 | ... |
在增加文件的时候,需要处理allowed_seeks
字段。这里的16384U
有点奇怪,是啥意思?
根据注释,我们假设:
- 一次Seek耗时10ms
- 读写1MB耗时10ms,也就是我们的IO速度是100MB/s
- 一次Compaction,假设是1MB,需要消耗25MB的IO
- 需要从这一层读取1MB
- 从下一层读取10-12MB的数据(boundaries may be misaligned)
- 写10-12MB的数据到下一层
这说明25次Seek的开销等于1MB数据的Compaction成本,也就是一次Seek大概摊还下来是40KB数据的压缩成本。我们做一些保留,让16KB对应一次Compaction,也就是允许更多的Seek次数。
同时,我们将f->allowed_seeks
最小值设为100,这样也不会一直Compaction。
1 | ... |
VersionSet::Builder::SaveTo
SaveTo
的最终影响是MaybeAddFile
,也就是说将文件添加到Version里面。具体是添加到v->files_
里面。
1 | // Save the current state in *v. |
下面的循环中,我们依次处理每一层的合并。主要内容是:
- 将添加的文件合并到
files_
- 删除文件
之前介绍过base_
在构造时传入,一般为CURRENT,我们就是要对base_
去应用这些修改。
所以,我们是
1 | base_->files_[level] + (levels_[level].added_files - levels_[level].deleted_files) = v->files_[level] |
base_iter
用来遍历原有的文件。
1 | ... |
我们首先预留最大空间,避免到时候的频繁动态分配。但是实际上最终未必用到这个空间,因为MaybeAddFile
不一定真的添加文件。
下面就是插入操作,这个有点奇怪。我们先初始化了bpos
,但是循环中自增的却是base_iter
,for(A;B;C)
里面A和C的主语不一样,很奇怪。其实bpos
标记了我们要遍历的终点。具体解释一下,这个函数其实是一个归并的过程,分两步:
- 插入原有的
base_
里面的文件,这些文件要小于等于added_file
std::upper_bound
找到第一个大于added_file
的位置bpos
,也就是我们的base_iter
往后遍历,不会超过bpos
。
我们用MaybeAddFile
插入,因为这些文件可能已经被标记删除。 - 插入
added_file
**那么这么做的好处在哪里呢?我认为是减少了比较的次数,从O(n)到了O(logn)**。因为我们这里是BytewiseComparator
,是两个Slice之间的比较,所以开销还是比较大的,这里是值得学习的一个Best Practice。
1 | ... |
在Debug的状态下,会去检查除Level0之外的层有没有重叠。检查方法也很简单,就是看后一个文件的smallest是不是一定严格大于前一个文件的largest。
1 | ... |
VersionSet::Builder::MaybeAddFile
1 | void MaybeAddFile(Version* v, int level, FileMetaData* f) { |
VersionSet::Finalize
1 | void VersionSet::Finalize(Version* v) { |
下面是针对第0层的特殊情况。我们知道LevelDB的第0层最多存在4个文件【Q】(我觉得未必,详见kL0_SlowdownWritesTrigger
),这就是由kL0_CompactionTrigger
控制的。这里使用文件数量,注释里面列了两个原因:
- 允许更大的写buffer,从而减少Level0 Compaction的数量。
这里的写buffer应该是options_.write_buffer_size
这个东西。这个阈值控制Memtable何时转换成Immutable Memtable,以及在Recover的时候何时直接dump成SSTable。
佶屈聱牙,实际上的意思是,这个意思是,如果写buffer太大,如果我们用固定的size限制死了的话,可能Level0的文件数量会很少,比如就1个,这样会导致频繁的Level0 Compaction。 - Level0的文件每次读取都会被Merge。我们不希望有很多个小文件(perhaps because of a small write-buffer setting, or very high compression ratios, or lots of overwrites/deletions)。
如果写buffer很小,这样会导致更多的Level0文件。因为Level0的文件是overlap的,所以如果数量过多,每次查询需要Seek的文件数量就越多。
1 | ... |
对于第1层以下的层,计算文件总大小,而不是文件数量了。MaxBytesForLevel
的大概意思就是Level1总大小是10M,下面每一层翻10倍。
1 | ... |
MaxBytesForLevel
这个函数计算每一层的最大大小。
1 | static double MaxBytesForLevel(const Options* options, int level) { |
析构函数
将自己从链表中移除。
对于自己管理的所有文件,引用计数减一。【Q】这边不搞个原子操作么?
1 | Version::~Version() { |
LevelDB对MVCC的实现总结
版本升级
文章中论述了一次版本升级的过程,但我会批注一下具体实现的函数和逻辑
- 新建一个Session Record,记录状态变更信息
- 讨论版本升级原因
- Minor Compaction或者日志replay
在Session Record中记录新增的文件信息、最新的journal编号、数据库sequence number以及下一个可用的文件编号。 - Major Compaction
在Session Record中记录新增、删除的文件信息、下一个可用的文件编号即可。
- Minor Compaction或者日志replay
- 通过VersionEdit生成新版本
相较于旧的版本信息,新的版本信息更改的内容为:- 每一层的文件信息:在
VersionSet::Builder::Apply
中。 - 每一层的计分信息:在
VersionSet::Finalize
中。
- 每一层的文件信息:在
- 将Session Record持久化
在VersionSet::Builder::SaveTo
中。 - 讨论是否是第一条Session Record
在LogAndApply的Finalize调用之后的部分- 是
新建一个Manifest文件,并将完整的版本信息全部记录进Session Record作为该Manifest的基础状态写入,同时更改Current文件,将其指向新建的Manifest。 - 不是
将该条Session Record进行序列化后直接作为一条记录写入即可。
- 是
- 将当前的Version设置为刚创建的Version
这个会修改current_
的指向。这个操作应该是原子的(不然最新版本岂不是会不一致么)实际上也在mutex_
的保护下。
在LogAndApply对AppendVersion
的调用中。
Snapshot机制
我们在这里介绍Snapshot机制,主要是为了方便说明它对Compaction的影响:导致同一个user key的不同的Sequence Number版本存在多个。
Snapshot实际上就是某个特定的Sequence Number。
【Q】Sequence Number是全局递增的么?应该是这样的,在Put和Get的实现中,看到的都是读取的VersionSet::LastSequence()
这个。
1 | const Snapshot* DBImpl::GetSnapshot() { |
Compaction主函数
总览
调用路径
- BackgroundCompaction
- BackgroundCall
- BGWork
- MaybeScheduleCompaction
会Schedule方法BGWork
。
这个函数在BackgroundCall,以及诸如Get等读写方法中都会被调用。
- MaybeScheduleCompaction
- BGWork
- BackgroundCall
Compaction条件
- Minor Compaction
在Recover过程中ApproximateMemoryUsage
检测到Memtable超限,会直接触发对Memtable的Compaction。但这个Compaction是局部的,因为我们在恢复过程中,所以不需要诸如LogAndApply这种维护Version的工作。
存在Immutable Memtable - Manual Compaction
CompactRange调用 size_compaction
在VersionSet::PickCompaction
中检查并启动。
当Level0文件数目过多,或者某个Level的总大小过大。
在函数NeedsCompaction
中判断当前Version的compaction_score_
(size compaction)和file_to_compact_
(seek compaction)。seek_compaction
seek次数太多。我们知道,当一个文件找不到时,就需要到高一级的Level中去查找。假如在Level(n)
中没找到,但是在Level(n+1)
中找到了,就认为Level(n)
有一次未命中。容易发现如果未命中次数多了,就说明Level N和Level N+1
的文件overlap很厉害,这就需要通过一次Major Compaction来解决这个问题。
DBImpl类
LevelDB通过class DB
对外暴露C++接口,这个DB
的实现就是DBImpl
。
DBImpl::BackgroundCall
BackgroundCall是在后台线程中执行的。
1 | void DBImpl::BackgroundCall() { |
MakeRoomForWrite
函数会在background_work_finished_signal_
等待Compaction结束。
1 | ... |
DBImpl::MaybeScheduleCompaction
函数MaybeScheduleCompaction
决定是否进行Compaction。
这里需要加锁,不然可能会导致开两个后台进程,而LevelDB只允许一个后台进程。
1 | void DBImpl::MaybeScheduleCompaction() { |
PosixEnv::Schedule
这里的env_
的实现实际上是一个PosixEnv
。
我们查看源码,原来这个后台进程只有一个started_background_thread_
,一开始先检查它是否存在,如果不存在,就创建一个,然后detach掉。
接下来就是一个生产者消费者模式。不过有点奇怪,是先Signal,再入队,不应该先修改条件,再Signal么。
我在文章中提过陈硕大佬的一篇博客,在CV语境中,先Signal,再设置条件flag(代码里面的Case 6)也是可以的,但只限于单waiter使用。
1 | void PosixEnv::Schedule( |
下面放一下消费者的代码
1 | void PosixEnv::BackgroundThreadMain() { |
NeedsCompaction
1 | bool NeedsCompaction() const { |
Compaction类
定义在version_set.h文件里面。
主要成员和成员函数
std::vector<FileMetaData*> inputs_[2];
表示这个Compaction涉及的两个level的文件,也就是输入。
其中level层是inputs_[0]
。level + 1层是inputs_[1]
,称为parents。std::vector<FileMetaData*> grandparents_;
level + 2层的文件,通常称为grandparents。int level() const { return level_; }
我们将level_
和level_+1
层进行压缩。int num_input_files(int which) const
bool IsTrivialMove() const;
是否可以直接移动,而不涉及merge或者split操作。bool ShouldStopBefore(const Slice& internal_key);
VersionEdit* edit() { return &edit_; }
/edit_
这个应该很好理解,Compaction肯定会有文件增删,即使是移动,也是跨层的。所以这里需要一个VersionEdit
来描述。
IsTrivialMove
这个函数用来判断在Major Compaction的时候能不能直接移动老的文件到下面一层,而不归并生成新的文件,条件有三个:
- level层只有一个
【Q】疑问:如果level层有多个,level+1层没有,那么我直接移动到下面一层也是安全的?那么禁止这么做的目的是什么?
检查对GetOverlappingInputs
的分析,发现可能是不安全的。如果说Level0的某个文件f
和Level1的文件有Overlap,那么就必须要扫描整个Level0层的所有文件,将与f
有Overlap的文件都要移到下一层。 - level + 1层没有
这个原因应该好理解,如果level+1层有,那么我们就得比较和这个文件有没有Overlap。 - 和level + 2层的overlap没有超过阈值(实际上是20M)
1 | bool Compaction::IsTrivialMove() const { |
DBImpl::BackgroundCompaction
这个过程是Compaction的主过程,需要全程持锁。
Minor
我们首先需要去CompactMemTable
,也就是Minor Compaction。这个肯定是优先级更高的,因为我们只有两个Memtable,所以我们肯定想把Immutable Memtable快速腾空。
1 | void DBImpl::BackgroundCompaction() { |
Major
详见Major Compaction章节
Minor Compaction流程
CompactMemTable
主要流程三部分:
- WriteLevel0Table
- 将Immutable Memtable生成SSTable文件
这个文件的基本信息写到FileMetaData
里面,并在最后写入VersionEdit
。
注意,在Recover的过程中,这里其实也可以传入Memtable。 - 计算添加到哪一层
这个文件未必会放到Level0,可能会直接放到Level1甚至Level2,具体由kMaxMemCompactLevel
控制。 - 将上面说的
FileMetaData
写入VersionEdit
因此这个函数的实际返回是传入的VersionEdit* edit
。
- 将Immutable Memtable生成SSTable文件
- LogAndApply
用我们得到的VersionEdit
,去更新数据库状态,并记录。 - RemoveObsoleteFiles
重置Immutable Memtable。
删除无用文件。主要包括kLogFile
/kLogFile
/kTableFile
等。
1 | void DBImpl::CompactMemTable() { |
下面,就是要把edit
应用到当前的VersionSet上。
【Q】SetPrevLogNumber
是啥意思?为啥要设置为0呢?
1 | ... |
WriteLevel0Table
在前文中,已经介绍过了WriteLevel0Table
的作用,下面看实现。
首先,我们计算出一个NewFileNumber
,也就是落盘时体现的文件名。关于这个函数,我们之前已经介绍过了,体现在诸如MANIFEST-xxxxx
或者yyyyy.log
这里的序号。
pending_outputs_
中保存了所有正在Compact的SSTable文件,这些文件不能被删除。这引发了我两个问题:
- 什么时候会删除?
在RemoveObsoleteFiles
里面,马上就能看到了,不急不急 - 为什么在BuildTable之后就可以删除了?
1 | Status DBImpl::WriteLevel0Table(MemTable* mem, VersionEdit* edit, |
接着,BuildTable
创建一个TableBuilder
写入数据。值得注意的是,这里并没有加锁。我之前认为这是因为BuildTable
里面会自带加锁,但是检查代码并没有。这可能是因为Compaction是单独的线程,诸如生成并写SSTable的过程是可以单独提出来处理的。
1 | ... |
新生成的文件未必会放到Level0,可能会直接放到Level1。例如,如果新的SSTable文件和Level1中的文件没有重叠,那么就有可能被放到Level1,具体还需要查看Level2和新SSTable的重叠情况。因此PickLevelForMemTableOutput
会生成一个level,表示放到哪一层。
下面的edit->AddFile
就是将这个SSTable加到当前的VersionEdit中。
1 | ... |
env_
实际上是封装了文件系统等操作。
1 | ... |
RemoveObsoleteFiles
搞清楚几个问题:
- 清理文件的范围?看
env_->GetChildren
的实现,应该是所有这个db下的文件。 - 清理文件的类型?
1 | void DBImpl::RemoveObsoleteFiles() { |
1 | ... |
Major Compaction流程
【Q】思考
在开始研究Major Compaction前,我们主动思考这个问题
对于Level0里面的文件,是不是可以直接和Level1中的文件Merge?
答案是不行的,见GetOverlappingInputs
的论述。如果level中的某个文件的key的range过大,它可能和level+1层的很多文件有重合,这样的compaction写放大很重,如何解决这个问题?
首先,这也是为什么LevelDB要分成很多层的原因,在Merge的时候,最多和下一层中的所有文件Overlap,写放大是可控的。
其次,在Compact的时候,LevelDB一直关注和level+2层的key的重叠情是否超过一定量,即MaxGrandParentOverlapBytes
函数。- 在
ShouldStopBefore
判断是否要结束当前SSTable写入,新开文件的时候,考虑当前文件和level+2的Overlap,如果过了,就新开文件。 - 在
IsTrivialMove
判断是否可以直接移动文件到下层的时候,考虑要移动的文件和level+2层的Overlap,如果过了,就不能移动。 - 在
PickLevelForMemTableOutput
选择Minor Compaction的层时,考虑这个Immutable Memtable的Overlap,如果过了,就不能放在这一层。
- 在
从level到level+1的Compaction会对level+2产生什么影响?
LevelDB中多个不相干的合并是可以并发进行的,这个的实现是怎样的?
需要注意,Level0文件是彼此Overlap的,所以是相干的。
【Q】那么当一个Major Compaction开始的时候,是如何判定是否相干,如果不相干就不Compact的呢?从LevelDB的代码来看,只有一个后台线程进行Compact操作,所以我认为虽然在设计上LSM树是允许并行Compact的,但是LevelDB并没有实现,但RocksDB肯定是实现的。LevelDB中,每个user key在一层中是不是只会出现一次?
大多数情况是的,有两个例外。
首先,Level0是Overlap的,可能有多个。
其次,如果使用了Snapshot,那么在下层可能也会有user key相同,但是sequence不同的。见AddBoundaryInputs
的论述。我们往Manifest文件里面写了什么?
LevelDB有容量限制么?
应该是没有的,但是当最下面一层变得特别大之后,Compaction的开销会很大。LevelDB到底是限制的每一层的文件数量还是大小?
【Q】如果限制的是总大小,如果保证生成的SSTable的大小是大致相同的?
对于Major Compaction来说,是在DoCompactionWork
里面通过下面的代码来判断的,也就是说当文件大小达到一定规模后,就会产生新的文件了。1
2
3if (compact->builder->FileSize() >=
compact->compaction->MaxOutputFileSize()) {
status = FinishCompactionOutputFile(compact, input);这个调用最后会转到
options->max_file_size
上。LevelDB每一层的文件数量有限制么?
首先Level0肯定有,大家说是4个么?我觉得不是。参考下面的代码,4只是表示有4个文件就开始Level0的Compaction。当文件数达到12个,才是上限,这个时候就要停止写了。1
2
3
4
5
6// Level-0 compaction is started when we hit this many files.
static const int kL0_CompactionTrigger = 4;
// Soft limit on number of level-0 files. We slow down writes at this point.
static const int kL0_SlowdownWritesTrigger = 8;
// Maximum number of level-0 files. We stop writes at this point.
static const int kL0_StopWritesTrigger = 12;LevelDB底层SSTable中的数据永无出头之日么?
怎么可能,只要数据被修改,那么就会先到Memtable里面。Compaction是如何删除文件的?
注意,即使遍历到有删除标记的,并且这个删除标记的序列号最大。我们也不应该尝试删除,至少要检查下面的层有没有。详见DoCompactionWork
DBImpl::BackgroundCompaction
下面是对Major Compaction的处理。
计算Compaction对象
首先,我们要处理Manual Compaction的情况。如果manual_compaction_
不是null,就触发Manual Compaction。我没看到非测试的代码里面有设置manual_compaction_
的,但是leveldb_compact_range
这个api会显示调用CompactRange
,并且DB
这个接口中也有CompactRange
方法,也就是说,LevelDB对外暴露这个方法。
1 | class LEVELDB_EXPORT DB { |
其次,我们调用PickCompaction
处理size compaction和seek compaction的情况。PickCompaction
会返回当前要Compact的文件,如果返回null,就啥事都不做。对于PickCompaction
而言,如果既没有size compaction,又没有seek compaction,返回null。
这个过程是持锁的
1 | void DBImpl::BackgroundCompaction() { |
根据Compaction对象进行Compact操作
经过上面的代码,我们就得到了一个Compaction* c
对象。
如果之前PickCompaction
没给出这个c
,那么就说明这一次不要Compact。
如果满足IsTrivialMove
条件,就可以不生成新的文件,直接将原文件移动到下一层。
对于Trivial的情况我们直接更新c->edit()
,不走InstallCompactionResults
的逻辑了。
1 | Status status; |
如果不满足IsTrivialMove
条件,就是一般情况,由DoCompactionWork
处理。DBImpl::CompactionState
这个类又封装了Compaction
,这是因为要处理两个Level之间的合并,所以要加一些额外的字段。
然后我们要CleanupCompaction
,这个除了清空compact对象,还需要根据compact->outputs
,找到pending_outputs_
里面对应的文件,并移除出pending_outputs_
。我们知道compact->outputs
记录了每个输出文件的元信息,而pending_outputs_
记录了正在compact的文件,我们compact结束,就把这些文件移出去。在Major Compaction中,文件是在DoCompactionWork -> OpenCompactionOutputFile
中被加入pending_outputs_
的。
1 | CompactionState* compact = new CompactionState(c); |
收尾
如果是Manual的,需要清空Manual状态。
1 | if (status.ok()) { |
Version::PickCompaction
size compaction的优先级是高于seek compaction的。
遍历current_->compaction_level_
这一层的所有文件,找到第一个largest大于compact_pointer_[level]
的文件,放到Compaction* c
的inputs_[0]
中。
如果一轮循环下来没找到,说明所有的文件的largest都小于compact_pointer_[level]
,也就是这一层所有的key都小于compact_pointer_[level]
,那就把第一个文件放进去。
1 | Compaction* VersionSet::PickCompaction() { |
对于seek compaction,把要Compact的那个文件加到c->inputs_[0]
就行,逻辑很简单。
1 | } else if (seek_compaction) { |
对于Level0,有个特别的处理,这个参考GetOverlappingInputs
函数的说明。
1 | c->input_version_ = current_; |
现在,我们已经得到了c->inputs_[0]
。除了c->inputs_[0]
的情况,否则c->inputs_[0]
里面都只有一个文件。
通过SetupOtherInputs
可以计算c->inputs_[1]
,也就是level+1层涉及哪些文件。
1 | SetupOtherInputs(c); |
Version::SetupOtherInputs
SetupOtherInputs
计算在Compaction时,level+1层涉及哪些文件。在这个函数之后,我们就得到了正确的c->inputs_
数组、c->grandparents_
字段,以及compact_pointer_
字段。在这个函数之后,PickCompaction
就结束了,BackgroundCompaction
会执行后面的流程,也就是DoCompactionWork
。
基本的思想是:所有和level层有重叠的level+1层文件都要参与Compact。得到这些文件后,反过来看下,利用这些level+1层的文件,能不能Compact更多level层的文件?
这个函数被CompactRange
和PickCompaction
调用,也就是所有的Major Compaction逻辑都会走到这里。
GetRange和GetRange2
GetRange计算inputs_[0]
/inputs_[1]
的区间。
GetRange2计算inputs_[0]
和inputs_[1]
的区间。
GetRange很简单,遍历每一个文件,然后更新smallest和largest,这里注意都需要icmp_.Compare
。
1 | void VersionSet::GetRange(const std::vector<FileMetaData*>& inputs, |
GetRange2很简单,就直接合并inputs_[0]
和inputs_[1]
的内容到一个vector里面,然后调用GetRange。
1 | void VersionSet::GetRange2(const std::vector<FileMetaData*>& inputs1, |
AddBoundaryInputs
AddBoundaryInputs是一个很重要的函数,但只有很少的Blog能讲明白这个函数的来龙去脉。
翻译一下AddBoundaryInputs
这个函数的注释。他提取出compaction_files
里面最大的文件b1,在这里是c->inputs_[0]
里面最大的文件。
然后在level_files
里面找到一个b2,满足b1和b2的user key是相等的,这样的b2称为boundary file。我们需要将这个b2加入到compaction_files
里面,并且继续找上界。
如果有两个块(应该就是SSTable)b1和b2,他们的范围分别是(l1, u1)
和(l2, u2)
,如果我们只Compact b1,不Compact b2,那么在读取的时候就会出错。因为它只会返回b2的结果,而永远不会返回b1的结果,因为b1在b2上层了。与此同时,我们需要注意到b2的结果可能还是一个较旧的数据,因为根据Memtable里面的介绍,Sequence Number是从新到旧来排序的。
1 | void AddBoundaryInputs(const InternalKeyComparator& icmp, |
【Q】看起来,这个函数做的是和GetOverlappingInputs
一样的事情,他们的区别是什么呢?首先,GetOverlappingInputs
的初心不是扩展边界而是计算某一层和某个range重合的文件,只是对Level0要特殊处理一下。其次,这篇文章中进行了解释。
如下图所示,两个sstable中,出现了user key相同(都为key2)但是Sequence Number不同的两个Internal Key。
所以可以看到GetOverlappingInputs
的特殊处理关注的是Level0上某一个要Compact的文件中的所有key是否还会出现在其他的SSTable文件中。而AddBoundaryInputs
关注的是某个Key的其他版本是否还会出现在其他的SSTable中。
【Q】这里引发了第二个疑问,为什么同一层中会出现两个相同user key的Key呢?我觉得这个可能是因为这个Key出现在两个SSTable的边界上,所以这个函数叫AddBoundaryInputs
吧。
仔细回顾一下DoCompactionWork
的实现,似乎是可能没处理完一个Key,就ShouldStopBefore
了的,但即使这样,后面的文件里面也不会再写有关这个user key的内容了。那么究竟在什么情况下会发生这种情况呢?根据这篇文章中指出Snapshot机制会导致“同一层中会出现两个相同user key的Key”这个问题。
【Q】这里引发了第三个疑问,出现了两个user key,会不会影响读取呢?实际上只要位于同一层就不影响,因为根据Memtable里面的介绍,Sequence Number是从新到旧来排序的。我们的查找方式允许我们每一次都找到b1里面的值。
特别值得注意的是,这个问题关系到Issue 320和PR 339。AddBoundaryInputs
函数也是在那个时候引进的。不过值得注意的是,这个patch在2016年就提了,但是2019年才被合进去。
SetupOtherInputs主体
首先AddBoundaryInputs
扩充一下c->inputs_[0]
。
然后获得Level N的range。
然后计算Level N+1和Level N重叠的SSTable文件,并放入c->inputs_[1]
。
最后,计算Level N和Level N+1合并起来的range。
1 | void VersionSet::SetupOtherInputs(Compaction* c) { |
下面的的代码,就是之前说的优化。
如果c->inputs_[1]
不为空,也就是Level N+1层有需要进行Merge的文件。我们将level中和所有和[all_start,all_limit]
重叠的文件加到expoand0里面,并调用AddBoundaryInputs
处理边界。
1 | // See if we can grow the number of inputs in "level" without |
下面,设置一下c->grandparents_
这个字段。
1 | // Compute the set of grandparent files that overlap this compaction |
记录下一轮的压缩起始文件,也就是设置compact_pointer_
。我们在这里立即更新,而不是等到VersionEdit被Apply的时候更新,这样当Compaction失败后,我们能下次能尝试一个不同的key range。
- 【Q】什么是压缩起始文件?
查看PickCompaction
函数,它会找到largest大于compact_pointer_[level]
后的第一个文件。
可以发现,其实每一次要Compaction的文件就是通过compact_pointer_
指定的。 - 【Q】在这之后,Compaction会因为什么失败?
1 | // Update the place where we will do the next compaction for this level. |
DBImpl::CompactionState
SequenceNumber smallest_snapshot;
小于smallest_snapshot
的Sequence Number是不重要的,因为我们不会为提供smallest_snapshot
的snapshot。
所以,如果我们看到Sequence Number小于等于smallest_snapshot
的某个S
,就可以丢弃小于S
的这个key的其他版本。
【Q】这里是不是在说,如果只有S这个独苗,那还是要写进去的?std::vector<Output> outputs;
Output* current_output() { return &outputs[outputs.size() - 1]; }
保存每个输出文件的元信息。例如smallest和largest。WritableFile* outfile;
Major Compaction过程中,需要输出到level+1层的文件。注意,可能有多个这样的文件,参考ShouldStopBefore
。TableBuilder* builder;
uint64_t total_bytes;
DBImpl::DoCompactionWork
这个对应了一般情况下的Compact过程,来自BackgroundCompaction
的调用。
那么这个函数做啥呢,不就是个归并排序么?且慢,我们如何处理同一个user key有不同Sequence Number呢?我们的目标肯定是只保留最新的。
其中CompactionState
封装了Compaction
。
1 | Status DBImpl::DoCompactionWork(CompactionState* compact) { |
这里要assert一下,即要压缩的Level N层是要有文件的。
【Q】这个Snapshot啥回事?
根据文章,如果有Snapshot,则保留大于Snapshot SN的所有Record,以及一个小于Snapshot SN的Record中,SN最大的Record。
1 | assert(versions_->NumLevelFiles(compact->compaction->level()) > 0); |
我们执行MakeInputIterator
,得到的迭代器可以按照key大小遍历所有冲突文件中的每个KV对。
1 | Iterator* input = versions_->MakeInputIterator(compact->compaction); |
下面这个while循环遍历刚才得到的迭代器input
,进行Major Compaction。
但是,且慢,每一次我们都需要先检查有没有Immatable Memtable,如果有的话,就需要先执行Minor Compaction。这也说明了Minor Compaction的优先级更高。
【Q】我们看到了两个原子量的获取:
shutting_down_
,采用了Release-Acquire内存模型,保证了一定的并行顺序。
如果线程A Release Store,线程B Acquire Load,那么线程A中所有在Release前的(atomic或者非atomic)写,对线程B都可见。memory_order_relaxed
,采用了Relaxed内存模型。
只保证读写的原子性,不保证并发时和其他变量的顺序。
1 | while (input->Valid() && !shutting_down_.load(std::memory_order_acquire)) { |
检查当前输出文件(应当位于level+1层)是否与level+2层文件有过多冲突,如果是就要完成当前输出文件,并产生新的输出文件。
1 | Slice key = input->key(); |
下面就是判断是不是能drop
,也就是和前面计算的compact->smallest_snapshot
比较。
正常情况下ParseInternalKey
不会失败,我们跳过这个分支
1 | // Handle key/value, add to state, etc. |
下面这个if,判断的是current_user_key
第一次出现的情况,包括处理完上一个user key,到达下一个user key,或者刚开始处理第一个user key的情况。我们设置last_sequence_for_key
为最大,那么就永远不会触发drop。
1 | if (!has_current_user_key || |
下面我们比较Sequence Number,如果last_sequence_for_key
都小于compact->smallest_snapshot
了,那么我这个key肯定更小,这是因为Sequence Number是按照降序排列的。对于这种情况,我们省点事,直接不要了。
1 | if (last_sequence_for_key <= compact->smallest_snapshot) { |
下一个判断复杂点,表示对于特定情况下,一个删除操作也是可以丢掉的。
如果某个删除操作的版本小于快照版本,并且在更高层没有相同的user key,那么这个删除操作及其之前更早的插入操作可以同时丢弃了。
1 | } else if (ikey.type == kTypeDeletion && |
如果drop条件不符合,那么就写入到compact->current_output()
里面,同时更新largest。
同时我们关注文件大小,如果超限了,就FinishCompactionOutputFile。
1 | if (!drop) { |
截至现在,我们已经遍历完迭代器了。
1 | if (status.ok() && shutting_down_.load(std::memory_order_acquire)) { |
更新状态
1 | CompactionStats stats; |
下面,我们加锁。所以其实在遍历input
这个迭代器的时候,是没有在加锁的。InstallCompactionResults
是一个关键过程,它将这次Compaction的内容加入到VersionEdit里面,并且最终调用LogAndApply
。内容包括什么呢?增加和删除的文件:
InstallCompactionResults
会调用Compaction::AddInputDeletions
,需要删除的文件,包括input_[0]
和input_[1]
- 向
compact->compaction->edit()
中添加compact->outputs
中的所有文件
1 | mutex_.Lock(); |
Reference
- https://bean-li.github.io/leveldb-version/
- https://zhuanlan.zhihu.com/p/34674504
- https://blog.csdn.net/tmshasha/article/details/47703245
- https://zhuanlan.zhihu.com/p/51573929
- https://leveldb-handbook.readthedocs.io/zh/latest/basic.html
- https://blog.lovezhy.cc/2020/08/17/LevelDB%E6%BA%90%E7%A0%81%E8%A7%A3%E6%9E%90%EF%BC%88%E4%BA%94%EF%BC%89-%20CURRENT%E5%92%8CManifest/
- https://sf-zhou.github.io/leveldb/leveldb_08_complete_process.html
- http://blog.jcix.top/2018-05-11/leveldb_paths/
- http://bean-li.github.io/leveldb-version/
- https://zhuanlan.zhihu.com/p/46718964
- http://www.hootina.org/blog/articles/leveldb%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/leveldb%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%9019.html
- https://sf-zhou.github.io/leveldb/leveldb_08_complete_process.html
这是一个DB完整执行过程的表述。 - https://www.ravenxrz.ink/archives/1ba074b9.html
介绍了Snapshot - https://izualzhy.cn/leveldb-PickCompaction
解释了GetOverlappingInputs的原理 - https://izualzhy.cn/leveldb-version
解释了Version的实现 - http://lerencao.github.io/posts/lsm-tree-compaction-strategy/
- http://www.scylladb.com/2018/01/17/compaction-series-space-amplification/
上面两篇文章介绍STCS和LCS - https://zhuanlan.zhihu.com/p/181498475
图解Compact过程 - https://github.com/facebook/rocksdb/wiki/Compaction
RocksDB对Compaction的讲解 - https://blog.csdn.net/weixin_36145588/article/details/78064777
- https://sf-zhou.github.io/leveldb/leveldb_09_compaction.html
这位同学解释了AddBoundaryInputs的来源 - http://www.petermao.com/leveldb/leveldb-8-snapshot.html
介绍了snapshot机制 - https://zhuanlan.zhihu.com/p/60188395
带Snapshot的Compaction,以及为什么会导致Issue 320的问题 - https://zhuanlan.zhihu.com/p/360345923
也讲解了AddBoundaryInputs的来源,并且指出了快照会导致Issue 320的问题。 - https://zhuanlan.zhihu.com/p/35343043
讲解VersionSet/VersionEdit里面出现的各种文件编号 - https://leveldb-handbook.readthedocs.io/zh/latest/version.html
版本控制相关 - https://bean-li.github.io/leveldb-manifest/
有关Manifest文件的深入讨论 - http://1feng.github.io/2016/08/24/mvcc-and-manifest/
介绍MVCC机制,很好 - https://draveness.me/database-concurrency-control/
同样介绍了MVCC,包括乐观锁和悲观锁机制