ssdb源码阅读之数据结构

大家好，这里是tiankonguse的公众号(tiankonguse-code)。
tiankonguse曾是一名ACMer，现在是鹅厂视频部门的后台开发。
这里主要记录算法，数学，计算机技术等好玩的东西。

这篇文章从公众号tiankonguse-code自动同步过来。
如果转载请加上署名：公众号tiankonguse-code，并附上公众号二维码，谢谢。

零、背景

之前在《荒蛮时代诞生的union服务》中介绍过，我负责一个批量拉数据的KV服务。
这个服务上层有共享内存式的缓存，底层支持各种数据源回源，其中80%的回源都是拉取视频数据，而视频数据中80%资料都储存在一个REDIS中。
现在面临的问题是回源的储存需要储存全量数据，而这个数据量越来越大了，基于全内存设计的REDIS支持不住了，我们需要切换到基于硬盘设计的ssdb上去。

这里涉及两个名词提前介绍下：KEY和FIELD。
KEY代表一个资料的主键，FIELD对应各种资料的名称，如标题、简介、导演等，具体细节阅读《荒蛮时代诞生的union服务》来辅助理解。

切换前，对REDIS的QPS评估是KEY级别的，即不关心拉取多少资料。而切换到SSDB后，发现SSDB的QPS翻了好多倍，原来SSDB所有命令都是基于kv来实现的。
为了充分了解SSDB的潜在风险，这个周末花了一些时间阅读了SSDB的源码，这里记录一下SSDB是怎么基于kv实现所有REDIS命令的。

一、全局介绍

ssdb在github上有源码，搜索ssdb一般第一个就是对应的介绍。
从目录结构上可以看出来，项目代码分6大部分：客户端模块、网络模块、ssdb模块、util模块、整体模块以及第三方库模块。

这里重点关注的是ssdb对REDIS各种命令的实现，所以就不关注客户端模块和第三方库模块，而只关注ssdb服务相关的模块了。

从线程方面看来，ssdb分了几大模块：网络处理主线程，单写线程，读线程池，过期处理线程等。

主线程用于接受客户端的请求。收到请求后根据命令路由到写线程或者读线程队列中，当命令被对应线程真实处理后，对应的线程给业务回包。
而对于key过期逻辑的实现，由单独一个线程实现，下面讲过期的实现时会提到。

二、实现方式

上面提到过，ssdb使用KV的方式把REDIS的各种复杂数据结构都实现了一遍。
那我们自然就会有个疑问：怎么实现呢？性能怎么样呢？
下面我们就分别来看看吧。

三、redis kv结构

redis的kv是一种最普通的数据结构了。
所有的nosql只支持这种数据结构。

由于ssdb的key是拼接出来了，为了防止和业务的key冲突，这里需要制定一个特殊的规则来避免冲突。
这个规则就是经典的tlv(type-length-value)规则，当然ssdb为了节省内容，在不发生冲突的时候，会使用tv(type-value)规则。

比如REDIS有一个KV，key是hello，value时word。
则ssdb的key储存为 khello，value是word。
其中前面的k就是为kv数据结构加的前缀，ssdb为每种数据结构定义了唯一的前缀。

四、redis hash结构

如果使用redis储存业务资料的话，更多使用的是hash结构，因为我们一个key往往有很多资料。
比如对于视频，资料有标题title，简介desc，状态state等等，使用hash再合适不过了。

那对于视频Id是123的视频，我们在ssdb是如何储存这些资料呢？
依旧使用上面提到的tlv规则，就可以拼出三个key来：h{3}123=title，h{3}123=desc，h{3}123=state。
h代表hash的前缀type，{3}代表key的长度，这里是字符值为3，固定一字节，而不是数字3。
接着是key的字符串，然后是=连接符，最后是字段名。

hash有几个命令是获取hash下的所有字段，这个该如何实现呢？
这个需要ssdb的kv满足一个特性：实际储存的kv需要满足字典序有序，这时我们就可以像二分查找一下，快速找到指定区间的值了。
对于数字是二分查找，对于字符串，自然就是字典树查找了。所以这里复杂度是n*log(m)级别的，还可以接受。

对于hash，有另外一个命令hlen，含义是hash内字段的个数。
如果按照上面的字典树方法来查找，复杂度虽然可以接受，但是耦合度就比较高了。
比如字典树的节点上储存了当前字数的节点数，查询依旧是log(m)的，但是对储存是第三方kv库，并不是所有的第三方库支持这一特性的。
所以ssdb的实现方式是单独开一个新key来储存hash的个数，这样复杂发依旧是log(m)，而耦合性瞬间没有了。
key的格式是:H123。

五、redis zset结构

redis的zset结构是一种很强大的数据结构，名字叫做有序集合。
zset和hash很类似，不过hash里面field的值变成了zset里面的权重或者评分。
有了评分，就涉及基于评分的排序了。

zset内部会维护field的值以及评分的排序，很多排行榜都是基于zset实现的。

这里以学习的成绩排名为例吧，假设有个数学比赛，3个同学进行竞争，并得到了优异的成绩，现在我们需要对其储存以及查询。
数学比赛就是zset的key, 使用math代替。3位同学的名称和成绩分别是 a:100，b:50,，c:-90。

对于field到评分值得关系，实现方式和hash类似：s{4}math{1}a，s{4}math{1}b，s{4}math{1}c。
而对于分数到字段的关系，则是：z{4}math={100}=a，z{4}math={50}=b，z{4}math-{90}=c。
对于zset字段的个数，则是：Zmath

这里有两个有人会吐槽。
第一点是zset field到评分的key为什么都是lv了，之前不是等号分割吗？这里换一种方式就显得不和谐和优美了。是的，我也觉得这里不优美，但是他就是这样实现的。
第二点是分数到字段的关系中，正数的符号是=，负数的符号是-，看起来也不协调不优美。这个就没办法了，谁让计算机中+小于-呢？

不管怎样，这里复杂度还不错，更新都是log级别的。
当然这里对score有限制，必须是整数，而redis支持浮点数的。

六、redis list结构

对于list，如果在内存中使用链表实现的话，就会很简单。
如果使用kv的方式实现列表，我们如何实现呢？

这里先来看看简单的命令，即把list当做双向队列来看待。

双向队列一般是只能从头部和尾部出入数据，不能从中间出入数据。
如果我们给头部的数据一个递增编号，尾部的数据给一个递减的编号，则列队中的编号一定是连续递增的。
根据这个结论，我们就可以使用kv的方式简单实现list了。

首先需要两个kv分别来储存首部和尾部的编号分配到哪里了：q{namesize}name{minseqflag}，q{namesize}name{minseqflag}。
minseqflag和minseqflag是两个约定好的固定值，对应的value就是实际的边界编号。
业务数据的key格式是: q{namesize}name{seq}
而对于列表的大小，通用使用一个单独key储存：Q{name}。

对于lpush或者rpush时，我们先计算对应的seq，同时写入数据然后更新seq即可。
对于lpop或者rpop时，我们计算出对应的seq，同时删除数据然后更新seq即可。
对于lindex和lset操作，含义是取出或设置对应下标位置的列表值，这里也可以计算出对应的seq，然后得到对应值或者设置值。

REDIS的有一些操作比较反人类，比如linsert和lrem操作。
lrem含义为删除某些指定元素，linsert含义是在某些位置插入一些元素。
这两个操作不符合队列的定义，一旦操作后，seq就不满足连续的特征，所以ssdb不支持这个操作。
假设非要实现这要一个操作，那操作后就需要重新调整整个队列，使其seq保持连续，那复杂度就是O(n*log(m))了。

七、过期时间

ssdb底层使用的是第三方kv库，ssdb在上面做了逻辑(多个key代表一个数据结构)，所以过期这个功能也需要自己实现。
上面可以看到，除了redis kv结构外，其他redis数据结构都使用了多个kv来标识。所以这里只有redis kv可以简单的实现过期时间，如果其他数据结构也实现kv的话，淘汰数据的复杂度就会偏高了。

我们先来看看redis kv怎么实现过期时间吧，然后再讨论下其他数据结构实现过期实现的话代价是什么。

ssdb把所有设置过期时间的key放在一个固定的zset下面，zset的字段就是设置过期时间的key，而字段的score值就是过期的毫秒时间点。

zset有一个功能：根据score排序。
所以ssdb开了一个线程，不断的从zset里面取出一些score最小的数据，检查是否过期。
过期了就删除对应的redis kv，同时也从zset里面删除。

假设要给redis hash实现过期时间，这里删除的复杂度n*log(m)了，n代表删除的字段个数，m代表ssdb总kv的个数。
如果非要实现redis其他数据结构的过期时间的话，还有一个问题：ssdb协议与redis协议不兼容。

为什么呢？ 因为ssdb为不同数据结构增加了不同的前缀。也就是不同数据结构可以有相同的key。
而这在redis里面是不允许的。
所以为ssdb设置过期时间时，需要明确指定为哪个数据结构设置过期时间。

如果这个删除的时间复杂度能够接受，也能够接受这个ssdb专用协议，那ssdb支持这些功能也是可以得了。

八、结语

好了，ssdb的数据结构终于写完了。