基于 RocksDB 的索引数据存储

NewSQL技术近几年发展十分迅猛，国内外都有了较成熟的系统。在业界一些开源系统的实现中，Rocksdb起到了核心的存储和查询功能。其中的一个核心设计需求，就是把结构化的表数据以及索引数据转换为kv数据存储到Rocksdb中。本文就该需求的设计方案进行了介绍，以供大家参考。

我们知道Rocksdb是一个kv形式的存储引擎，就像一个有序的大map，map的key,value都是字节数组，其排序顺序就由key这个二进制字节数组决定。Rocksdb除了提供随机读写kv的接口，还提供了创建一个迭代器，从大于等于某个key开始的位置向下扫描数据的接口。

利用上述两种接口，结合设计良好的数据存储格式，Rocksdb就可以作为结构化数据存储和查询的引擎。

比如我们有如下数据表结构：

TABLE `temp` (

`id` smallint(6) NOT NULL,

`i` smallint(6) NOT NULL,

`f` float NOT NULL,

`c` char(60) NOT NULL,

`msg` char(120) DEFAULT NULL,

PRIMARY KEY (`id`),

KEY `i_index` (`i`),

KEY `f_index` (`f`),

KEY `c_index` (`c`),

KEY `i_f_index` (`i`,`f`),

KEY `i_c_f_index` (`i`,`c`,`f`)

)

一、构造主键索引

首先为每一行记录生成一条kv数据，k是temp表id字段，value是其他几个字段序列化后的二进制字节数组。序列化协议可以自定义，也可以使用protobuf协议。

因为id字段是主键索引，当查询条件是 where id = 101 或者where id in ( 101,105,108)的时候，可以根据Rocksdb的get或者mget接口，高效的获取某一条和某几条数据。

当查询条件是 where id > -100 and id < 200 这样的range查询的时候，我们可以创建一个迭代器，指向第一个大于等于-100的记录，然后向下扫描至200的记录。这个操作需要一个seek随机读和一个scan顺序读操作，也有很高的读取性能。

要支持上述的range查询，需要保证表数据在Rocksdb中，按照id字段的字节序递增存储。

如果直接将id字段的二进制位作为key存储到Rocksdb中呢？我们知道整数在计算机中时按照补码进行存储，正数最高位是0，负数最高位是1，直接存储就会造成负数存储在正数的下面，造成逻辑顺序不一致的现象。

因此只要把非负数的最高位变成1，负数的最高位变成0，就可以保证key的二进制顺序和其代表的整数的数值顺序是一致的。如下图：

就有了下面的转换函数：

var N uint16 = 0x8000

func encodeInt16(i int16) []byte {

u := uint16(i) + N

buf := make([]byte, 2)

binary.BigEndian.PutUint16(buf, u)

return buf

}

func decodeToInt16(buf []byte) (int16, error) {

if len(buf) < 2 {

return 0, fmt.Errorf("invalid buf")

}

u := binary.BigEndian.Uint16(buf)

i := int16(u - N)

return i, nil

}

主键索引采用大端法进行存储，下面介绍的各个索引也都采用大端法存储。

二、构造整数字段索引

构造完了主键字段，接下来看第一个索引 KEY `i_index` (`i`)。首先这是一个非唯一索引，因此Rocksdb的key字段，必须同时包含i字段和主键id字段，Rocksdb的value为空即可。

key的格式可以是2字节的i字段和2字节的id字段。i字段和id字段仍然按照上述的最高位取反原则进行处理。这样可以保证i_index先按照i字段排序，i字段相同的记录再按照id字段排序。

在查询 where i = 100 或者where i > -100 and i < 200的时候，都可以转换为Rocksdb的迭代器seek加scan操作。在获取了满足条件的主键id集合之后，可以从主键索引数据中，通过mget操作获取id集合的完整数据。

如果i_index是一个唯一性索引，Rocksdb的key字段只需要包含 i字段即可，value字段存储id字段。

三、构造浮点数字段索引

接下来看第二个索引KEY `f_index` (`f`) 。首先这个也是非唯一索引，构造的key中也需要包含f 字段和id字段。id字段仍然采用最高位取反的逻辑。对于f字段，因为其是一个浮点数，首先了解一下浮点数的存储格式。

我们知道浮点数的二进制格式跟整数是不同的。比如float类型，由1个bit的符号位，8个bit的指数部分，23个bit的尾数部分组成。

回顾一下 var f float =10.75 的二进制位是怎么存储的呢？

1. 把十进制小数转换成为二进制小数，整数部分10转换成二进制得到 1010，小数部分0.75转换成二进制得到0.11, 所以10.75的二进制小数表示为1010.11；

2. 对其做规格化处理，小数点向左移动3位，得到1.01011 * 2的3次方；

3. 于是，8bit的指数部分由指数值3+127=130得到，130的二进制位是10000010(加127是固有的换算逻辑)；

4. 23bit的尾数部分：因为二进制小数规格化处理之后(1.01011)，小数点之前总是1，因此只存储小数点之后的01011五个bit；

5. 最高位是符号位：正数为0；

6. 最终的二进制表示为:0  10000010   01011000000000000000000，16进制表示0x412c0000。

如果浮点数是-10.75呢，只是把最高位变成1即可。其16进制表示：0xc12c0000。

简单验证一下结果：

func print(u uint32) {

f := *(*float32)(unsafe.Pointer(&u))

fmt.Printf("%f ", f)

}

func main() {

print(0x412c0000)

print(0xc12c0000)

}

10.750000 -10.750000

Process finished with exit code 0

我们发现绝对值相同的两个浮点数，只是最高位符号位的不同而已，其余各个bit都相同。

继续分析浮点数的二进制位。由于对二进制小数做了规格化，都变成了1.xxx * 2的n次方这种格式。

1. 在8bit指数部分相同的情况下，23bit尾数越大，其浮点数值越大。例如 1.01011 *2的3次方 (十进制10.75) 大于 1.01001*2的3次方(十进制10.25), 其二进制表示也恰好满足字节序的大于关系。

2. 8bit指数部分二进制位越大的浮点数其值也越大。例如 1.000*2的3次方 (十进制8.0) 大于所有的1.xxx*2的2次方数。

有了上述两个规律：我们就能知道浮点数>0的情况，其二进制顺序就能代表其数值顺序。小于0的浮点数仅仅是最高符号位为1,其余各位跟其绝对值小数相同。

于是我们采用如下规则：

1. 大于等于0的浮点数，最高位设为1。小于0的浮点数，其最高位设置为0。这条可以保证：负数的二进制字节序都小于正数的字节序，正数的字节序满足字节序跟数值顺序一致。

2. 负数的最高位设置为0以后，对其它位进行取反。

因为负数的字节序列是原码表示，对原码进行取反即可保证字节序和数值序一致。

得到最终的转换函数：

func encodeFloat(f float32) []byte {

u := *(*uint32)(unsafe.Pointer(&f))

if f >= 0 {

u |= 0x80000000

} else {

u = ^u

}

buf := make([]byte, 4)

binary.BigEndian.PutUint32(buf, u)

return buf

}

func decodeToFloat(buf []byte) (float32, error) {

if len(buf) < 2 {

return 0, fmt.Errorf("invalid buf")

}

u := binary.BigEndian.Uint32(buf)

if u >= 0x80000000 {

u += 0x80000000

} else {

u = ^u

}

f := *(*float32)(unsafe.Pointer(&u))

return f, nil

}

因此，第二个索引KEY `f_index` (`f`) ,其写入Rocksdb的key格式，可以是4字节经过浮点处理的f字段和2字节的经过整数处理的id字段，value为空。

四、构造字符串字段索引

接下来看第三个索引 KEY `c_index` (`c`) ，也是非唯一性索引，所以key中必须包含字符串c 和id字段，value为空即可。

由于c字段是不定长的字符串，id字段直接放在其后会导致排序字段错乱。

比如下面两条索引数据：

abc 1006 (代表记录 id=1006 c=abc)

abcdefgh 1005 (代表记录 id=1005 c=abcdefgh)

可以看到，第一条索引的id=1006，其二进制由两个字节组成，会参与跟第二条索引的 de两个字符构成的二进制位的比较。1006的二进制最高位取反后大于de两个字符的二进制位，就会导致排序顺序不正确。而且字符串本身也需要一个长度字段，也会影响到整体的排序正确性。

Facebook利用Rocksdb，为mysql实现了一版存储引擎，其中创建字符串索引部分采用了以下算法。(该算法在tidb中也得到了应用)

1. 首先将字符串按照8字节为一组，分成若干组，group_num= len(str)/8 + 1。

2. 最后一组不够8字节，对其补足若干个二进制0。

3. 对每一组末尾添加一个字节，字节的值是 255减去该组填充的0字节的个数。

比如有下面几个字符串的转换示例：

[] -> [0,0,0,0,0,0,0,0,247] (空字符串)

[1,2,3] -> [1,2,3,0,0,0,0,0,250] (字符串123)

[1,2,3,0] -> [1,2,3,0,0,0,0,0,251] (字符串123\0)

[1,2,3,4,5,6,7,8]->[1,2,3,4,5,6,7,8,255,0,0,0,0,0,0,0,0,247]

(字符串12345678)

[1,2,3,4,5,6,7,8,9]->[1,2,3,4,5,6,7,8,255,9,0,0,0,0,0,0,0,248]

(字符串123456789)

这样构造完成c字段的编码字节数组，在其后接上两字节的经过最高位取反的id字段，组成一个key写入Rocksdb中即可。

简单分析一下该算法：

在两条记录的c字段字符串长度都小于8的情况下，由于都补齐了8字节，后面id字段并不会导致排序错乱。比如有下面三条index数据。

abc00000,250,1001 ( 代表记录 id=1001, c=abc )

abcdef00,253,1002 ( 代表记录 id=1002, c=abcdef )

ad000000,249,1003 ( 代表记录 id=1003, c=ad )

在一条记录的c字段小于8字节，另一条记录的c字段大于8字节的时候，比如有下面两条index数据： 

abc00000,250,1001 ( 代表记录 id=1001, c=abc )

abcdefgh,255,abc00000,250, 1004 ( 代表记录 id=1004, c=abcdefghabc)

由于c字段为abc的短字符串，其后添加了5个0，已然小于下面的长字符串，其后的字符串长度字段或id字段，再也没有机会影响短字符串跟长字符串的比较了。

五、构造联合索引

接下来我们看一个联合索引KEY `i_f_index` (`i`,`f`) ，这个是一个整数加一个浮点数。因为是非唯一索引，所以写入Rocksdb的key由两字节的i字段(最高位取反) + 4字节的f字段( 最高位取反+负数其他位也取反 ) + 2字节的主键id字段(最高位取反)，value为空即可。

最后一个联合索引 KEY `i_c_f_index` (`i`,`c`,`f`) ，key中包含四种数据类型：整数，字符串，浮点数和主键id。只需要按照上述介绍的算法，依次处理每种数据类型拼接出key即可。

六、总结

我们有了索引，就可以像mysql一样，根据索引快速定位数据。如果一个查询语句有很多个过滤条件，涉及多个索引字段，选择不同的索引进行查询，得到的性能是不一样的。因此，也需要像mysql一样根据一些统计信息构造出一个查询计划，选择合适的索引列进行查询。感兴趣的同学可以继续关注一下直方图以及Count-Min Sketch等数据结构。另外，也需要深入了解Rocksdb的get mget seek scan等操作的原理和性能，结合数据库的统计信息才能更好的构造查询计划。