Rocksdb BlockBasedTable 格式

这个页面是从LevelDB的文档在table格式派生出来的，它反映了我们在开发RocksDB期间所做的更改。

BlockBasedTable是RocksDB中默认的SST表格式。

文件格式

  1. <beginning_of_file>
  2. [data block 1]
  3. [data block 2]
  4. ...
  5. [data block N]
  6. [meta block 1: filter block]                  (see section: "filter" Meta Block)
  7. [meta block 2: stats block]                   (see section: "properties" Meta Block)
  8. [meta block 3: compression dictionary block]  (see section: "compression dictionary" Meta Block)
  9. [meta block 4: range deletion block]          (see section: "range deletion" Meta Block)
  10. ...
  11. [meta block K: future extended block]  (we may add more meta blocks in the future)
  12. [metaindex block]
  13. [index block]
  14. [Footer]                               (fixed size; starts at file_size - sizeof(Footer))
  15. <end_of_file>

该文件包含内部指针，称为块句柄，包含以下信息:

  1. offset:         varint64
  2. size:           varint64

有关varint64格式的说明，请参阅本文档。

(1)文件中的键/值对序列按排序顺序存储，并划分为数据块序列。这些块在文件的开头一个接一个地出现。 每个数据块都根据block_builder.cc中的代码进行格式化 (参见文件中的代码注释)，然后可选压缩。 (2)在数据块之后，我们存储了一堆元块。下面将描述所支持的元块类型。将来可能会添加更多的元块类型。每个元数据块再次使用block_builder.cc进行格式化。然后选择压缩。 (3)metaindex块包含每个元块的一个条目，其中键是元块的名称，值是指向该元块的块句柄。 (4)索引块包含每个数据块的一个条目，其中键是一个字符串>=该数据块中的最后一个键，然后是连续数据块中的第一个键。 值是数据块的块句柄。如果使用kTwoLevelIndexSearch作为索引类型，则索引块是索引分区上的第二级索引，即，每个条目指向另一个索引块，该索引块包含每个数据块的一个条目。在本例中，格式为

  1. [index block - 1st level]
  2. [index block - 1st level]
  3. ...
  4. [index block - 1st level]
  5. [index block - 2nd level]

直到RocksDB 5.14版本，BlockBasedTableOptions::format_version=2，索引块的格式和数据块是相同的，其中索引块使用相同的键格式， 但特殊值，,，表示指向数据块。format_version=3,4为索引块提供了更优化但不兼容前向的格式。

  • format_version=3(因为RocksDB 5.15):在大多数情况下，索引块中的键不需要序列号seq。 在这种情况下，format_version跳过对序列号的编码，并在TableProperties中设置index_key_is_user_key，读者可以使用它来了解如何解码索引块。
  • format_version=4(因为RocksDB 5.16):通过对索引值(即块句柄)进行增量编码来更改索引块的格式。 这将保存每个重启间隔中非head索引项的BlockHandle::偏移量的编码。如果使用，则设置TableProperties::index_value_is_delta_encoded，读者可以使用它来了解如何解码索引块。 每个键的格式是(shared_size、non_shared_size、shared、non_shared)。每个值的格式，即当shared_size为0时，块句柄(偏移量，大小)为(偏移量，大小)，其中包含每个重启点的第一个条目。 否则格式为delta-size =块句柄大小-最后一个块句柄的大小。

format_version=4中的索引格式如下:

  1. restart_point   0: k, v (off, sz), k, v (delta-sz), ..., k, v (delta-sz)
  2. restart_point   1: k, v (off, sz), k, v (delta-sz), ..., k, v (delta-sz)
  3. ...
  4. restart_point n-1: k, v (off, sz), k, v (delta-sz), ..., k, v (delta-sz)
  5. where, k is key, v is value, and its encoding is in parenthesis.

(5)在文件的末尾是一个固定长度的页脚，其中包含metaindex和索引块的块句柄以及一个神奇的数字。

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

Filter 元数据块

Full filter 在这个过滤器中，有一个用于整个SST文件的过滤器块。

Partitioned Filter 整个过滤器被划分为多个块。添加一个顶级索引块来将键映射到相应的筛选器分区。点击这里了解更多内容。

Block-based filter 注意:下面解释了不推荐使用的基于块的过滤器。

如果在数据库打开时指定了”FilterPolicy”，则每个表中存储一个筛选器块。”metaindex”块包含一个条目，它从”filter.”映射到过滤器块的块句柄，其中””是过滤器策略的Name()方法返回的字符串。 filter块存储一系列过滤器，其中filter i包含FilterPolicy::CreateFilter()对存储在块中的所有键的输出，这些键的文件偏移量位于范围内

  1. [ i*base ... (i+1)*base-1 ]

目前，”base”是2KB。例如，如果block X和Y从[0KB ..，通过调用FilterPolicy::CreateFilter()将X和Y中的所有键转换为过滤器，得到的过滤器将作为过滤器块中的第一个过滤器存储。 过滤块的格式如下:

  1.  [filter 0]
  2.  [filter 1]
  3.  [filter 2]
  4.  ...
  5.  [filter N-1]
  7.  [offset of filter 0]                  : 4 bytes
  8.  [offset of filter 1]                  : 4 bytes
  9.  [offset of filter 2]                  : 4 bytes
  10.  ...
  11.  [offset of filter N-1]                : 4 bytes
  13.  [offset of beginning of offset array] : 4 bytes
  14.  lg(base)                              : 1 byte

过滤器块末尾的偏移数组允许有效地将数据块偏移量映射到相应的过滤器。

Properties 元数据块

这个元块包含一系列属性。键是属性的名称。值是属性。 stats块的格式如下:

  1.  [prop1]    (Each property is a key/value pair)
  2.  [prop2]
  3.  ...
  4.  [propN]

保证属性的排序没有重复。 默认情况下，每个表提供以下属性。

  1. data size               // the total size of all data blocks. 
  2. index size              // the size of the index block.
  3. filter size             // the size of the filter block.
  4. raw key size            // the size of all keys before any processing.
  5. raw value size          // the size of all value before any processing.
  6. number of entries
  7. number of data blocks

RocksDB还为用户提供”callback”来收集他们对这个表感兴趣的属性。请参考UserDefinedPropertiesCollector。

Compression Dictionary 元数据块

这个metablock包含用于在compressing/decompressing每个块之前启动压缩库的字典。它的目的是解决小数据块上的动态字典压缩算法的一个基本问题: 字典是在块上的一次单遍历期间构建的，所以小数据块总是有小的，因此无效的字典。

我们的解决方案是使用一个字典初始化压缩库，该字典是根据前面看到的块中采样的数据构建的。然后将此字典存储在文件级元块中，以便在解压期间使用。 这个字典大小的上限可以通过CompressionOptions::max_dict_bytes配置。默认情况下为零，即，则不会生成或存储该块。目前，kZlibCompression、kLZ4Compression、kLZ4HCCompression和kZSTDNotFinalCompression都支持该特性。

更具体地说，压缩字典只在压缩到数据最大、最稳定的最底层时构建。为了避免多次遍历输入数据，字典只包含来自子压缩的第一个输出文件的示例。然后，字典被应用到所有后续输出文件的元块中并存储在元块中。 注意，字典不会应用到第一个文件中，也不会存储在第一个文件中，因为它的内容直到该文件被完全处理后才会最终确定。

目前的采样是一致随机的，每个采样是64字节。在选择样例偏移量时，我们不知道输出文件的大小，所以我们假设它将达到最大大小，这通常是正确的，因为它是子压缩中的第一个文件。 如果文件更小，一些样本间隔将引用EOF之外的偏移量，这意味着字典将比CompressionOptions::max_dict_bytes更小。

Range Deletion 元数据块

这个metablock包含文件的key-range和seqnum-range中的范围删除。 范围删除不能与点数据一起内联到数据块中，因为这样范围就不能进行二进制搜索。

块格式是标准的键值格式。范围删除编码如下:

  1. * 用户键:范围的开始键
  2. * 序号:将范围删除插入数据库的序号
  3. * 值类型:kTypeRangeDeletion
  4. * 值:范围的结束键

当使用与非范围数据类型(put、delete等)相同的机制插入时，范围删除被分配序列号。它们还使用与点数据相同的刷新/压缩机制遍历LSM。它们可以被淘汰。(已删除)只在压缩到最底部级别时。