在開發(fā)LedisDB的時(shí)候猿妈，我曾考慮將zset的score使用跟redis一樣的double類型拿穴，但是卻沒想好如何將double在底層LevelDB或者RocksDB下存儲(chǔ)，使其能夠支持zset中zrangebyscore等命令，所以只能考慮使用int64類型來代替稼虎。但在開發(fā)qdb的時(shí)候庐杨，最開始我們?nèi)匀恢皇侵С謎nt64选调，但最終通過努力，支持了double灵份，使其能跟redis的zset api完全兼容仁堪。其實(shí)后來發(fā)現(xiàn)，實(shí)現(xiàn)很簡(jiǎn)單填渠。
LevelDB和ZSet
這里需要簡(jiǎn)單說明一下LevelDB（RocksDB只是它的一個(gè)衍生優(yōu)化版本弦聂，但最核心基本的原理還是一樣的）。
LevelDB是一個(gè)高性能的KV存儲(chǔ)庫氛什，數(shù)據(jù)在LevelDB里面是根據(jù)key來進(jìn)行排序存儲(chǔ)的莺葫，而key和value是任意的字節(jié)數(shù)組。在外部看來枪眉，LevelDB里面的數(shù)據(jù)就是一個(gè)有序map徙融，map里面的key是順序存儲(chǔ)的，如下：
{
"key1" : "value1",
"key2" : "value2",
...
}
在redis里面瑰谜，zset是一個(gè)有序集合欺冀，每一個(gè)member都對(duì)應(yīng)一個(gè)score，member是唯一的萨脑，score則可能重復(fù)隐轩。我們可以通過score進(jìn)行很多處理，譬如獲取[score1, score2]這個(gè)區(qū)間的所有元素渤早，或者獲取某個(gè)member對(duì)應(yīng)的score再整個(gè)zset里面的rank职车。為了實(shí)現(xiàn)上面的需求，我們需要在內(nèi)部用一個(gè)有序的數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)score以及其對(duì)應(yīng)的member，redis使用skip list來進(jìn)行處理悴灵，那如何將這樣的映射關(guān)系在LevelDB里面很好的處理呢扛芽？
因?yàn)長(zhǎng)evelDB將數(shù)據(jù)是按照key順序存儲(chǔ)的，所以我們只需要將score的信息綁定到key上面积瞒，就能很容易的實(shí)現(xiàn)一個(gè)簡(jiǎn)易的skip list川尖。對(duì)于一個(gè)zset里面的member，可能在LevelDB里面實(shí)際的key結(jié)構(gòu)如下：
key:score:member
對(duì)于一個(gè)zset來說茫孔，key和member都是arbitrary bytes array叮喳，可以很方便的綁定到LevelDB的key上面，但是score可是double的缰贝，如何綁定上去參與排序呢馍悟？
LedisDB ZSet int64 score
再說double之前，先來聊聊LedisDB的做法剩晴，LedisDB使用的score是int64锣咒，對(duì)于一個(gè)int64來說，計(jì)算機(jī)內(nèi)部是使用8 bytes進(jìn)行存儲(chǔ)的赞弥，下面是例子毅整，會(huì)打印不同int64數(shù)據(jù)在小端序和大端序下8字節(jié)array十六進(jìn)制表現(xiàn)：
import "fmt"
import "math"
import "encoding/binary"
func p(a int64) {
b1 := make([]byte, 8)
b2 := make([]byte, 8)
binary.LittleEndian.PutUint64(b1, uint64(a))
binary.BigEndian.PutUint64(b2, uint64(a))
fmt.Printf("%0x\t%0x\n", b1, b2)
}
func main() {
p(0)
p(1)
p(0xFFFF0000)
p(math.MaxInt64)
p(-1)
p(-200)
p(-300)
p(math.MinInt64)
}
輸出結(jié)果如下：
0000000000000000 0000000000000000
0100000000000000 0000000000000001
0000ffff00000000 00000000ffff0000
ffffffffffffff7f 7fffffffffffffff
ffffffffffffffff ffffffffffffffff
38ffffffffffffff ffffffffffffff38
d4feffffffffffff fffffffffffffed4
0000000000000080 8000000000000000
第一列是小端序打印的結(jié)果，第二列是大端序打印的結(jié)果嗤攻。首先我們可以看到毛嫉，對(duì)于0來說，無論什么端序妇菱，都是全0承粤，對(duì)于正整數(shù)來說，我們可以看到闯团，0xFFFF0000是鐵定大于1的辛臊，但是在對(duì)應(yīng)的小端序存儲(chǔ)的bytes array里面，會(huì)發(fā)現(xiàn)如果按照字節(jié)序進(jìn)行排序0100000000000000是大于0000ffff00000000的房交，而大端序的結(jié)果0000000000000001是小于00000000ffff0000的彻舰。對(duì)于負(fù)整數(shù)也是一樣，-200是大于-300的候味，但是小端序的結(jié)果是小于刃唤，而大端序的結(jié)果是大于。
所以我們可以知道白群，對(duì)于一個(gè)整數(shù)尚胞，我們需要使用大端序的方式將其綁定到LevelDB的key上面，這樣才能參與正常的排序帜慢。但是我們又發(fā)現(xiàn)笼裳，如果直接這樣處理唯卖，負(fù)數(shù)的大端序結(jié)果是鐵定大于正數(shù)的，譬如-1的ffffffffffffffff就大于1的0000000000000001躬柬，所以為了正常的處理整數(shù)的排序拜轨，我們只需要在key上面加一個(gè)前綴標(biāo)志就可以了。LedisDB里面做了如下處理：
key<38ffffffffffffff:member
key<ffffffffffffffff:member
key=0000000000000000:member
key=0000000000000001:member
因?yàn)?code>=的ascii值大于<允青，我們將正整數(shù)和0前面加上=橄碾，將負(fù)數(shù)前面加上<，這樣在進(jìn)行字節(jié)序排序的時(shí)候昧廷，正數(shù)和0一定能排在負(fù)數(shù)的后面堪嫂，也就是完全能滿足從小到大排序的需求了偎箫。
QDB ZSet double score
上面可以知道木柬，我們使用大端序加上一個(gè)前綴標(biāo)志，就能很好的處理int64類型的score的排序淹办，但double可沒有這么簡(jiǎn)單眉枕，不然LedisDB早就支持了。
首先我們來看看double類型IEEE754規(guī)范怜森，對(duì)于一個(gè)double來說速挑，使用8 bytes存儲(chǔ)，格式如下：
- 符號(hào): 1 bit （0為正副硅，1為負(fù)）
- 指數(shù): 11 bits
- 分?jǐn)?shù): 52 bits
對(duì)于一個(gè)64 bits的double姥宝，如果指數(shù)為e，那么它對(duì)應(yīng)的值計(jì)算方式為:
如果指數(shù)越大恐疲，那么double的值越大腊满，如果分?jǐn)?shù)越大，在相同指數(shù)的情況下面double值也越大培己。所以我們?nèi)绻麑ouble使用大端序存放到8字節(jié)array里面碳蛋，我們就能直接進(jìn)行字節(jié)序比較，但這個(gè)僅限于正的double情況下省咨。因?yàn)閷?duì)于負(fù)的double肃弟，它除了最高位bit為1這一點(diǎn)不一樣之外，其余完全跟相反的正數(shù)底層存儲(chǔ)方式一模一樣零蓉，所以如果我們直接將其轉(zhuǎn)為大端序比較笤受，會(huì)發(fā)現(xiàn)結(jié)果是相反的。一個(gè)簡(jiǎn)單地例子:
func d(a float64) {
b := make([]byte, 8)
binary.BigEndian.PutUint64(b, math.Float64bits(a))
fmt.Printf("%064b\n", binary.BigEndian.Uint64(b))
}
func main() {
d(0)
d(1)
d(2)
d(-1)
d(-2)
}
結(jié)果如下：
0000000000000000000000000000000000000000000000000000000000000000
0011111111110000000000000000000000000000000000000000000000000000
0100000000000000000000000000000000000000000000000000000000000000
1011111111110000000000000000000000000000000000000000000000000000
1100000000000000000000000000000000000000000000000000000000000000
這里在插入一片廣告文章敌蜂，推薦閱讀箩兽，這里。
當(dāng)初LedisDB就是因?yàn)闆]有辦法很好的處理負(fù)double的排序比較問題紊册，才采用了int64比肄，但是真的沒有辦法嗎快耿？為啥int64類型的負(fù)數(shù)能通過大端序進(jìn)行字節(jié)序比較呢？我們知道芳绩，在計(jì)算機(jī)內(nèi)部掀亥，負(fù)數(shù)是使用補(bǔ)碼存儲(chǔ)的，也就是反碼加1妥色，負(fù)數(shù)的反碼搪花，就是在源碼的基礎(chǔ)上，符號(hào)位不變嘹害，其余各個(gè)位取反撮竿。對(duì)于-1來說，它的源碼為[10000001]笔呀，反碼為[11111110]幢踏，補(bǔ)碼為[11111111]。（為了簡(jiǎn)單许师，使用int8表示的）房蝉。就因?yàn)樗辛巳》吹倪@一步，我們才能直接用大端序字節(jié)序比較微渠。
所以對(duì)于double的負(fù)數(shù)搭幻，我們也僅僅需要干一件事情，就是取反逞盆，那么它的大端序字節(jié)序比較就是正常的了檀蹋。在QDB里面，對(duì)于一個(gè)double云芦，我們做了如下處理:
// We can not use lexicographically bytes comparison for negative and positive float directly.
// so here we will do a trick below.
func float64ToUint64(f float64) uint64 {
u := math.Float64bits(f)
if f >= 0 {
u |= 0x8000000000000000
} else {
u = ^u
}
return u
}
func uint64ToFloat64(u uint64) float64 {
if u&0x8000000000000000 > 0 {
u &= ^uint64(0x8000000000000000)
} else {
u = ^u
}
return math.Float64frombits(u)
}
如果一個(gè)double數(shù)據(jù)值大于等于0俯逾，那么我們將最高位bit設(shè)置為1，而對(duì)于負(fù)數(shù)焕数，我們直接取反纱昧，就這一步簡(jiǎn)單的操作，就能讓我們完美的支持double的score了堡赔。
總結(jié)
讓QDB的zset支持double score识脆，其實(shí)很簡(jiǎn)單的一件事情，但我在開發(fā)LedisDB的時(shí)候竟然沒有想到如何去解決善已。我們很多時(shí)候灼捂，往往追求高大上的東西，譬如架構(gòu)换团，設(shè)計(jì)模式等悉稠，但忽略了計(jì)算機(jī)最基本的底層知識(shí)（上面這些其實(shí)也就是大小端序，補(bǔ)碼艘包，反碼等）的猛，所以有時(shí)候還真的重新好好把最基本的東西給回顧一下耀盗。
最后，在推薦一下QDB卦尊，QDB是一個(gè)類似Redis的KV數(shù)據(jù)庫叛拷，底層使用LevelDB/RocksDB作為存儲(chǔ)引擎，解決了Redis內(nèi)存限制問題岂却，同時(shí)能支持string忿薇，hash，list躏哩，set和zset這幾種數(shù)據(jù)結(jié)構(gòu)署浩，性能卓越，你也可以認(rèn)為它是LedisDB的升級(jí)版本扫尺。
網(wǎng)址 https://github.com/reborndb/qdb筋栋。
