LevelDB SSTable格式详解(1)--688IT编程网

LevelDB SSTable格式详解

作者：phylips@bmy

leveldb使用

2012-01-16

1.SSTable文件格式 (3)

1.1.格式说明 (3)

1.2.基本机制 (5)

1.2.1.数据压缩 (5)

1.2.2.Varint编码 (5)

1.2.3.CRC校验 (6)

1.2.4.前缀压缩 (10)

1.2.5.索引优化 (11)

1.3.几个问题 (12)

2.一个实际的SSTable文件 (13)

2.1.数据组成 (13)

2.2.二进制内容 (14)

3.单个文件读写过程 (15)

3.1.读文件 (15)

3.1.1.基本过程 (15)

3.1.2.代码分析 (16)

3.2.写文件 (17)

3.2.1.基本过程 (17)

3.2.2.代码分析 (17)

4.与HFile的对比分析 (18)

4.1.HFile V1文件格式 (20)

4.2.对比分析 (21)

5.性能因素 (21)

5.1.Block大小 (22)

5.2.重启点区间大小 (22)

5.3.压缩 (22)

5.4.CRC (22)

6.参考文献 (22)

7.附录 (23)

32c_defs.h (23)

_crc32ctable.c (24)

1.SSTable文件格式

SSTable是Sorted String Table的简称，也就是Bigtable底层的数据存储格式。SSTable文件是用来存储一系列有序的KeyValue对的，Key和Value都是字节串，KeyValue对根据固定比较规则有序地写入到文件中，文件内部分成一系列的Blocks(Block不会太大，常见的是64KB大小)，同时具有必要的索引信息。这样就既可以顺序地读取内部KeyValue记录，也能够根据某个Key值进行快速定位。

Google开源的LevelDB对应了Bigtable中的tablet server，LevelDB的代码中自然也包含了SSTable这一重要结构。下面会对SSTable的格式进行详细地解说，同时还会就一些影响性能的关键点进行分析，并将它与开源类Bigtable系统HBase中的HFile进行一个对比。

1.1.格式说明

单个SSTable文件的格式如上图所示，文件由五大部分组成：Data Blocks，Meta Blocks，MetaIndexBlock，DataIndexBlock，Footer。除Footer部分外，其余都是一些block组成的结构，每个block则是由多个KeyValue组成的数据块。文件包含一些内部指针。每个这样的指针被称为一个BlockHandle，包含如下信息： offset: varint64

size: varint64

如图所示，Footer中会有一个meta index handle用来指向Meta Index Block，还有一个data index handle用来指向Data Index Block，然后这两个Index Block，实际上是一系列Data Blocks和Meta Blocks的索引，其内部的KeyValue值就包含了指向文件中的一系列Meta Block和Data Block的handle。

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

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

(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这两个block的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

magic: fixed64; // == 0xdb4775248b80fb57

所以footer的总大小为40+8=48。

另需注意如下几点:

1.图中handle类型，也就是上面提到的BlockHandle，由offset和size组成

2.handle中的size大小不包括Type和CRC这两部分

3.CRC检验的内容包含了Type部分

4.block type目前有两种：0-不压缩,1-snappy压缩

需要着重解释的是：上图中除DataBlock外，其他类型的Block：MetaBlock，MetaIndexBlock，DataIndexBlock也都同属Block这一相同结构，都具有BlockData，Type，CRC这三部分，为简化起见，并没有画出这一级，只是画出了存在于这些Block中的KeyValue内容。同时对于BlockData来说，也是具有内部结构的，如上图中DataBlock部分画出的那样，BlockData又由如下几部分组成：KeyValue数据，Restart数组，RestartsNum。其中KeyValue部分结构如图顶部所示，Restart