SSTable内部的存储格式为:
<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- 文件中的键值对按顺序存储在多个文件的data block中。data block按照block_builder.cc中的逻辑进行格式化,然后在根据option判断是否要压缩。
- data block后面存储一系列meta block
- 再后面存储的是metaindex block。存储的key是meta block的名字,value为指向meta block的BlockHandle。
- index block:每个kv对对应一个data block,key>=data block的lastkey小于后续一个data block的第一个key,value是指向data block的BlockHandle。
- 再文件的尾部包含一个固定长度的footer。包含的内容如下:
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 Meta Block
如果在打开数据库时指定了FilterPolicy,则会在每个表中存储一个filter block。metaindex block包含一个kv对,将 filter. 映射到filter block的 BlockHandle,其中 是过滤器策略的 Name() 方法返回的字符串。
Filter Block存储了一系列的过滤器,其中第 i个过滤器所包含的数据,是对所有满足以下条件的 Key 调用FilterPolicy::CreateFilter()生成的输出结果:这些 Key 所属的Data Block,其在文件中的物理偏移量必须恰好落在[ i * base ... (i + 1) * base - 1 ]这个区间内。目前,“base” 的大小被固定为 2KB。
举个例子:如果数据块 X 和数据块 Y 的起始物理偏移量都落在[ 0KB .. 2KB - 1 ]这个范围内,那么 X 和 Y 里面的所有 Key 都会被打包凑在一起,共同调用一次FilterPolicy::CreateFilter()聚合成一个过滤器。这个生成的过滤器,将被作为第一个过滤器(即 filter 0)存储在filter block中。
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 byteoffset of filter数组用来快速查找对应的过滤器(过滤器的长度不是固定的,所以需要索引来快速查找)。
“stats” Meta Block
这个元数据块包含一系列统计数据。键是统计数据的名称,值包含统计数据本身。