leveldb文档翻译(2)-leveldb的实现

这部分是来自于leveldb的impl.md文档,详细介绍了leveldb实现方面的设计。

1、文件

leveldb其实是Bigtable的简单的实现。Bigtable论文地址:http://research.google.com/archive/bigtable.html。当然,文件的组织方法和bigtable有一些不同之处,下面会逐个介绍。

1.1 日志文件

一个日志文件(*.log)存储一系列的最近的更新。每一个更新都会添加到当前日志文件的最后。当所有日志文件达到了预定义的大小(默认是4M),它会转换成一个有序的表(参见下面介绍),一个新的日志文件被创建提供给之后的更新。

当前日志文件的副本是保存在一个内存结构中(称为memtable)。每一次读都会向这个memtable中查询,所以读操作其实还是映射到所有记录下来的更新中。

2.有序表

一个有序表(*.ldb)存储了一系列的由键排序的键值对。每个键值对要么键对应着值,要么是键对应着一个删除标记。(删除标记保存在旧的排序表中存储着过时的值)。

排序表的集合是由一系列的等级(level)组织的。排序表如果是由一个日志文件生成,就会被置为一个特别的younglevel(也被称为level-0)。当young文件的数量超过了某个特定的阈值(当前是4),所有的young level文件和所有键范围重叠的level-1文件被合并在一起产生一系列的新的level-1文件(我们每2MB的数据创建一个新的level-1文件)

属于young level的文件可能自己相互包含重叠的键,但属于其他等级的文件有唯一的不重叠的键范围。level-L(L >= 1),当level-L所有的文件大小超过了(10^L)MB(例如,level-1是10MB,level2是100MB),在level-L中取一个文件,和所有在level-(L+1)中与之重叠的文件,合并成level-(L+1)的新的文件集合。这些合并使得新的更新逐渐从young-level的文件转移到最大的等级,这个过程只需要批量的读写操作即可完成(注:最小的时间复杂度)

2.1 Manifest

一个MANIFEST文件中个列举了由各个level组成的有序表的集合,包含了相应的键范围,以及其他重要的元数据。任何时候数据库被打开,一个新的MANIFEST文件(文件名中有一个新的数字代表)被创建。MANIFEST文件和log文件的格式相同,任何发生的改变都会被添加到这个文件中(比如文件添加或者移除)。

2.2 Current

CURRENT是一个简单的文本文件,包含了最新的MANIFEST文件的名字。

2.3 信息日志(Info logs)

信息消息被打印到LOG和LOG.old文件中

2.4 其他

其他文件用来记录一些杂项。(LOCK,*.dbtmp)

3.Level 0

当一个日志文件增长到一个特定的值(默认1MB):
创建一个新的memtable和log文件,并将未来的更新放在这里。
在后台的操作:
将上一个memtable的内容写入到sstable
丢弃上一个memtable
删除旧的日志文件和旧的memtable
将新的sstable添加到young(level 0) level。

4.压实(不是对数据进行压缩,只是将数据整合到一起,并且在这个过程中会去除重复键以及删除的键)

当level L超出了文件大小的限制,我们在另外一个后台线程中压实它。这个压实操作选择level L中的一个文件以及来自下一个level L+1的所有与之重叠的文件。注意:如果一个level-L文件只和一个level-(L+1)文件部分重叠,这个文件的所有部分都被作为压实的输入,然后在压实之后被丢弃。例外:因为level-0是特别的(level-0的文件可能彼此重叠),我们特殊对待从level-0到level-1的压实:当这些level-0文件彼此重叠时,一个level-0的压实会选择多个level-0的文件。

一个压实操作合并选择的文件的内容,产生一系列的level-(L+1)文件。在当前的输出文件超过目标文件大小(2MB)时,我们切换到一个产生的新的level-(L+1)文件。在当前输出文件的键范围增长到足够大,以致于和超过10个level-(L+2)的文件产生重叠时,我们同样切换到产生的新的输出文件。最后一条准则保证了之后的一次level-(L+1)文件压实不会从level-(L+2)中选择太多的数据。

旧的文件被丢弃,新的文件被加入到服务状态。

特定level的压实通过键空间的压实。详细来说,对于每个level L,我们记住最后一次level L的压实的结尾的键。下一次level L的压实将会选择在这个键之后的第一个文件(如果没有这个文件,就从键空间的起点环绕。

压实会丢弃覆盖的值,如果没有更大的数字level包含一个范围重叠当前键的文件,也会丢弃删除标记。

4.1 时间复杂度

level-0的压实将会从level-0中读取最多4个1MB的文件,在最坏情况下读取所有的level-1文件(10MB)。这样一来,我们将会读取14MB,写入14MB。

对于其他等级的压实,我们将会从level L中选择一个2MB的文件。最坏的情况下,将会从level L+1中重叠大概12个文件(10个文件是因为level-(L+1)是level-L的10倍大,其他在两边的两个文件是因为level L的文件范围通常和level-(L+1)的文件范围是不对齐的)。压实因此会读取26MB,写入26MB。假设磁盘IO速度为100MB/s,最差的压实大概消耗0.5s

如果我们减慢后台写入,只取全速100MB/s的10%,一次压实可能耗时5s。如果用户的写入速度为10MB/s,我们可能创建许多level-0的文件(大概5*10MB总共50MB)。这将明显的增加读取消耗,因为每次读取合并了更多的文件增加了负载。

解决方案1:为了减轻这个问题,我们可能希望当level-0文件数很大的时候,增加日志切换的阈值。虽然缺点是这个阈值越大,需要越多的内存来保存相应的memtable。

解决方案2:我们可能希望当level-0的文件数变多时,人为增加写入速度。

解决方案3:我们致力于降低大量文件合并的成本。也许大多数level-0文件在缓存中都有未压缩的块,我们仅仅需要担心O(N)复杂度的合并迭代。

4.2 文件的数量

除了总是生成2MB的文件,我们也可以为更高的等级生成更大的文件,以此减少文件的总数,虽然代价是更多突发的压缩。当然,我们也可以将文件集合分片放在不同的文件夹中。

在2011年2月4日,在ex3文件系统上做了一次测试,该测试显示,在很多文件的目录中做100K次文件打开的平均用时如下:

Files in directory Microseconds to open a file
1000 9
10000 10
100000 16

因此,在现代文件系统中,也许连分片也是不需要的。

5.恢复

  • 读取CURRENT去找到最后一次提交的MANIFEST文件名
  • 读取该MANIFEST文件
  • 清除过期的文件
  • 我们可以在这里打开所有的sstables,但是懒加载可能会更好。
  • 将log块转换成新的level-0 sstable
  • 开始将恢复的序列导向到新的日志文件的新的写入流。

6.文件的垃圾回收

每次恢复的最后以及每次压缩的最后DeleteObsoleteFiles()会被调用。它会找出数据库中所有的文件的名字。然后删除所有的不是当前日志文件的日志文件。再删除所有的不涉及到某些level和不是一个活跃的压缩输出的表文件。

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注