redis数据结构转kv存储

发表于 分类于

目的

类似kvrocks这类的以磁盘ssd作为底层冷数据，并且存储引擎（如rocksdb）只支持kv的场景，又需要支持redis协议，提供五类数据模型，即string、hash、set、zset、list。那么必须找到一种高效的方式将此类数据结构转化到kv存储中，并利用底层存储引擎的gc能力（如rocksdb的compaction）来过滤旧数据。

在快手，有多种此类数据库，如以本地rocksdb为存储引擎的，靠主从同步和数据分片的容量型存储kiwi，以及使用分布式存储底座的kwaikv两种数据库，本文用于学习与记录其具体实现思路。

实际上跟kvrocks区别不大，新版本的kvrocks看上去已经更加先进了

为了方便理解，以下过程均以rocksdb为例来讨论，其实hash存储引擎也可以。

总览

gc过程

像rocksdb的gc的接口，会告诉你当前key和value的值。当前的key设计都是有某种格式，可以取出key的类型，如是string还是hash元数据或是hash子field的数据等等，对于非string的数据的key还会记录本key的版本号，过期时间等，通过以上信息来做gc处理.

key排序

对于rocksdb，其在level1之后的sst中会按key直接排序，为了让hashtag一致的key尽量放在一起，便于前缀搜索（删除）等能力，所以的redis请求的key都会处理为

1
2
3
+---------+-----+
| hashtag | key |
+---------+-----+

string类型

写过程（set）

转换后整体key结构如下：

1
2
3
+-----+--------------------+
| key | type(如String是'S') |
+-----+--------------------+

即找出hashtag，将key转换为hashtag+key+类型号，而value使用pb来表达

1
2
3
4
5
6
message StringValue {
    uint64 expire_at      = 1; //过期时间
    bytes  user_value     = 2; //实际的值
    uint64 user_value_len = 3; //值长度
    uint64 seq            = 4; //数据版本，每次修改后单调递增
}

其中seq是单调递增的，比如使用hlc时钟的值来做。

那么set过程很简单，就将以上键值直接调存储引擎的kv存储写进去即可。对于rocksdb，它后续会自己gc掉旧值。

读过程(get)

同样直接get就行。只不过get完之后，多判断一个是否过期，若过期，直接返回nil。

gc过程

过程很简单，gc时取出值，pb解码，获取过期时间，判断是否过期来决定是否gc。

hash类型

元数据结构

会将整个hash结构，分为元数据以及实际field两种kv存储。

其元数据的key结构如下，其中用''包括的就是实际字符，表示一种标识而已

1
2
3
4

+-----+-----+-----+----------+-----+
| key | 'H' | '_' | key_size | 'H' |
+-----+-----+-----+----------+-----+

可以看到有一个key_size。倒数第一位的’H’表示该为hash结构的key。

元数据的value表示为pb如下

1
2
3
4
5
6
7
8
9
message HashMetadata {
    uint64 version             = 1; //sub key版本，用于异步删除
    uint64 expire_at           = 2;
    uint32 count               = 3;
    uint32 slot_num            = 4;
    repeated bytes user_fields = 9;
    bytes data                 = 10; // inline data
    uint64 seq                 = 11; // 数据版本
}

这里对pb一些字段重点解释一下：

  • bytes data如果有值，表示元数据和实际的全部数据放在了一起存储，对于超大hash结构而言，这是不可接受的。所以也提供配置可以让两者分开成kv存储。
  • slot_num，理解为hash字段所有的field的分片数。如果该值不设置。那么每一个hash的field都会作为一个kv存储到底层引擎中。如果该值设置了，假如为10，那么底层存储最多，该hash的key对应的field只会有10个kv存储，因此可以理解为将多个field聚合在了一起，减少访问底层存储的次数，但同样的缺点是无法控制每个slot的对应field数量的大小，最终可能会变得非常大。
  • version，递增的版本号，可以用hlc时钟。实际表示一种存在的先后顺序，只要hash这个key创建了，在删除之前该字段都不会改变。直到删除再创建。
  • count, field的数量
  • user_fields,存储所有field的键，这个实际作为一种优化，作为field数量少时，能快速判断某些键是否存在。当field数量太大时该值会被置为空，走正常逻辑。
  • seq，表示真正的读写版本号，每次进行hash的写操作，该值递增。同样可以使用hlc时钟。

    seq实际上没什么用，用来数据库看信息的而已

field数据结构

key结构如下

1
2
3
4
+-----+-----+-----+--------------+-----+-----------------+-------+----------+-----+
| key | 'H' | '_' | meta:version | '_' | 'F'(hash-field) | field | key_size | 'H' |
+-----+-----+-----+--------------+-----+-----------------+-------+----------+-----+

  • ‘F’表示该为hash的field
  • key_size不是field这个长度，而是hash-key长度
  • 注意里面包含了元数据版本号

value没有特殊结构，直接采用的原value的string值。

写过程(hmset)

以下不解释以上数据结构对应的优化路径，如slot_num、user_fields、bytes_data等等，用正常的路径解释全过程。

所有的写操作都聚合成一个原子操作write_batch，底层存储引擎保证了同时成功或同时失败。

以命令举例：hmset key filed1 1 filed 2

  1. 获取key对应的meta元数据信息，若没有，则创建一个。若原来存在，查询field1和field2的值，如果原来该值若不存在，往底层存储新增该值。
  2. 根据第一步得到的新增field数量，更新meta元数据的count值，后续也需要返回新增field的数量给用户
  3. meta的seq增加，最终写入新的元数据

读过程(hget)

  1. 获取meta信息，主要是获取version，来拼接field的对应key前缀
  2. 直接get对应field的值即可

meta的version太老了（还未gc），或者过期了，代码会表现为获取不到meta信息，则可以直接返回get不到对应的field的值

gc过程

对于meta数据kv，只需要检查是否过期，或者其count数量是否为0即可。如果满足以上，那么可以直接gc掉。

对于field数据,回查meta版本信息，如果meta版本大于当前field版本，或者meta已经过期了，都可以gc。

实际回查meta太重了，因此用了一个缓存存了起来，缓存1秒钟更新一次，防止短期compaction产生大量回查db的操作。

set类型

和hash类型几乎一模一样，只有value为空的区别。

list类型

元数据结构

key的结构和hash基本一致

1
2
3
4

+-----+-----+-----+----------+-----+
| key | 'L' | '_' | key_size | 'L' |
+-----+-----+-----+----------+-----+

value的pb结构如下

1
2
3
4
5
6
7
8
message ListMetadata {
    uint64 version     = 1;
    uint64 expire_at   = 2;
    uint32 count       = 3;
    uint64 left_index  = 4;
    uint64 right_index = 5;
    uint64 seq         = 6;
}

注意，meta值初始化时，left_index并非为0，right_idx（开区间）并非为1，具体实现是取了uint64的最大值的一半，从而可以往两边扩容。即lpush时能减少left_index，rpush时增加right_index。

field数据结构

key结构如下，其实和hash差不多，field换成了当前item所在的index而已

1
2
3
4
+-----+-----+-----+--------------+-----+-----------------+-------+----------+-----+
| key | 'L' | '_' | meta:version | '_' | 'I'(list-field) | index | key_size | 'L' |
+-----+-----+-----+--------------+-----+-----------------+-------+----------+-----+

value值就是list这个item的值

写过程(lpush与lpop)

lpush如下：

  1. 查meta
  2. 改meta，即lpush改left_index，count=count+1等
  3. 写具体item的kv值。

lpop如下：

  1. 查meta，获得left_index，其+1则为当前最左边的key的index
  2. db->Get()获取对应的key，然后db->Delete()

读过程(lrange)

  1. 查meta，得到left_index和right_index，通过和lrange传入的start与end计算实际底层存储key对于的index范围
  2. 获取upper_bound位置（查找右边界对应的key）对应的底层db迭代器，然后一路向左扫
  3. 扫的时候检查所以key的前缀是否满足对应格式(key+'L'+meta:version等等)，满足则加入返回数组中，一直扫到足够的数据为止。

    rocksdb会用类似于归并的方法，level0多个sst+level1->level10多路扫描。

以上还有一个注意点，扫的过程应该是快照扫，否则扫到非预期的结果，比如扫着扫着，compaction给gc掉了。所以严格来说需要上层给key加锁，要不就确保快照读(rocksdb快照读其实也跟gc冲突，无解)，不能改其meta数据。

一种做法是，gc时在版本校验的基础上，增加时间检查，不准gc 30分钟内的旧版本数据。（version实际是hlc时钟）

gc过程

跟hash一模一样。

zset类型

元数据结构

key的结构和hash基本一致

1
2
3
4

+-----+-----+-----+----------+-----+
| key | 'Z' | '_' | key_size | 'Z' |
+-----+-----+-----+----------+-----+

value的pb结构如下

1
2
3
4
5
6
message ZSetMetadata {
    uint64 version     = 1;
    uint64 expire_at   = 2;
    uint32 count       = 3;
    uint64 seq         = 4;`
}

field数据结构

有两种field，即一个field会在rocksdb中有两种kv同时存在

只有member

：

key结构如下，其实和hash差不多，field换成了当前member的名字而已(非score)

1
2
3
4
+-----+-----+-----+--------------+-----+------------------+-------+----------+-----+
| key | 'Z' | '_' | meta:version | '_' | 'M'(zset-member) | member | key_size | 'Z' |
+-----+-----+-----+--------------+-----+------------------+-------+----------+-----+

value值就是这个member的score值

member和score都有

1
2
3
4
+-----+-----+-----+--------------+-----+------------------------+-------+--------+----------+-----+
| key | 'Z' | '_' | meta:version | '_' | 'S'(zset-score-member) | score | member | key_size | 'Z' |
+-----+-----+-----+--------------+-----+------------------------+-------+--------+----------+-----+

之所以score放前面，是利用了rocksdb的排序能力，score是特殊处理的一种uint64格式，可以让rocksdb直接按大于排序

value值为空

写过程(zadd)

如zdd key score1 member1 score2 member2

过程如下，注意若第2步查member不存在，那么直接跳到第3步：

  1. 查元数据，得到version
  2. 查member1的只带member的field的值，得到old-score，如果和新插入的score相等直接返回，如果不相等，记录删除命令->带member和旧score的field。
  3. 往db中put更新只带member的field对应的新值，同时也put，member和score都有的field的新值。
    å
    若是zrem，直接删除两个field即可。

读过程(zrangebyscore)

如zrangebyscore key 200 221 withscores

  1. 查元数据，得到version
  2. 获取db的迭代器，将其seek定位到最低分数200处，即定位到如下，注意member直接为空，因为rocksdb会保证按前缀排序，因此大于200分数的，必定在其右侧。
    1
    2
    3
    4
    +-----+-----+-----+--------------+-----+------------------------+-------+--------+----------+-----+
    | key | 'Z' | '_' | meta:version | '_' | 'S'(zset-score-member) | 200 | "" | key_size | 'Z' |
    +-----+-----+-----+--------------+-----+------------------------+-------+--------+----------+-----+

  3. 将迭代器调用Next(),逐步获取后面的key，校验其key格式是否满足以上前缀，若满足，取出score值，判断分熟是否在range范围内，如果在，直接添加到返回列表即可

注：zrange（非byscore）的实现比redis差很多，迭代器会从头扫到尾，直到满足返回数量，没法用二分查找定位到start_index的位置。

gc过程

跟hash一模一样。