跳转至

leveldb 源码分析 14

本系列《leveldb 源码分析》共有 22 篇文章,这是第十四篇

9 LevelDB 框架之 1

到此为止,基本上 Leveldb 的主要功能组件都已经分析完了,下面就是把它们组合在一起,形成一个高性能的 k/v 存储系统。这就是 leveldb::DB 类。 这里先看一下 LevelDB 的导出接口和涉及的类,后面将依次以接口分析的方式展开。 而实际上 leveldb::DB 只是一个接口类,真正的实现和框架类是 DBImpl 这个类,正是它集合了上面的各种组件。 此外,还有 Leveldb 对版本的控制,执行版本控制的是 VersionVersionSet 类。 在 leveldb 的源码中,DBImpl 和 VersionSet 是两个庞然大物,体量基本算是最大的。对于这两个类的分析,也会分散在打开、销毁和快照等等这些功能中,很难在一个地方集中分析。 作者在文档 impl.html 中描述了 leveldb 的实现,其中包括 文件组织compactionrecovery 等等。下面的 9.1 和 9.2 基本都是翻译子 impl.html 文档。 在进入框架代码之前,先来了解下 leveldb 的文件组织和管理。

9.1 DB 文件管理

9.1.1 文件类型

对于一个数据库 Level 包含如下的 6 种文件:

1/[0-9]+.log:db 操作日志 这就是前面分析过的操作日志,log 文件包含了最新的 db 更新,每个更新都以 append 的方式追加到文件结尾。当 log 文件达到预定大小时(缺省大约 4MB),leveldb 就把它转换为一个有序表(如下 -2),并创建一个新的 log 文件。 当前的 log 文件在内存中的存在形式就是 memtable,每次 read 操作都会访问 memtable,以保证 read 读取到的是最新的数据。

2/[0-9]+.sst:db 的 sstable 文件 这两个就是前面分析过的 静态 sstable 文件,sstable 存储了以 key 排序的元素。每个元素或者是 key 对应的 value,或者是 key 的删除标记(删除标记可以掩盖更老 sstable 文件中过期的 value)。 Leveldbsstable 文件通过 level 的方式组织起来,从 log 文件中生成的 sstable 被放在 level 0。当 level 0 的 sstable 文件个数超过设置(当前为 4 个)时,leveldb 就把所有的 level 0 文件,以及有重合的 level 1 文件 merge 起来,组织成一个新的 level 1 文件(每个 level 1 文件大小为 2MB)。 Level 0 的 SSTable 文件(后缀为.sst)和 Level>1 的文件相比有特殊性:这个层级内的.sst 文件,两个文件可能存在 key 重叠。对于 Level>0,同层 sstable 文件的 key 不会重叠。考虑 level>0,level 中的文件的总大小超过 10^level MB 时(如 level=1 是 10MB,level=2 是 100MB),那么 level 中的一个文件,以及所有 level+1 中和它有重叠的文件,会被 merge 到 level+1 层的一系列新文件。Merge 操作 的作用是将更新从低一级 level 迁移到最高级,只使用批量读写(最小化 seek 操作,提高效率)。

3/MANIFEST-[0-9]+:DB 元信息文件 它记录的是 leveldb 的元信息,比如 DB 使用的 Comparator 名,以及各 SSTable 文件的管理信息:如 Level 层数、文件名、最小 key 和最大 key 等等。

4/CURRENT:记录当前正在使用的 Manifest 文件 它的内容就是当前的 manifest 文件名;因为在 LevleDb 的运行过程中,随着 Compaction 的进行,新的 SSTable 文件被产生,老的文件被废弃。并生成新的 Manifest 文件来记载 sstable 的变动,而 CURRENT 则用来记录我们关心的 Manifest 文件。 当 db 被重新打开时,leveldb 总是生产一个新的 manifest 文件。Manifest 文件使用 log 的格式,对服务状态的改变(新加或删除的文件)都会追加到该 log 中。 上面的 log 文件、sst 文件、清单文件,末尾都带着序列号,其序号都是单调递增的(随着 next_file_number 从 1 开始递增),以保证不和之前的文件名重复。

5/log:系统的运行日志,记录系统的运行信息或者错误日志。 6/dbtmp:临时数据库文件,repair 时临时生成的。 这里就涉及到几个关键的 number 计数器,log 文件编号,下一个文件(sstable、log 和 manifest)编号,sequence。 所有正在使用的文件编号,包括 log、sstable 和 manifest 都应该小于下一个文件编号计数器。 9.1.2 Level 0

当操作 log 超过一定大小时(缺省是 1MB),执行如下操作:

S1 创建新的 memtable 和 log 文件,并重导向新的更新到新 memtable 和 log 中; S2 在后台: S2.1 将前一个 memtable 的内容 dump 到 sstable 文件; S2.2 丢弃前一个 memtable; S2.3 删除旧的 log 文件和 memtable S2.4 把创建的 sstable 文件放到 level 0

9.2 Compaction

level L 的总文件大小查过限制时,我们就在后台执行 compaction 操作。Compaction 操作从 level L 中选择一个文件 f,以及选择中所有和 f 有重叠的文件。如果某个 level (L+1) 的文件 ff 只是和 f 部分重合,compaction 依然选择 ff 的完整内容作为输入,在 compaction 后 f 和 ff 都会被丢弃。 另外:因为 level 0 有些特殊(同层文件可能有重合),从 level 0 到 level 1 的 compaction 就需要特殊对待:level 0 的 compaction 可能会选择多个 level 0 文件,如果它们之间有重叠。 Compaction 将选择的文件内容 merge 起来,并生成到一系列的 level (L+1) 文件中,如果输出文件超过设置(2MB),就切换到新的。当输出文件的 key 范围太大以至于和超过 10 个 level (L+2) 文件有重合时,也会切换。后一个规则确保了 level (L+1) 的文件不会和过多的 level (L+2) 文件有重合,其后的 level (L+1) compaction 不会选择过多的 level (L+2) 文件。 老的文件会被丢弃,新创建的文件将加入到 server 状态中。 Compaction 操作在 key 空间中循环执行,详细讲一点就是,对于每个 level,我们记录上次 compaction 的 ending key。Level 的下一次 compaction 将选择 ending key 之后的第一个文件(如果这样的文件不存在,将会跳到 key 空间的开始)。 Compaction 会忽略被写覆盖的值,如果更高一层的 level 没有文件的范围包含了这个 key,key 的删除标记也会被忽略。

9.2.1 时间

Level 0 的 compaction 最多从 level 0 读取 4 个 1MB 的文件,以及所有的 level 1 文件(10MB),也就是我们将读取 14MB,并写入 14BM。 Level > 0 的 compaction,从 level L 选择一个 2MB 的文件,最坏情况下,将会和 levelL+1 的 12 个文件有重合(10:level L+1 的总文件大小是 level L 的 10 倍;边界的 2:level L 的文件范围通常不会和 level L+1 的文件对齐)。因此 Compaction 将会读 26MB,写 26MB。对于 100MB/s 的磁盘 IO 来讲,compaction 将最坏需要 0.5 秒。 如果磁盘 IO 更低,比如 10MB/s,那么 compaction 就需要更长的时间 5 秒。如果 user 以 10MB/s 的速度写入,我们可能生成很多 level 0 文件(50 个来装载 5*10MB 的数据)。这将会严重影响读取效率,因为需要 merge 更多的文件。

解决方法 1:为了降低该问题,我们可能想增加 log 切换的阈值,缺点就是,log 文件越大,对应的 memtable 文件就越大,这需要更多的内存。 解决方法 2:当 level 0 文件太多时,人工降低写入速度。 解决方法 3:降低 merge 的开销,如把 level 0 文件都无压缩的存放在 cache 中。

9.2.2 文件数

对于更高的 level 我们可以创建更大的文件,而不是 2MB,代价就是更多突发性的 compaction。或者,我们可以考虑分区,把文件放存放多目录中。 在 2011 年 2 月 4 号,作者做了一个实验,在 ext3 文件系统中打开 100KB 的文件,结果表明可以不需要分区。

文件数 文件打开 ms 1000 9 10000 10 100000 16

9.3 Recovery & GC

9.3.1 Recovery

Db 恢复的步骤:

S1 首先从 CURRENT 读取最后提交的 MANIFEST S2 读取 MANIFEST 内容 S3 清除过期文件 S4 这里可以打开所有的 sstable 文件,但是更好的方案是 lazy open S5 把 log 转换为新的 level 0sstable S6 将新写操作导向到新的 log 文件,从恢复的序号开始 9.3.2 GC

垃圾回收,每次 compaction 和 recovery 之后都会有文件被废弃,成为垃圾文件。GC 就是删除这些文件的,它在每次 compaction 和 recovery 完成之后被调用。