LevelDB SSTable格式详解

LevelDB SSTable 格式详解

作者：phylips@bmy

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

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

4.1. HFile V1 文件格式 ...................................................................................... 20

4.2. 对比分析 .................................................................................................... 21

5. 性能因素 .............................................................................................................. 21

5.1. Block大小 ................................................................................................... 22

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

5.3. 压缩 ............................................................................................................ 22

6. 参考文献 .............................................................................................................. 22

7. 附录 ...................................................................................................................... 23

7.1. crc32c_defs.h .............................................................................................. 23

7.2. gen_crc32ctable.c ....................................................................................... 24

Blocks(Block 不会太大，常见的是 64KB 大小)，同时具有必要的索引信息。这样

就既可以顺序地读取内部 KeyValue 记录，也能够根据某个 Key 值进行快速定位。

Google 开源的 LevelDB 对应了 Bigtable 中的 tablet server，LevelDB 的代码中自然

也包含了 SSTable 这一重要结构。下面会对 SSTable 的格式进行详细地解说，同时

还会就一些影响性能的关键点进行分析，并将它与开源类 Bigtable 系统 HBase 中

的 HFile 进行一个对比。

1.1. 格式说明

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

offset: 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 会根据 block_builder.cc

(4) An "index" block。会为每个 data block 保存一条记录,key 值是>=对应的 data

block 里最后那个 key 值，同时在后面的那个 data block 第一个 key 值之前的那个

(5) 文件的最后是一个定长的 footer，包含了 metaindex 和 index 这两个 block 的

BlockHandle，以及一个 magic number。

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

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

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

5.meta index 和 data index 是两个相对特殊的 block,其内部的 KeyValue 具有特殊含

义，如图所示。目前的 LevelDB 版本中并未实现 Meta Block。

需要着重解释的是：上图中除 DataBlock 外，其他类型的 Block：MetaBlock，

MetaIndexBlock，DataIndexBlock 也都同属 Block 这一相同结构，都具有BlockData，

Block 中的 KeyValue 内容。同时对于 BlockData 来说，也是具有内部结构的，如

上图中 DataBlock 部分画出的那样，BlockData 又由如下几部分组成：KeyValue 数

制的分析。

当然，即使没有安装 Snappy，LevelDB 也是可以工作的。因为为了保证可移植性，

LevelDB 中对该压缩算法的调用也做了一层封装，如下：port/port_posix.h

inline bool Snappy_Compress(const char* input, size_t length,

::std::string* output) {

#ifdef SNAPPY

output->resize(snappy::MaxCompressedLength(length));

size_t outlen;

snappy::RawCompress(input, length, &(*output)[0], &outlen);

output->resize(outlen);

用压缩，压缩也不会生效，内部也只是采用非压缩格式。当然如果用户已经安装

了 Snappy，那么 LevelDB 的 Makefile 就能检测出来并定义好相关的宏。

1.2.2.1. 基本原理

从上面图中可以看到，很多字段都是 varint 类型的。varint 是对整数类型进行了

变长编码。比如 int32 原本只有 4 字节，而编码后最短只需 1 个字节，最长需 5

个字节。在 key，value 长度都很小的情况下，采用 varint 编码的方式所带来的结

构信息的空间节省会非常明显。

在 varint 编码中，编码后的每个字节的最高位用来表示后面的那个字节是否属于