欢迎光临
我们一直在努力

【Leveldb】compaction 实现分析

触发compaction的时机

下面的场景都是通过函数MaybeScheduleCompaction来触发compaction的,函数内部会在检查是否需要做compaction。

  • Memtable写满转为Immtable时,触发compaction。
  • Open db结束后会触发compaction。
  • compaction完成之后会在触发一次compaction。
  • 读SSTable后并且seek的第一个SSTable的allowed_seeks小于等于0那么触发compaction。
  • 调用CompactRange接口手动触发compaction。
  • MaybeScheduleCompaction中可以做compaction的场景:

  • 存在Immtable。
  • 是手动执行的compaction。
  • Level-0的文件个数大于4个。
  • LevelNNN 的 SSTable 总字节大小超过目标上限(10^(N) * 1MB)。
  • Immtable序列化为SSTable

    Immtable序列化流程如下:

  • 获取新的FileNumber,由VersionSet生成全局递增的u64数值。最新的数值会保存在Manifest中。
  • 迭代Immtable将内存中的kv对序列化到文件中。
  • 更新Manifest,将序列化的SSTable记录到对应的level中,更新next_file_number_、last_sequence_到Maniefest中。
  • 释放immtable。
  • 清除老的WAL文件。
  • SSTable合并

    PickCompaction

  • 挑选当前level需要做compaction的SSTable
    • 对于当前level的size达到限制触发的compaction,选取>compact_pointer_记录的key大的第一个SSTable
    • 对于读SSTable后触发的compaction,选取的就是记录的allowed_seeks小于等于0的SSTable
    • 如果是level-0,那么需要将level-0中所有和上面选取的SSTable有交集的SSTable都选取出来。
  • 从level+1中挑选SSTable,需要和level中选出的SSTable的key有交集。
  • 设置compact_pointer_记录当前compaction到哪个key了。
  • 合并key

  • 将pick出来的SSTable生成一个MergingIterator,作为compaction的输入迭代器。
  • 迭代所有的key-value对,对于需要保留的就输出到output文件中,output文件通过TableBuilder打开。这里保留的key的最小sequence是快照列表中最老的快照的sequence。
  • 在迭代过程中,如果output的文件大小与祖父层(level+2)文件的重叠量超过 20MB,那么就重新开启一个新的文件作为输出。
  • 如果输出文件超过最大限制(2MB),那么也马上开启新的文件进行写入。
  • 将SSTable和compact_pointer_的变更记录到Manifest中。到这里compaction的结果就已经上线了。
  • 清理

  • 释放input_version
  • 删除无用的SSTable文件
  • 清理compaction过程中使用的内存,比如compact,outfile。
  • 赞(0)
    未经允许不得转载:171主机测评 » 【Leveldb】compaction 实现分析
    分享到: 更多 (0)

    评论 抢沙发

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址