专栏首页linjinhe的专栏LevelDB 完全解析(11):Compaction

LevelDB 完全解析(11):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 => DBImpl::WriteLevel0Table => BuildTable

Major Compaction

  1. 每次 compaction 结束,更新 manifest 之后,都会调用 VersionSet::Finalize 计算下一次要进行 major compaction 的 level。
  2. 每次 major compaction 开始时,调用 VersionSet::PickCompaction 计算需要进行 compaction 的 SSTable。
  3. 如果选中的 level-n 的 SSTable 和 level-n+1 的 SSTable 的 key 范围没有重叠,可以直接将 level-n 的 SSTable “移动”到 level-n+1,只需要修改 Manifest。
  4. 否则,调用 DBImpl::DoCompactionWork 对 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),让 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 的寿命也是个问题。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LevelDB 完全解析(4):Manifest

    内容上,Manifest 文件保存了整个 LevelDB 实例的元数据,比如:每一层有哪些 SSTable。 格式上,Manifest 文件其实就是一个 lo...

    linjinhe
  • LevelDB 完全解析(3):SSTable

    SSTable 全称 Sorted String Table,顾名思义,里面的 key-value 都是有序保存的。除了两个 MemTable,LevelDB ...

    linjinhe
  • LSM-Tree 的写放大写放大、读放大、空间放大RockDB 写放大简单分析参考文档

    基于 LSM-Tree 的存储系统越来越常见了,如 RocksDB、LevelDB。LSM-Tree 能将离散的随机写请求都转换成批量的顺序写请求(WAL + ...

    linjinhe
  • LevelDB:Compaction

    LevelDB 的写操作是 Append-Only 的,新的数据写入后,相应的旧数据就过期了。过期的数据需要被 Garbage Collection,不然数据文...

    linjinhe
  • 分布式——详解Google leveldb中的LMST细节

    LSMT是一个在分布式系统当中应用非常广泛,并且原理直观简单的数据结构。在上一篇文章当中我们进行了详细的讨论,有所遗忘或者是新关注的同学可以点击下方的链接回顾一...

    TechFlow-承志
  • LevelDB 完全解析(7):初始化

    options - 打开/创建 LevelDB 实例的配置参数。 dbname - 保存数据的目录名。 dbptr - 初始化成功的 LevelDB 实例保...

    linjinhe
  • 【深度知识】LevelDB从入门到原理详解

    LevelDB是Google开源的持久化KV单机数据库,具有很高的随机写,顺序读/写性能,但是随机读的性能很一般,也就是说,LevelDB很适合应用在查询较少,...

    辉哥
  • LevelDB 完全解析(8):读操作之 Get

    LevelDB 通过 leveldb::DB::Get 接口对外提供点查询的能力,具体的实现是 leveldb::DBImpl::Get。接口声明如下:

    linjinhe
  • LevelDB:读操作

    前面写了两篇文章介绍 LevelDB 的整体架构和接口使用。这篇文章,我们从代码的角度看看 LevelDB 的设计与实现,先从读操作开始。

    linjinhe
  • LevelDB原理解析:数据的读写与合并是怎样发生的?

    导语 | LevelDB是一款十分优秀的存储引擎,具有极高的数据读写性能,尤其是写入性能,在笔者经历的多个项目中都有用到,因此本文打算结合LevelDB的部分源...

    腾小云
  • leveldb实现分析

    | 导语  leveldb是google开源的单机key-value存储引擎。基于Log-Structured-Merge Tree的实现。本文先介绍leve...

    腾讯Bugly
  • 鸿篇巨制 —— LevelDB 的整体架构

    本节信息量很大,我们要从整体上把握 LevelDB 这座大厦的结构。当我们熟悉了整体的结构,接下来就可以各个击破来细致了解它的各种微妙的细节了。

    老钱
  • 【问题修复】osd自杀问题跟踪

    RGW的index数据以omap形式存储在OSD所在节点的leveldb中,当单个bucket存储的Object数量高达百万数量级的时候,deep-scrub和...

    Lucien168
  • LevelDB 完全解析(1):MemTable

    MemTable,顾名思议,就是内存表。每个 LevelDB 实例最多会维护两个 MemTable: mem_ 和 imm_。mem_ 可以读写,imm_ 只读...

    linjinhe
  • LevelDB 完全解析(2):Log

    这里的 log 是指 Write Ahead Log。前面说了,LevelDB 写入的数据会先保存到 MemTable。为了防止宕机导致数据丢失,在将数据写入 ...

    linjinhe
  • LevelDB 完全解析(5):Cache

    在 LevelDB 中,block cache 和 table cache 都是基于 ShardedLRUCache 实现的。

    linjinhe
  • LevelDB 完全解析(6):Filter

    LevelDB 可以设置通过 bloom filter 来减少不必要的读 I/O 次数。

    linjinhe
  • 漫谈 LevelDB 数据结构(二):布隆过滤器(Bloom Filter)

    LevelDB 是一个单机的 KV 存储引擎,但没有使用传统的平衡查找树以平衡读写性能,而是使用了 LSM-tree 结构来组织数据,牺牲部分读性能来换取较高的...

    青藤木鸟
  • RGW Bucket Shard优化

    bucket index是整个RGW里面一个非常关键的数据结构,用于存储bucket的索引数据,默认情况下单个bucket的index全部存储在一个shard文...

    Lucien168

扫码关注云+社区

领取腾讯云代金券