基于RocksDB实现Sorted Set的思路
现在各大公司都在基于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通常形如
通过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类型的存储结构是
解析公式为
可以简单证明（不考虑二进制表示的符号）
- 在正数域上，若实数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），让所有负数的二进制小于正数。
第二步，因为正数顺序对了，但是负数单调性是反的，那么我们只需要把负数除了符号位的其他位全部反转，单调性就反过来了。
|
1 2 3 4 5 6 7 8 9 10 11 |
// 不保证编译得过= =| // 转换成存储格式 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（这个在分布式系统中可能会有坑的，比如同步的时候）。
hbase转化成用户表示写反了吧？