LevelDB-Compaction

压缩，数据重新组合，平衡读写效率

1. 清理无效数据
2. 维护数据有序性

作用

1. 读写效率

   写操作，只需要一次顺序的文件写和一个时间复杂度为O(log n)的内存操作。

   读操作，首先需要进行一个复杂度为O(log n)的内存查询操作，若没有命中数据，则需按数据的新旧程度在0层文件中依次进行查找遍历。由于0层文件中可能存在重叠(overlap)，最差情况下，可能需要遍历所有的文件。

   随着运行时间的增长，0层的文件个数会越来越多，在最差的情况下，查询一个数据需要遍历所有的数据文件，这显然是不可接受的。

   因此leveldb设计了一个Major Compaction 的过程，将0层中的文件合并为若干个没有数据重叠的1层文件。

   对于没有数据重叠的文件，一次查找过程就可以进行优化，最多只需一个文件的遍历即可，提高了读取的效率。

2. 平衡读写

   Major Compaction 的过程是一个多路归并的过程，有大量的磁盘读开销，也有大量的磁盘写开销，是一个性能瓶颈。

   当用户写入速度大于 Major Compaction 速度时，level-0 文件数量不断上升，导致用户读取效率下降。

   • level-0 文件数量超过 SlowdownTrigger 时，LevelDB 使写入速度减慢
   • level-0 文件数量超过 PauseTrigger 时，LevelDB 暂停写入，直至 Major Compaction 完成

3. 整理数据

   每条数据有一条版本信息，同时存在多个版本的数据，为减少对空间的占用，会在 Major Compaction 过程中进行合并。

触发

• 主动触发

  调用 CompactRange

• 自动触发

  • MinorCompaction

    将 Immutable MemTable 持久化到 SST 的过程

  • MajorCompaction

    level-n 的 SSTable 超过限制，level-n 和 level-n+1 的 SSTable 会进行 compaction

    • level-0 的限制，SST 文件的数量（默认4个）
    • level-n (n>0) 的限制，所有SST 文件的总大小（10^n）M
    • 某文件无效读取次数过多

实现

MinorCompaction


每次MinorCompaction结束后，都会生成一个新的sstable文件，使Leveldb的版本状态变化，会进行一个版本的更替。

MinorCompaction要求在尽可能短的时间内完成，否则会堵塞正常的写入操作，因此MinorCompaction的优先级高于MajorCompaction。MajorCompaction可能会被MinorCompaction暂停。

Code

DBImpl::CompactMemTable
->
DBImpl::WriteLevel0Table
->
BuildTable

MajorCompaction


触发条件

1. 0层文件数（4个）

   为了提高读取效率

2. 非0层文件大小限制（10^N）

   level-i层数据已经切分，因此一次读取最多读取一个SST，此处不在考虑读取效率，而是降低Compaction的IO开销，通过限制大小，来减少上层输入的各个范围的大数据量与当前层合并产生的IO性能影响，使其尽量保持常量。

   1层文件总大小上限为10MB，2层为100MB，依次类推，最高层（7层）没有限制。

   1. 最差情况：所有层同时达到合并条件，每一层都需要合并。

   2. 优化策略：对最差情况进行优化

      1. level-i层只有一个文件
      2. level-i层与level-i+1层没有数据重叠文件
      3. level-i层与level-i+2层重叠的文件不超过10个

      对于三种情况中的任何一种，直接将level-i层的文件copy到level-i+1层。

      三种条件仍然只能小程度的解决大量合并的问题，引入错峰合并机制

3. 文件无效读取次数多

   1. 寻找错峰合并的文件

      一个文件一次查询的开销为10ms, 若某个文件的查询次数过多，且查询在该文件中不命中

   2. 判断错峰合并的时机

      一个1MB的文件，对其合并的开销为25ms。因此当一个文件1MB的文件无效查询超过25次

      1. 统计方式：采样探测

         正常的数据访问（用户直接调用Get接口、用户使用迭代器进行访问）时，进行采样探测。

      2. 采样规则：

         SST文件的元数据，有一个字段seekLeft，在访问SST文件时，若访问命中，则无处理，若未命中，则对当前SST文件的seekLeft减一，直至减少至0，触发错峰合并

Code

VersionSet::Finalize => VersionSet::PickCompaction => DBImpl::DoCompactionWork

1. 计算 level
2. 选择 SST
3. 如key无重叠，copy；否则归并

流程

寻找输入文件

1. 普通合并场景

   level-0层文件数过多引发的合并场景，或由于level-i层文件总量过大的合并场景，采用RoundRobin方式，按Key进行合并，记录上次合并的最大Key，下次按Key之后的首个文件进行合并。

2. 错峰合并场景

   无效查询次数过多的那个输入文件。

扩大输入文件的集合

1. 红星为起始输入文件；
2. 在level-i层中，查找与起始输入文件有key重叠的文件，红线所标注，最终构成level-i层的输入文件；
3. 利用level-i层的输入文件，在level-i+1层找寻有key重叠的文件，为绿线标注的文件，构成level-i，i+1层的输入文件；
4. 利用两层的输入文件，在不扩大level-i+1输入文件的前提下，查找level-i层的有key重叠的文件，蓝线标注的文件，构成最终的输入文件；


多路合并

将level-i层的文件，与level-i+1层的文件中的数据进行归并，输出到level-i+1层的若干个新文件中，即合并完成。

过程中，需要将冗余的数据进行清理，同一条数据的多个版本信息，只保留最新的那一份。

仍然在使用的旧版本的数据，不能立刻删除，等到使用结束，释放句柄后，根据引用计数来进行清除。


可以写入数据前进行排序，减少多路合并的IO开销。

积分计算

每次compaction都会消除若干旧文件，新增+1层的新文件，因此触发进行合并的条件状态发生了变化。故在leveldb中，使用了计分牌来维护每一层文件的文件个数及数据总量信息，来挑选出下一个需要进行合并的层数。

计分的规则很简单：

• 对于0层文件，该层的分数为文件总数／4；
• 对于非0层文件，该层的分数为文件数据总量／数据总量上限；

将得分最高的层数记录，若该得分超过1，则为下一次进行合并的层数；

问题

会对稳定性和性能带来一定影响

• 消耗 CPU

  对 SST 解析、解压、压缩。

• 消耗 I/O

  大量的 SST 批量读写，十几倍甚至几十倍的写放大会消耗不少 I/O，同时缩短 SSD 的寿命。

• 缓存失效

  删除旧 SST，生成新 SST。新 SST 的首次请求无法命中缓存，引发系统性能抖动。

只能尽量控制Compaction的速度，使其平缓，尽量不引起波动

写放大

系统内部的IO数据量，比实际写入的IO数据量大很多倍

• WAL写入，1倍IO
• Immutable 写入 Level-0，1倍IO
• Level-0和Level-1的Compaction（Level-0的每个SST中的Key都有所重叠，全量Level-0与Level-1合并），2倍IO
• Level-i和Level-i+1的Compaction（Level-i+1的数据量是Level-i的10倍），11倍IO

总的写放大为 $1+1+2+11(n-1) = 11n-7$ (n为Level数) 倍；

假设以最大Level(7)计算，写入1G数据量，实际IO量为70G，写放大了70倍。