LevelDB：实现(译)

作者：Jeff Dean, Sanjay Ghemawat

原文：http://leveldb.googlecode.com/svn/trunk/doc/impl.html

译者：phylips@bmy 2011-8-17

出处：http://duanple.blog.163.com/blog/static/7097176720112643946178/ 

LevelDB的实现本质上类似于Bigtable中的tablet(参见Bigtable论文5.3节)。但是，与论文中的具体的文件组织方式稍有不同，解释如下： 

每个数据库由一组存储在指定目录下的一个文件集合组成。有如下几种文件类型：

日志文件(*.log)存储了最近的一系列更新。每个更新操作会被追加到当前的日志文件中。当日志文件达到预定义的大小后，会被转化为一个sorted table，同时一个新的日志文件会被创建出来以接受未来的更新。

同时会在一个内存结构(memtable)中保存一份当前的日志文件的一个copy。该copy会参与到每次读操作中，这样最新的已日志化的更新就能够反映到读操作中。

sorted table (*.sst) 存储了一系列根据key值排好序的记录。每条记录要么是某key值对应的value，要么是一个针对该key值的删除标记。(删除标记会被用来去掉那些老的sorted tables中已过时的value值)。

sorted tables集合是通过一系列的level来进行组织的。从日志文件生成的sorted table会被放置在一个特殊的young level(也称作level 0)内。当该level下的文件数超过一定阈值(当前是4)时，该level下的所有文件会与level 1下与之有重叠的那些文件merge到一块，从而产生一系列新的level 1下的文件(我们会为每2MB的数据创建一个level 1文件)。

在level 0下的不同文件可能包含重叠的key值。但是其他level下的文件，它们的key range都是不重叠的(是指同一个level内部的文件不会重叠，不同的level之间会存在重叠)。设现有level L(L>=1),当level L下的文件总大小超过(10^L)MB时(比如，对应level 1就是10MB，level 2就是100MB，…),level L下的一个文件就会与level L+1下的所有与它有重叠的key的文件merge成一系列level L+1下的新文件。为最小化昂贵的seek开销，这些merge操作通过批量的读写操作，逐步的将新的更新从young level迁移到最大的level下。

MANIFEST文件列出了组成每个level的sorted tables集合，对应的key range，以及其他一些重要的元数据。只要数据库被重新打开，就会产生一个新的MANIFEST文件(文件名会嵌入一个新的数字)。MANIFEST文件会被格式化为一个log，所有导致状态改变(文件增加或删除)的变更都会追加到该log里。

CURRENT 是一个包含了最新的MANIFEST文件名称的文本文件。

一些信息会被输出到名为LOG及LOG.old的文件中。

其他用于各种目的的可能会产生的文件 (LOCK, *.dbtmp).

当日志文件超过一定大小(默认1MB)时，会进行如下操作：

l  创建一个全新的memtable结构和log文件，同时将未来的更新指向它们

l  同时在后台进行如下操作：

?  将之前的memtable的内容写入到sstable里

?  丢弃该memtable

?  删除老的log文件及memtable

?  将新的sstable添加到level 0下

当level L的大小超过自身的限制时，我们会在一个后台线程中进行compact操作。该操作会选择来自level L的一个文件，以及那些level L+1中所有与该文件重叠的文件。需要注意的是，即使level L下的这个文件只与level L+1下的某文件的一部分有重叠，也需要读取整个level L+1下的那个文件进行compaction，之后这个旧的level L+1下的文件就会被丢弃。另外：因为level 0很特殊(文件相互之间可能是有重叠的)，因此对于从level 0到level 1的compaction需要特殊对待：当level 0的某些文件相互重叠时，它的compaction就需要选择不止一个level 0的下的文件。Compaction会merge它选定的那些文件产生一系列新的level L+1下的文件。当当前输出文件大小达到目标大小(2MB)时，我们就会产生出一个新的level L+1下的文件。另外当当前输出文件的key range已经大的与10个以上的level L+2下的文件有重叠时，我们也会立即产生出一个新文件，而不一定非要等到它达到2MB，这是为了保证后面针对level L+1的Compaction不会从level L+2下获取过多数据。

老的文件会被丢弃，新的文件会被添加到服务状态。针对特定level下的Compaction是在整个key值空间内螺旋式地进行的。详细来说，比如对于Level L，我们会记住它上次compaction的那个最后的key值，在对于Level L的下次compaction时，我们会选择排在该key之后的第一个文件开始(如果没有这样的文件，那我们就再从头开始)。

Compaction会丢弃掉被覆盖的那些value值。同时如果更高level下的文件的key range不包含当前key时，针对它的删除标记也可以被丢弃掉{!更高level下的文件实际上是一些更老的值，如果它们包含该key，那么如果我们丢弃该低level下的删除标记，会导致该删除操作的丢失}

Level 0的compaction可能会从level 0下读取最多4个1MB文件，以及最坏情况下会读取所有的level 1下的文件(10MB)，这意味着，我们可能需要读14MB，写14MB。

除了比较特殊的Level 0的compaction，其他情况下我们会选取level L下的一个2MB的文件。最坏情况下，level L+1下可能有12个文件与它重叠(10是因为level L+1比level L大10倍，另外的2是因为在level L下的文件边界通常与level L+1下的边界并不是对其的)。因此compaction会读26MB，写26MB。假设磁盘IO带宽是100MB/s，最坏情况下的compaction可能需要大概0.5秒。

如果我们对后台操作进行一些限制，比如限制在全部IO带宽的10%，那么compaction时间可能会达到5秒。如果用户在用户以10MB/s的速度写入，我们就可能会创建出大量的level 0下的文件(可能会达到50，因为compaction需要5秒，而5秒内客户端已经又写入了50MB，而每个1MB，因此是50个)。这可能会显著增加读操作的开销，因为每次读操作都需要merge更多的文件。

解决方案 1:为了减少这种问题，我们可以在level-0下的文件数很大的时候，增加log切换的阈值。缺点是，阈值越大，相对应的memtable用掉的内存也就会越多。

解决方案2: 当level 0下的文件数上升很快时，我们可以人为地降低写操作速率。

解决方案3: 尽量降低merge的开销。由于大多数的level 0下的文件的block都已经缓存在cache里了，因此我们只需要关注merge迭代过程中的O(N)的复杂度。

为降低文件数，我们可以为更高level下的文件使用更大的文件大小，取代固定的2MB文件。当然这可能导致更多的compactions过程中的波动。另外我们也可以将文件集合划分到多个目录下。 

2011-02-04，我们在ext3文件系统下做了一个关于目录下的文件数与文件打开时间的关系的实验：

Files in directory   Microseconds to open a file

1000   9

10000  10

100000 16

看起来在现代文件系统中，没有必要进行目录切分。

Recovery

读取CURRENT文件找到最新提交的MANIFEST文件名
读取该 MANIFEST文件
清空垃圾文件
我们可以打开所有的sstable，但是使用惰性加载的方式会更好些...
将日志转化为一个新的level 0下的sstable
Start directing new writes to a new log file with recovered sequence#
Garbage collection of files

DeleteObsoleteFiles()会在每次compaction结束及recovery结束后调用。它会找到数据库中所有文件的名称。删掉除当前日志文件的所有日志文件。删掉那些不属于任何level及任何活动的compaction输出的table文件。

文件格式如下：

===========

  <beginning_of_file>

  [data block 1]

  [data block 2]

  ...

  [data block N]

  [meta block 1]

  ...

  [meta block K]

  [metaindex block]

  [index block]

  [Footer]        (fixed size; starts at file_size - sizeof(Footer))

  <end_of_file>

文件包含一些内部指针。每个这样的指针被称为一个BlockHandle，包含如下信息：

  offset:          varint64

  size:            varint64 

(1)文件内的key/value对序列有序排列，然后划分到一系列的data blocks里。这些blocks一个接一个的分布在文件的开头。每个data block会根据block_builder.cc里的代码进行格式化，然后进行可选地压缩。

(2)在数据blocks之后存储的一些meta blocks，目前支持的meta block类型会在下面进行描述。未来也可能添加更多的meta block类型。每个meta block也会根据block_builder.cc里的代码进行格式化，然后进行可选地压缩。

(3) A "metaindex" block.会为每个meta block保存一条记录，记录的key值就是meta block的名称，value值就是指向该meta block的一个BlockHandle。

(4) An "index" block.  会为每个data block保存一条记录,key值是>=对应的data block里最后那个key值，同时在后面的那个data block第一个key值之前的那个key值，value值就是指向该meta block的一个BlockHandle。

(5) 文件的最后是一个定长的footer，包含了metaindex和index这两个blocks的BlockHandle，以及一个magic number。

      metaindex_handle:    char[p];    // Block handle for metaindex

      index_handle:        char[q];    // Block handle for index

      padding:             char[40-p-q]; // 0 bytes to make fixed length

                                     // (40==2*BlockHandle::kMaxEncodedLength)

       magic:                 fixed64;    // == 0xdb4775248b80fb57

"stats" Meta Block

------------------

该meta block包含一系列统计信息。Key就是该统计单元的名称，value包含一系列统计信息如下：

  data size

  index size

  key size (uncompressed)

  value size (uncompressed)

  number of entries

  number of data blocks

日志文件内容由一系列的32KB blocks组成。唯一的异常是文件的末尾可能只包含一个部分块。每个block由一系列记录组成：

   block := record* trailer?

{!‘*’可以看做是正则表达式里的*,代表0个或n个record。‘?’也是，代表0个或者1个trailer }

   record :=

        checksum: uint32       // crc32c of type and data[]

        length: uint16

        type: uint8            // One of FULL, FIRST, MIDDLE, LAST

        data: uint8[length]

一条记录永远都不会从block的最后6个字节开始(因为它肯定放不下，看上面的记录checksum+length+type就占了7个字节了)。在这里组成trailer的最左处那些字节，要么完全是由0字节组成要么必须被读取者跳过。  

此外: 如果当前block目前只剩下7个字节，然后现在需要添加一个非0长度的记录，那么写入者需要输出一个FIRST记录(不包含任何的用户数据)来填充该block剩余的7字节的空，然后将用户数据存放到下一个block里。

未来可以添加更多的类型。某些读取者可能会直接skip掉那些它不理解的记录，其他的一些可能会报告某些数据被skip掉了。

FULL == 1

FIRST == 2

MIDDLE == 3

LAST == 4 

FULL 类型的记录包含了完整的用户记录. 

FIRST, MIDDLE, LAST 用于那些被分成多个片段(通常是因为block的边界导致的)的用户记录的。FIRST表明是用户记录的第一个片段，FIRST表明是用户记录的最后一个片段，MID表明用户记录的中间片段类型。

Example: consider a sequence of user records:

   A: length 1000

   B: length 97270

   C: length 8000

A会作为一个FULL类型的记录存放在第一个block里。B 会被划分成三个片段:第一个片段会填充第一个block的剩余部分, 第二个片段会填充整个的第二个block, 第二个片段会填充第三个block的前面一部分. 最后，第三个block就只剩下6个字节，会作为trailer而留空。C将会作为一个FULL类型的记录存放在第四个block里。 

===================

Some benefits over the recordio format: 

(1) We do not need any heuristics for resyncing - just go to next block boundary and scan.  If there is a corruption, skip to the next block.  As a side-benefit, we do not get confused when part of the contents of one log file are embedded as a record inside another log file.

(2) Splitting at approximate boundaries (e.g., for mapreduce) is simple: find the next block boundary and skip records until we hit a FULL or FIRST record.

(3) We do not need extra buffering for large records. 

Some downsides compared to recordio format: 

(1) No packing of tiny records.  This could be fixed by adding a new record type, so it is a shortcoming of the current implementation,not necessarily the format.

(2) No compression.  Again, this could be fixed by adding new record types.