Tendis的Scan命令设计与实现

Scan命令

Scan
命令是Redis中经常使用的命令.用来扫描key-space
中的key,经常用于数据校验. 如在进行服务迁移后,可以通过对源端进行Scan,获取到扫描的key,之后去目的端进行数据校验即可.同时还兼具HSCAN/SSCAN/ZSCAN
等Scan簇命令来对HASH/SET/ZSET
等结构进行复合key扫描.

Scan具有如下保证：

• 完整的Scan扫描会将所有的key返回给用户.即只要在扫描结束前存在,最终会在某个时刻返回给用户 

• 完整的Scan扫描不会返回不存在的key,即在扫描期间不在的key,绝不会返回给用户

所以导致Scan
存在这样的问题:

• 某个key
  可能会被多次返回,需要用户自行进行去重操作

• 某个key
  在扫描期间不是持续存在的,有可能作为结果返回,也可能不会返回, 属未定义行为

在最新的Redis 6.x版本中,Scan命令支持的子命令包括: COUNT
, MATCH
, TYPE
,使用如下:

SCAN cursor [MATCH pattern] [COUNT count] [TYPE type]

127.0.0.1:6379> scan 176 MATCH *11* COUNT 1000
1) "0"
2)  1) "key:611"
    2) "key:711"
    3) "key:118"
    4) "key:117"
    5) "key:311"
    6) "key:112"
    7) "key:111"
127.0.0.1:6379>

Scan的设计实现

在Redis中,Scan命令在src/db.c
中编码实现.

函数调用栈为:processInputBuffer
-> processCommand
->scanCommand
->scanGenericCommand

在scanGenericCommand
中实现了通用接口,

供SCAN/HSCAN/SSCAN/ZSCAN
调用实现.

只关注SCAN的命令实现,按照以下的逻辑进行处理:

1.  Parse Options (参数解析) 按顺序迭代,从InputBuffer
中解析出MATCH, COUNT, TYPE
等Options

while (i < c->argc) {
  j = c->argc - i;
  if (!strcasecmp(c->argv[i]->ptr, "count") && j >= 2) {
    ...
  } else if (!strcasecmp(c->argv[i]->ptr, "match") && j >= 2) {
    ...
  } else if (!strcasecmp(c->argv[i]->ptr, "type") && j >= 2) {
    ...
  } else {
    addReply(c,shared.syntaxerr);
    goto cleanup;
  }
}

2.  Iterate the Collection (迭代扫描key集合) 根据不同的类型分别进行key
扫描, 包括:String, Hash,Set, Zset

if (ht) {       * string */
  *,,,*/
  void *privdata[2];
  long maxiterations = count*10;


  *...*/
  privdata[0] = keys;
  privdata[1] = o;
  do {
    cursor = dictScan(ht, cursor, scanCallback, NULL, privdata);
  } while (cursor &&
    maxiterations-- &&
    listLength(keys) < (unsigned long)count);
} else if (o->type == OBJ_SET) {
  ...
} else if (o->type == OBJ_HASH || o->type == OBJ_ZSET) {
  ...
} else {
  serverPanic("Not handled encoding in SCAN.");
}

3.  Filter elements (过滤元素) 对扫描得出的集合进行元素过滤, 只返回符合COUNT/MATCH/TYPE
的key
集合

node = listFirst(keys);
while (node) {
  robj *kobj = listNodeValue(node);
  nextnode = listNextNode(node);
  int filter = 0;


  /* Filter element if it does not match the pattern. */
  if (!filter && use_pattern) {
    /*...*/
  }


  /* Filter element if it is an expired key. */
  if (!filter && o == NULL && expireIfNeeded(c->db, kobj, true)) filter = 1;


  /* Remove the element and its associted value if needed. */
  if (filter) {
    /*...*/
   }


  /*...*/
   if (o && (o->type == OBJ_ZSET || o->type == OBJ_HASH)) {
     /* filter ZSET/HASH */
  }
  node = nextnode;
}

4. Reply to the client (回复客户端) 将迭代扫描的结果按照预定的格式返回给客户端，完成一次Scan
命令请求.

addReplyMultiBulkLen(c, 2);
addReplyBulkLongLong(c,cursor);


addReplyMultiBulkLen(c, listLength(keys));
while ((node = listFirst(keys)) != NULL) {
  robj *kobj = listNodeValue(node);
  addReplyBulk(c, kobj);
  decrRefCount(kobj);
  listDelNode(keys, node);
}

在Tendis中实现Scan

Tendis作为全面兼容Redis协议的, 兼容大多数Redis命令的存储服务,也需要对Scan命令进行支持.但是Tendis的内部实现和Redis区别较大.

• Redis使用dict
  来保存所有的键值对, Scan所返回的cursor
  游标语义是: 扫描到的哈希桶下标

• Tendis使用RocksDB
  作为存储引擎, 将不同的数据类型编码为key-value
  键值对保存在LSM-Tree
  中.

所以在Tendis中实现Scan需要关注这几方面:

1. 设计核心的扫描算法

2. 在Tendis中cursor具有何种语义?

3. cursor需要作为全局层级的记录,还是Session层级的记录?

4. 是否需要对Scan的option进行扩展?

5. 维护Cursor记录所需要的开销如何?

我们从上述几方面来解释Scan在Tendis中的设计与实现。

Scan核心算法

基于RocksDB
提供的接口进行相关的key
扫描查找,核心算法伪码描述如下:

Container<record> set;
for each store in kvstores        // iterate all kv-stores
  txn = rocksdb.transcation       // seek by rocksdb transcation
  iter = txn.createIterator
  prefix = genRecordKey
  iter.seek(prefix)
  while count                     // scan specific count keys
    record = iter.next
    if (filter(record))           // filter key set
      set.add(record)
    done
  done
done


return set;                       // return the result

Cursor的语义

在Redis中,cursor
作为返回的结果首项,表示最后扫描到的key
所在哈希桶下标.在Tendis的底层存储中是不存在哈希桶的概念的.

我们虽然提供了X个kvstore
(实际为RocksDB
实例),但是这些kv-store
的下标并不足以反映出当前扫描到的位置, 仅凭[0..9]的下标也无法在多次Scan
中进行接续扫描, 会导致Scan
多次调用时性能骤降.

我们赋予Cursor
新的语义:用来表示当前扫描到的KV Record
在当前kv-store
的位置.

可以这样理解其语义: 返回的Cursor
表示,已经扫描到[kvstoreid, cursor]
位置的key
.这样的作用是:

• 可以标志目前扫描扫描到的位置,用来下次快速获取上次的记录位置,并进行新一轮的扫描

• 返回Integer
  类型的值,与原生Redis兼容, 基于Redis的服务可以无缝进行迁移,不会出现Cursor
  结果解析的问题.

根本的原因在于: Cursor
是用来记录上次扫描的位置, 本身字面义在用户端是没有意义的, 对Cursor
而言,只有0
与!0
的情况

Cursor记录保存的可见域

当我们修改了Cursor
的语义后,可以使用相关的结构进行Cursor
记录的保存:

struct CursorMapping {
  size_t kvstoreId;              // kv-store id
  std::string lastScanPos;       // last scan key, use to seek quickly
  uint64_t sessionId;            // user session id
  uint64_t timeStamp;            // cursor mapping ts
};

通过struct CursorMapping
来保存Cursor->Record
的映射关系. 那么需要将映射关系保存在何种层级？global-level
亦或是session-level
?

我们需要保证的是: 不同Session
之间进行的Scan
操作是可以接续起来的,

Redis
因为Cursor
是桶下标,所以是全局可见的. 因此, Tendis
中CursorMapping
也需要作为全局的资源进行保存.

目前提供在ServerEntry
中进行全局的CursorMapping
映射保存: class ServerEntry { ... std::deque<CursorMap> _cursorMaps; ... };

扩展Scan的Options

社区版本的Scan支持COUNT
, MATCH
, TYPE
三种类型的Options,分别为:

•COUNT
: 返回指定数目的key(在key足够的情况下)•MATCH
: 返回符合模式匹配的key•TYPE
: 返回指定类型的key

在此基础上,我们可以基于Tendis的结构设计,对Options进行扩展,支持SLOTS
, SEQ
等Option.

• SLOTS
  : 返回指定slots
  的key
  (适用于集群场景下) Redis基于slots
  来实现数据分片, 在多数的集群场景下,我们可能只需要扫描本节点负责SLOTS
  的数据.在进行数据搬迁时的脏数据可以通过SLOTS
  子命令来进行过滤.这是基于Tendis的记录格式实现的. 简单描述如下:

SlotID | Type | DbID | PK | 0 | Version | SK | PK_LEN | Reserved

SlotID
作为首位编码, 在进行RocksDB
层面的记录检索时,可以进行过滤扫描.

• SEQ
  : 返回指定节点的key
  (适用于集群场景下,非用户直接操作) 在以往的集群方案下, 跨集群的Scan操作需要在代理层面实现,进行Cursor
  的移位调整来实现.Tendis为了方便代理层的接入,支持SEQ
  子命令.用来进行节点ID
  标识, 在Cursor
  内部进行修改, 高16位作为NodeID,
  低48位作为Cursor
  默认SEQ
  为0

维护Cursor的开销

维护全局的CursorMap
是存在一定程度上代价的.需要对其进行资源限制.

• 保证CursorMap
  满负载下的内存占用可控 对CursorMap
  的上限进行MAX_SIZE
  限制,通过tendis.MAX_MAPPING_COUNT
  控制 对单个Session
  所持有的CursorMapping
  上限进行限制, 由tendis.MAX_SESSION_LIMIT
  控制

• 保证CursorMap
  的清理不会致使Scan
  操作出现故障 由于配置了维护上限, 生成新的映射关系时,需要对较早的映射关系进行淘汰清理.目前使用惰性删除进行清理

     即:在新的映射关系加入时,对较早的映射关系进行清理淘汰

     具体的实现是,提供3组维护的结构:

// {cursor, mapping}
std::unordered_map<uint64_t, CursorMapping> _cursorMap;   
// {ts, cursor}
std::map<uint64_t, uint64_t> _cursorTs;  
// {id, Ts(es)}
std::unordered_map<uint64_t, std::set<uint64_t>> _sessionTs;

_cusrsorMap
: 实际映射关系存储的结构 

_cursorTs
 :用来进行Cursor与Ts之间快速反向摄取的结构. 

_sessionTs
:用来进行Session-level
层级的数据维护. set
中保存的是session mapping
的Ts

提供两条淘汰删除的策略:

•  当Session
  的映射数目达到上限时, 淘汰本Session
  的映射关系

•  当global
  的映射数目达到上限时, 淘汰非本Session
  的LRU映射关系

根据上述两条策略,可以使得维护的CursorMap
既具有全局可见性,同时各Session
之间不会直接干扰.

Scan可能存在的问题

相较于Redis的原生Scan, Tendis的实现主要表现在Cursor
语义的修改,目前的语义描述当前扫描的key
在DB
中的大致位置(Redis
不具备)

优点: 使用Tendis的Scan实现,配合dbsize
,可以对Scan的进度有大致的估算.使用Redis表示哈希桶下标的Cursor
不具备这样的能力.

缺点: 在DB数据变化较为频繁,且导致原有记录被移位时
,

• 若添加数据, 可能会导致Scan返回重复的key
  (行为同Redis)

• 若删除数据,可能会漏扫中间的少数gap
  (若原有记录被抹消,则会重新reset
  扫描进度)

在Scan上进行扩展

上面我们分析了如何在Tendis上实现Scan. 

除此之外还有SSCAN/HSCAN/ZSCAN
簇命令执行. 对于扫描的操作不再赘述, 同理即可. 我们需要考虑如何实现Cursor
语义的实现. 

同理.我们在CursorMap
的基础上扩展, 实现KeyCursorMap
. 将std::unordered_map<uint64_t, CursorMapping> _cursorMap;
 修改为std::unordered_map<std::string, CursorMapping> _keyCursorMap;
 

原来使用Cursor
数值作为key进行索引, 

现在使用编码String=>"key_cursor"
的形式进行编码. 

这样便可以使KeyCursorMap
也能很好的使用基于Key
的Scan
操作. 

另外, 对于Key的Scan操作竞争较大,可以通过哈希取模的形式减少竞争.

扩展阅读

Tendis项目地址^[1]

Scan实现源码^[2]

Scan相关文档^[3]

References

[1]
 https://github.com/Tencent/Tendis
[2]
 https://github.com/Tencent/Tendis/blob/dev-2.2/src/tendisplus/commands/scan.cpp#L298
[3]
 http://tendis.cn/#/Tendisplus/%E7%9F%A5%E8%AF%86%E5%BA%93/%E5%91%BD%E4%BB%A4/scan