leveldb的实现


同样是翻译自github。https://github.com/google/leveldb/blob/master/doc/impl.md

文件

leveldb的实现在本质上类似于单个BigTable tablet的表示。然而leveldb中文件的组织补充了与BigTable的一些不同的表示。下面会依次解释。

每个数据库都由存放在目录中的一组文件表示。下面会列出一些不同的文件类型

日志文件

    日志文件(*.log)保存了最近的一系列的更新。每个更新都会被追加到当前的日志文件中。当日志文件的大小到达了一个预设的值(默认大约是4M),它就会转换成一个有序的表(下面会介绍),然后会创建新的日志文件以待之后的更新使用。

    当前日志文件的副本保存在一个内存结构中(memtable)。这个副本在每次读时被查询,因此读操作反映所有记录的更新。

排序表

    排序表(*.ldb)保存了根据key排序的条目集合。每个条目,要么是key的值,要么是key 的删除标记(保留删除标记以隐藏旧的排序表中过时的值)

    排序表的集合通过等级的序号进行组织。从日志文件中生成的排序表放在一个特殊的年轻等级中(也叫做 level-0)。当年轻文件的数量超过一个确定的阈值时(当前是4个),所有的年轻文件与重叠的level-1文件合并到一起,产生一系列的新的level-1文件(我们每2M创建一个level-1文件)

    年轻等级中的文件可能包含有重叠的key。然而其他等级中的文件有着不重叠的key范围。假设level的序号L,且L >=1,当Level-L中的文件总大小超过(10^L)MB(比如level-1 10M,level-2 100M,...),level-L中的一个文件和Level-(L+1)的所有重叠文件都合并成为level-(L+1)的一组新文件。这些合并具有仅使用批量的写入和更新,就将新的更新逐渐地从年轻等级迁移到更大的等级的效果。

Manifest

    MANIFEST文件列出了组成每个级别的排序表集,相应的键范围和其他重要的元数据。每当重新打开数据库时,就会创建一个新的Manifest文件(文件名中嵌入序号)。Manifest文件的格式设置为日志,并且对数据库的服务状态的更改(随着文件的新增和删除)将追加到该日志中

Current

    Current是一个简单的文本文件,包含了最近的MANIFEST文件名称

信息日志

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

其他

    其他文件也可能存在用于其他用途的文件(LOCK,*.dbtmp等)

Levle-0

    当日志文件增长的超过一个给定的大小(默认4M):创建一个全新的内存表和日志文件,并且将将来的更新定向到新日志文件中。

    在后端中:

1.将之前的内存表内容写入到sstable中

2.丢弃旧的内存表

3.删除旧的日志文件和旧的内存表

4.将新的sstable添加到年轻等级中(level-0)

压缩

    当等级-L的大小超过它的限定大小时,我们就会在后端线程中进行压缩。压缩会从等级-L中挑选一个文件,从下一个等级-L+1的挑选出所有有重叠的文件。请注意,如果一个等级-L的文件只和等级-L+1的文件部分重叠,那么等级L+1中的文件条目作为压缩的输入使用,在合并结束之后被被丢弃。此外:因为等级-0是特殊的(该等级中的文件可能互相重叠),我们对待等级-0到等级-1的压缩也是特殊的:等级-0的压缩可能挑选多个等级-0的文件,如果一些文件相互重叠。

    压缩会合并挑选出来的文件中的内容,以产生等级-(L+1)的一系列文件。我们在当前输出文件达到目标大小时(2M),切换到产生一个新的等级-(L+1)文件。我们也在当前文件的key范围增长到足以重叠十个等级(L+2)文件时,我们也切换到产生一个新的输出文件。最后一条规则保证了稍后的压缩,等级-(L+1)文件不会从等级-(L+2)中挑选太多数据。

    旧文件将被丢弃,而新文件将增加到服务状态中

    特定级别的压缩在key空间中旋转。更详细地说,对于每个等级L,我们记住了上次等级L压缩的结束的key,下一次等级L的压缩时,会从这个key之后的第一个文件中开始(如果没有这样的文件,则换行到key空间的起始处)

    压缩会丢弃覆盖的值。它们也丢弃删除标记,如果没有更高编号的等级包含范围与当前key重叠的文件

定时

    等级-0压缩将从等级-0中读取最多四个1M文件,并且最坏的情况下,所有等级-1的文件(10M)。例如,我们将读14M,写14M。

    除了特殊的等级-0压缩外,我们从等级-L中挑选一个2M文件,最坏的情况下,该文件会覆盖12个来自下一个等级-L+1的文件(10个是因为等级-L+1是等级-L的10倍大小,并且另外2个是因为等级-L的边界处的文件范围通常不会与等级-L+1的文件范围对齐)。因此压缩要读取26M,写入26M。假设磁盘IO的带宽是100M/s(现代驱动的大概范围),那么最坏情况下的压缩会花费将近0.5秒的时间。

    如果我们将后端写的速度限制到很小的范围内,比如全速100M/s的10%,压缩可能需要花费5秒。如果用户写入的带宽是10M/s,我们可能会建立很多level-0的文件(大概50个,以持有5*10MB)。这个可能明显地增加了读的开销,因为每次读取都会合并更多文件的开销。

解决方案1:为了减少这个问题,当level-0的文件数目很大时,我们可能要增加日志转换的阈值。尽管这个缺点就是这个阈值越大,保存相应的内存表所需的内存就越多。

解决方案2:当level-0的熟练增大时,我们可能要人工地降低写的速率

解决方案3:我们致力于降低合并的成本。或许level-0的大多数文件将其放置在缓存中未压缩,我们只要担心在合并的遍历过程中的O(N)的复杂度。

文件数量

我们可以为更大的等级创建更大的文件来代替总是创建2M的文件。尽管这个代价是更多地突发压缩。又或者,我们可以将文件集切分到多个目录中。

在2011年2月4日的在ext3文件系统中的实验,显示了在目录中打开不同数量的100K大小的文件的时间:

目录中的文件数量 打开文件的时间(微妙)
1000 9
10000 10
100000 16
    因此,也许在现代的文件系统上,甚至不需要分片。

修复


  • 读取CURRENT文件,找到最近的已提交的MANIFEST文件
  • 读取该MANIFEST文件
  • 清除过期文件
  • 微妙可以在这里打开所有的sstable文件,但是也许延迟打开会更好
  • 将日志大块转换到新的level-0的sstable
  • 开始将新的写定向到新的带有修复后的序列号#的日志文件中

垃圾收集文件

RemoveObsoleteFiles()在每次压缩的结束时和修复结束时被调用。它会查找数据库中的所有文件,删除所有不是当前日志文件的日志文件,删除所有未从某个等级引用,并且不是当前活跃压缩输出的排序表文件。


评论

发表评论