Rocksdb Compaction源码详解（二）：Compaction 完整实现过程 概览

1. 摘要

阅读本文前建议看看Rocksdb Compaction 源码详解（一）：SST文件详细格式源码解析，先初步了compaction操作的SST文件结构

Rocksdb的compaction流程可以说是比较核心的流程了，它的存在除了保证不同sst 文件之间的key-value之间的有序性，数据的压缩存储，清理过时数据之外，还需要在存储细节上做一些优化来进一步提升LSM tree的读性能（Range tombstone的构造，提升了deleteRange区间的key-value的判断效率；filter block的创建，提升判断一个key是否存在的概率；index block的创建，支持二分查找和hash map的查找，提升针对普通key-value的查找性能…）。

虽然LSM tree的顺序写入保证了写性能，但是其本身的存储结构却牺牲了读性能，所以需要通过compaction这样的机制随着IO的持续写入来不断得微调整 整个数据存储系统的结构，来降低读对系统的影响。

本节中涉及的代码都是基于rocksdb 6.6.fb版本来描述的，阅读完预计一个多小时，建议大家先概览，然后选择部分感兴趣的来看，欢迎大家一起交流讨论

2. Compaction 概述

接下来我将带领大家欣赏这样一个有趣机制的实现，

rocksdb实现了多种这样的compaction策略，这里以默认的level compaction为切入点:

如图2.1 对compaction的实现做了一个整体的描述，图有点复杂？这张图能够将compaction的大体流程讲清楚，但对于其中的一些优化细节的实现还是太过笼统。限于本人能力有限，会在自己能力范围内为大家讲清楚这个机制。

图2.1 compaction整体流程概述

主要分为三个阶段:

1. Prepare key，主要是从SST文件中读取需要参与compaction的key-value数据
2. Process key，主要是进行key value数据的合并，排序，处理不同的key type的操作
3. write key，将key-value数据写入对应的block数据之中

不过其详细实现并不是三个阶段这么简单，非常多的细节，看看上面那张笼统概述的图就知道了。

3. 实现

上图将整个Compaction的总体过程分为三部分，这个划分并不是官方的划分，只是为了方便大家理解，从代码中提炼出来的主要逻辑。为了避免篇幅太过冗长，这里选择将对应代码逻辑的calltrace 添加进来，对于有趣的关键逻辑再做详细说明。以下部分到描述 对应上图中的流程就是从左向右看的三个部分：

3.1 Prepare keys 过程

​ 主要做如下几件事情:

• 根据每一层的score来 取出参与compaction 层
• 利用clean cut算法来 来从层中取出参与compaction的文件
• 将文件中的key-value 边界取出，并做一个边界排序，确认最终的key的边界范围
• 依据边界范围，按照subcompaction limit 拆分成一个一个subcompaction ， 创建对应的sub处理的线程，进入下一个阶段

大体过程如下 图3.1

图3.1 compaction到prepare key 部分

3.1.1 compaction触发的条件

rocksdb的compaction都是后台运行，通过线程BGWorkCompaction 进行compaction的调度。

该线程的触发一般有两种情况

一种是手动compact, CompactFiles来进行手动compaction操作

另一种是自动MaybeScheduleFlushOrCompaction，这个函数在切换wal（SwitchWAL）或者write_buffer(memtable)满的时候被调用。

我们主要还是分析自动compaction的逻辑，这也是通用逻辑。接下来分析MaybeScheduleFlushOrCompaction函数中的compact逻辑，这里可以看到RocksDB中后台运行的compact会有一个限制(max_compactions).而我们可以看到这里还有一个变量 unscheduled_compactions_，这个变量表示需要被compact的columnfamily的队列长度.

 while (bg_compaction_scheduled_ < bg_job_limits.max_compactions && unscheduled_compactions_ > 0) { 
    CompactionArg* ca = new CompactionArg; ca->db = this; ca->prepicked_compaction = nullptr; bg_compaction_scheduled_++; //正在被调度的compaction线程数目 unscheduled_compactions_--; //待调度的线程个数，及待调度的cfd的长度 //调度BGWorkCompaction线程 env_->Schedule(&DBImpl::BGWorkCompaction, ca, Env::Priority::LOW, this, &DBImpl::UnscheduleCompactionCallback); } 

compact的时候RocksDB也有一个队列叫做DBImpl::compaction_queue_.

std::deque<ColumnFamilyData*> compaction_queue_; 

这个队列的更新是在函数SchedulePendingCompaction更新的，且unscheduled_compactions_变量是和该函数一起更新的，也就是只有设置了该变量才能够正常调度compaction后台线程。

void DBImpl::SchedulePendingCompaction(ColumnFamilyData* cfd) { 
    if (!cfd->queued_for_compaction() && cfd->NeedsCompaction()) { 
    AddToCompactionQueue(cfd); ++unscheduled_compactions_; } } 

上面的核心函数是NeedsCompaction,通过这个函数来判断是否有sst需要被compact，因此接下来我们就来详细分析这个函数.当满足下列几个条件之一就将会更新compact队列,通过调用LevelCompactionPicker::NeedsCompaction函数来进行是否满足compaction的条件判断的，以下条件只要满足一个就可以进行compaction的调度：

• 有超时的sst(ExpiredTtlFiles)
• files_marked_for_compaction或者bottommost_files_marked_for_compaction都不为空
  两个vector类型的数组
  
  
• 遍历所有的level的sst,然后判断是否需要compact
  这里通过每个sst的score进行判断，后续会对该score进行描述
  
  

bool LevelCompactionPicker::NeedsCompaction( const VersionStorageInfo* vstorage) const { 
    if (!vstorage->ExpiredTtlFiles().empty()) { 
    return true; } if (!vstorage->FilesMarkedForPeriodicCompaction().empty()) { 
    return true; } if (!vstorage->BottommostFilesMarkedForCompaction().empty()) { 
    return true; } if (!vstorage->FilesMarkedForCompaction().empty()) { 
    return true; } for (int i = 0; i <= vstorage->MaxInputLevel(); i++) { 
    if (vstorage->CompactionScore(i) >= 1) { 
    return true; } } return false; } 

3.1.2 compaction 的文件筛选过程

因此接下来我们来分析最核心的CompactionScore,这里将会涉及到两个变量,这两个变量分别保存了level以及每个level所对应的score(这里score越高表示compact优先级越高)，而score小于１则表示不需要compact.

这里是通过两个数组进行相关变量的更新

 std::vector<double> compaction_score_; //当前sst的score std::vector<int> compaction_level_; //当前sst需要被compact到的层level 

这两个变量的更新是在函数void VersionStorageInfo::ComputeCompactionScore中被更新的，这个函数会区别leve-0和其他level的处理逻辑

1. 首先会计算level-0下所有文件的大小(total_size)以及文件个数(num_sorted_runs).
2. 用文件个数除以level0_file_num_compaction_trigger来得到对应的score
3. 针对levelStyle的compaction，需要从上面的score和(total_size/max_bytes_for_level_base)取最大值,作为当前参与compaction的score。因为有的时候level-0在密集型IO场景下会瞬时达到很大，超过level-1的max_bytes_for_level_base，所以需要针对这种场景设置score

void VersionStorageInfo::ComputeCompactionScore( ...... for (int level = 0; level <= MaxInputLevel(); level++) { 
    double score; if (level == 0) { 
    ...... int num_sorted_runs = 0; uint64_t total_size = 0; for (auto* f : files_[level]) { 
    if (!f->being_compacted) { 
    total_size += f->compensated_file_size; //所有level-0文件总大小 num_sorted_runs++; //所有文件个数 } } ...... score = static_cast<double>(num_sorted_runs) / mutable_cf_options.level0_file_num_compaction_trigger; if (compaction_style_ == kCompactionStyleLevel && num_levels() > 1) { 
    // Level-based involves L0->L0 compactions that can lead to oversized // L0 files. Take into account size as well to avoid later giant // compactions to the base level. score = std::max( score, static_cast<double>(total_size) / mutable_cf_options.max_bytes_for_level_base); } } 

针对非level-0的处理逻辑，也是获取当前level未正在进行compaction的所有文件大小，然后除以MaxBytesForLevel得到score

 // Compute the ratio of current size to size limit. uint64_t level_bytes_no_compacting = 0; for (auto f : files_[level]) { 
    if (!f->being_compacted) { 
    level_bytes_no_compacting += f->compensated_file_size; } } score = static_cast<double>(level_bytes_no_compacting) / MaxBytesForLevel(level); } compaction_level_[level] = level; compaction_score_[level] = score; 

3.1.3 compaction每一层level大小的计算过程

一种是静态的数值，即每一层的大小都是固定的

一种是动态调整的，动态根据每一层大小进行计算，得到最大level_max_bytes，并依此递推之前的level

其中函数有一个函数 MaxBytesForLevel(level)，很明显就是获取当前level的最大的文件大小。实现如下:

uint64_t VersionStorageInfo::MaxBytesForLevel(int level) const { 
    // Note: the result for level zero is not really used since we set // the level-0 compaction threshold based on number of files. assert(level >= 0); assert(level < static_cast<int>(level_max_bytes_.size())); return level_max_bytes_[level]; } 

其中数组level_max_bytes_ 的更新是在CalculateBaseBytes函数中进行，在其中的更新过程还是与我们option设置的一个参数相关

level_compaction_dynamic_level_bytes，如果这个配置被置为false，意味着每一层的大小都是固定的，则会有如下的更新规则：

• 如果是level-1 ，那么将其level_max_bytes_设置为options.max_bytes_for_level_base 这样的配置
• 如果是大于level-1的level，则他们的level_max_bytes_ 计算方式如下:

  Level-n = level_max_bytes_[n – 1] * max_bytes_for_level_multiplier*max_bytes_for_level_multiplier_additional[n]

其中 max_bytes_for_level_multiplier和max_bytes_for_level_multiplier_additional都是通过option进行设置的，其中max_bytes_for_level_multiplier_additional默认为1

假如: max_bytes_for_level_base = 1024 ，max_bytes_for_level_multiplier = 10

则L1,L2,L3 依次为：1024，10240，的大小

 if (!ioptions.level_compaction_dynamic_level_bytes) { 
    base_level_ = (ioptions.compaction_style == kCompactionStyleLevel) ? 1 : -1; // Calculate for static bytes base case for (int i = 0; i < ioptions.num_levels; ++i) { 
    if (i == 0 && ioptions.compaction_style == kCompactionStyleUniversal) { 
    level_max_bytes_[i] = options.max_bytes_for_level_base; } else if (i > 1) { 
    level_max_bytes_[i] = MultiplyCheckOverflow( MultiplyCheckOverflow(level_max_bytes_[i - 1], options.max_bytes_for_level_multiplier), options.MaxBytesMultiplerAdditional(i - 1)); } else { 
    level_max_bytes_[i] = options.max_bytes_for_level_base; } } } 

假如level_compaction_dynamic_level_bytes 被设置为true，即每次计算出来的level_max_bytes可能会不一样

这个参数主要是为了保证LSM tree密集IO压力下仍然能够保证合理的树型结构（良好的树型结构能够提供优秀的查找性能），这里的计算方式是这样的

• 找到当前树形结构数据量最多的一层，作为Target_Size(Ln)
• 通过公式Target_Size(Ln-1) = Target_Size(Ln) / max_bytes_for_level_multiplier递推之前的level大小

比如当前系统中最大的level的 target size是10G，num_levels = 6,max_bytes_for_level_multiplier = 10

那么从L6-L1依次每一层level的大小如下，10G,1G,102M,10.2M,1.02M,102KB

首先计算第一个非空的level.

 uint64_t max_level_size = 0; int first_non_empty_level = -1; for (int i = 1; i < num_levels_; i++) { 
    uint64_t total_size = 0; for (const auto& f : files_[i]) { 
    total_size += f->fd.GetFileSize(); } if (total_size > 0 && first_non_empty_level == -1) { 
    first_non_empty_level = i; } if (total_size > max_level_size) { 
    max_level_size = total_size; } } 

得到最小的那个非0的level的size.

 uint64_t base_bytes_max = std::max(options.max_bytes_for_level_base, l0_size); uint64_t base_bytes_min = static_cast<uint64_t>( base_bytes_max / options.max_bytes_for_level_multiplier); uint64_t cur_level_size = max_level_size; for (int i = num_levels_ - 2; i >= first_non_empty_level; i--) { 
    // Round up after dividing cur_level_size = static_cast<uint64_t>( cur_level_size / options.max_bytes_for_level_multiplier); } 

找到base_level_size，一般来说也就是cur_level_size.

 // Find base level (where L0 data is compacted to). base_level_ = first_non_empty_level; while (base_level_ > 1 && cur_level_size > base_bytes_max) { 
    --base_level_; cur_level_size = static_cast<uint64_t>( cur_level_size / options.max_bytes_for_level_multiplier); } if (cur_level_size > base_bytes_max) { 
    // Even L1 will be too large assert(base_level_ == 1); base_level_size = base_bytes_max; } else { 
    base_level_size = cur_level_size; } 

然后给level_max_bytes赋值

 uint64_t level_size = base_level_size; for (int i = base_level_; i < num_levels_; i++) { 
    if (i > base_level_) { 
    level_size = MultiplyCheckOverflow(level_size, level_multiplier_); } level_max_bytes_[i] = std::max(level_size, base_bytes_max); } 

3.1.4 挑选参与compaction的文件

其中Compact的所有操作都在DBImpl::BackgroundCompaction中进行，因此接下来我们来分析 这个函数. 首先是从compaction_queue_队列中读取第一个需要compact的column family.

 // cfd is referenced here auto cfd = PopFirstFromCompactionQueue(); // We unreference here because the following code will take a Ref() on // this cfd if it is going to use it (Compaction class holds a // reference). // This will all happen under a mutex so we don't have to be afraid of // somebody else deleting it. if (cfd->Unref()) { 
    delete cfd; // This was the last reference of the column family, so no need to // compact. return Status::OK(); } 

没有禁止自动compaction的时候，接下来通过PickCompaction选取当前CF中所需要compact的内容.

if (!mutable_cf_options->disable_auto_compactions && !cfd->IsDropped()) { 
    c.reset(cfd->PickCompaction(*mutable_cf_options, log_buffer)); ... } 

而这个函数会根据设置的不同的Compact策略调用不同的方法，这里我们只看默认的LevelCompact的对应函数.

Compaction* LevelCompactionBuilder::PickCompaction() { 
    // Pick up the first file to start compaction. It may have been extended // to a clean cut. SetupInitialFiles(); if (start_level_inputs_.empty()) { 
    return nullptr; } assert(start_level_ >= 0 && output_level_ >= 0); // If it is a L0 -> base level compaction, we need to set up other L0 // files if needed. if (!SetupOtherL0FilesIfNeeded()) { 
    return nullptr; } // Pick files in the output level and expand more files in the start level // if needed. if (!SetupOtherInputsIfNeeded()) { 
    return nullptr; } // Form a compaction object containing the files we picked. Compaction* c = GetCompaction(); TEST_SYNC_POINT_CALLBACK("LevelCompactionPicker::PickCompaction:Return", c); return c; } 

这里PickCompaction分别调用了三个主要的函数.

• SetupInitialFiles　这个函数主要用来初始化需要Compact的文件.
• SetupOtherL0FilesIfNeeded 如果需要compact的话，那么还需要再设置对应的L0文件
• SetupOtherInputsIfNeeded 选择对应的输出文件

先来看SetupInitialFiles,这个函数他会遍历所有的level,然后来选择对应需要compact的input和output.

这里可看到，他会从之前计算好的的compact信息中得到对应的score.

void LevelCompactionBuilder::SetupInitialFiles() { 
    // Find the compactions by size on all levels. bool skipped_l0_to_base = false; for (int i = 0; i < compaction_picker_->NumberLevels() - 1; i++) { 
    start_level_score_ = vstorage_->CompactionScore(i); start_level_ = vstorage_->CompactionScoreLevel(i); assert(i == 0 || start_level_score_ <= vstorage_->CompactionScore(i - 1)); ................................................................ } 

只有当score大于一才有必要进行compact的处理(所有操作都在上面的循环中).这里可以看到如果是level0的话，那么output_level 则是vstorage_->base_level(),否则就是level+1. 这里base_level()可以认为就是level1或者是最小的非空的level(之前*CalculateBaseBytes*中计算).

if (start_level_score_ >= 1) { 
    if (skipped_l0_to_base && start_level_ == vstorage_->base_level()) { 
    // If L0->base_level compaction is pending, don't schedule further // compaction from base level. Otherwise L0->base_level compaction // may starve. continue; } output_level_ = (start_level_ == 0) ? vstorage_->base_level() : start_level_ + 1; if (PickFileToCompact()) { 
    // found the compaction! if (start_level_ == 0) { 
    // L0 score = `num L0 files` / `level0_file_num_compaction_trigger` compaction_reason_ = CompactionReason::kLevelL0FilesNum; } else { 
    // L1+ score = `Level files size` / `MaxBytesForLevel` compaction_reason_ = CompactionReason::kLevelMaxLevelSize; } break; } else { 
    // didn't find the compaction, clear the inputs ...................................................... } } } 

上面的代码中我们可以看到最终是通过*PickFileToCompact*来选择input以及output文件.因此我们接下来就来分这个函数.

首先是得到当前level(start_level_)的未compacted的最大大小的文件

 // Pick the largest file in this level that is not already // being compacted const std::vector<int>& file_size = vstorage_->FilesByCompactionPri(start_level_); const std::vector<FileMetaData*>& level_files = vstorage_->LevelFiles(start_level_); 

紧接着就是这个函数最核心的功能了，它会开始遍历当前的输入level的所有待compact的文件，然后选择一些合适的文件然后compact到下一个level.

unsigned int cmp_idx; for (cmp_idx = vstorage_->NextCompactionIndex(start_level_); cmp_idx < file_size.size(); cmp_idx++) { 
    .......................................... } 

然后我们来详细分析上面循环中所做的事情 首先选择好文件之后，将会扩展当前文件的key的范围，得到一个”clean cut”的范围， 这里”clean cut”是这个意思，假设我们有五个文件他们的key range分别为:

f1[a1 a2] f2[a3 a4] f3[a4 a6] f4[a6 a7] f5[a8 a9] 

如果我们第一次选择了f3,那么我们通过clean cut，则将还会选择f2,f4，因为他们都是连续的. 选择好之后，会再做一次判断，这次是判断是否正在compact的out_level的文件范围是否和我们选择好的文件的key有重合，如果有，则跳过这个文件. 这里之所以会有这个判断，主要原因还是因为compact是会并行的执行的.

int index = file_size[cmp_idx]; auto* f = level_files[index]; // do not pick a file to compact if it is being compacted // from n-1 level. if (f->being_compacted) { 
    continue; } start_level_inputs_.files.push_back(f); start_level_inputs_.level = start_level_; if (!compaction_picker_->ExpandInputsToCleanCut(cf_name_, vstorage_, &start_level_inputs_) || compaction_picker_->FilesRangeOverlapWithCompaction( { 
   start_level_inputs_}, output_level_)) { 
    // A locked (pending compaction) input-level file was pulled in due to // user-key overlap. start_level_inputs_.clear(); continue; } 

选择好输入文件之后，接下来就是选择输出level中需要一起被compact的文件(output_level_inputs). 实现也是比较简单，就是从输出level的所有文件中找到是否有和上面选择好的input中有重合的文件，如果有，那么则需要一起进行compact.

Ps:这里的输出并不是说已经完成输出的过程了，而是提前计算后续将要输出到 哪一层

 InternalKey smallest, largest; compaction_picker_->GetRange(start_level_inputs_, &smallest, &largest); CompactionInputFiles output_level_inputs; output_level_inputs.level = output_level_; vstorage_->GetOverlappingInputs(output_level_, &smallest, &largest, &output_level_inputs.files); if (!output_level_inputs.empty() && !compaction_picker_->ExpandInputsToCleanCut(cf_name_, vstorage_, &output_level_inputs)) { 
    start_level_inputs_.clear(); continue; } base_index_ = index; break; 

继续分析PickCompaction，我们知道在RocksDB中level-0会比较特殊，那是因为只有level-0中的文件是无序的，而在上面的操作中， 我们是假设在非level-0,因此接下来我们需要处理level-0的情况,这个函数就是 SetupOtherL0FilesIfNeeded.

这里如果start_level_为０，也就是level-0的话，才会进行下面的处理，就是从level-0中得到所有的重合key的文件，然后加入到start_level_inputs中.

实现上通过调用 GetOverlappingL0Files 来实现

 assert(level0_compactions_in_progress()->empty()); InternalKey smallest, largest; GetRange(*start_level_inputs, &smallest, &largest); // Note that the next call will discard the file we placed in // c->inputs_[0] earlier and replace it with an overlapping set // which will include the picked file. start_level_inputs->files.clear(); vstorage->GetOverlappingInputs(0, &smallest, &largest, &(start_level_inputs->files)); // If we include more L0 files in the same compaction run it can // cause the 'smallest' and 'largest' key to get extended to a // larger range. So, re-invoke GetRange to get the new key range GetRange(*start_level_inputs, &smallest, &largest); if (IsRangeInCompaction(vstorage, &smallest, &largest, output_level, parent_index)) { 
    return false; } assert(!start_level_inputs->files.empty()); 

假设start_level_inputs被扩展了，那么对应的output也需要被扩展，因为非level0的其他的level的文件key都是不会overlap的. 那么此时就是会调用 SetupOtherInputsIfNeeded .

 if (output_level_ != 0) { 
    output_level_inputs_.level = output_level_; if (!compaction_picker_->SetupOtherInputs( cf_name_, mutable_cf_options_, vstorage_, &start_level_inputs_, &output_level_inputs_, &parent_index_, base_index_)) { 
    return false; } compaction_inputs_.push_back(start_level_inputs_); if (!output_level_inputs_.empty()) { 
    compaction_inputs_.push_back(output_level_inputs_); } // In some edge cases we could pick a compaction that will be compacting // a key range that overlap with another running compaction, and both // of them have the same output level. This could happen if // (1) we are running a non-exclusive manual compaction // (2) AddFile ingest a new file into the LSM tree // We need to disallow this from happening. if (compaction_picker_->FilesRangeOverlapWithCompaction(compaction_inputs_, output_level_)) { 
    // This compaction output could potentially conflict with the output // of a currently running compaction, we cannot run it. return false; } compaction_picker_->GetGrandparents(vstorage_, start_level_inputs_, output_level_inputs_, &grandparents_); } else { 
    compaction_inputs_.push_back(start_level_inputs_); } return true; 

回到 PickCompaction 函数，最终就是构造一个compact返回

 // Form a compaction object containing the files we picked. Compaction* c = GetCompaction(); TEST_SYNC_POINT_CALLBACK("LevelCompactionPicker::PickCompaction:Return", c); return c; 

3.1.5 Compaction job根据获取到数据分配compaction 线程

最后再回到BackgroundCompaction中，这里就是在得到需要compact的文件之后，进行具体的compact. 这里我们可以看到核心的数据结构就是CompactionJob,每一次的compact都是一个job,最终对于文件的compact都是在 CompactionJob::run中实现.

CompactionJob compaction_job( job_context->job_id, c.get(), immutable_db_options_, env_options_for_compaction_, versions_.get(), &shutting_down_, preserve_deletes_seqnum_.load(), log_buffer, directories_.GetDbDir(), GetDataDir(c->column_family_data(), c->output_path_id()), stats_, &mutex_, &bg_error_, snapshot_seqs, earliest_write_conflict_snapshot, snapshot_checker, table_cache_, &event_logger_, c->mutable_cf_options()->paranoid_file_checks, c->mutable_cf_options()->report_bg_io_stats, dbname_, &compaction_job_stats); compaction_job.Prepare(); NotifyOnCompactionBegin(c->column_family_data(), c.get(), status, compaction_job_stats, job_context->job_id); mutex_.Unlock(); compaction_job.Run(); TEST_SYNC_POINT("DBImpl::BackgroundCompaction:NonTrivial:AfterRun"); mutex_.Lock(); status = compaction_job.Install(*c->mutable_cf_options()); if (status.ok()) { 
    InstallSuperVersionAndScheduleWork( c->column_family_data(), &job_context->superversion_context, *c->mutable_cf_options(), FlushReason::kAutoCompaction); } *made_progress = true; 

在RocksDB中，Compact是会多线程并发的执行，而这里怎样并发，并发多少线程都是在CompactionJob中实现的，简单来说，当你的compact的文件range不重合的话，那么都是可以并发执行的。

我们先来看CompactionJob::Prepare函数，在这个函数中主要是做一些执行前的准备工作，首先是取得对应的compact的边界，这里每一个需要并发的compact都被抽象为一个sub compaction.因此在 GenSubcompactionBoundaries 会解析到对应的sub compaction以及边界.解析完毕之后，则将会把对应的信息全部加入sub_compact_states中。

void CompactionJob::Prepare() { 
    .......................... if (c->ShouldFormSubcompactions()) { 
    const uint64_t start_micros = env_->NowMicros(); GenSubcompactionBoundaries(); MeasureTime(stats_, SUBCOMPACTION_SETUP_TIME, env_->NowMicros() - start_micros); assert(sizes_.size() == boundaries_.size() + 1); for (size_t i = 0; i <= boundaries_.size(); i++) { 
    Slice* start = i == 0 ? nullptr : &boundaries_[i - 1]; Slice* end = i == boundaries_.size() ? nullptr : &boundaries_[i]; compact_->sub_compact_states.emplace_back(c, start, end, sizes_[i]); } MeasureTime(stats_, NUM_SUBCOMPACTIONS_SCHEDULED, compact_->sub_compact_states.size()); } ...................................... } 

因此我们来详细分析 GenSubcompactionBoundaries ，这个函数比较长，我们来分开分析，首先是遍历所有的需要compact的level,然后取得每一个level的边界(也就是最大最小key)加入到bounds数组之中。

...... for (size_t lvl_idx = 0; lvl_idx < c->num_input_levels(); lvl_idx++) { 
    int lvl = c->level(lvl_idx); if (lvl >= start_lvl && lvl <= out_lvl) { 
    const LevelFilesBrief* flevel = c->input_levels(lvl_idx); size_t num_files = flevel->num_files; ...... if (lvl == 0) { 
    // For level 0 add the starting and ending key of each file since the // files may have greatly differing key ranges (not range-partitioned) for (size_t i = 0; i < num_files; i++) { 
    bounds.emplace_back(flevel->files[i].smallest_key); bounds.emplace_back(flevel->files[i].largest_key); } } else { 
    // For all other levels add the smallest/largest key in the level to // encompass the range covered by that level bounds.emplace_back(flevel->files[0].smallest_key); bounds.emplace_back(flevel->files[num_files - 1].largest_key); if (lvl == out_lvl) { 
    // For the last level include the starting keys of all files since // the last level is the largest and probably has the widest key // range. Since it's range partitioned, the ending key of one file // and the starting key of the next are very close (or identical). for (size_t i = 1; i < num_files; i++) { 
    bounds.emplace_back(flevel->files[i].smallest_key); } } } } } ...... 

然后就对获取到的bounds进行排序去重

 std::sort(bounds.begin(), bounds.end(), [cfd_comparator](const Slice& a, const Slice& b) -> bool { 
    return cfd_comparator->Compare(ExtractUserKey(a), ExtractUserKey(b)) < 0; }); // Remove duplicated entries from bounds bounds.erase( std::unique(bounds.begin(), bounds.end(), [cfd_comparator](const Slice& a, const Slice& b) -> bool { 
    return cfd_comparator->Compare(ExtractUserKey(a), ExtractUserKey(b)) == 0; }), bounds.end()); 

接近着就来计算理想情况下所需要的subcompactions的个数以及输出文件的个数.

 // Group the ranges into subcompactions const double min_file_fill_percent = 4.0 / 5; int base_level = v->storage_info()->base_level(); uint64_t max_output_files = static_cast<uint64_t>(std::ceil( sum / min_file_fill_percent / MaxFileSizeForLevel(*(c->mutable_cf_options()), out_lvl, c->immutable_cf_options()->compaction_style, base_level, c->immutable_cf_options()->level_compaction_dynamic_level_bytes))); uint64_t subcompactions = std::min({ 
   static_cast<uint64_t>(ranges.size()), static_cast<uint64_t>(c->max_subcompactions()), max_output_files}); 

最后更新boundaries_，这里会根据根据文件的大小，通过平均的size,来吧所有的range分为几份，最终这些都会保存在boundaries_中.

 if (subcompactions > 1) { 
    double mean = sum * 1.0 / subcompactions; // Greedily add ranges to the subcompaction until the sum of the ranges' // sizes becomes >= the expected mean size of a subcompaction sum = 0; for (size_t i = 0; i < ranges.size() - 1; i++) { 
    sum += ranges[i].size; if (subcompactions == 1) { 
    // If there's only one left to schedule then it goes to the end so no // need to put an end boundary continue; } if (sum >= mean) { 
    boundaries_.emplace_back(ExtractUserKey(ranges[i].range.limit)); sizes_.emplace_back(sum); subcompactions--; sum = 0; } } sizes_.emplace_back(sum + ranges.back().size); } else { 
    // Only one range so its size is the total sum of sizes computed above sizes_.emplace_back(sum); } 

然后我们来看CompactJob::Run的实现,在这个函数中，就是会遍历所有的sub_compact,然后启动线程来进行对应的compact工作，最后等到所有的线程完成，然后退出.

 std::vector<port::Thread> thread_pool; thread_pool.reserve(num_threads - 1); for (size_t i = 1; i < compact_->sub_compact_states.size(); i++) { 
    thread_pool.emplace_back(&CompactionJob::ProcessKeyValueCompaction, this, &compact_->sub_compact_states[i]); } // Always schedule the first subcompaction (whether or not there are also // others) in the current thread to be efficient with resources ProcessKeyValueCompaction(&compact_->sub_compact_states[0]); // Wait for all other threads (if there are any) to finish execution for (auto& thread : thread_pool) { 
    thread.join(); } 

可以看到run中的逻辑是 ，通过 ProcessKeyValueCompaction 拿到的sub_compact_states进行真正的compaction处理实际key-value的数据。

通过这样冗长的调用链，终于进入到了下一个阶段～～～

3.2 Process keys

​ 主要做如下几件事情

• 将 当前subcompaction 的k-v的数据取出，维护一个迭代器来进行访问（此时会构造一个堆排序的存储结构，来通过迭代器访问堆顶元素）
• ·这里指客户端对指定的key下发的merge操作，包括list append, add …之类的操作)

  合并的过程主要是 取到当前internal key的最新的snapshot对应的操作（主要针对put/delete，保留range_deletion）

• 将合并好的数据返回，交给迭代器一个一个 进行访问，并进行后续的write操作（每访问一个，pop堆顶，并重建堆，再取堆顶元素）
• 创建输出的文件，并绑定builder 和 writer，方便后续的数据写入

3.2.1 构造能够访问所有key的迭代器

首先我们进入到*ProcessKeyValueCompaction*函数之中，通过之前步骤中填充的sub_compact数据取出对应的key-value数据，构造一个InternalIterator。

 std::unique_ptr<InternalIterator> input(versions_->MakeInputIterator( sub_compact->compaction, &range_del_agg, env_options_for_read_)) 

构造的过程是通过函数MakeInputIterator进行的，我们进入到该函数，这个函数构造迭代器的逻辑同样区分level-0和level-其他

• 先获取当前sub_compact所属的cfd
• 针对level-0,为其中的每一个sst文件构建一个table_cache迭代器，放入list之中
• 针对其他非level-0的层，每一层直接创建一个及联的迭代器并放入list之中。也就是这个迭代器从它的start就能够顺序访问到该层最后一个sst文件的最后一个key
  因为非level-0的sst文件之间本身是有序的，不像level-0的sst文件之间可能有重叠。
  
  
• 将所有层的迭代器添加到一个迭代器数组之中，拿到该数组，通过 NewMergingIterator 迭代器维护一个底层的排序堆结构，完成所有层之间的key-value的排序

获取到当前sub_compact的cfd

auto cfd = c->column_family_data() 

针对level-0中的每一个sst文件，构造一个table_cache的迭代器

 if (c->level(which) == 0) { 
    const LevelFilesBrief* flevel = c->input_levels(which); for (size_t i = 0; i < flevel->num_files; i++) { 
    list[num++] = cfd->table_cache()->NewIterator( read_options, env_options_compactions, cfd->internal_comparator(), *flevel->files[i].file_metadata, range_del_agg, c->mutable_cf_options()->prefix_extractor.get(), /*table_reader_ptr=*/nullptr, /*file_read_hist=*/nullptr, TableReaderCaller::kCompaction, /*arena=*/nullptr, /*skip_filters=*/false, /*level=*/static_cast<int>(which), /*smallest_compaction_key=*/nullptr, /*largest_compaction_key=*/nullptr); } } 

对于非level-0的层，直接将该层构造一整体的迭代器

 // Create concatenating iterator for the files from this level list[num++] = new LevelIterator( cfd->table_cache(), read_options, env_options_compactions, cfd->internal_comparator(), c->input_levels(which), c->mutable_cf_options()->prefix_extractor.get(), /*should_sample=*/false, /*no per level latency histogram=*/nullptr, TableReaderCaller::kCompaction, /*skip_filters=*/false, /*level=*/static_cast<int>(which), range_del_agg, c->boundaries(which)); 

最后将获取到的迭代器数组交给 NewMergingIterator ，进行排序结构的维护。接下来我们看一下这个底层自动堆排序的迭代器是如何创建起来的。

如果list是空的，则直接返回空

如果只有一个，那么认为这个迭代器本身就是有序的，不需要构建一个堆排序的迭代器（level-0 的sst内部是有序的，之前创建的时候是为level-0每一个sst创建一个list元素；非level-0的整层都是有序的）

如果多个，那么直接通过MergingIterator来创建堆排序的迭代器

InternalIterator* NewMergingIterator(const InternalKeyComparator* cmp, InternalIterator** list, int n, Arena* arena, bool prefix_seek_mode) { 
    assert(n >= 0); if (n == 0) { 
    return NewEmptyInternalIterator<Slice>(arena); } else if (n == 1) { 
    return list[0]; } else { 
    if (arena == nullptr) { 
    return new MergingIterator(cmp, list, n, false, prefix_seek_mode); } else { 
    auto mem = arena->AllocateAligned(sizeof(MergingIterator)); return new (mem) MergingIterator(cmp, list, n, true, prefix_seek_mode); } } } 

接下来看一下 MergingIterator 这个迭代器的实现,通过将传入的list也就是函数中的children中的所有元素添加到一个vector中，再遍历其中的每一个key-value，通过函数 AddToMinHeapOrCheckStatus 构造堆排序的底层结构，关于该数据结构中的元素顺序是由用户参数option.comparator指定，默认是 BytewiseComparator 支持的lexicographical order，也就是字典顺序。

 children_.resize(n); for (int i = 0; i < n; i++) { 
    children_[i].Set(children[i]); } for (auto& child : children_) { 
    AddToMinHeapOrCheckStatus(&child); } current_ = CurrentForward(); 

关于函数AddToMinHeapOrCheckStatus中的构造过程通过函数，完成

 void upheap(size_t index) { 
    T v = std::move(data_[index]); while (index > get_root()) { 
    const size_t parent = get_parent(index); if (!cmp_(data_[parent], v)) { 
    //这个比较器由用户传入，默认是字典序,即data[parent] < v 返回true break; // break的时候表示v已经无法下降，data_[parent]的字典序比v大，就退出循环吧 } data_[index] = std::move(data_[parent]); index = parent; } data_[index] = std::move(v); reset_root_cmp_cache(); } 

构造最小堆的过程无非就是让插入的元素字典序中越小，越向上，如果没法上升则就放在原地，具体过程代码已经很明确了。

到此我们已经完成了整个key-value迭代器的构建，且获取到之后迭代器内部的元素是一个最大堆的形态。

3.2.2 通过SeekToFirst和Next指针 处理元素

回到 ProcessKeyValueCompaction 函数,使用构造好的internalIterator再构造一个包含所有状态的CompactionIterator，直接初始化就可以，构造完成需要将 CompactionIterator 的内部指针放在整个迭代器最开始的部位，通过Next指针来获取下一个key-value，同时还需要需要在每次迭代器元素内部移动的时候除了调整底层堆中的字典序结构之外，还兼顾处理各个不同type的key数据，将kValueType，kTypeDeletion，kTypeSingleDeletion，kValueDeleteRange,kTypeMerge 等不同的key type处理完成。这一部分内容有非常多的逻辑，本篇还是先专注于compaction的主体逻辑。

关于kTypeDeleteRange的处理逻辑，感兴趣的伙伴可以参考Rocksdb DeleteRange实现原理。

c_iter->SeekToFirst(); ...... while (status.ok() && !cfd->IsDropped() && c_iter->Valid()) { 
    // Invariant: c_iter.status() is guaranteed to be OK if c_iter->Valid() // returns true. const Slice& key = c_iter->key(); const Slice& value = c_iter->value(); ...... c_iter->Next(); ... } 

这个while循环内部的逻辑除了Next()指针内部后台元素的处理之外，就是我们下面要讲的写入key-value到output的逻辑了。

3.3 Write keys

这一步其实是在ProcessKeyValueCompaction函数之内，其实主要是写入SST文件之中

• 确认key 的valueType类型，如果是data_block或者index_block类型，则放入builder状态机中

  优先创建filter_buiilder和index_builder，index builer创建成 分层格式(两层index leve, 第一层多个restart点，用来索引具体的datablock；第二层索引第一层的index block)，方便加载到内存进行二分查找，节约内存消耗，加速查找；其次再写data_block_builder

• 如果key的 valueType类型是 range_deletion，则加入到range_delete_block_builder之中
• 先将data_block builder 利用绑定的输出的文件的writer写入底层文件
• 将filter_block / index_builder / compress_builder/range_del_builder/properties_builder 按照对应的格式加入到 meta_data_builder之中，利用绑定ouput 文件的 writer写入底层存储
• 利用meta_data_handle 和 index_handle 封装footer,写入底层存储

3.3.1 将builder与输出文件的writer绑定

这里的写入建议大家先看一下SST文件详细格式源码解析，

默认的 blockbase table SST 文件有很多不同的block，除了data block之外，其他的block都是需要先写入到一个临时的数据结构 builder，然后由builder通过其绑定的output 文件的writer写入到底层磁盘形成磁盘的sst文件结构

这里的逻辑就是将builder与output文件的writer进行绑定，创建好table builder

 // Open output file if necessary if (sub_compact->builder == nullptr) { 
    status = OpenCompactionOutputFile(sub_compact); if (!status.ok()) { 
    break; } } 

3.3.2 通过table_builder的状态机添加block数据

然后调用builder->Add函数构造对应的builder结构，添加的过程主要是通过拥有三个状态的状态机完成不同block的builder创建，状态机是由构造tablebuilder的时候创建的。

• kBuffered 为状态机的初始状态。处于这个状态的时候，内存有较多缓存的未压缩的datablock。在该状态的过程中，通过 EnterUnbuffered 函数构造compression block，依此构建对应的index block和filterblock。最终将状态置为下一个状态的：kUnbuffered
• kUnbuffered 这个状态时，compressing block已经通过之前的buffer中的data初步构造完成，且接下来将在这个状态通过 Finish 完成各个block的写入 或者通过 Abandon 丢弃当前的写入
• kClosed 这个状态之前已经完成了table builder的finish或者abandon，那么接下来将析构当前的table builder

对于第一个状态我们，进入如下逻辑，如果data block能够满足flush的条件，则直接flush datablock的数据到当前bulider对应的datablock存储结构中。

接着进入EnterUnbuffered函数之中：

 if (should_flush) { 
    assert(!r->data_block.empty()); Flush(); if (r->state == Rep::State::kBuffered && r->data_begin_offset > r->target_file_size) { 
    EnterUnbuffered(); } 

EnterUnbuffered 函数主要逻辑是构造compression block，如果我们开启了compression的选项则会构造。

同时依据之前flush添加到datablock中的数据来构造index block和filter block，用来索引datablock的数据。选择在这里构造的话主要还是因为flush的时候表示一个完整的datablock已经写入完成，这里需要通过一个完整的datablock数据才有必要构造一条indexblock的数据。

其中data_block_and_keys_buffers数组存放的是未经过压缩的datablock数据

 for (size_t i = 0; ok() && i < r->data_block_and_keys_buffers.size(); ++i) { 
    const auto& data_block = r->data_block_and_keys_buffers[i].first; auto& keys = r->data_block_and_keys_buffers[i].second; //多个datablock，取其中的一个 assert(!data_block.empty()); assert(!keys.empty()); for (const auto& key : keys) { 
    if (r->filter_builder != nullptr) { 
    r->filter_builder->Add(ExtractUserKey(key)); } r->index_builder->OnKeyAdded(key); } WriteBlock(Slice(data_block), &r->pending_handle, true /* is_data_block */); if (ok() && i + 1 < r->data_block_and_keys_buffers.size()) { 
    Slice first_key_in_next_block = r->data_block_and_keys_buffers[i + 1].second.front(); Slice* first_key_in_next_block_ptr = &first_key_in_next_block; r->index_builder->AddIndexEntry(&keys.back(), first_key_in_next_block_ptr, r->pending_handle); } } 

这里构造index block的原则还是说 提升索引datablock的效率之外还想要减少内存的消耗，所以这里会保存一段经过压缩的key的数据作为一个data block的偏移索引。

下一个data block的start key是”the tea”

那么针对下一个data block的索引key就可以保存为”the s”，这样既能保证比上一个datablock中的key都要大，也能保证比下一个datablock中的数据都要小，也能减少内存的消耗。

这里初始化的index builer的类型根据blockbased的option来创建：

• 如果指定了kTwoLevelIndexSearch，则初始化为PartitionedIndexBuilder,它的index 结构是前n-1层是用来存储索引datablock的数据，最后一层是存储索引前n-1层index block的数据。
• 如果是默认的kBinarySearch，则就是支持二分查找的，则就是ShortenedIndexBuilder

  还有其他的三种不同的index type

  kHashSearch kTwoLevelIndexSearch kBinarySearchWithFirstKey 

关于四种不同的index block，后续将专门分析，三种不同的数据结构，索引算法和效率也有差异。

在 EnterUnbuffered 函数创建index block

 if (table_options.index_type == BlockBasedTableOptions::kTwoLevelIndexSearch) { 
    p_index_builder_ = PartitionedIndexBuilder::CreateIndexBuilder( &internal_comparator, use_delta_encoding_for_index_values, table_options); index_builder.reset(p_index_builder_); } else { 
    index_builder.reset(IndexBuilder::CreateIndexBuilder( table_options.index_type, &internal_comparator, &this->internal_prefix_transform, use_delta_encoding_for_index_values, table_options)); } 

回到 ProcessKeyValueCompaction 中的while循环中，我们不断的遍历迭代器中的key，将其添加到对应的datablock，并完善indeblock和filter block，以及compression block。

3.3.3 通过构建的meta_index_builder和Footer完成数据的固化

接下来将 通过 FinishCompactionOutputFile 之前添加的builder数据 进行整合，处理一些delete range 的block以及更新当前compaction的边界。

这个函数调用是当之前累计的builder中block数据的大小达到可以写入的sst文件本身的大小 max_output_file_size ，会触发当前函数

 Status input_status; if (sub_compact->compaction->output_level() != 0 && sub_compact->current_output_file_size >= sub_compact->compaction->max_output_file_size()) { 
    // (1) this key terminates the file. For historical reasons, the iterator // status before advancing will be given to FinishCompactionOutputFile(). input_status = input->status(); output_file_ended = true; } ...... if (output_file_ended) { 
    const Slice* next_key = nullptr; if (c_iter->Valid()) { 
    next_key = &c_iter->key(); } CompactionIterationStats range_del_out_stats; status = FinishCompactionOutputFile(input_status, sub_compact, &range_del_agg, &range_del_out_stats, next_key); RecordDroppedKeys(range_del_out_stats, &sub_compact->compaction_job_stats); } 

FinishCompactionOutputFile函数内部最终调用s = sub_compact->builder->Finish();完成所有数据的固化写入

 bool empty_data_block = r->data_block.empty(); Flush(); //再次执行 先尝试将key-value的数据刷到datablock if (r->state == Rep::State::kBuffered) { 
    EnterUnbuffered(); // 依据datablock数据构建index ,filter和compression block数据 } // To make sure properties block is able to keep the accurate size of index // block, we will finish writing all index entries first. if (ok() && !empty_data_block) { 
    r->index_builder->AddIndexEntry( &r->last_key, nullptr /* no next data block */, r->pending_handle); } ...... BlockHandle metaindex_block_handle, index_block_handle; MetaIndexBuilder meta_index_builder; WriteFilterBlock(&meta_index_builder); //filter_builder数据添加到 meta_index_builder WriteIndexBlock(&meta_index_builder, &index_block_handle);//添加index_builder WriteCompressionDictBlock(&meta_index_builder); //添加compression block WriteRangeDelBlock(&meta_index_builder); //添加range tombstone WritePropertiesBlock(&meta_index_builder); //添加最终的属性数据 if (ok()) { 
    // flush the meta index block WriteRawBlock(meta_index_builder.Finish(), kNoCompression, &metaindex_block_handle); } if (ok()) { 
    WriteFooter(metaindex_block_handle, index_block_handle); //写Footer数据 } r->state = Rep::State::kClosed; //最终返回table_builder的close状态，析构当前的table builer return r->status; } 

4. Compaction 的一些周边功能

这里主要介绍一些Compaction 的周边功能，包括remote compaction 以及 手动Compaction 的一些调度策略。

4.1 Remote Compaction

更多的设计细节可以直接跳到: Rocksdb Remote Compaction 设计实现。

4.2 CompactRange

这个功能是为用户提供的手动触发 compaction 的接口，接口形态如下：

 virtual Status CompactRange(const CompactRangeOptions& options, ColumnFamilyHandle* column_family, const Slice* begin, const Slice* end) = 0; virtual Status CompactRange(const CompactRangeOptions& options, const Slice* begin, const Slice* end) { 
    return CompactRange(options, DefaultColumnFamily(), begin, end); } 

CompactRange 如果想要调度 fullcompaction ，并不是一次调度所有层的所有文件，而是在接口实现中拆分成按层调度的compaction job，还是主要关注 level compaction的实现调度。

DBImpl::CompactRange ...... // 前面做了一些筛选，取到了当前LSM-tree 拥有sst文件的最大层 for (int level = 0; level <= max_level_with_files; level++) { 
    int output_level; // in case the compaction is universal or if we're compacting the // bottom-most level, the output level will be the same as input one. // level 0 can never be the bottommost level (i.e. if all files are in // level 0, we will compact to level 1) ... // 对于level compaction，ouput level 是当前层 + 1. output_level = level + 1; if (cfd->ioptions()->compaction_style == kCompactionStyleLevel && cfd->ioptions()->level_compaction_dynamic_level_bytes && level == 0) { 
    output_level = ColumnFamilyData::kCompactToBaseLevel; } // 对当前层调度 compaction s = RunManualCompaction(cfd, level, output_level, options, begin, end, exclusive, false, max_file_num_to_ignore); ...... 

对于level compaction来说，在按层循环调度compaction 的过程中 output level 是当前level +1。如果配置了 level_compaction_dynamic_level_bytes ，且当前level 是0，则会有优先 compact到最后一层 (num_levels -1 )。

如果有需要，RunManualCompaction 这个接口也可以单独用来调度 指定某一层的compaction。

4.3 MarkCompaction

细节可以参考 通过 MarkCompaction 加速 Delete 版本清理，给了用户足够的定制化空间进行自己行为的调度。

5. 总结

关于以上实现原理的描述并没有将细节完全讲清楚，比如

• Prepare keys过程，pickcompaction函数中clean cut算法的实现原理，有点像B树的查找，但具体实现还需要研究
• Process keys过程，那么多复杂的迭代器转来转去 从开始的Internal Iterator，mergeIterator, CompactionIterator…不同迭代器之间是什么关系呢？
• Write keys的过程细节最多，设计也是最多的。
  • Filter block的实现 – block base filter和full filter两种基本实现，效率和实现算法之间的差异
  • index filter中的四种不同的index filter实现，索引datablock的效率如何体现在实现的查找算法之上。
  • Compression block的实现，rocksdb支持常见的snappy，zlib,lz4等压缩算法，在compersion block中这一些压缩算法是怎么实现的，都需要仔细研究揣摩。

希望有想法，了解的伙伴一起交流讨论。