Redis与KV存储(RocksDB)融合之编码方式

简介

Redis 是目前 NoSQL 领域的当红炸子鸡，它象一把瑞士军刀，小巧、锋利、实用，特别适合解决一些使用传统关系数据库难以解决的问题。Redis 作为内存数据库,所有的数据全部都存在内存中，特别适合处理少量的热数据。当有巨量数据超过内存大小需要落盘保存时，就需要使用 Redis + KV存储的方案了。

本文涉及的Ardb就是一个完全兼容Redis协议的NoSQL的存储服务。其存储基于现有成熟的KV存储引擎实现，理论上任何类似B-Tree/LSM Tree实现的KV存储实现均可作为Ardb的底层存储实现，目前Ardb支持LevelDB/RocksDB/LMDB.

本文以Ardb为例，介绍Redis与KV存储之间融合时编解码层的实现。

编码方式

Redis与KV存储的融合方案中， 编解码层是一个很重要的环节。通过编解码层，我们可以屏蔽了各种kv存储实现的不同，可以在任意一个简单的kv存储引擎上，封装实现Redis中string，hash，list，set，sorted set等复杂类型的数据结构。

对于String类型，很显然可以与KV存储中的一个KV对一一对应;

对于其它的容器类型，我们需要

• 一个KV来存储其整个Key的元信息（比如List的成员个数，过期时间等）；
• 每一个成员需要一个KV来保存成员的名称和值；

对于sorted set，其每个成员有score和rank两个属性，所以需要：

• 一个KV保存整个Key的元信息
• 每一个成员需要一个KV保存 score信息
• 每一个成员需要一个KV保存每个成员对应 rank 信息

Key的编码格式

对于所有的Key， 包含同样的前缀，编码格式定义如下：

[<namespace>] <key> <type> <element...>

namespace用于支持类似redis中的库概念, 可以为任意字符串, 不限制必须为数字;
key则是一个变长二进制字符串
type用于定义一个简单key-value的类型，此类型隐含表明key的数据结构类型;一个字节
meta信息的key中type固定为KEY_META；具体类型将在value中定义（参考下一节）
除以上三部分外，不同类型的key可能有附加字段；如Hash的key可能需要附加field字段

Value的编码格式

内部Value则比较复杂，编码均以type开始， type取值即上节定义的KeyType

<type> <element...>

后续格式根据各种类型定义不同.

各类型数据编码方式

各类型数据的编码方式如下: ns代表namespace

            KeyObject                             ValueObject
String      [<ns>] <key> KEY_META                 KEY_STRING <MetaObject>
Hash        [<ns>] <key> KEY_META                 KEY_HASH <MetaObject>
            [<ns>] <key> KEY_HASH_FIELD <field>   KEY_HASH_FIELD <field-value>
Set         [<ns>] <key> KEY_META                 KEY_SET <MetaObject>
            [<ns>] <key> KEY_SET_MEMBER <member>  KEY_SET_MEMBER
List        [<ns>] <key> KEY_META                 KEY_LIST <MetaObject>
            [<ns>] <key> KEY_LIST_ELEMENT <index> KEY_LIST_ELEMENT <element-value>
Sorted Set  [<ns>] <key> KEY_META                 KEY_ZSET <MetaObject>
            [<ns>] <key> KEY_ZSET_SCORE <member>  KEY_ZSET_SCORE <score>
            [<ns>] <key> KEY_ZSET_SORT <score> <member> KEY_ZSET_SORT

ZSet编码实例

这里以最复杂的Sorted Set来做实例。假设有个Sorted Set为 A: {member=frist, score=1}, {member=second, score=2}。其在Ardb中的存储方式如下：
Key A的存储编码为：

// 伪代码中的|代表域的分割，不代表实际存储为"|"。实际序列化的时候每个域是按照特定位置序列化的.
键为：ns|1|A(1代表是KEY_META元信息类型) 
值为：元信息编码（redis数据类型/zset，过期时间，成员个数，最大最小score等）

成员first的score信息存储编码为:

键为：ns|11|A|first (11代表类型为KEY_ZSET_SCORE)
值为：11|1 (11代表类型KEY_ZSET_SCORE，1为该成员first的score）

成员first的rank信息存储编码为:

键为：ns|10|A|1|first (10代表类型为KEY_ZSET_SORT, 1为score)
值为：10 (代表类型KEY_ZSET_SORT，无意义。rocksdb中自动按key大小排序，所以很容易算出rank，不需要存储和更新）

成员second的score信息存储编码略。
当用户使用zcard A命令时，直接访问namespace_1_A即可得到元信息中该有序集合的数目;
当用户使用zscore A first时，直接访问namespace_A_first即可得到first成员的score;
当用户使用zrank A first时，先用zscore得到score,再查找namespace_10_A_1_first的序号；

具体的存储方式代码如下:

KeyObject meta_key(ctx.ns, KEY_META, key);
ValueObject meta_value;
for (each_member) {
  // KEY_ZSET_SORT 存储rank信息
  KeyObject zsort(ctx.ns, KEY_ZSET_SORT, key);
  zsort.SetZSetMember(str);
  zsort.SetZSetScore(score);
  ValueObject zsort_value;
  zsort_value.SetType(KEY_ZSET_SORT);
  GetDBWriter().Put(ctx, zsort, zsort_value); 
  
  // 存储score信息
  KeyObject zscore(ctx.ns, KEY_ZSET_SCORE, key);
  zscore.SetZSetMember(str);
  ValueObject zscore_value;
  zscore_value.SetType(KEY_ZSET_SCORE);
  zscore_value.SetZSetScore(score);
  GetDBWriter().Put(ctx, zscore, zscore_value);
}
if (expiretime > 0)
{
    meta_value.SetTTL(expiretime);
}
// 元信息
GetDBWriter().Put(ctx, meta_key, meta_value);

Del的实现

所有的数据结构都有保存meta的一个key-value，而meta信息的key编码格式是统一的，因此不可能出现不同数据结构有相同名字的情况。（这就是为什么保存Key的KV对中，K固定为KEY_META类型，而对应redis类型信息存在META类型数据的Value中的原因）。
Del实现中会先查询meta的key-value，得到具体数据结构类型，然后执行对应的删除工作， 类似如下的步骤：

• 查询指定key的meta信息，得到数据结构类型
• 根据具体类型，执行删除工作
• 所以一次del至少需要 一次读 + 后续删除写操作

具体代码如下：

int Ardb::DelKey(Context& ctx, const KeyObject& meta_key, Iterator*& iter)
{
  ValueObject meta_obj;
  if (0 == m_engine->Get(ctx, meta_key, meta_obj))
  {
    // 如果是string类型直接删除即可
    if (meta_obj.GetType() == KEY_STRING)
    {
      int err = RemoveKey(ctx, meta_key);
      return err == 0 ? 1 : 0;
    }
  }
  else
  {
    return 0;
  }

  if (NULL == iter)
  {
    // 如果是复杂类型，需要按照namespace,key,类型前缀遍历库
    // 搜索出所有前缀为 namespace|类型|Key的成员
    iter = m_engine->Find(ctx, meta_key);
  }
  else
  {
    iter->Jump(meta_key);
  }
  
  while (NULL != iter && iter->Valid())
  {
    KeyObject& k = iter->Key();
    ...
    iter->Del();
    iter->Next();
  }
}

前缀搜索代码如下:

Iterator* RocksDBEngine::Find(Context& ctx, const KeyObject& key) {
  ...
  opt.prefix_same_as_start = true;
  if (!ctx.flags.iterate_no_upperbound)
  {
    KeyObject& upperbound_key = iter->IterateUpperBoundKey();
    upperbound_key.SetNameSpace(key.GetNameSpace());
    if (key.GetType() == KEY_META)
    {
      upperbound_key.SetType(KEY_END);
    }
    else
    {
      upperbound_key.SetType(key.GetType() + 1);
    }
    upperbound_key.SetKey(key.GetKey());
    upperbound_key.CloneStringPart();
  }
  ...
}

Expire的实现

在一个key-value存储引擎上支持复杂数据结构的expire过期数据的实现比较困难，ardb中则用几个特殊技巧实现了对所有数据结构的过期（expire）的支持。
具体实现如下：

• meta的value中保存expire信息， 用绝对unix时间（ms）保存；
• 基于以上设计，ttl/pttl等查询ttl的操作只需要一次读meta即可完成；
• 基于以上设计，任何对meta信息的读取，都会触发expire的判断，由于对meta信息的读操作是必须的步骤，这里无需额外的读操作（和Redis一样访问时会触发）
• 创建一个namespace TTL_DB专门存放TTL排序信息。
• 保存设置expire时间到meta时， 当expire时间非0时，额外保存一个key-value， type为KEY_TTL_SORT； key的编码格式为 [TTL_DB] "" KEY_TTL_SORT , value为空；所以类似expire 等设置过期时间的操作，在ardb的实现中将会多一次写操作；
• 在自定义的comparator中，对KEY_TTL_SORT类型的key比较规则为先比较，这样KEY_TTL_SORT数据将会以过期时间远近保存在一起
• ardb中独立启动一个线程，每隔一定时间（100ms）顺序扫描KEY_TTL_SORT类型数据；当过期时间小于当前时间，即可触发删除操作；当过期时间大于当前时间，即可终止本次扫描。（相当于是Redis中的定时任务serverCron中处理过期Key）。

结语

通过编码层的转换，我们可以很好的对KV存储进行封装从而和Redis进行融合。所有对Redis数据的操作，经过编码层的转换，最终会转化为对KV存储的n次读写(N>=1)。在符合Redis命令语义的情况下，编码曾设计应当尽量的减少n的次数。
最重要的一点是，Redis与KV存储的融合并不是为了替换Redis，而是寻求一种在性能可接受的情况下使得单机能支持远超内存限制的数据量。在特定的场景中，也可以作为冷数据的存储方案与Redis热数据之间互联互通。

硬广来了，不要急：
即日起购买阿里云数据库Redis版（首台）3年5折、1年6折、按月7折啦，赶快点击购买吧：https://m.aliyun.com/markets/aliyun/act/redissaleoff?spm=5176.8112568.483450.6.o85c4v

阿里云数据库Redis团队诚邀加入：
https://job.alibaba.com/zhaopin/position_detail.htm?spm=0.0.0.0.l7roxQ&positionId=26437