LevelDB-Compaction
LevelDB-Compaction
压缩,数据重新组合,平衡读写效率
- 清理无效数据
- 维护数据有序性
作用
-
读写效率
写操作,只需要一次顺序的文件写和一个时间复杂度为O(log n)的内存操作。
读操作,首先需要进行一个复杂度为O(log n)的内存查询操作,若没有命中数据,则需按数据的新旧程度在0层文件中依次进行查找遍历。由于0层文件中可能存在重叠(overlap),最差情况下,可能需要遍历所有的文件。
随着运行时间的增长,0层的文件个数会越来越多,在最差的情况下,查询一个数据需要遍历所有的数据文件,这显然是不可接受的。
因此leveldb设计了一个Major Compaction 的过程,将0层中的文件合并为若干个没有数据重叠的1层文件。
对于没有数据重叠的文件,一次查找过程就可以进行优化,最多只需一个文件的遍历即可,提高了读取的效率。
-
平衡读写
Major Compaction 的过程是一个多路归并的过程,有大量的磁盘读开销,也有大量的磁盘写开销,是一个性能瓶颈。
当用户写入速度大于 Major Compaction 速度时,level-0 文件数量不断上升,导致用户读取效率下降。
- level-0 文件数量超过 SlowdownTrigger 时,LevelDB 使写入速度减慢
- level-0 文件数量超过 PauseTrigger 时,LevelDB 暂停写入,直至 Major Compaction 完成
-
整理数据
每条数据有一条版本信息,同时存在多个版本的数据,为减少对空间的占用,会在 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

触发条件
-
0层文件数(4个)
为了提高读取效率
-
非0层文件大小限制(10^N)
level-i层数据已经切分,因此一次读取最多读取一个SST,此处不在考虑读取效率,而是
降低Compaction的IO开销
,通过限制大小,来减少上层输入的各个范围的大数据量与当前层合并产生的IO性能影响,使其尽量保持常量。1层文件总大小上限为10MB,2层为100MB,依次类推,最高层(7层)没有限制。
-
最差情况:所有层同时达到合并条件,每一层都需要合并。
-
优化策略:对最差情况进行优化
- level-i层只有一个文件
- level-i层与level-i+1层没有数据重叠文件
- level-i层与level-i+2层重叠的文件不超过10个
对于三种情况中的任何一种,直接将level-i层的文件copy到level-i+1层。
三种条件仍然只能小程度的解决
大量合并
的问题,引入错峰合并
机制
-
-
文件无效读取次数多
-
寻找
错峰合并
的文件一个文件一次查询的开销为10ms, 若某个文件的查询次数过多,且查询在该文件中不命中
-
判断
错峰合并
的时机一个1MB的文件,对其合并的开销为25ms。因此当一个文件1MB的文件无效查询超过25次
-
统计方式:采样探测
正常的数据访问(用户直接调用Get接口、用户使用迭代器进行访问)时,进行采样探测。
-
采样规则:
SST文件的元数据,有一个字段
seekLeft
,在访问SST文件时,若访问命中,则无处理,若未命中,则对当前SST文件的seekLeft
减一,直至减少至0,触发错峰合并
-
-
Code
VersionSet::Finalize => VersionSet::PickCompaction => DBImpl::DoCompactionWork
- 计算 level
- 选择 SST
- 如key无重叠,copy;否则归并
流程
寻找输入文件
-
普通合并场景
level-0层文件数过多引发的合并场景,或由于level-i层文件总量过大的合并场景,采用
RoundRobin
方式,按Key进行合并,记录上次合并的最大Key,下次按Key之后的首个文件
进行合并。 -
错峰合并场景
无效查询次数过多的
那个输入文件
。
扩大输入文件的集合
- 红星为起始输入文件;
- 在level-i层中,查找与起始输入文件有key重叠的文件,红线所标注,最终构成level-i层的输入文件;
- 利用level-i层的输入文件,在level-i+1层找寻有key重叠的文件,为绿线标注的文件,构成level-i,i+1层的输入文件;
- 利用两层的输入文件,在不扩大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倍。