leveldb实现笔记阅读

| 分类 存储  | 标签 leveldb 

读了一遍leveldb作者写的实现笔记,记(fan)录(yi)要(yi)点(bian), 该文回答了以下问题:

  • leveldb数据是如何组织的
  • 读,写,删是如何工作的
  • 合并是如何工作的

日志文件

一个日志文件(log file)记录了一系列最新的更新。每个更新都追加到当前的日志文件中。 当日志文件到达一个预先设置的阈值(默认为4M左右),当前日志文件会被转换为一个sst文件, 然后创建一个新的日志文件来保存将来的更新操作。当前的日志文件在内存里面也保留了一份(memtable)。内存中的副本,可以让读操作获取到最近的更新,避免读到陈旧数据。

有序表

有序表(.sst文件)存储了一系列按key排序的键值对(对,有序的)。每个键值对要么包含了某个key对应的value,要么记录着一个删除标记,表示某个key已经被删除了。(删除标记的保留可以防止老的有序表中的值被读取到)

一组有序表集合被组织为多个层次(levels)。有序表产生的来源有两个,一个由日志文件转化而来,另一个是由低层中的sst文件合并而来。日志文件产生的有序表位于一个特殊层,叫做level-0, 即0层。当0层中的文件数量超过一个预设阈值(默认为4)时,做文件合并:将所有0层中的文件,以及1层中key范围与其有重合的文件,做合并操作,产生新的有序表,放到1层中(默认1层中每个文件的大小是2MB)。

0层中文件包含的key的范围可能相互间存在交集,但其它层的文件包含的key的范围是没有交集的。对于L层中的文件,L >= 1,当所有文件的大小加起来超过了(10 ^ LMB)(i.e, 1层是10MB,2层是100MB。。。)时,将L层的一个文件,与L+1层中所有key范围与其重合的文件合并,产生一组新的文件到L+1层中。这些合并的效果很明显: 只是用一些读和写操作,逐渐将0层中的最近更新迁移到最高层,最小化磁盘寻道带来的性能损耗。但问题来了,如何从L层中选择一个文件去和L+1层中的文件合并呢? 简单来说,就是按照key轮转, 具体细节参考合并部分。

Manifest文件

Manifest文件列出了每一层所有的有序表,每个有序表包含的key的范围,以及其他的元数据。在一个数据库在被再次打开时,一个新的MANIFEST文件会被建立(文件名中有个新的数字)。MANIFEST文件和日志文件操作的方式一致, 记录数据库状态改变(文件增加或者删除)的信息会被追加到MANIFEST文件的结尾。

Current文件

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

Info日志文件

运行时信息输入到LOG文件和LOG.old文件中。

其它文件

LOCK文件,临时文件等等。

0 层

当日志文件增长超过一定的大小时(默认1MB):

  • 创建一个全新的的memtable和日志文件,新的更新写入新建的memtable和日志文件中
  • 在后台,做要做如下几件事情:

    • 将之前的memtable的内容写入一个有序表
    • 删除memtable中的内容
    • 删除旧的日志文件和旧的memtable
    • 将新的有序表加入到0层

合并

当第L层的大小超过限制,一个后台线程对其进行合并。合并线程会从第L层中挑出一个有序表文件,并且找到第L+1层中所有和这个文件的key范围重合的有序表文件。注意,即使一个L层有序表的key范围只和L+1层某个有序表的key范围部分重合,这个L+1层的有序表的整个文件都要作为合并操作的输入,合并完成后,这个文件将会被丢弃。另外:由于0层比较特殊(有序表文件的key范围可以相互重合),0层和1层的合并需要被特殊处理:一个涉及0层的合并操作有可能从0层中选取多个有序表,只要它们的key范围相互重合。

对L层的合并操作会合并被选取的文件(L层的一个文件和L+1层的若干个文件)的内容,产生一系列的第L+1层文件。何时产生文件?当合并操作产生的输出文件超过目标大小时(2M),就会在第L+1层产生一个新的文件。另外,当合并操作输出文件的key范围增长到足以覆盖10个以上的L+2层文件时,也会在L+1层产生一个文件,这可以防止后续对L+1层的某个文件进行合并时,从L+2层选取太多的数据。

合并完成时,旧的文件会被丢弃,新文件会加入到MANIFEST中,更新数据库的状态信息。

上面问到了,当对L层文件进行合并时,如何从多个有序表文件中选取出一个。具体做法是,按照key轮转。由于很容易得到L层文件包含的所有key的排序信息,我们可以从包含最小key的文件开始;每次合并的时候,计算出从L层选取的文件包含的key范围,记录该范围的结束key;下次做合并时,找到起始key刚好大于这个结束key的文件,选取这个文件做合并操作。

L层的合并操作,会丢弃L+1层被覆盖的值(很简单,新值代替旧值);而对带有删除标记的key/value对,如果任何一个位于大于L层的文件不包含这个key,该删除标记也会被丢弃(删除的对象不存在)。

合并耗时

0层合并操作会从0层中最多读4个1MB的文件,且最坏情况下会读取1层的所有文件(1层中所有文件的key范围和被选取的0层文件的key范围都有重合)。此时,最多读取14MB,写14MB。

除了特殊的0层合并,对于其他任意L > 0层的合并,会从L层选取一个2MB的文件。最坏情况下,该文件的key范围会同12个L+1层文件的key范围重合(10是因为L+1层文件总数是L层文件数的10倍,参考合并细节; 2是因为L层和L+1层文件的key范围往往不会对齐),所以合并操作会读26MB,写26MB。假设磁盘的吞吐是100MB/s, 那么最慢的时候合并会花0.5s。

如果我们限制后台线程合并线程的写的速度,比如100M/s吞吐的10%,一次合并操作最多花上5s。如果用户以10MB/s的速度写,那么在一次合并操作期间,0层会产生很多文件(最有能有50个, 5 * 10M/1M)。0层中文件多对读操作很不利,因为0层文件的key范围是可以重合的,每做一次读,都需要对多个文件做一次合并的操作。解决方案:

  • 当0层文件数变多时,增加memtable的大小。增加memtable的大小可以减少memtable的数量,但是需要耗费更多的内存。
  • 当0层文件变多时,可以人为降低写入速度
  • 大部分的0层文件可能都是以未压缩的状态存在于缓存中,因此解决读操作中复杂度为O(N)的大范围合并问题,可以降低读的性能损耗

文件数量

我们可以增加文件的大小,不再生成一些2MB的文件,生成8M, 16M等等大小,更大的文件意味着更少的文件数量,但是以为着合并操作中更动的读写。或者,将文件分布到不同的目录中,也可能是个选项。

故障恢复

故障恢复的步骤:

  • 读取CURRENT文件找到最近提交的MANIFEST文件的名字
  • 读取目标MENIFEST文件
  • 清理过时文件
  • 可以打开所有的有序表,或者等到用到的时候打开
  • 将日志文件转化为新的0层文件
  • 将新的写操作写入到新的日志文件

文件的垃圾回收

DeleteObsoleteFiles()在每次合并结束的时候或者故障恢复结束的时候会被调用。执行时,该函数会找到数据库中所有文件的名字,然后删掉除当前正在使用的日志文件外的所有日志文件,删除所有不被任何层级引用,也不是任意合并操作生成的有序表文件。

Ref:

  • https://leveldb.googlecode.com/svn/trunk/doc/impl.html
  • https://en.wikipedia.org/wiki/Log-structured_merge-tree

上一篇     下一篇