RocksDB 的 Compact

概述

RocksDB是基于LSM实现，但LSM并不是一个具体的数据结构，而是一种数据结构的概念和设计思想，具体细节参考LSM论文。而LSM中的其中最重要部分就是Compact，由于数据文件采用Append only方式写入，而对于过期的数据，重复的，已删除的数据，需要通过Compact进行逐步的清理。

RocksDB的Compact策略有两种kCompactionStyleUniversal和kCompactionStyleLevel，用户可以在Options::compaction_style中设置。在这里我们基于Level Compact策略来介绍：

参数介绍

关于RocksDB层级关系中有几个相关的参数需要介绍:

参数	说明	默认值
`write_buffer_size`	限定Memtable的大小	64MB
`level0_file_num_compaction_trigger`	限定Level 0层的文件数量	4
`target_file_size_base`	每一层单个目标文件的大小	64MB
`target_file_size_multiplier`	每一层单个目标文件的乘法因子	1
`max_bytes_for_level_base`	每一层所有文件的大小	256MB
`max_bytes_for_level_multiplier`	每一层所有文件的乘法因子	10
`level_compaction_dynamic_level_bytes`	是否将Compact的策略改为层级从下往上应用	False
`num_levels`	LSM的层级数量	7

参数target_file_size_base和target_file_size_multiplier用来限定Compact之后的每一层的单个文件大小。target_file_size_base是Level-1中每个文件的大小，Level N层可以用target_file_size_base * target_file_size_multiplier ^ (L -1) 计算。target_file_size_base 默认为64MB，target_file_size_multiplier默认为1。
参数max_bytes_for_level_base和max_bytes_for_level_multiplier 用来限定每一层所有文件的限定大小。 max_bytes_for_level_base是Level-1层的所有文件的限定大小。Level N层的所有文件的限定大小可以用 (max_bytes_for_level_base) * (max_bytes_for_level_multiplier ^ (L-1)) 计算。max_bytes_for_level_base的默认为256MB，max_bytes_for_level_multiplier默认为10。
参数level_compaction_dynamic_level_bytes用来指示Compact的策略改为层级从下往上应用。Target_Size(Ln-1) = Target_Size(Ln) / max_bytes_for_level_multiplier来限定大小：假如 max_bytes_for_level_base是 1GB, num_levels设为6。最底层的实际容量是276GB, 所以L1-L6层的大小分别是 0, 0, 0.276GB, 2.76GB, 27.6GB and 276GB。

何时Compact

之前的博文我们介绍了RocksDB的写入过程，先写入Memtable，当Memtable写满达到限定的大小后会写入新的Memtable，而这个写满的Memtable会被后台线程Flush到磁盘文件即Level-0。

当Level-0文件的数量达到了限定的数量，Compact线程会将Level-0的文件Compact到Level-1，下面的层级以此类推。

如何选择被Compact的文件

RocksDB会对每一层设置一个score，score用来表示进行Compact的优先级，score越大，越需要进行Compact。

如何计算score

如果是Level-0层，先计算当前有多少个没有Compact的文件个数num_sorted_runs和参数限定的Level-0层Compact触发数量的比值，再与 Level-0层未进行Compact的所有文件的总大小与参数限定的Level-1的比值做比较。

// 没有Compact的文件个数/参数限定的Level-0的文件个数 
score = static_cast<double>(num_sorted_runs) /
                mutable_cf_options.level0_file_num_compaction_trigger;
if (compaction_style_ == kCompactionStyleLevel && num_levels() > 1) {
   // 整个Level-0的所有文件大小/参数限定的Level-1的文件大小
	score = std::max(
              score, static_cast<double>(total_size) /
                     mutable_cf_options.max_bytes_for_level_base);
  }

如果是Level-N层，会计算每一层未进行Compact的所有文件大小，然后再和这一层的限定容量做对比，得到一个比值，这个值就是该层的score，该层的限定容量大小就是之前提及的计算公式。
1
2
3
// Level-N层的score计算
score = static_cast<double>(level_bytes_no_compacting) /
MaxBytesForLevel(level);

如何Compact

Compact操作主要包括两种：将内存中的Immutable Memtable通过Flush转为磁盘上的SST文件，还有一种就是将磁盘上的SST文件，根据相关规则属性由上层向下层的转存。

Immutable Memtable的Flush

Flush的入口在db/db_impl_compaction_flush.cc的BackgroundFlush()

当Memtable写满之后被转为Immutable Memtable，RocksDB会将其Flush至Level-0层：

选择所有尚未被Flush的Immutable Memtable保存至mems_
选择第一个Immutable Memtable即mems_[0]的version信息代表这次Flush操作的元信息
调用WriteLevel0Table()，进行Level-0文件的写入
将Memtable中的table_和range_del_table_通过BuildTable构造新的SST文件，之后通过Add()插入数据
- 这里的Table用的是Column Family的option默认设定的的BlockBasedTable,代码在table/block_based_table_builder.cc，通过Add()依次插入SST文件中的Index, Filter, Data各个Block，这部分涉及SST的文件布局，稍后的博文会着重介绍。
将变化的SST文件元信息写入manifest文件

SST文件的Compact

Compact的入口在db/db_impl_compaction_flush.cc的BackgroundCompaction()，我们这里依然以Leveled Compaction为例，Compaction的执行函数在CompactionJob::Run():

RocksDB会将所有的Level计算出score，经过冒泡排序，首先寻找score最高的Level，如果Level的score大于1，则选择这个Level进行Compaction
选择Level-N中尚未被Compaction的文件PickCompaction()
对于Level-0层文件，RocksDB总是选择所有的文件进行Compact执行操作，因为Level-0层的文件之间，可能会有key范围的重叠
对于Level-N层，通过GetOverlappingInputs()选取Level-N+1中与Level-N中重叠的两部分SST文件
RocksDB的CompactionIterator::SeekToFirst()将这两部分文件里所有被删除的且不存在于更高层的Level的key、重复的key、Compaction Filter中过滤的key标记为为无效
将所有有效的key写入新的SST文件
合并结束，利用VersionEdit更新VersionSet，更新统计信息