LevelDB 完全解析(十一):Compaction

Compaction 的作用

因为 LevelDB 的增删改都是通过追加写来实现的,所以需要通过后台线程的 compaction 来:

  1. 清理过期(旧版本或者已删除)的数据。

  2. 维护数据的有序性。

Compaction 的触发

除了从外部调用 CompactRange,LevelDB 有几种情况会自动触发 compaction:

  1. 当 MemTable 的大小达到阈值时,进行 MemTable 切换,然后需要将 Immutable MemTable 刷到外存上 —— 一般称之为 Minor Compaction。

  2. 当 level-n 的 SSTable 超过限制,level-n 和 level-n+1 的 SSTable 会进行 compaction —— 一般称之为 Major Compaction。

    1. level-0 是通过 SSTable 的数量来判断是否需要 compaction。

    2. level-n(n > 0) 是通过 SSTable 的大小来判断是否需要 compaction。

Minor Compaction

Minor Compaction 比较简单,基本代码路径是: DBImpl::CompactMemTable [1] => DBImpl::WriteLevel0Table [2] => BuildTable [3]

Major Compaction

  1. 每次 compaction 结束,更新 manifest 之后,都会调用 VersionSet::Finalize [4] 计算下一次要进行 major compaction 的 level。

  2. 每次 major compaction 开始时,调用 VersionSet::PickCompaction [5] 计算需要进行 compaction 的 SSTable。

  3. 如果选中的 level-n 的 SSTable 和 level-n+1 的 SSTable 的 key 范围没有重叠,可以直接将 level-n 的 SSTable “移动”到 level-n+1,只需要修改 Manifest。

  4. 否则,调用 DBImpl::DoCompactionWork [6] 对 level-n 和 level-n+1 的 SSTable 进行多路归并。

Compaction 的问题

Compaction 会对 LevelDB 的性能和稳定性带来一定影响:

  1. 消耗 CPU:对 SSTable 进行解析、解压、压缩。

  2. 消耗 I/O:大量的 SSTable 批量读写,十几倍甚至几十倍的写放大会消耗不少 I/O,同时缩短 SSD 的寿命(SSD 的写入次数是有限的)。

  3. 缓存失效:删除旧 SSTable,生成新 SSTable。新 SSTable 的首次请求无法命中缓存,可能引发系统性能抖动。

常见的做法是,控制 compaction 的速度(比如 RocksDB 的 Rate Limiter [7] ),让 compaction 的过程尽可能平缓,不要引起 CPU、I/O、缓存失效的毛刺。这种做法带来一个问题:compaction 的速度应该控制在多少?Compaction 的速度如果太快,会影响系统性能;Compaction 的速度如果太慢,会阻塞写请求。这个速度和具体的硬件能力、工作负载高度相关,往往只能设置一个“经验值”,比较难通用。同时这种做法只能在一定程度上减少系统毛刺、抖动,Compaction 带来的写放大依然是那么大。

写放大简单分析

  • +1 - WAL 的写入。

  • +1 - Immutable Memtable 写入到 level-0 文件。

  • +2 - level-0 和 level-1 的 compaction(level-0 的每个 SSTable 的 key 范围是重叠的。一般控制 level-0 和 level-1 的数据大小是一样的,每次拿全量 level-0 的数据和全量 level-1 的数据进行 compaction)。

  • +11 - level-n 和 level-n+1 合并的写入(n >= 1,默认情况下,level-n+1 的数据大小是 level-n 的 10 倍)。

所以,总的写放大是 4 + 11(n-1)  = 11n - 7 倍。

假设有 5 个 level,写放大最大是 48 倍——也就是说,外部写入 1GB 的数据,内部观察到的 I/O 写流量会有 48GB。

关于 LSM-Tree 的写放大有不少论文进行了详细的介绍、讨论和提出优化方案,比如:

  1. Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging - 这篇论文将各种 compaction 方式和影响介绍得非常清楚。

  2. WiscKey: Separating Keys from Values in SSD-conscious Storage - 通过将键值分离,大大减少了写放大。

  3. ...

小结

  1. 根据实际经验,在大部分场景下, compaction 带来的问题不是特别明显。

  2. 一些会有突发流量的情况,很容易造成 compaction 的速度跟不上实际写入的速度,导致写失败。

  3. Write intensive 的场景,写放大缩短了 SSD 的寿命也是个问题。

参考资料

[1]

DBImpl::CompactMemTable: https://github.com/google/leveldb/blob/1.22/db/db_impl.cc#L535

[2]

DBImpl::WriteLevel0Table: https://github.com/google/leveldb/blob/1.22/db/db_impl.cc#L491

[3]

BuildTable: https://github.com/google/leveldb/blob/1.22/db/builder.cc#L17

[4]

VersionSet::Finalize: https://github.com/google/leveldb/blob/1.22/db/version_set.cc#L1050-L1086

[5]

VersionSet::PickCompaction: https://github.com/google/leveldb/blob/1.22/db/version_set.cc#L1270

[6]

DBImpl::DoCompactionWork: https://github.com/google/leveldb/blob/1.22/db/db_impl.cc#L878

[7]

Rate Limiter: https://github.com/facebook/rocksdb/wiki/Rate-Limiter

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章