引言
SSTable操作
SSTable如何工作？ SSTable在最初始的论文中可以总结出下面的特点：
- 写入的时候不写入磁盘而是先写入内存表的数据结构。
- 当数据结构内存占用超过一定的阈值就可以直接写入到磁盘文件由于已经是排好序的状态，所以可以对于旧结构覆盖，写入效率比较高。并且写入和数据结构改动可以同时进行。
- 读写顺序按照 内存 - 磁盘 - 上一次写入文件 - 未找到。
- 后台定时线程定时合并和压缩排序分段，将废弃值给覆盖或者丢弃。
[[SSTable]] 最早出现在谷歌的论文当中，LevelDB的SSTable设计也有部分特性体现这个数据结构，但是是否完全一致未知，LevelDB利用SSTable在磁盘中维护多层级的数据节点。
也可以认为了解SSTable结构就相当于了解了LevelDb的核心数据结构设计。
多层级SSTable
我们重点看看多层级的SSTable部分，levelDB在磁盘中扫描SSTable的时候LevelDB并不会跳过层级，这里肯定会有疑问每个层级都扫一遍的效率问题，针对这个问题作者在db中设计了下面的数据结构：
struct FileMetaData { FileMetaData() : refs(0), allowed_seeks(1 << 30), file_size(0) {} int refs; int allowed_seeks; // 允许压缩搜索 uint64_t number; uint64_t file_size; // 文件大小 InternalKey smallest; // 表提供的最小内部密钥 InternalKey largest; // 表提供最大内部密钥 };
在上面的结构体声明中定义了压缩SSTable文件的全部信息，包括最大值和最小值，运行查找次数，文件引用次数和文件号，SSTable会按照固定的形式存储到同一个目录下面，所以可以通过文件号进行快速搜索。
查找和记录key顺序类似，都是按照从小到大的顺序进行读取的，以Level0为例，里面通常包含4个固定的SSTable，并且内部通常存在key交叉，所以会按照从SSTable1-4的顺序进行读取，而更高层次的层级则通过查找上面结构体的最大值和最小值的信息（smallest和largest）。
具体的文件搜索细节可以通过TableCache::FindTable查找 ，由于篇幅有限这里就不贴代码了，简要逻辑是配合缓存和RandomAccessFile对于文件进行读写，然后把读到的文件信息写入到内存中方便下次获取。
如果了解Mysql Btree设计会发现文件搜索有些类似页目录的查找。不同的是Btree页目录通过页目录等稀疏搜索。
SSTable合并
了解完SSTable的查找，我们再来看看SSTable是如何合并的，之前提到过SSTable通过 MaybeScheduleCompaction尝试合并，需要注意这个合并压缩和Bigtable的形式类似，都是根据不同的条件判断是否进行合并，一旦可以合并便执行BackgroundCompaction操作。
另外合并分为两种情况，一种是Minor Compaction，另一种是将Memtable数据写满转为不可变对象（实际就是加锁），执行CompactMemtable进行压缩。
下面是合并的调用逻辑图：
合并操作简化版源代码如下：
void DBImpl::CompactMemTable() { VersionEdit edit; Version* base = versions_->current(); WriteLevel0Table(imm_, &edit, base); versions_->LogAndApply(&edit, &mutex_); RemoveObsoleteFiles(); }
CompactMemTable方法会先构建当前的修改版本号，然后调用WriteLevel0Table()方法尝试把当前的Imumtable写入到Level0的层级。 如果发现Level0的层级SSTable过多，则进一步进行Major Compaction，同时根据BackgroudCompcation()选择合适的压缩层级和压缩方式。
下面是writeLevel0的简化代码：
简化代码的最后几行代码会获取文件信息的最大值和最小值以此判断是否在当前SSTable搜索还是跳转到下一个。
数据如果是写入Level0我们可以看作是Major Compaction。
Status DBImpl::WriteLevel0Table(MemTable* mem, VersionEdit* edit, Version* base) { // SSTable文件信息 FileMetaData meta; meta.number = versions_->NewFileNumber(); pending_outputs_.insert(meta.number); Iterator* iter = mem->NewIterator(); // 构建SSTable文件 BuildTable(dbname_, env_, options_, table_cache_, iter, &meta); pending_outputs_.erase(meta.number); // 注意，如果 file_size 为零，则该文件已被删除，并且不应被添加到清单中。 // 获取文件信息的最大值和最小值 const Slice min_user_key = meta.smallest.user_key(); const Slice max_user_key = meta.largest.user_key(); // level层级扫描 base->PickLevelForMemTableOutput(min_user_key, max_user_key); // 写入文件 edit->AddFile(level, meta.number, meta.file_size, meta.smallest, return Status::ok();
结合上下两段源码可以发现文件管理最终是通过VersionEdit来完成的，如果写入成功了则返回当前的SSTable的FileMetaData，在VersionEdit内部通过logAndApply的方式记录文件内部的变化，也就是前文介绍的日志管理功能了，完成之后通过RemoveObsoleteFiles()方法进行数据的清理操作。
如果Level0写满了此时就需要进行Major Compaction，这个压缩会比前面的要复杂一些因为涉及低层级到高层级的压缩。
这里需要再回看BackgroundCompaction的代码，具体代码如下：
void DBImpl::BackgroundCompaction() { // 如果存在不可变imumem,进行压缩合并 CompactMemTable(); versions_->PickCompaction(); VersionSet::LevelSummaryStorage tmp; CompactionState* compact = new CompactionState(c); DoCompactionWork(compact); CleanupCompaction(compact); c->ReleaseInputs(); RemoveObsoleteFiles(); }
首先根据VersionSet 查找需要压缩的信息，并且打包加入到 Compaction 对象，这个对象根据查询次数和大小限制来选择需要压缩的两个层级，因为level0中包含很多重叠键，则会在更高层级找到有重叠的键的SSTable，再通过FileMetaData找到需要压缩的文件，另外查询频繁的SSTable将会“升级”到更高层级进行压缩存储，并且更新文件信息方便下一次查找。
合并的触发条件
每个 SSTable 在创建之后的 allowed_seeks 都为 100 次，当 allowed_seeks < 0 时就会触发该文件的与更高层级和合并，因为频繁查询的数据通常会降低系统性能。
这样的设计理由是在高层级搜索键说明在上一层肯定是相同的键查找，同时也是为了减少每次都覆盖扫描多层级扫描寻找数据。最终这种设计方式核心是以更新FileMetaData 来减少下一次查询的性能开销。
另外这种处理可以简单理解为我们在操作系统中进行深层次文件夹搜索的时候，如果频繁查询某个深层次的数据很麻烦，解决此问题的第一种方式是建立一个“快捷方式”的文件夹，另一种是直接做标签直接指向这个目录，其实两者都是差不多的，所以压缩设计也是同理。
吐槽：Major Compaction，Minor Compaction 这个名字有感觉和JVM的垃圾回收新生代和老年代回收熟悉感。
LevelDB 中的 DoCompactionWork 方法会对所有传入的 SSTable 中的键值使用归并排序进行合并，最后会在更高层级中生成一个新的 SSTable。
归并排序主要是对于key进行归并，使得迭代的时候key就是有序的可以直接合并到指定的高高层级。关键代码存在于下面的代码
Iterator* input = versions_->MakeInputIterator(compact->compaction);
归并排序
[[DoCompactionWork归并排序]] 的源代码如下：
Status DBImpl::DoCompactionWork(CompactionState* compact) { int64_t imm_micros = 0; // Micros spent doing imm_ compactions if (snapshots_.empty()) { // 快照为空，找到直接采用记录信息的最后序列号 compact->smallest_snapshot = versions_->LastSequence(); } else { // 快照存在，则抛弃之前所有的序列 compact->smallest_snapshot = snapshots_.oldest()->sequence_number(); } // 对于待压缩数据进行，内部生成一个MergingIterator，当构建迭代器之后键内部就是有序的状态了，也就是前面说的归并排序的部分 Iterator* input = versions_->MakeInputIterator(compact->compaction); input->SeekToFirst(); Status status; ParsedInternalKey ikey; std::string current_user_key; //当前记录user key bool has_current_user_key = false; SequenceNumber last_sequence_for_key = kMaxSequenceNumber; while (input->Valid() && !shutting_down_.load(std::memory_order_acquire)) { // 优先考虑imumemtable的压缩工作 if (has_imm_.load(std::memory_order_relaxed)) { const uint64_t imm_start = env_->NowMicros(); imm_micros += (env_->NowMicros() - imm_start); } Slice key = input->key(); if (compact->compaction->ShouldStopBefore(key) && compact->builder != nullptr) { status = FinishCompactionOutputFile(compact, input); } // 处理键/值，添加到状态等。 bool drop = false; if (!ParseInternalKey(key, &ikey)) { // 删除和隐藏呗删除key current_user_key.clear(); has_current_user_key = false; // 更新序列号 last_sequence_for_key = kMaxSequenceNumber; } else { if (!has_current_user_key || user_comparator()->Compare(ikey.user_key, Slice(current_user_key)) != 0) { // 用户key第一次出现 current_user_key.assign(ikey.user_key.data(), ikey.user_key.size()); has_current_user_key = true; last_sequence_for_key = kMaxSequenceNumber; } if (last_sequence_for_key <= compact->smallest_snapshot) { // 压缩以后旧key边界的被新的覆盖 drop = true; // (A) } else if (ikey.type == kTypeDeletion && ikey.sequence <= compact->smallest_snapshot && compact->compaction->IsBaseLevelForKey(ikey.user_key)) { // 对于这个用户密钥： // (1) 高层没有数据 // (2) 较低层的数据会有较大的序列号 // (3) 层中的数据在此处被压缩并具有 // 较小的序列号将在下一个被丢弃 // 这个循环的几次迭代（根据上面的规则（A））。 // 因此，此删除标记已过时，可以删除。 drop = true; } last_sequence_for_key = ikey.sequence; } }
归并排序并且处理完键值信息完成跨层级压缩，之后便是是一些收尾工作，收尾工作需要对于压缩之后的信息统计。
CompactionStats stats; stats.micros = env_->NowMicros() - start_micros - imm_micros; //选择两个层级的SSTable for (int which = 0; which < 2; which++) { for (int i = 0; i < compact->compaction->num_input_files(which); i++) { stats.bytes_read += compact->compaction->input(which, i)->file_size; } } for (size_t i = 0; i < compact->outputs.size(); i++) { stats.bytes_written += compact->outputs[i].file_size; } // 压缩到更高的层级 stats_[compact->compaction->level() + 1].Add(stats); // 注册压缩结果 InstallCompactionResults(compact); // 压缩信息存储 VersionSet::LevelSummaryStorage tmp; Log(options_.info_log, "compacted to: %s", versions_->LevelSummary(&tmp)); return status;
最后层级压缩的默认层级为7个层级，在源代码中有如下定义：
static const int kNumLevels = 7;
小结：
这里我们小结一下合并压缩的两个操作：Minor Compaction和Major Compaction：
Minor Compaction：这个GC主要是Level0层级的一些压缩操作，由于Level0层级被较为频繁使用，类似一级缓存，键值不会强制要求进行排序，所以重叠的键会比较多，整个压缩的过程比较好理解，关键部分是skiplist（跳表）中构建一个新的SSTable并且插入到指定层级。
注：Minor Compaction进行的时候会暂停Major Compaction操作。
Minor Compaction：这个比Minor Compaction复杂不少，不仅包含跨层级压缩，还包括键范围确定和迭代器归并排序和最终的统计信息操作，其中最最关键的部分是归并排序压缩列表，之后将旧文件和新文件合并生产新的VersionSet信息，另外这里除开全局的压缩进度和管理操作之外。
另外Minor Compaction完成之后还会再尝试一次Minor Compaction，因为Minor Compaction可能回带来更多的重复键，所以再进行一次压缩可以进一步提高查找效率。
Major Compaction：这个操作需要暂停整个LevelDB的读写，因为此时需要对于整个LevelDb的多层级进行跨层级合并，跨层级压缩要复杂很多，具体的细节会在后面介绍。
这里可以认为是作者在测试的过程发现一种情况并且做的优化。
存储状态 - VersionSet
从这个对象名称来看直接理解为“版本集合”，在内部通过一个Version的结构体对于键值信息进行“版本控制”，毫无疑问这是由于多线程压缩所带来的特性，所以最终是一个双向链表+历史版本的形式串联，但是永远只有一个版本是当前版本。 VersionSet最为频繁也是比较关键的一个操作函数[[LogAndApply]]，下面是简化之后的VersionSet::LogAndApply代码：
这里可以对照关系型数据库Mysql的Mvcc中的undo log类比进行理解
Status VersionSet::LogAndApply(VersionEdit* edit, port::Mutex* mu) { // 更新版本链表信息 if (!edit->has_prev_log_number_) { edit->SetPrevLogNumber(prev_log_number_); } edit->SetNextFile(next_file_number_); edit->SetLastSequence(last_sequence_); Version* v = new Version(this); // 构建当前的版本version，委托给建造器进行构建 Builder builder(this, current_); builder.Apply(edit); builder.SaveTo(v); // 关键方法：内部通过打分机制确定文件所在的层级，值得注意的是level0的层级确定在源代码中有较多描述 Finalize(v); // 如有必要，通过创建包含当前版本快照的临时文件来初始化新的描述符日志文件。 std::string new_manifest_file; // 没有理由在这里解锁*mu，因为我们只在第一次调用LogAndApply时（打开数据库时）碰到这个路径。 new_manifest_file = DescriptorFileName(dbname_, manifest_file_number_); // 写入mainfest文件 env_->NewWritableFile(new_manifest_file, &descriptor_file_); // 写入版本信息快照 WriteSnapshot(descriptor_log_); // 把记录写到 MANIFEST中 descriptor_log_->AddRecord(record); //如果创建了新的文件，则将当前版本指向这个文件 SetCurrentFile(env_, dbname_, manifest_file_number_); // 注册新版本 AppendVersion(v); return Status::OK(); }
关键部分注释已给出，这里的Mainfest细节在之前没有提到过，在作者提供的impl.md是这样介绍mainfest的：
MANIFEST 文件列出了组成每个级别的排序表集、相应的键范围和其他重要的元数据。 每当重新打开数据库时，都会创建一个新的 MANIFEST 文件（文件名中嵌入了一个新编号）。 MANIFEST 文件被格式化为日志，并且对服务状态所做的更改（随着文件的添加或删除）被附加到此日志中。
从个人的角度来看，这个文件有点类似BigTable中的元数据Meta。
SSTable文件格式
理解这部分不需要急着看源代码，在仓库中的table_format.md的文件中同样有相关描述，这里就直接照搬官方文档翻译了：
leveldb 文件格式 <beginning_of_file> [数据块 1] [数据块 2] ... [数据块N] [元块 1] ... [元块K] [元索引块] [索引块] [页脚]（固定大小；从 file_size - sizeof(Footer) 开始） <end_of_file>
我们可以根据描述画一个对应的结构图：
上面的结构图从上至下的介绍如下：
- 数据块：按照LSM-Tree的数据存储规范，按照key/value的顺序形式进行排序，数据块根据
block.builder.cc的内部逻辑进行格式化，并且可以选择是否压缩存储。 - 元数据块：元数据块和数据块类似也使用
block.builder.cc进行格式化，同时可选是否压缩，元数据块后续回扩展更多的类型（主要用作数据类型记录） - “元索引”块：为每个其他元数据块索引，键为元块的名称，值是指向该元块的 BlockHandle。
- “索引块”：包含数据块的索引，键是对应字符串>=数据块的最后一个键，并且在连续的数据块的第一个键之前，值是数据块的 BlockHandle。
- 文件的最后是一个固定长度的页脚，其中包含元索引和索引块的 BlockHandle 以及一个幻数。
幻数又被称为魔数，比如JAVA的字节码第一个字节8位是
CAFEBABE，数值和字节大小没什么意义，更多是作者的兴趣。
注意Footer页脚固定48个字节的大小，我们能在其中拿到 元索引块 和 索引块的位置，然后通过这两个索引寻找其他值对应的位置。
更详细的内容可以继续参考table_format.md介绍，这里就不再赘述了。
TableBuilder：
SSTable接口定义于一个TableBuilder构建器当中，TableBuilder 提供了用于构建 Table 的接口，关于此接口的定义如下：
TableBuilder提供了用于建立表的接口 (一个从键到值的不可变和排序的映射)。
多个线程可以在一个TableBuilder上调用const方法而不需要外部同步。但如果任何一个线程可能调用一个非常量方法，所有访问同一个TableBuilder的线程必须使用外部同步。
// TableBuilder 提供了用于构建 Table 的接口 //（从键到值的不可变且排序的映射）。 // // 多个线程可以在 TableBuilder 上调用 const 方法，而无需 // 外部同步，但如果任何线程可能调用 // 非常量方法，所有访问同一个 TableBuilder 的线程都必须使用 // 外部同步。 class LEVELDB_EXPORT TableBuilder { public: TableBuilder(const Options& options, WritableFile* file); TableBuilder(const TableBuilder&) = delete; TableBuilder& operator=(const TableBuilder&) = delete; /* 改变该构建器所使用的选项。注意：只有部分的 选项字段可以在构建后改变。如果一个字段是 不允许动态变化，并且其在结构中的值 中的值与传递给本方法的结构中的值不同。 结构中的值不同，该方法将返回一个错误 而不改变任何字段。 */ Status ChangeOptions(const Options& options); void Add(const Slice& key, const Slice& value); void Flush(); Status status() const; Status Finish(); /* 表示应该放弃这个建设者的内容。停止 在此函数返回后停止使用传递给构造函数的文件。 如果调用者不打算调用Finish()，它必须在销毁此构建器之前调用Abandon() 之前调用Abandon()。 需要。Finish()、Abandon()未被调用。 */ void Abandon(); uint64_t NumEntries() const; uint64_t FileSize() const; private: bool ok() const { return status().ok(); } void WriteBlock(BlockBuilder* block, BlockHandle* handle); void WriteRawBlock(const Slice& data, CompressionType, BlockHandle* handle); struct Rep; Rep* rep_; }; }
小结：
SSTable 相关的设计在整个LevelDB中有着重要的地位和作用，我们介绍了SSTable的多层级合并和压缩的细节，以及两种不同的压缩形式，第一种是针对Level0的简单压缩，简单压缩只需要把存在于内存中的SSTable也就是将Imumemtable压缩到磁盘中存储，特别注意的是这个动作在第一次完成之后通常还会再执行一次。
另一种是针对频繁Key查询进行的多层级压缩，多层级压缩要比简单压缩复杂许多，但是多层级压缩是提高整个LevelDB写入性能和查询性能到关键。
最后，从LevelDB中也可以看到很多经典数据结构和算法的实现，比键管理利用了跳表+归并排序的方式提高管理效率，排序的内容不仅利于查询，在存储的时候也有利于数据的顺序扫描。
Skiplist跳表
跳表不仅在LevelDb中使用，还在许多其他的中间件中存在实现，这一部分内容将会放到下一篇文章单独介绍。
