ledisDB底层实现

2022-04-18 00:00:00 遍历 获取 存放 将其 则是

Hash

hash可以算是一种两级kv,首先通过key找到一个hash对象,然后再通过field找到或者设置相应的值。 在ledisdb里面,我们需要将key跟field关联成一个key,用来存放或者获取对应的值,也就是key:field这种格式。 这样我们就将两级的kv获取转换成了一次kv操作。 另外,对于hash来说,(后面的list以及zset也一样),我们需要快速的知道它的size,所以我们需要在leveldb里面用另一个key来实时的记录该hash的size。 hash还必须提供keys,values等遍历操作,因为leveldb里面的key默认是按照内存字节升序进行排列的,所以我们只需要找到该hash在leveldb里面的小key以及大key,就可以轻松的遍历出来。在前面我们看到,我们采用的是key:field的方式来存入leveldb的,那么对于该hash来说,它的小key就是"key:",而大key则是"key;",所以该hash的field一定在"(key:, key;)"这个区间范围。至于为什么是“;”,因为它比":"大1。所以"key:field"一定小于"key;"。后续zset的遍历也采用的是该种方式,就不在说明了。

List

list只支持从两端push,pop数据,而不支持中间的insert,这样主要是为了简单。我们使用key:sequence的方式来存放list实际的值。 sequence是一个int整形,一个list多存放1<<31 - 2000条数据,至于为啥是1000,我说随便定得你信不? 对于一个list来说,我们会记录head seq以及tail seq,用来获取当前list开头和结尾的数据。 当次push一个list的时候,我们将head seq以及tail seq都设置为listInitialSeq。当lpush一个value的时候,我们会获取当前的head seq,然后将其减1,新得到的head seq存放对应的value。而对于rpush,则是tail seq + 1。 当lpop的时候,我们会获取当前的head seq,然后将其加1,同时删除以前head seq对应的值。而对于rpop,则是tail seq - 1。 我们在list里面一个meta key来存放该list对应的head seq,tail seq以及size信息。

ZSet

zset可以算是为复杂的,我们需要使用三套key来实现。需要用一个key来存储zset的size,需要用一个key:member来存储对应的score,需要用一个key:score:member来实现按照score的排序。

这里重点说一下score,在redis里面,score是一个double类型的,但是我们决定在ledisdb里面只使用int64类型,原因一是double还是有浮点精度问题,在不同机器上面可能会有误差(没准是我想多了),另一个则是我不确定double的8字节memcmp是不是也跟实际比较结果一样(没准也是我想多了),其实更可能的原因在于我们觉得int64就够用了,实际上我们项目也只使用了int的score。 因为score是int64的,我们需要将其转成大端序存储(好吧,我假设大家都是小端序的机器),这样通过memcmp比较才会有正确的结果。同时int64有正负的区别,负数高位为1,所以如果只是单纯的进行binary比较,那么负数一定比正数大,这个我们通过在构建key的时候负数前面加"<",而正数(包括0)加"="来解决。所以我们score这套key的格式就是这样: key<score:member //<0key=score:member //>=0 对于zset的range处理,其实就是确定某一个区间之后通过leveldb iterator进行遍历获取,这里我们需要明确知道的事情是leveldb的iterator正向遍历的速度和逆向遍历的速度完全不在一个数量级上面,正向遍历快太多了,所以好别去使用zset里面带有rev前缀的函数。

总结

总的来说,用leveldb来实现redis那些的数据结构还算是比较简单的,同时根据我们的压力测试,发现性能还能接受,除了zset的rev相关函数,其余的都能够跟redis保持在同一个数量级上面,具体可以参考ledisdb里面的性能测试报告以及运行ledis-benchmark自己测试。 后续ledisdb还会持续进行性能优化,同时提供expire以及replication功能的支持,预计6月份我们就会实现。 ledisdb的代码在这里https://github.com/siddontang/ledisdb,希望感兴趣的童鞋共同参与。

 

摘自:http://www.itkeyword.com/doc/0652992288452803948

 

相关文章