归并 SST 控制版本堆积与读放大
RocksDB 的分层压实选择若干有序 SST,归并为新文件,在维护读取语义的同时清理可回收记录。
相关概念
工程问题#
持续写入产生多个有序文件和同键旧版本;若不整理,查询候选文件数与无效数据空间会持续增加。
实际实现#
迭代器归并已排序输入,压实迭代器依据序列号、快照和其它层中的记录决定保留内容,再顺序生成输出 SST。
处理流程#
- 挑选达到压实条件的输入文件。
- 为输入建立有序归并迭代器。
- 保留仍可见版本并过滤可回收条目。
- 写出新 SST 并安装新的文件版本。
源码片段#
固定版本 · 原文摘录table/compaction_merging_iterator.ccv9.7.3 · L275–L293
275void CompactionMergingIterator::Next() {276 assert(Valid());277 // For the heap modifications below to be correct, current_ must be the278 // current top of the heap.279 assert(current_ == CurrentForward());280 // as the current points to the current record. move the iterator forward.281 if (current_->type == HeapItem::ITERATOR) {282 current_->iter.Next();283 if (current_->iter.Valid()) {284 // current is still valid after the Next() call above. Call285 // replace_top() to restore the heap property. When the same child286 // iterator yields a sequence of keys, this is cheap.287 assert(current_->iter.status().ok());288 minHeap_.replace_top(current_);289 } else {290 // current stopped being valid, remove it from the heap.291 considerStatus(current_->iter.status());292 minHeap_.pop();293 }CompactionMergingIterator::Next
当前输出来自最小堆堆顶;只推进该有序输入,再替换堆顶恢复堆序,输入耗尽则移除。VersionSet::MakeInputIterator 经 NewCompactionMergingIterator 构造此迭代器。这是多路有序归并,不是对所有数据重新排序。
截取普通键迭代分支;随后还有范围删除标记分支。按快照丢弃旧版本的判断在 CompactionIterator 中,不能由这里的 pop 推断删除数据库记录。
收益与取舍#
工程分析带来的收益
- 减少文件重叠带来的查询负担。
- 在语义允许时回收旧版本与删除标记。
付出的代价
- 重复读取和重写数据形成写放大。
- 后台压实占用带宽、CPU 和临时空间。
可比较的选择
Universal / tiered compaction通常以较多读取和空间开销换取较低写放大,需按工作负载选择。
版本与适用范围#
基线 9.7.3,以 leveled compaction 为例。归并已有序输入;有快照或更低层旧值时不能随意丢弃版本和墓碑。
参考来源#
源码、官方文档与原始论文01
RocksDB 9.7.3 压实执行
源码9.7.3db/compaction/compaction_job.cc · CompactionJob::ProcessKeyValueCompaction
03
RocksDB 9.7.3 版本保留条件
源码9.7.3db/compaction/compaction_iterator.cc · CompactionIterator::NextFromInput
相关实现与比较#
1 个相关案例RocksDB 可为 SST 配置 Bloom filter,在读取数据块前排除不可能包含目标键的文件,减少无效查询工作。
附源码片段 · 检索与计算