概述

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

Rocksdb的Compact策略有两种kCompactionStyleUniversalkCompactionStyleLevel,用户可以在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_basetarget_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_basemax_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的比值做比较。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    // 没有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.ccBackgroundFlush()

当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.ccBackgroundCompaction(),我们这里依然以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重复的keyCompaction Filter中过滤的key标记为为无效
  • 将所有有效的key写入新的SST文件
  • 合并结束,利用VersionEdit更新VersionSet,更新统计信息