LevelDB:Compaction

农历新年的最后一天,趁着假期看看代码,顺便做点笔记。时间上比较仓促,如有问题/疑问,欢迎指出。

简介

LevelDB 的写操作是 Append-Only 的,新的数据写入后,相应的旧数据就过期了。过期的数据需要被 Garbage Collection,不然数据文件的体积会持续膨胀,这是不可接受的。

LevelDB 通过后台线程的 compation 来对过期数据进行 Garbage Collection。

分析

LevelDB 在执行读操作和写操作的时候都有可能会调用 MaybeScheduleCompaction 函数,MaybeScheduleCompaction 有可能触发 compaction。

  if (have_stat_update && current->UpdateStats(stats)) {
    MaybeScheduleCompaction();
  }
  1. 当本次读取的数据没有在 MemTable 和 Immutable MemTable 命中, 而是从 SST 文件查找时,have_stat_updatetrue 。(相关代码
  2. 从 SST 文件查找时,如果查找的文件多于一个,则记录下第一个查找的文件,存放在 stats 。(相关代码
  3. UpdateStats 函数根据步骤 2 记录下的 SST 文件, allowed_seeks (一开始初始化为 2^30)减 1。当 allowed_seeks <= 0 且当前没有其它文件等待 compaction 时,记录当前文件为待 compaction 的文件,并返回 true ,否则返回 false。(相关代码
  • 个人理解

浏览代码的时候,上面 2 和 3 的逻辑让我不是很好理解。自己思考了一下,现在来尝试回答一下(不一定完全准确)。

LevelDB-多级缓存结构.PNG

LevelDB 的结构,其实就是一个多级缓存的结构。看看读操作的顺序就是很好理解这个多级缓存结构。

  1. MemTable 是 Immutable MemTable 的缓存。
  2. Immutable MemTable 是 Level 0 的缓存。
  3. Level0 是 Level1 的缓存。
  4. Level1 是 Level2 的缓存。
  5. ...

从 SST 文件进行查找时,首先根据要查找的 Key 从文件的元数据(记录着每一个 SST 文件 Key 范围)找出每个 Level 对应的文件(某些 Level 可能没有对应的文件,Level0 可能有多个对应文件)。按照文件的新旧排序,就组成这个 Key 对应的一个多级缓存。查找的时候也是按照这个顺序,如果最新的 SST_n 文件命中目标,则直接返回结果,否则继续查找 SST_n-1、SST_n-2 ...

Level-SST-Cache.PNG

这种情况下,我们自然希望大部分请求都能在第一个 SST 文件命中,这样效率最高。 如果有很多请求不能从第一个查找的文件命中目标,说明,这个文件的 Key 并没有缓存的价值,应该把这个文件向下一级 Level 合并掉,这样可以减少无效的文件查找。

  • 写操作调用 MaybeScheduleCompaction

写操作会调用 MakeRoomForWrite 为即将写入数据准备空间。整个逻辑由下面几个分支组成。(相关代码

  1. !bg_error_.ok() :后台任务有错误,直接返回错误。
  2. allow_delay && versions_->NumLevelFiles(0) >= config::kL0_SlowdownWritesTrigger :正常的写操作都 allow_delay 都为 true 。Level0 的文件数量超过了 config::kL0_SlowdownWritesTrigger ,说明有可能写入太多了,后台线程来不及 Compaction,需要减慢写操作。LevelDB 减慢写操作的方法是,每个写操作 sleep 1ms。
  3. !force && (mem_->ApproximateMemoryUsage() <= options_.write_buffer_size) :MemTable 还有足够的空间支持这次写入,直接返回。
  4. imm != NULL : 来到这里说明 MemTable 的空间不够了,且 Immutable MemTable 还存在(没被 compaction 或 正在被 compaction),需要等到compaction 完成。
  5. versions_->NumLevelFiles(0) >= config::kL0_StopWritesTrigger : Level0 的文件实在太多了,停止写入操作,等待 compaction 完成。
  6. 来到这里说明:1. Level0 的文件数量在正常范围内;2. Immutable MemTable 已经被 Compact;3. MemTable 已经满了。此时会切换 MemTable,并调用 MaybeScheduleCompaction

MaybeScheduleCompaction函数的实现比较简单:判断几个分支的情况,最后确定需要 Compaction 则将任务交交给后台线程。

  1. bg_compaction_scheduled_ : 后台线程已经在进行 compaction。
  2. shutting_down_.Acquire_Load() :正在关闭数据库。
  3. !bg_error_.ok() : 后台任务错误。
  4. imm_ == NULL && manual_compaction_ == NULL && !versions_->NeedsCompaction() :不需要 compaction。
  5. 由后台线程调用 DBImpl::BGWork 进行compaction。DBImpl::BGWork 直接调用了 DBImpl::BackgroundCall。 (相关代码
  1. 调用 BackgroundCompaction 执行 compaction 。
  2. 调用 MaybeScheduleCompaction 尝试再触发 compaction。
  1. 持久化 Immutable MemTable:如果存在 Immutable MemTable,则调用 CompactMemTable 进行 compaction。一个 Immutable MemTable 被持久化为 Level0 的一个 SST 文件。(相关代码
  2. 非人工触发,调用 VersionSet::PickCompaction ,获得一个 Compaction 对象。class Compaction 封装了本次要进行 compaction 的信息。( class Compaction相关代码 )。人工触发的 compaction 走另一个分支,暂不讨论。
  3. VersionSet::PickCompaction 选择要进行 compaction 的文件的策略有两种(相关代码): 1)size compaction,某一 Level 的数据太多了; 2)seek compaction,太多查询没有命中第一个 SST 文件。 另外还有一点要注意的就是 Level0 需要特殊处理,因为每个文件的 Key 范围可能是相交的。
  4. LevelDB 的 compaction 是 Level_n-1 合并到 Level_n。一些比较特殊的情况,只需要把 Level_n-1 的文件**移到 ** Level_n 即可。
  5. 一般的 compaction 分下面几步: 1)调用 DoCompactionWork, 执行 compaction。 2)调用 CleanupCompaction,清理已经完成的 compaction 完成。 3)调用 DeleteObsoleteFiles, 删除无效文件。

小结

  1. Compaction 都是通过 MaybeScheduleCompaction函数触发的。
  2. Compaction 是单线程异步完成的。
  3. seek compaction:LevelDB 在 SST 文件查找效率较低时(太多请求不在第一个 SST 文件命中,导致 allowed_seeks 小于等于 0)会触发 compaction。
  4. LevelDB 切换 MemTable 会生成 Immutable MemTable,需要将 Immutable MemTable 持久化,此时会触发 compaction。
  5. size compaction :每次执行 Compaction 的任务完成后,会尝试再次调用 MaybeScheduleCompaction 。因为有可能 level_n 的这次 compaction 导致 level_n+1 的 size 太大,需要进行 compaction。
  6. Compaction 是单线程异步完成的,所以,LevelDB 的写入速度在一定程度上受限于 compaction 的速度。对于写入量比较平稳的业务可能影响不大,但是对于经常有写入峰值的业务,峰值时的写入请求可能会受影响。

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

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java架构

Java 10正式发布,最新特性全解读

1834
来自专栏芋道源码1024

告诉你 Redis 是一个牛逼货

Redis 是一个 Key-Value 存储系统。和 Memcached 类似,它支持存储的 value 类型相对更多,包括 string(字符串)、 list...

1230
来自专栏申龙斌的程序人生

零基础学编程004:集成开发环境IDE

几天前介绍了《用在线编程环境快速上手》学习Python等编程语言,这种教学环境中的例子都非常简单,你不需要在自己的电脑中安装任何的软件,就可以马上动手学习Pyt...

3195
来自专栏大数据杂谈

Python 爬虫实战:股票数据定向爬虫

2754
来自专栏mini188

openfire的组件(Component)开发

在之前的文章《Openfire阶段实践总结》中提到过一种openfire的扩展模式Compoent。本文将主要探讨对这种模式的应用与开发方法。 内部与外部组件介...

2508
来自专栏happyJared

用Python统计你的简书数据

  说来也巧,之前有一次无意间留意到简书好像没有做文章总阅读量的统计(准确的说法应该叫展示),刚好最近有时间,趁这个机会就用Python写了这么个功能,既是学习...

1411
来自专栏腾讯Bugly的专栏

【MIG专项测试组】腾讯手机管家实战分析:内存突增是为神马?

应用版本升级后使用内存突增?如何跟踪?这次MIG专项测试组为大家分享内存问题跟踪实战过程! MIG专...

3364
来自专栏happyJared

爬虫进阶:Scrapy抓取boss直聘、拉勾心得经验

关于使用Scrapy的体会,最明显的感受就是这种模板化、工程化的脚手架体系,可以说是拿来即可开箱便用,大多仅需按一定的规则套路配置,剩下的就是专注于编写跟爬虫业...

2652
来自专栏Coco的专栏

【前端性能】浅谈域名发散与域名收敛

2352
来自专栏北京马哥教育

Python 爬虫实战:股票数据定向爬虫

功能简介 目标: 获取上交所和深交所所有股票的名称和交易信息。 输出: 保存到文件中。 技术路线: requests—bs4–re 语言:python3.5 ...

38711

扫码关注云+社区