in LevelDB 分布式数据库 ~ read.

LevelDB-Compaction

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](https://raw.githubusercontent.com/ccyuki/vnote_img/main/personal/written/leveldb-compaction.md/482552615235572.png =478x)

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

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

Code

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

MajorCompaction

![MajorCompaction](https://raw.githubusercontent.com/ccyuki/vnote_img/main/personal/written/leveldb-compaction.md/353885110214757.png =468x)

触发条件

  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重叠的文件,蓝线标注的文件,构成最终的输入文件;

![Compation_process](https://raw.githubusercontent.com/ccyuki/vnote_img/main/personal/written/leveldb-compaction.md/267824917225830.png =625x)

多路合并

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

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

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

![Compaction_merge](https://raw.githubusercontent.com/ccyuki/vnote_img/main/personal/written/leveldb-compaction.md/416305217248270.png =699x)

可以写入数据前进行排序,减少多路合并的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倍。