Skip to content

Latest commit

 

History

History
364 lines (269 loc) · 13.6 KB

PlainTable-Format.md

File metadata and controls

364 lines (269 loc) · 13.6 KB

介绍

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文件的一部分来实现
  • 增加一个选项来移除大小的限制,这会需要额外的索引的内存。
  • 可能建立额外的稀疏索引来实现通用迭代搜索的。