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