LevelDB的边边角角之一

LevelDB的边边角角之一

0, Varint64

变长数字，主要用于压缩数字，来源于protobuf。

1, Log 和Table的文件格式

Google recordio的文件格式

Checksum

Original size

Compressed Size

(un/compressed) Data

 

Checksum

Original size

Compressed Size

(un/compressed) Data

 

 

Checksum: 32bits;

Original Size: 64bits，数据的原始大小；

Compressed Size: 64bits压缩后的大小，如果不是压缩，就为0；

Data: 实际的数据

 

LevelDB memtable: Arena+SkipList

Arena，

所有的block都保存在一个vector<char*>中

1，当前block有freeSpace>size直接返回；

2，如果size大于blockSize/4则new_block返回，否则只new_block并用block其中的一部分（这样浪费了当前的block剩余空间）；

SkipList，

 

LevelDB log文件格式

block := record* trailer

record :=

checksum: uint32 //crc32c of type and data[], little-endian

length: uint32 // little-endian？其实是uint16

type: uint8 // enum of { FULL, FIRST, MIDDLE, LAST}

data: uint[length]

 

下图为一个Block(32KB), log file由一连串block组成。

Record 1

Checksum

Length

Type

data

 

Record 2...

Record n

Trailer

 

 

与recordio format的对比：

好处：可以直接跳过一个一个block

坏处：暂时对小的record没有packing，并没有压缩数据，但都可以通过添加type进行支持。

 

LevelDB table文件格式

immutable, 不可修改的。

k/v 对都是有序地按序写在data block中，data/index block均可以被压缩（状态位在？）

meta block就是下面的filter/stat meta block，也可以支持更多的。

每个block的大小？

index和footer放在文件最后是宜于生成文件，并方便open文件后重定位。

 

Data block 1

Data block 2

...

Data block N

Meta block 1

…

Meta block K

Meta Index block

Index block

Footer (fixed size: starts at file_size - sizeof(footer))

BlockHandle:

offset: varint64

size: varint64

相当于内部index到data的指针

metaindex

key name of meta block

value BlockHandle 指向meta block

index，每个data block一条记录

key string>=last_key

value BlockHandle指向data block

footer 这是定长的。

metaindex_handle: char[p], block handle for metaindex

index_handle: char[q], block handle for index

padding: char[40-p-q], 填充zeroed bytes

40==2*BlockHandle::kMaxEncodedLength

magic: fixed64

filter meta block

[TBD]

stat meta block

data size/ index size/ key size(uncompressed)/ value size(uncompressed)

number of entries/ number of data blocks

 

2, 从log file到合并 table file

log file，每个update都添加到log里，当大于（默认4MB）会转为sorted table，

内存中的影像是memtable。生成sst（young level-0）后，这个log就会给删掉，memtable?

sorted tables的compaction，sst分为一系列的levels，young level，也就是level-0，中的文件可能会有覆盖范围的key（overlapping key)，而level-L(L>0)则每个文件的key范围都是没有互相覆盖的。

当level-L的所有文件总大小超过10^L(MB)时，会用其中一个level-L的文件File1+所有key范围与File1有覆盖的level-(L+1)的文件File2..k 合并成一个新的level-L+1文件。

这样做的好处？单条的读？bulk的批量读？

Manifest一个普通的log file，保存每个level下的所有sst， 并对应的key ranges，以及其他的meta data。

Current普通文本，里面就指向当前在用的Manifest文件。

其他的Lock文件和dbtmp等等，

A, Reference:

1) leveldb tutorial, http://leveldb.googlecode.com/svn/trunk/doc/index.html

2) leveldb brief of implements, http://leveldb.googlecode.com/svn/trunk/doc/impl.html

3) table file format, http://leveldb.googlecode.com/svn/trunk/doc/table_format.txt

4) log file format, http://leveldb.googlecode.com/svn/trunk/doc/log_format.txt

 

5) blog 很详细的一个分析 http://blog.csdn.net/sparkliang/article/category/1342001