RocksDB PlainTable 学习

作者: GOGOYAO | 来源:发表于2019-07-16 10:16 被阅读0次

[TOC]

参考

RockDB 官方 wiki - PlainTable-Format
RockDB 官方 wiki 中文版- PlainTable-Format
看图了解RocksDB

1. 简介

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

创建一个全内存索引，使用二分法+哈希的方法替代直接二分查找
绕过 block cache，避免 block 的拷贝和维护 LRU cache 的开销
使用 mmap，避免查询时的内存拷贝

限制：

文件大小小于31位整型数
不支持数据压缩
不支持delta编码
不支持Iterator.Prev()
不支持无前缀的Seek()
构建索引的表加载速度较慢
只支持 mmap 模式

可以通过

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

或者

options.table_factory.reset(NewTotalOrderPlainTableFactory());

两种方式使用。NewPlainTableFactory()创建的基于前缀进行哈希索引的plain table，这也是 plain table 主要优化的对象。NewTotalOrderPlainTableFactory()不需要指定前缀提取器，创建的是纯二分查找的 plain table，主要是为了保全功能，对性能没怎么优化。

整体结构如下：

整体结构图

它的索引比较特殊，由hash结构和二进制查找缓存两部分组成。依然按照key的前缀做hash，如果桶对应的K-V记录很少，则直接指向第一个key（有多个key属于该桶）的记录位置。如果属于桶的K-V记录多于16条，或者包含多于一个前缀的记录，则先指向二进制查找缓存（先二分查找），而后指向第一个key的记录位置。

2. 文件格式

2.1. 总览

<beginning_of_file>
      [data row1]
      [data row1]
      [data row1]
      ...
      [data rowN]
      [Property Block]
      [Footer]                               (fixed size; starts at file_size - sizeof(Footer))
<end_of_file>

PlainTable的文件格式分为三部分

Data Row - 一个 kv 数据对，格式见后文分析
Property Block - 存放了两个信息：1. data_size，文件中数据部分的结束位置；2. fixed_key_len：如果所有的 key 都是相同长度，代表 key 的长度，否则设为0
Footer - 和BlockBasedTable format 一样

2.2. Data Row

每个 data row 如下编码：

   <beginning of a row>
      encoded key
      length of value: varint32
      value bytes
   <end of a row>

2.2.1. key 的编码

key 有两种编码方式：kPlain 和 kPrefix，在创建 plain table 工厂类的时候可以指定。

2.2.1.1. Plain 编码

如果 key 指定为定长，则按照 plain internal key 编码。
如果指定 key 没有指定为定长，则 key 是变长的，如下编码：

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

internal bytes 编码见后文

2.2.1.2. Prefix 编码

Prefix 编码是一种特殊的delta编码。如果上一个 key 和当前 key 的前缀相同（前缀根据用户提供的前缀提取器决定），我们可以避免重复 key的前缀部分。
前缀相同的场景下，有三种情况对 key 进行编码（记住所有的 key 都排好序了，所以共享相同前缀的 key 是挨在一起的）：

相同前缀的第一个 key，完整的 key 需要写入
相同前缀的第二个 key，需要记录前缀长度和前缀以外（简记为后缀）的字节数
相同前缀的第三个及之后的 key，只写入后缀部分
针对以上三种情况，定义了三个 flag 来表示完整 key、前缀、后缀。三种情况都需要记下 size。第一个字节编码如下：

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

前2个 bit 位是Type，00表示完整 key，01表示前缀，02表示后缀。后6个 bit 位用于存放 key 的 size：如果6个 bit不是全1，则表示 key 的大小；否则这个字节之后，会写入一个varint32。varint32加上0x3F就是 key 的size。这个方法在 key 比较短的时候可以省空间。
三种情况的举例说明如下：

完整 key

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

第二个 key

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

第三个及之后的 key

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

Internal Bytes 见后文。
有如下的 key，前后缀通过空格分开：

AAAA AAAB
AAAA AAABA
AAAA AAAC
AAAB BAA # wiki 上是AAABB AA，应该是错的，这里我更正了
AAAC AAAB

编码结果如下：

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

其中，FK 是完整 key的 flag，SF 是后缀flag，PF 是前缀flag。

当一个前缀下的 key 过多的时候，为防止 seek 性能受影响，将会重写完整 key。

2.2.1.3. internal bytes 编码

不管是Plain还是前缀编码类型，内部key的内部字节码都以同一种方式编码。在 RocksDB 中，key 的 internal bytes（固定为64位）包含 type （value，delete，merge等，低8位）和 sequence ID（高56位）。通常格式如下：

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

$\color{red}{注：这里 sequence ID 和 type 的顺序和官方 wiki 相反，wiki 中应该是以小端法来阐述的，此处改为大端法，方便和源码对应理解}$

其中，type 占用1个字节，sequence ID 占用7个字节。对于sequence ID为0的value 类型，还可以进一步优化空间占用。当确认没有 key 没有更早的值（或者说，level风格压缩的最后一层的第一个key，或者universal风格的最后一个文件），sequence ID 就填为0，这样可以更好的压缩和编码。比如说，在 PlainTable中，我们使用1个字节"0xFF"而不是8个字节存储 internal bytes：

 +----------- ...... -------------+----+
 |       user key                 |0xFF|
 +----------- ..... --------------+----+

$\color{red}{注：wiki 上写的是“0x80”，但是代码中是“char(0取反)”，应该是“0xFF”，此处以代码为准}$

$\color{red}{注：这里结合BlockBasedTable的 key 格式一起看，加深理解}$

key 的结构

2.2.2. 内存索引格式

2.2.2.1. 基本思想

内存索引构建的时候，是尽可能的紧凑的。在顶层，索引是一个哈希表，每一个桶要么是文件里的偏移，要么是一个二分查找索引。二分查找在两种情况下需要：

哈希冲突：两个以上的前缀哈希到了一个桶
一个前缀下的 key 太多：需要加速同一个前缀里的查找

2.2.2.2. 格式

索引由两部分内存构成：

哈希桶数组
一个包含索引的缓冲区，索引支持二分查找（下面称之为“二分查找缓冲区”，用“文件”特指SST文件）

key 通过前缀（通过Options.prefix_extractor提取）的哈希值哈希到桶上

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

如果 flag = 0 并且 offset 等于文件数据末尾的offset，那说明这个桶里没有数据；如果 offset 更小，说明这个桶里从offset 开始只有一个前缀。如果 flag = 1，offset 存放的是一个二分查找缓冲区。用一个 bit 位记录 flag，31位记录 offset 的编码方式是为了数据更加紧凑。

二分查找缓冲区的偏移开始，二分查找索引如下编码：

<begin>
  number_of_records:  varint32
  record 1 file offset:  fixedint32
  record 2 file offset:  fixedint32
  ....
  record N file offset:  fixedint32
<end>
# N表示 record 的数量，offset 是升序

2.2.2.3. 举例

假设文件内容如下：

+----------------------------+ <== 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: empty
bucket 2: 0007
bucket 3: 0003 0008
bucket 4: empty

桶2因为只有一个前缀（"0007"），且只有2行数据（<16），因此不需要二分查找索引。
桶0需要二分查找索引，因为前缀0005有超过16行数据。
桶3需要二分查找，因为有不止一个前缀。
我们需要为桶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
+---+---------------------------------------+

2.2.2.4. 索引查找

要查询一个 key，首先使用Options.prefix_extractor计算 key 的前缀，然后找到前缀对应的桶。如果桶里没有记录（Flag 为0并且 offset 是文件数据结尾），则 key 不存在；否则：

如果 Flag 为0，意味着桶里只有一个前缀，且这个前缀下没有很多 key，offset 字段只想的就是前缀在文件中的偏移。直接线性查找即可。
如果 Flag 为1，则这个桶需要进行二分查找。根据offset 字段取出二分查找索引，从二分查找索引找到所属的区域，然后在区域中进行线性查找。

2.2.2.5. 构建索引

创建索引的时候，扫面文件。对每一个 key 计算前缀，从第一个前缀开始，记录每个前缀的第(16n+1, n=0,1,2...)行的信息（包括前缀哈希值，偏移）。16是二分查找后进行线性查找的最大行数。增加这个数字，可以减少索引的内存消耗，但是会增加线性查找带来的开销。根据前缀的数量，确定最优的桶大小。分配所需的精确桶和二分查找缓冲区，然后根据桶大小填充索引。

2.2.2.6. 布隆过滤器

可以为查找请求配置前缀的布隆过滤器。用户可以给每个前缀配置所需字节数。当调用Get()或者Seek()的时候，先检查布隆过滤器，过滤掉不存在的前缀，再进行索引查找。

3. 未来计划

把索引变成现成 sst 文件的一部分
增加可选项根据内存消耗的权衡，去除文件大小限制
构建额外更稀疏的索引，支持更通用的 iterator seek