LevelDB 学习笔记2：合并

部分图片来自 RocksDB 文档

LevelDB 中会发生两种不同的合并行为，分别称为 minor compaction 和 major compaction

将内存数据库刷到硬盘的过程称为 minor compaction

• 产出的 L0 层的 sstable
  • 事实上，LevelDB 不一定会将 minor compaction 产生的 sstable 放到 L0 里
• L0 层的 sstable 可能存在 overlap
• 如果上一次产生的 imm memtable 还没能刷盘，而新的 memtable 已写满，写入线程必须等待到 minor compaction 完成才能继续写入
  • 只允许同时存在一个 imm memtable

主要流程在 CompactMemTable() 中

• 借助工具类 TableBuilder 构建 sstable 文件
  • BuildTable()
• 选择将这个产生的 sstable 文件放到哪一层去
  • PickLevelForMemTableOutput()
  • 如果某个 sstable 文件和 L0 层没有重叠部分，就可以考虑将它扔到后面的层级里
  • 如果满足
    • 和 level + 1 层不重叠
    • 且不要和 level+ 2 有太多的重叠部分
  • 我们就可以将它扔到 level + 1 层去
  • 我们希望它能放到第二层去
    • 这样可以避免 0 -> 1 层合并的巨大 I/O 开销
  • 但我们不希望它直接扔到最后一层，这样可能带来带来的问题是
    • 如果某个 key 被重复改写，可能带来磁盘空间的浪费
    • 比如你写到 L7 中，然后再改写它时可能又在 L6 里写了一份副本，以此类推，可能每一层里都有这个 key 的副本
  • 最高可以放到 config::kMaxMemCompactLevel（默认为 2）层里去
• 提交版本修改
  • 增加新的 sstable 文件
• 删除 imm memtable 的日志文件

• L0 层的记录有 overlap，搜索的时候可能要遍历所有的 L0 级文件
  • 当 L0 层文件数量到达阈值（kL0_CompactionTrigger，默认值为 4）时，会被合并到 L1 层中去
  • 在没有 overlap 的层里搜索时，只需要找到 key 在哪个文件里，然后遍历这个文件就行了
  • 所以针对 L0 层的 major compaction 可以提高数据检索效率

• major compaction 过程会消耗大量时间，为了防止用户写入速度太快，L0 级文件数量不断增长，LevelDB 设置了两个阈值
  • kL0_SlowdownWritesTrigger，默认值为 8
    • 放缓写入，每个合并写操作都会被延迟 1ms
  • kL0_StopWritesTrigger，默认值为 12
    • 写入暂停，直到后台合并线程工作完成

除了 L0 层以外，其他层级内 sstable 文件的 key 是有序且不重叠的

• LevelDB 的写入都是 Append 的，也就是不管是修改还是删除，都是添加新的记录，因此数据库里可能存在 key 相同的多条记录
  • major compaction 也起到合并相同 key 的记录、减小空间开销的作用
• 而且如果 L1 层文件积累的太多，L0 层文件做 major compaction 的时候，需要和大量的 L1 层文件做合并，导致 compaction 的 I/O 开销很大
  • 所以合并操作也能降低 compaction 的 I/O 开销
• 当 Li（i > 0）层文件大小超过 \(10^i\) MB 时，也会触发 major compaction，选择至少一个 Li 层文件和 Li+1 层文件合并
  • 下面这个图来自 RocksDB 文档，所以阈值跟 LevelDB 不一样