基于RocksDB实现Sorted Set的思路

22. 三月 2020 分布式, 数据库 0

现在各大公司都在基于RocksDB实现自家的分布式存储引擎,RocksDB基于LSM模型,灵活性和性能都非常高,而且有持久化能力,通常被设计用来作为纯内存缓存如Redis、Codis的替代品(缓存路线),甚至某些场景下MySQL的替代品(NewSQL路线)。通常来说都是先成为一个分布式缓存产品,替换掉Redis等,然后再发展成为一个NewSQL产品替代MySQL,路线选择有多方面的原因这里就先不讨论了。

既然用RocksDB做通用存储,那就躲不开协议的问题,产品都是拿来给业务用的,为了尽可能低降低业务迁移成本,通常都会兼容Redis、MySQL协议。

Sorted Set(ZSet)是Redis中的一个数据结构,简单讲就是一个weighted set,支持按权重、排名进行顺(倒)序扫描,同时又支持Set的增删改查操作。如何在设计这种存储结构呢。

存储结构

通常类似Hash、List、Set、ZSet这种类型都,因为要存储一些元信息(如size、version),需要使用Meta+Data一组KV来实现。

Meta通常形如

长得有点像pika的nemo引擎了

通过MetaSymbol避免与其他Data KV冲突,Version是一个递增的值,在ZSet被创建时生成,Version和TTL也可以存储在value中,像pika的blackwidow引擎那样。这个东西在哪对于Meta没有太大影响,对Data会有点影响,后面聊。

Data通常有两组KV,因为ZSet需要支持lexical、score两种排序,通常形如

这样lexical和score的顺序扫描就就可以通过分别scan两种Data来实现了。

Score的映射

Redis的ZSet中的score是double类型的,且支持”+inf”、”-inf”,根据IEEE 754标准,double类型的存储结构是

IEEE 754 Double Floating Point Format.svg
图片来自Wikipedia

解析公式为

可以简单证明(不考虑二进制表示的符号)

  • 在正数域上,若实数a>b,那么a的二进制表示也是大于b的。
  • 在负数域上,若实数a>b,那么a的二进制表示小于b。
  • 对于任意负数a,正数b,那么a的二进制表示大于b。

所以在整个double表示的实数区间里,他们的函数图像是分段的,并不保序。这样是不能直接存储在Key中的(因为RocksDB默认按Key的字典序排序),需要做一下转换。

Naive方案

都转换成正数,这样就保序了,最简单,但是有丢失精度的风险,需要

  • 限定用户输入的实数实数精度(可以乘10^n将小数挪到整数位)
  • 限定用户输入的实数范围(否则保存小数的时候可能乘爆)

Blackwidow方案

Blackwidow引擎将两个data分别放在不同的Column Family中,然后针对按score排序的data实现了RocksDB Comparator,直接按double比较大小。

这种方法有除了看起来最直观,对性能也有一定好处,比如:meta单独一个CF检索性能会由于混合存储;meta不需要在key中保存前缀区分类型等。但是每个类型都开一个CF可能会对引擎开发有其他设计上的影响。

完美方案

参考 HBase编码方案

前面我们分析过负数与他的二进制表示单调性相反,实数与他的二进制表示单调性相同,那么有没有办法让负数的单调性反转一下呢?有。

第一步我们把所有负数的符号位反转一下(xor 1),让所有负数的二进制小于正数。

第二步,因为正数顺序对了,但是负数单调性是反的,那么我们只需要把负数除了符号位的其他位全部反转,单调性就反过来了。

// 不保证编译得过= =|
// 转换成存储格式
double user_score = 123.456;
const void* ptr = reinterpret_cast<const void*>(&user_score);
uint64_t internal_score = *reinterpret_cast<const uint64_t*>(ptr);
internal_score ^=  (internal_score & 0x8000000000000000) ? 0xFFFFFFFFFFFFFFFF : 0x8000000000000000;

// 转换成用户表示
uint64_t internal_score = 0x82BC000000000001;
internal_score ^= (internal_score & 0x8000000000000000 ? 0xFFFFFFFFFFFFFFFF : 0x8000000000000000;
const void* ptr = reinterpret_cast<const void*>(&internal_score);
double user_score = *reinterpret_cast<const double*>(ptr);

Version和TTL

我们既可以跟userKey拼在一起放在Key里,也可以放在Value里,他们区别就在于:如果在Key里,那么通过一个userKey获取Meta的时候(或者获取Data的时候),要用Seek的方式;但是如果这些东西在Value里,那么Key其实就是确定的了,可以使用Get直接获取。

TTL字段在Data中可存可不存,这取决于compaction如何实现。如果不存,那么compaction就完全依赖Meta;如果存了,意味着Meta和Data需要分别进行Compaction(这个在分布式系统中可能会有坑的,比如同步的时候)。

全部参考资料


发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据