固定链接 LevelDB源分析之compaction过程

LevelDB源分析之compaction过程

LevelDB源分析之compaction过程

1. LevelDB 简介

LevelDB 是 Google 开源的一款单机 KV 持久存储引擎,可以看作是BigTable 的单机版本。通过 LSM 树(Log Structured Merge Tree),LevelDB 牺牲了一定的读性能,但提高了写性能。对外 LevelDB 提供了常用的 PutGetDelete 等接口,还支持 Snapshot、Recovery 等操作。

本篇文章主要分析 LevelDB 的 compaction 过程以及分层设计的思想,对于 LevelDB 不熟悉的同学,可以先查看其他资料。

2. LSM 树在 LevelDB 中的应用

我们知道直接在磁盘中进行随机写性能是比较低的,那么为了获得较好的随机写性能,LevelDB 使用 LSM 树来组织数据。我们首先看下写流程:

当有一条记录要写入磁盘时,LevelDB 首先会将本次写操作 Append 到日志中(相当于顺序写),然后把这条记录插入内存中的 Memtable 中(Memtable 底层使用 skiplist 来保证记录有序),可见 LevelDB 将随机写转化为了顺序写。

Memtable 达到一定大小时,就会被 dump 到磁盘,这里有两个原因:1. 内存是有限的,不能将数据都放在内存中;2. 断电后内存中的数据就会全部丢失,虽然有日志可以恢复数据,但每次都恢复全部的数据显然不现实。

Memtable 一般情况下会被 dump 到 level 0,level L 中 tables 总大小超过一定大小时,LevelDB 就会在 level L 中选取一些 table 与 level L+1 中有 key 重叠的 table 进行 compaction,生成新的 table。这里我们思考一下为什么需要设计多层 level?

如果只有 level 0,随着 Memtable 不断被 dump 到磁盘上,level 0 上的 table 数量就会越来越多,并且这些 tables 的 key 存在相互重叠的情况。每次读操作时,如果在 Memtable 中没有找到数据,就需要在所有 tables 中进行查找,显然读性能受到了严重影响。

为了解决这一问题我们可以考虑限制 level 0 上 tables 的数量,同时增加一个 level 1,当 level 0 上 tables 数量超过一定大小时,就选取一些相互重叠的 tables 将其合并到 level 1,这样 level 1 中 tables 的 key 是相互不重叠的。此时我们最多只需要读 N+1 个文件,而 N 是比较小的,这样就达到了较好的读性能。

从上面的分析中似乎只要设计两层 level 就可以了,那为什么 LevelDB 还要多层的设计呢?设想一下随着 compaction 次数的增加,level 1 上的 tables 数量也会变得很多,这样极端情况下,level 0 上的一个 table 的 key range 可能会和 level 1 上所有tables 相重合,这样在进行 compaction 时就需要合并 level 1 上所有的 table,IO 开销太大。所以为了降低 compaction 时的 IO 开销,需要进行分层的设计。

3. compaction 过程源码分析

3.1 compaction 触发时机

读写数据时都会触发 compaction ,我们首先看下写数据时的触发流程:

写数据时主要调用 DBImpl::Write() 接口,在 Write() 接口中会调用 MakeRoomForWrite() 接口,我们看下这个接口的内部逻辑:

可见这个函数的主要作用是判断 Memtable 中有没有空间可写,当没有空间时将 Memtable 转化为 Immutable,最后调用MaybescheduleCompaction()函数判断要不要进行 compaction,这个函数最终会调用到BackgroundCompaction(),在这个函数中进行具体的 compaction 逻辑,那接下来我们就看下触发 compaction 的具体逻辑吧。

从上面可以看出 LevelDB 中的 compaction 主要分为三种

  1. Memtable 的 compaction
  2. Trivial compaction
  3. 一般的 compaction

3.2 选取需要被 compaction 的 sst

我们直接分析一般 compaction 的过程,前两种 compaction 都是在一般 compaction 的基础上实现的。

首先看下 LevelDB 是如何选取要被 compaction 的 sst 的:

3.3 compaction 的具体过程

找到了需要进行 compaction 的 sst,下面我们再来看下具体的 compaction 过程:

可见 compaction 过程主要将需要合并的 sst 按 key 值顺序生成新的 sst,同时删除标记为 delete 的 key,最后将新的 sst 加入到 Version 中,完成合并。

3.4 如何生成新的 Version

每次合并完成后都会生成一个新的 Version,新 Version= 当前 Verson + VersionEdit。VersionEdit 中保存了要被删除和添加的 sst,通过 LogAndApply 生成新的 Version:

至此,LevelDB 的 compaction 流程就分析完了。

本文作者:张迪

您的留言将激励我们越做越好