Plain Table 格式

介绍

PlainTable是RocksDB的SST文件格式，针对纯内存或真正的低延迟媒介上的低查询延迟进行了优化。

优点:

  • 建立一个内存索引，用散列+二分查找替换普通二分查找
  • 绕过块缓存以避免块复制和LRU缓存维护的开销。
  • 查询时避免任何内存副本(mmap)

限制:

  • 文件大小需要小于31位整数。
  • 不支持数据压缩
  • 不支持增量编码
  • 不支持Iterator.Prev()
  • 不支持非基于前缀的Seek()
  • 对于构建索引，表加载较慢
  • 只支持mmap模式。

我们计划减少一些限制。

用法

您可以在table.h中调用两个工厂函数NewPlainTableFactory()或NewTotalOrderPlainTableFactory()来为带有参数的普通表生成一个表工厂， 并将其传递给选项。table_factory或ColumnFamilyOptions.table_factory。如果使用前一个函数，则需要指定前缀提取器。例子:

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

或

  1. options.table_factory.reset(NewTotalOrderPlainTableFactory());

有关参数的说明，请参阅include/rocksdb/table.h中的两个函数的注释。

NewPlainTableFactory()使用键前缀为基于散列索引的普通表创建普通表工厂。这就是明文优化的目的。

NewTotalOrderPlainTableFactory()不需要前缀提取器，而是使用完全二进制索引。这个函数主要是为了使明文功能完备。在本例中，我们还没有高度优化查询性能。

  1. ### File Format
  2. #### Basic
  3. <beginning_of_file>
  4.   [data row1]
  5.   [data row1]
  6.   [data row1]
  7.   ...
  8.   [data rowN]
  9.   [Property Block]
  10.   [Footer]                               (fixed size; starts at file_size - sizeof(Footer))
  11. <end_of_file>

属性块和页脚的格式与基于相同的BlockBasedTable格式 有关每个数据行的格式，请参见Row Format。（ https://github.com/facebook/rocksdb/wiki/PlainTable-Format#row-format ） 属性块中的两个属性用于读取数据: 

  1. data_size: the end of data part of the file
  2. fixed_key_len: length of the key if all keys have the same length, 0 otherwise

行格式

每个数据行编码为:

  1. <beginning of a row>
  2.   encoded key
  3.   length of value: varint32
  4.   value bytes
  5. <end of a row>

有关已编码key的格式，请参阅key编码。 （ https://github.com/facebook/rocksdb/wiki/PlainTable-Format#key-encoding ）

Key编码

key有两种编码类型: kPlain和kPrefix，可以在创建plain表工厂时指定这两种编码类型。

普通编码

如果给定固定密钥长度，则对普通内部密钥进行编码。 如果没有给定固定的密钥长度，则密钥为可变长度，并将被编码为

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

有关内部字节的详细信息，请参阅内部字节编码。( https://github.com/facebook/rocksdb/wiki/PlainTable-Format#internal-bytes-encoding )

Prefix编码

kPrefix编码类型是一种特殊的增量编码，如果一行显示的前缀(由用户给出的前缀提取器确定)与前一个key相同，则可以避免重复key的前缀部分。

在这种情况下，有三种情况下编码一个键(记住所有键都是排序的，所以共享相同前缀的键在一起):

前缀的第一个键，其中需要写入完整的键 前缀的第二个键，其中需要记录前缀长度，以及前缀以外的字节(为了简化，这里我们将其称为后缀) 前缀的第三个或更晚的键，其中只需要写入后缀部分。

我们为指示全键定义了三个标志、一个前缀和一个后缀。对于这三种情况，我们都需要一个尺寸。它们以这种格式编码:

第一个字节的8位:

  1. +----+----+----+----+----+----+----+----+
  2. |  Type   |            Size             |
  3. +----+----+----+----+----+----+----+----+

前两位表示 全键(00)、前缀(01) 或 后缀(02)。最后6位代表大小。 如果大小位不都是1，则表示键的大小。否则，varint32是在这个字节之后写的。 这个varint值 + 0x3F(所有1的值)将是键大小。这样，较短的键只需要一个字节。

以下是上述三种情况的格式:

(1) 完整的键

  1. +----------------------+---------------+----------------+
  2. | Full Key Flag + Size | Full User Key | Internal Bytes |
  3. +----------------------+---------------+----------------+

(2) 前缀的第二个键

  1. +--------------------+--------------------+------------+----------------+
  2. | Prefix Flag + Size | Suffix Flag + Size | Key Suffix | Internal Bytes |
  3. +--------------------+--------------------+------------+----------------+

(3) 前缀的第三个和后面的键:

  1. +--------------------+------------+----------------+
  2. | Suffix Flag + Size | Key Suffix | Internal Bytes |
  3. +--------------------+------------+----------------+

有关所有三种情况的内部字节的详细信息，请参见内部字节编码。( https://github.com/facebook/rocksdb/wiki/PlainTable-Format#internal-bytes-encoding )

使用这种格式，在不知道前缀的情况下，只能使用全键的文件偏移量来查找行键。 因此，如果一个前缀中有太多的键，plain table builder可能会决定再次重写完整的键，即使它不是前缀的第一个键，以使查找更容易。

下面是一个例子，we for following keys(前缀和后缀由空格分隔):

  1. AAAA AAAB
  2. AAAA AAABA
  3. AAAA AAAC
  4. AAABB AA
  5. AAAC AAAB

将这样编码:

  1. FK 8 AAAAAAAB
  2. PF 4 SF 5 AAABA
  3. SF 4 AAAC
  4. FK 7 AAABBAA
  5. FK 8 AAACAAAB

(其中FK为全键标志，PF为前缀标志，SF为后缀标志)

内部字节编码

在普通编码类型和前缀编码类型中，内部键的内部字节都以相同的方式编码。 在RocksDB中，键的内部字节包括行类型(值、删除、合并等)和序列ID。通常，键的格式如下:

  1. +----------- ...... -------------+----+---+---+---+---+---+---+---+
  2. |       user key                 |type|      sequence ID          |
  3. +----------- ..... --------------+----+---+---+---+---+---+---+---+

其中类型取一个字节，序列ID取7个字节。 在普通表格式中，这也是优化一个键的常用方法。此外，我们还进行了优化，为一个常见的情况节省了一些额外的字节:序列ID为0的值类型。 RocksDB,我们有一个优化来填补序列ID为0时,一个关键我们确信没有前一个值这个关键系统中(具体来说,第一个关键的最后水平level-style压实或最后一个文件在统一风格),使更好的压缩和编码。 在PlainTable中，我们使用1字节”0x80”代替8字节作为内部字节:

  1. +----------- ...... -------------+----+
  2. |       user key                 |0x80|
  3. +----------- ..... --------------+----+

In-Memory 索引格式

基本思想

内存索引构建得尽可能紧凑。在顶层，索引是一个哈希表，文件中的每个bucket都要偏移，或者是一个二进制搜索索引。在两种情况下需要进行二分查找:

(1)哈希冲突:将两个或多个前缀哈希到同一个桶中 (2)一个前缀键数过多:需要加快前缀内查找

格式

索引由两部分内存组成:一个用于哈希桶的数组和一个包含二进制可搜索索引的缓冲区(下面将其称为”二进制搜索缓冲区”，并将”file”作为SST文件)。

Key根据其前缀的哈希值被哈希到bucket(使用Options.prefix_extractor提取)。

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

如果Flag = 0, offset字段等于文件末尾数据的偏移量，则表示null—该桶没有数据;如果偏移量更小，这意味着bucket只有一个前缀，从该文件偏移量开始。如果Flag = 1，则表示偏移量用于二进制搜索缓冲区。该偏移量的格式如下所示。

从二进制搜索缓冲区的偏移量开始，二进制搜索索引编码如下:

  1. <begin>
  2.   number_of_records:  varint32
  3.   record 1 file offset:  fixedint32
  4.   record 2 file offset:  fixedint32
  5.   ....
  6.   record N file offset:  fixedint32
  7. <end>

其中N = number_of_records。偏移量按升序排列。

只存储31位偏移量并使用1位来确定是否需要二进制搜索的原因是为了使索引紧凑。

索引的一个例子

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

  1. +----------------------------+ <== offset_0003_0000 = 0
  2. | row (key: "0003 0000")     |
  3. +----------------------------+ <== offset_0005_0000
  4. | row (key: "0005 0000")     |
  5. +----------------------------+
  6. | row (key: "0005 0001")     |
  7. +----------------------------+
  8. | row (key: "0005 0002")     |
  9. +----------------------------+
  10. |                            |
  11. |    ....                    |
  12. |                            |
  13. +----------------------------+
  14. | row (key: "0005 000F")     |
  15. +----------------------------+ <== offset_0005_0010
  16. | row (key: "0005 0010")     |
  17. +----------------------------+
  18. |                            |
  19. |    ....                    |
  20. |                            |
  21. +----------------------------+
  22. | row (key: "0005 001F")     |
  23. +----------------------------+ <== offset_0005_0020
  24. | row (key: "0005 0020")     |
  25. +----------------------------+
  26. | row (key: "0005 0021")     |
  27. +----------------------------+
  28. | row (key: "0005 0022")     |
  29. +----------------------------+ <== offset_0007_0000
  30. | row (key: "0007 0000")     |
  31. +----------------------------+
  32. | row (key: "0007 0001")     |
  33. +----------------------------+ <== offset_0008_0000
  34. | row (key: "0008 0000")     |
  35. +----------------------------+
  36. | row (key: "0008 0001")     |
  37. +----------------------------+
  38. | row (key: "0008 0002")     |
  39. +----------------------------+
  40. |                            |
  41. |    ....                    |
  42. |                            |
  43. +----------------------------+
  44. | row (key: "0008 000F")     |
  45. +----------------------------+ <== offset_0008_0010
  46. | row (key: "0008 0010")     |
  47. +----------------------------+ <== offset_end_data
  48. |                            |
  49. | property block and footer  |
  50. |                            |
  51. +----------------------------+

让我们假设在这个例子中，我们使用2字节固定长度的前缀，并且在每个前缀中，行总是递增1。

现在我们正在为文件构建索引。通过扫描文件，我们知道有4个不同的前缀(“0003”、”0005”、”0007”和”0008”)，假设我们选择使用5个哈希桶，根据哈希函数，将前缀哈希到桶中:

  1. bucket 0: 0005
  2. bucket 1: empty
  3. bucket 2: 0007
  4. bucket 3: 0003 0008
  5. bucket 4: empty

Bucket 2不需要二分查找，因为它只有一个前缀(“0007”)，并且只有2(<16)行。

Bucket 0需要二进制搜索，因为前缀0005有16多行。

Bucket 3需要二进制搜索，因为它包含多个前缀。

我们需要为bucket 0和3分配二进制搜索索引。结果如下:

  1. +---------------------+ <== bs_offset_bucket_0
  2. +  2 (in varint32)    |
  3. +---------------------+----------------+
  4. +  offset_0005_0000 (in fixedint32)    |
  5. +--------------------------------------+
  6. +  offset_0005_0010 (in fixedint32)    |
  7. +---------------------+----------------+ <== bs_offset_bucket_3
  8. +  3 (in varint32)    |
  9. +---------------------+----------------+
  10. +  offset_0003_0000 (in fixedint32)    |
  11. +--------------------------------------+
  12. +  offset_0008_0000 (in fixedint32)    |
  13. +--------------------------------------+
  14. +  offset_0008_0010 (in fixedint32)    |
  15. +--------------------------------------+

下面是哈希桶中的数据:

  1. +---+---------------------------------------+
  2. | 1 |    bs_offset_bucket_0 (31 bits)       |  <=== bucket 0
  3. +---+---------------------------------------+
  4. | 0 |    offset_end_data    (31 bits)       |  <=== bucket 1
  5. +---+---------------------------------------+
  6. | 0 |    offset_0007_0000   (31 bits)       |  <=== bucket 2
  7. +---+---------------------------------------+
  8. | 1 |    bs_offset_bucket_3 (31 bits)       |  <=== bucket 3
  9. +---+---------------------------------------+
  10. | 0 |    offset_end_data    (31 bits)       |  <=== bucket 4
  11. +---+---------------------------------------+

索引查找

要查找键，首先使用选项计算键的前缀。并找到前缀的桶。如果bucket上没有记录(标志=0，偏移量是文件中数据结束的偏移量)，则找不到键。否则,

如果Flag=0，则表示bucket只有一个前缀，而前缀没有多少键，所以offset字段指向前缀的文件偏移量。我们只需要从这里做线性搜索。

如果Flag=1，则需要对这个桶进行二叉搜索。可以从偏移量字段检索二进制搜索索引。在二叉搜索之后，从二叉搜索找到的偏移量进行线性搜索。

建立索引

构建索引时，扫描文件。对于每个键，计算它的前缀，记住(前缀的哈希值，偏移量)信息，从第一行开始，每个前缀(n=0,1,2…)的第(16n+1)行。 16是在二叉搜索之后的线性搜索中需要检查的最大行数。通过增加数量，我们可以节省索引的内存消耗，但为线性搜索支付更多的成本。 反之亦然。根据前缀的数量，确定最优桶大小。分配所需的精确桶和二进制搜索缓冲区，并根据桶的大小填充索引

布隆过滤器

可以为查询配置前缀上的bloom过滤器。用户可以配置为每个前缀分配多少位。 当执行查询(Seek()或Get()时，会检查bloom filter并在查找索引之前过滤掉不存在的前缀。

未来计划

  • 可以考虑将索引具体化为SST文件的一部分。
  • 添加一个选项，通过交换索引的内存消耗来消除文件大小的限制。
  • 可以构建额外的更稀疏索引，以启用一般迭代器查找。