基于 RocksDB 的索引数据存储

2019-05-14 11:23:53 文/58架构师 作者/ 李延朋 存储

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

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

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

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

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

一、构造主键索引

首先为每一行记录生成一条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的二进制顺序和其代表的整数的数值顺序是一致的。如下图:

就有了下面的转换函数:

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

二、构造整数字段索引

构造完了主键字段,接下来看第一个索引 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 的二进制位是怎么存储的呢?

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

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

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

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

最高位是符号位:正数为0;

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

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

简单验证一下结果:

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

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

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

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

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

于是我们采用如下规则:

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

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

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

得到最终的转换函数:

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

四、构造字符串字段索引

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

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

比如下面两条索引数据:

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

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

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

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

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

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

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

简单分析一下该算法:

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

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

由于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等操作的原理和性能,结合数据库的统计信息才能更好的构造查询计划。

免责声明:凡注明为其它来源的信息均转自其它平台,由网友自主投稿和发布、编辑整理上传,对此类作品本站仅提供交流平台,不为其版权负责。本网站对有关资料所引致的错误、不确或遗漏,概不负任何法律责任。如果您发现网站上有侵犯您的知识产权的作品,请与我们取得联系,我们会及时修改或删除。联系邮箱:leixiao@infoobs.com