Redis中keys, scan, smembers命令的区

发表于

这是我参与11月更文挑战的第19天，活动详情查看：2021最后一次更文挑战

起因

昨天在群里看到了一道面试题，题目是：

1
2
vbnet复制代码假如Redis里面有1亿个key，其中有10w个key是以某个固定的已知的前缀开头的
如果将它们全部找出来并且说明使用的方法的底层原理？

看群里的小伙伴们各抒己见，最后总结起来有如下三个命令：

  • keys：用于查找所有符合给定模式 pattern 的 key
  • smembers：返回集合 key 中的所有成员
  • scan：增量迭代当前数据库中的所有数据库键

其中，keys和smembers命令都是返回所有成员，时间复杂度为O(n)O(n)O(n)。scan虽然时间复杂度也是O(n)O(n)O(n)，但是它采用的是增量的方式，数据量较大的场景下，不会像前两者一样一直阻塞着线程。

上面都是通过网上搜索来的答案，具体是不是这样我也不确定。于是我跑去github上面下了redis的源码，看看源码里面是怎么样的。

github.com/redis/redis

源码

在源码文件中有一个命令表，位于redis\src\server.c文件中，在这里我们可以快速的找到各个命令对应的函数入口。

image.png

image.png

命令的入口找到了，我们就可以分别跳转过去看它的对应实现了。

keys

在keys命令函数中可以看到它是遍历了整个键空间字典，将与给定的pattern匹配的添加到返回列表中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
c复制代码void keysCommand(client *c) {
    dictIterator *di;
    dictEntry *de;
    sds pattern = c->argv[1]->ptr;
    int plen = sdslen(pattern), allkeys;
    unsigned long numkeys = 0;
    void *replylen = addReplyDeferredLen(c);

    di = dictGetSafeIterator(c->db->dict);
    allkeys = (pattern[0] == '*' && plen == 1);
    while((de = dictNext(di)) != NULL) {
        sds key = dictGetKey(de);
        robj *keyobj;

        if (allkeys || stringmatchlen(pattern,plen,key,sdslen(key),0)) {
            keyobj = createStringObject(key,sdslen(key));
            if (!keyIsExpired(c->db,keyobj)) {
                addReplyBulk(c,keyobj);
                numkeys++;
            }
            decrRefCount(keyobj);
        }
    }
    dictReleaseIterator(di);
    setDeferredArrayLen(c,replylen,numkeys);
}

smembers

smembers命令这边调用的是sinterGenericCommand函数，搜索范围传递的是0，表示全局搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
C复制代码/* SINTER key [key ...] */
void sinterCommand(client *c) {
    sinterGenericCommand(c, c->argv+1,  c->argc-1, NULL, 0, 0);
}

/* SINTER / SINTERSTORE / SINTERCARD
 *
 * 'cardinality_only' work for SINTERCARD, 只返回具有最小处理和内存开销的基数.
 *
 * 'limit' work for SINTERCARD, 达到限制后停止搜索。传递 0 表示无限制.
 */
void sinterGenericCommand(client *c, robj **setkeys,
                          unsigned long setnum, robj *dstkey,
                          int cardinality_only, unsigned long limit) {}

scan

由于scanGenericCommand代码太长来这里就不全贴出来，小伙伴们感兴趣的话可以下载源码搜索一下。

该函数的大概实现逻辑应该是先解析附带的参数，得到需要返回的数据长度以及游标值，再迭代集合获取所需数据。

具体的入口函数为disScan。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
c复制代码/* The SCAN command completely relies on scanGenericCommand. */
void scanCommand(client *c) {
    unsigned long cursor;
    if (parseScanCursorOrReply(c,c->argv[1],&cursor) == C_ERR) return;
    scanGenericCommand(c,NULL,cursor);
}

/* This command implements SCAN, HSCAN and SSCAN commands.
 * 如果对象 'o' 被传递，那么它必须是一个 Hash、Set 或 Zset 对象，
 * 否则如果 'o' 为 NULL，该命令将对与当前数据库关联的字典进行操作
 *
 * 当 'o' 不为 NULL 时，该函数假定客户端参数向量中的第一个参数是一个键，
 * 因此它会在迭代之前跳过它以解析选项。
 *
 * 在 Hash 对象的情况下，该函数返回 Hash 上每个元素的字段和值。 */
void scanGenericCommand(client *c, robj *o, unsigned long cursor) {}

最后

由于我是Java出身，对于c/c++的语法不熟悉，备注都是阅读源码后结合注释进行理解的，如果文中有备注错误的地方，希望大佬们可以帮忙指点一下！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%