跳转至

介绍

PlainTable 是一个 RocksDB SST 文件格式,针对低延迟纯内存或者非常低延迟的媒介进行了优化。

优势:

  • 一个内存中的索引会被建立,使用二分法 + 哈希的方法替代直接二分查找。
  • 绕过快缓存,来避免块拷贝和 LRU 缓存机制带来的浪费
  • 查询的时候避免任何内存拷贝(mmap)。

限制: - 文件大小需要小于 31bits 整形。 - 数据压缩不支持 - delta 编码不支持 - Iterator.Prev() 不支持 - 无前缀 Seek 不支持 - 加载表比构建索引慢 - 只支持 mmap 模式

我们有计划消减部分限制。

使用

你可以调用 table.h 中的两个工厂方法,NewPlainTableFactory 或者 NewTotalOrderPlainTableFactory,来生成一个平表的表工厂,他们通过 Options.table_factory 或者 ColumnFamilyOptions.table_factory 传递参数。如果你使用前者,你还需要指定一个前缀提取器。

例子:

options.table_factory.reset(NewPlainTableFactory());
options.prefix_extractor.reset(NewFixedPrefixTransform(8));

或者

options.table_factory.reset(NewTotalOrderPlainTableFactory());

参考 include/rocksdb/table.h 中关于这两个方法的注释和参数说明。

NewPlainTableFactory 创建的表工厂生成的平表会使用基于 key 前缀的哈希索引。这是 PlainTable 优化的方向。

NewTotalOrderPlainTableFactory 不需要提供前缀提取器,而是使用一个完全的二分索引。这个函数主要用于保证 PlainTable 的功能完整。我们没有对这个场景做高度查询性能优化

### File Format
#### Basic
    <beginning_of_file>
      [data row1]
      [data row1]
      [data row1]
      ...
      [data rowN]
      [Property Block]
      [Footer]                               (定长;从 file_size - sizeof(Footer) 开始)
    <end_of_file>

Property Block 的格式和脚注都跟 基于块的表格式 相同。

参考下面了解数据行的格式。

属性块中的两个属性用于读取数据:

  • data_size: 文件中数据部分的结束
  • fixed_key_len:如果所有 key 都有相同的长度,就会记录 key 的长度。否则为 0

行格式

每个数据行都以下列格式编码:

    <beginning of a row>
      编码的key
      数值长度: varint32
      数值字节流
    <end of a row>

key 编码方式参见下方

key 编码方式

有两种 key 编码方式:kPlain 和 kPrefix,在创建平表工厂的时候声明。

Plain 编码

如果 key 是定长,那么 key 就直接存储。

如果 key 不是定长,key 会是变长的,以下面方式编码:

[length of key: varint32] + user key + internal bytes

参考下面内部字节编码了解 internal bytes

前缀编码

kPrefix 编码类型是一个特别的 delta 编码,如果一行有跟前面一行一样的前缀(根据用户提供的前缀提取器决定),我们可以避免重复 key 的前缀部分。

在这种情况,有三种编码方式(记得所有的 key 都是排序好,这样有相同前缀的 key 就在一起)

  • 一个前缀的第一个 key,完整 key 需要被保留
  • 一个前缀的第二个 key,保存前缀长度,和除前缀以外的部分(或者说,尾缀)即可。
  • 一个前缀的第三个或者之后的 key,只需要写尾缀部分即可。

我们定义了三个标志来区分完整的 key,前缀,尾缀。对于所有三种类型,我们需要一个大小。他们用一下格式编码:

第一个 byte 的 8 个 bits

+----+----+----+----+----+----+----+----+
|  Type   |            Size             |
+----+----+----+----+----+----+----+----+

签名两个 bit 表示他是一个完整的 key(00),或者前缀(01)或者尾缀(02)。最后六个 bit 用于存储大小。如果大小的 bit 不是全部为 1,意味着这个就是 key 的大小,否则,一个 varint32 会在这个比特后面被写入。这个 varint 值 + 0x3F (6 个 bit 全 1 的值) 就是这个 key 的大小。这样,比较短的 key 只要一个比特就可以了。

这里是三种类型的格式:

(1) 完整 key

+----------------------+---------------+----------------+
| Full Key Flag + Size | Full User Key | Internal Bytes |
+----------------------+---------------+----------------+

(2) 前缀的第二个 key

+--------------------+--------------------+------------+----------------+
| Prefix Flag + Size | Suffix Flag + Size | Key Suffix | Internal Bytes |
+--------------------+--------------------+------------+----------------+

(3) 前缀的第三个或者更后面的 key

+--------------------+------------+----------------+
| Suffix Flag + Size | Key Suffix | Internal Bytes |
+--------------------+------------+----------------+

参考 Internal Bytes 以了解 Internal Bytes 的更多细节

使用这种格式,不用知道前缀,行 key 只能使用完整 key 的文件偏移进行查找。所以如果一个前缀有太多 key,平表的构筑器可能会决定重写完整的 key,及时这个不是该前缀的第一个 key,以减轻 seek 的压力。

这里是一个例子,我们有下面的 key(前缀和尾缀通过空格分隔)

AAAA AAAB
AAAA AAABA
AAAA AAAC
AAABB AA
AAAC AAAB

会被加密成下面的格式

FK 8 AAAAAAAB
PF 4 SF 5 AAABA
SF 4 AAAC
FK 7 AAABBAA
FK 8 AAACAAAB

这里 FK 表示完整 key flag,PF 表示前缀 flag,SF 表示尾缀 Flag

内部字节编码 (internal bytes encoding)

不管是 Plain 还是前缀编码类型,内部 key 的内部字节码都以同一种方式编码。在 RocksDB,一个 key 的内部字节包括一个行类型(值,delete,merge,等)以及一个序列 ID。通常,一个 key 以这样的格式排布:

+----------- ...... -------------+----+---+---+---+---+---+---+---+
|       user key                 |type|      sequence ID          |
+----------- ..... --------------+----+---+---+---+---+---+---+---+

这里 type 使用 1byte,序列号使用 7 个 byte。

在平表格式,这也是一个 key 被优化的一个方法。更进一步,我们有一个优化用来保存一个通用例子的一些额外的字节:序列 ID 为 0 的值类型。在 RocksDB,我们有一个优化,如果确认该 key 没有更早的值,把序列 ID 填充为 0(或者说,level 风格压缩的最后一层的第一个 key,或者 universal 风格的最后一个文件),这样能带来更好的压缩(compress)或者编码结果。在 PlainTable,我么使用一个 bite"0x80",而不是 8 个比特来存储内部字节。

 +----------- ...... -------------+----+
 |       user key                 |0x80|
 +----------- ..... --------------+----+

内存索引格式

基本思想

内存索引构建的时候是尽可能压缩打包的。在最高层,索引是一个哈希表,每个桶都是一个文件内的偏移或者一个二分搜索索引。二分搜索在以下两个情况时出现:

  • 哈希冲突:两个或者更多前缀被哈希到一个桶里
  • 一个前缀有太多 key:需要加速该前缀内的搜索

格式

索引有两部分内存组成:一个哈希桶用的数组,以及一个带有二分搜索索引的缓冲区(下面称之为“二分搜索缓冲区”,以及“文件”特指 SST 文件)

根据前缀(使用 Options.prefix_extractor 提取)的哈希结果,key 被哈希到桶。

+--------------+------------------------------------------------------+
| Flag (1 bit) | Offset to binary search buffer or file (31 bits)     +
+--------------+------------------------------------------------------+

如果 Flag 为 0,并且 offset 字段等于文件数据的结尾,这意味着 null,这个桶没有数据;如果 offset 比较小,这意味着这个桶只有一个前缀,从该文件的 offset 位置开始。如果 Flag 为 1,这意味着 offset 是一个二分搜索缓冲区。该偏移处的格式如下所示:

从二分搜索缓冲区的偏移起始处开始,一个二分搜索索引根据下列方式编码:

<begin>
  number_of_records:  varint32
  record 1 file offset:  fixedint32
  record 2 file offset:  fixedint32
  ....
  record N file offset:  fixedint32
<end>

这里 N = 记录数量。偏移为递增排序。

之所以使用 31bit 偏移使用 1bit 来决定是不是二分搜索,只是为了是的索引更加紧凑。

一个索引的例子

我们假设这是一个文件的内容:

+----------------------------+ <== offset_0003_0000 = 0
| row (key: "0003 0000")     |
+----------------------------+ <== offset_0005_0000
| row (key: "0005 0000")     |
+----------------------------+
| row (key: "0005 0001")     |
+----------------------------+
| row (key: "0005 0002")     |
+----------------------------+
|                            |
|    ....                    |
|                            |
+----------------------------+
| row (key: "0005 000F")     |
+----------------------------+ <== offset_0005_0010
| row (key: "0005 0010")     |
+----------------------------+
|                            |
|    ....                    |
|                            |
+----------------------------+
| row (key: "0005 001F")     |
+----------------------------+ <== offset_0005_0020
| row (key: "0005 0020")     |
+----------------------------+
| row (key: "0005 0021")     |
+----------------------------+
| row (key: "0005 0022")     |
+----------------------------+ <== offset_0007_0000
| row (key: "0007 0000")     |
+----------------------------+
| row (key: "0007 0001")     |
+----------------------------+ <== offset_0008_0000
| row (key: "0008 0000")     |
+----------------------------+
| row (key: "0008 0001")     |
+----------------------------+
| row (key: "0008 0002")     |
+----------------------------+
|                            |
|    ....                    |
|                            |
+----------------------------+
| row (key: "0008 000F")     |
+----------------------------+ <== offset_0008_0010
| row (key: "0008 0010")     |
+----------------------------+ <== offset_end_data
|                            |
| property block and footer  |
|                            |
+----------------------------+

假设在这个例子里,我们使用 2 个字节的固定长度前缀,在每个前缀中,行总是增加 1。

现在我们给这个文件构建索引。通过扫描这个文件,我们知道有 4 个不同的前缀("0003", "0005", "0007" 和 "0008"),并且假设我们选择使用 5 个哈希桶,根据哈希函数,前缀被哈希到记个桶:

bucket 0: 0005
bucket 1: 空
bucket 2: 0007
bucket 3: 0003 0008
bucket 4: 空

bucket2 不需要二分搜索,因为那里只有一个前缀(“0007”),并且他只有两行(<16 行)

Bucket 0 需要二分搜索,因为前缀 0005 有多于 16 个行。

bucket 3 需要二分搜索,因为他有多于一个前缀。

我们需要为 bucket 0 和 3 分配二分搜索索引。这里是结果:

+---------------------+ <== bs_offset_bucket_0
+  2 (in varint32)    |
+---------------------+----------------+
+  offset_0005_0000 (in fixedint32)    |
+--------------------------------------+
+  offset_0005_0010 (in fixedint32)    |
+---------------------+----------------+ <== bs_offset_bucket_3
+  3 (in varint32)    |
+---------------------+----------------+
+  offset_0003_0000 (in fixedint32)    |
+--------------------------------------+
+  offset_0008_0000 (in fixedint32)    |
+--------------------------------------+
+  offset_0008_0010 (in fixedint32)    |
+--------------------------------------+

然后这里是哈希桶的数据:

+---+---------------------------------------+
| 1 |    bs_offset_bucket_0 (31 bits)       |  <=== bucket 0
+---+---------------------------------------+
| 0 |    offset_end_data    (31 bits)       |  <=== bucket 1
+---+---------------------------------------+
| 0 |    offset_0007_0000   (31 bits)       |  <=== bucket 2
+---+---------------------------------------+
| 1 |    bs_offset_bucket_3 (31 bits)       |  <=== bucket 3
+---+---------------------------------------+
| 0 |    offset_end_data    (31 bits)       |  <=== bucket 4
+---+---------------------------------------+

索引查找

为了找到一个 key,首先通过 Options.prefix_extractor 计算 key 的前缀,然后找到该前缀的桶。否则,如果桶没有记录在里面(Flag 为 0 且偏移指向文件数据末尾),那么 key 就找不到。

如果 Flag=0,这意味着只有一个前缀在桶里并且该前缀没有很多 key,所以偏移字段的指针指向索引的文件偏移。我们只需要在那里做现行搜搜就可以了。

如果 Flag=1,那里有一个二分搜索树。二分搜索缓冲区可以从偏移字段指向的地方取出。二分搜索之后,通过线性搜索查找二分搜索中找到的偏移量。

构建索引

当构建索引的时候,扫描文件。对于每个 key,计算他的前缀,从第一个开始,对于每个前缀的第(16n+1)行 (n=0,1,2....),记住(前缀的哈希值,偏移)信息。16 是在二分搜索之后需要检查线性搜索的行的最大数量。通过增加这个数字,我们可以减少内存消耗,但是需要付出更多线性搜索的时间。减少这个值则相反。基于前缀的数量,决定一个合适的桶的大小。根据桶的大小,分配需要用来填充索引的额外的桶和二分搜索缓冲区。

Bloom 过滤器

可以配置一个用于查询的作用在前缀上的 bloom 过滤器。用户可以配置每个前缀使用多少 bit。当做查询的时候(Seek() 或者 Get()),bloom 过滤器会在查找索引前检查并过滤不存在的前缀。

未来的计划

  • 可能考虑把这个索引当成 SST 文件的一部分来实现
  • 增加一个选项来移除大小的限制,这会需要额外的索引的内存。
  • 可能建立额外的稀疏索引来实现通用迭代搜索的。