leveldb文档翻译(3)-leveldb的日志格式和表格式

Contents

日志文件的格式
- 这种记录格式的优点
- 对比这个记录格式的缺点
表文件的格式
- “filter”元块
“统计”元块

日志文件的格式

日志文件的内容是一个32KB大小的块的序列。唯一可能的意外是日志文件结尾可能包含一个不完整的块。

每一个块由以下记录组成

block := record* trailer?
record :=
  checksum: uint32     // crc32c of type and data[] ; little-endian
  length: uint16       // little-endian
  type: uint8          // One of FULL, FIRST, MIDDLE, LAST
  data: uint8[length]

（注：crc32c是一种检验算法）

一条记录绝不会在块的最后6个字节内开始（因为剩下的6个字节已经不够大，checksum,length,type总共需要7个字节）。任何留下的字节形成trailer(拖车?),这部分必须完全是0字节，读取的时候必须跳过。

注：如果当前块恰好有7个字节留下来，一个新的非0长度的记录被增加，写入必须用一个FIRST记录（包含0字节的用户数据，FIRST用来表示这是一条记录的开始部分）去填充块的最后7个字节，之后将所有的用户数据写在后来的块中。

更多的类型可能在以后会加入进来。一些读取程序可能会跳过它们不认识的记录类型，其他读取程序可能会报告有些数据被跳过了。

FULL == 1
FIRST == 2
MIDDLE == 3
LAST == 4

FULL记录包含一个完整的用户记录的内容

FIRST，MIDDLE，LAST是用来表示用户记录被分成多个片段（尤其是块的边界）。FIRST是用户记录的第一个片段，LAST是用户记录的最后一个片段，MIDDLE是所有用户数据的内部片段。

例如:有以下的用户数据

A: length 1000
B: length 97270
C: length 8000

A将会在第一块中存储为FULL记录。

B将会划分成3段：第一段占用第一块剩下的部分，第二段占用整个第二块，第三段占用第三块的前面部分。这将会在第三块中留下6个字节的空间，被留作空白当成trailer。

C将会在第四块中存储为一个FULL记录。

这种记录格式的优点

1.我们不需要任何的同步的启发式算法-直接跳到下一个块的边界并且扫描。如果有一个错误发生，跳到下一块。作为一个边界效益，当一个日志文件的内容的一部分被作为一个记录嵌入到另外一个日志文件中，我们不会变的困惑。

2.在近似边界上分割（比如mapreduce）是简单的：找到下一个块的边界，跳过记录直到我们遇到一个FULL或FIRST记录。

3.对于大的记录我们不需要额外的缓冲区。

对比这个记录格式的缺点

1.没有对微小的记录的包装。这可能通过添加新的记录类型来修复，因此它只是当前实现的短处，不是这种格式的必须。

2.没有压缩。同样的，这也可以通过添加新的记录格式来修复。

表文件的格式

<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

参考varints,里面有varint64格式的解释。

1.键值对序列是有序存储的，被分成多个数据块。这些数据块从文件开头一个接着一个。每一个数据块被block_builder.cc中的代码格式化，之后有选择的进行压缩。

2.在数据块之后我们存储一束元块。支持的元块类型在下面描述了。更多的元块类型可能在以后会加进来。每一个元块类型也是用block_builder.cc格式化，然后之后被有选择的压缩。

3.一个“元索引”块。它包含每一个其他的元块的入口，入口的键是这个元块的名字，值是一个BlockHandle指向元块。

4.一个“索引”块。这个块包含每个数据块的入口，键是一个大于等于当前数据块的最后一个键的字符串，在连续的数据块的第一个键之前。值是这个数据块的BlockHandle。

5.在文件的最后面是一个填充满长度的脚部，包含了元索引块和索引块的BlockHandle，还有一个魔术数字。

    metaindex_handle: char[p];     // Block handle for metaindex
    index_handle:     char[q];     // Block handle for index
    padding:          char[40-p-q];// zeroed bytes to make fixed length
                                   // (40==2*BlockHandle::kMaxEncodedLength)
    magic:            fixed64;     // == 0xdb4775248b80fb57 (little-endian)

“filter”元块

在数据库打开时如果 FilterPolicy被指定，每个表都会有一个filter块。“元索引”块包含一个入口，将filter.<N>指向了 BlockHandle，对于filter块，<N>是filter 策略的
Name() 方法返回的。

filter块存储了一系列的filters，filter i包含了FilterPolicy::CreateFilter()在所有存储在文件偏移落入到范围[ ibase … (i+1)base-1 ]的块中键的输出。

当前，”base”是2KB，对这个例子来说，如果块X和Y开始在范围 [ 0KB .. 2KB-1 ],所有的在X和Y之间的键将会通过调用FilterPolicy::CreateFilter()被转换成一个filter，得到的filter将会被存储成当前filter块的第一个filter。

filter block是以下格式的：

[filter 0]
[filter 1]
[filter 2]
...
[filter N-1]

[offset of filter 0]                  : 4 bytes
[offset of filter 1]                  : 4 bytes
[offset of filter 2]                  : 4 bytes
...
[offset of filter N-1]                : 4 bytes

[offset of beginning of offset array] : 4 bytes
lg(base)                              : 1 byte

filter块的最后的偏移数组允许高效地mapping一个数据块偏移到相应的filter。

“统计”元块

这个元块包含一束统计。键是统计项的名字。值包含着统计内容。

TODO(预览):记录了以下的统计

data size
index size
key size (uncompressed)
value size (uncompressed)
number of entries
number of data blocks