Redis5源码学习浅析redis命令之keys篇

共计 6121 个字符，预计需要花费 16 分钟才能阅读完成。

baiyan

命令含义：查找并返回所有符合给定模式 pattern 的 key
命令格式：

KEYS pattern

命令实战：

127.0.0.1:6379> keys *
1) "kkk"
2) "key1"

返回值：根据 pattern 匹配后的所有键的集合

keys 命令对应的处理函数是 keysCommand()：

void keysCommand(client *c) {
    dictIterator *di; 
    dictEntry *de;
    sds pattern = c->argv[1]->ptr; // 获取我们输入的 pattern
    int plen = sdslen(pattern), allkeys;
    unsigned long numkeys = 0;
    void *replylen = addDeferredMultiBulkLength(c); 

    di = dictGetSafeIterator(c->db->dict); // 初始化一个安全迭代器
    allkeys = (pattern[0] == '*' && pattern[1] == '\0'); // 判断是否返回全部 keys 的集合
    while((de = dictNext(di)) != NULL) { // 遍历整个键空间字典
        sds key = dictGetKey(de); // 获取 key 值
        robj *keyobj;

        // 如果是返回全体键的集合，或者当前键与我们给定的 pattern 匹配，那么添加到返回列表
        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); // 释放安全迭代器
    setDeferredMultiBulkLength(c,replylen,numkeys); // 设置返回值的长度
}

由于我们使用了 keys * 命令，需要返回所有键的集合。我们首先观察这段代码，它会使用一个安全迭代器，来遍历整个键空间字典。在遍历的同时，筛选出那些匹配我们 pattern 以及非过期的键，然后返回给客户端。由于其遍历的时间复杂度是和字典的大小成正比的，这样就会导致一个问题，当键非常多的时候，这个键空间字典可能会非常大，我们一口气使用 keys 把字典从上到下遍历一遍，会消耗非常多的时间。由于 redis 是单进程的应用，长时间执行 keys 命令会阻塞 redis 进程，造成 redis 服务对外的不可用状态。所以，很多公司都会禁止开发者使用 keys 命令，这可能导致 redis 服务长时间不可用。参考案例：Redis 的 KEYS 命令引起 RDS 数据库雪崩，RDS 发生两次宕机，造成几百万的资金损失
那么可能大家会问了，我如果换上其他范围比较小的 pattern 去替换之前的 *，不就可以避免一次性去遍历全部的键空间了吗？但是我们看上面的源码，由于它是在遍历到每一个 key 的时候，都会去判断当前 key 是否与传入的 pattern 所匹配，所以，并不是我们想象中的，只遍历我们传入的 pattern 的键空间元素集合，而需要遍历完整的键空间集合，在遍历的同时筛选出符合条件的 key 值。其实遍历的初始范围并没有缩小，其时间复杂度仍然为 O(N)，N 为键空间字典的大小。

在 keys 命令的遍历过程中，涉及到了安全迭代器的概念。与之相对的，还有非安全迭代器。那么，迭代器是如何工作的，安全与非安全的区别有是什么呢？我们首先来看迭代器的存储结构：

typedef struct dictIterator {
    dict *d; // 指向所要遍历的字典
    long index; // 哈希表中 bucket 的索引位置
    int table, safe; // table 索引（参考 dict 结构只能为 0 或 1），以及迭代器是否安全的标记
    dictEntry *entry, *nextEntry; // 存储当前 entry 和下一个 entry
    long long fingerprint; // 指纹，只在非安全迭代的情况下做校验
} dictIterator;

为了让大家能够看明白 index 和 table 字段的作用，我们又要贴上 dict 的结构了：

其中的 table 字段只能为 0 或 1。0 是正常状态下会使用的哈希表，1 是 rehash 过程中需要用到的过渡哈希表。而 index 就是每个哈希表中 01234567 这个索引了。迭代器中的 safe 字段就是用来区分迭代器类型是安全还是非安全的。所谓安全就是指在遍历的过程中，对字典的操作不会影响遍历的结果；而非安全的迭代器可能会由于 rehash 等操作，导致其遍历结果会有所误差，但是它的性能更好。

在 redis 中，安全迭代器通过直接禁止 rehash 操作，来让迭代器变得安全。那么，为什么禁止 rehash 操作就安全了呢？我们都知道，rehash 操作是渐进式的。每执行一个命令，才会做一个 rehash。rehash 操作会同时使用字典的两个 table。我们考虑这样一种情况：假设迭代器当前正在遍历第一个 table，此时进度已经到了索引 index 为 3 的位置，而某一个元素还没有进行 rehash，我们已经遍历过了这个元素。那么 rehash 和遍历同时进行，假设 rehash 完毕，这个元素到了第二个 table 的 index 为 33 的位置上。而目前迭代器的进度仅仅到了第二个 table 的 index 为 13 的位置，还没有遍历到 index 为 33 的位置上。那么如果继续遍历，由于这个元素已经在第一个 table 中遍历过一次，那么现在会被不可避免地遍历第二次。也就是说，由于 rehash 导致同一个元素被遍历了两次，这就是为什么 rehash 会影响迭代器的遍历结果。为了解决以上问题，redis 通过在安全迭代器运行期间禁止 rehash 操作，来保证迭代器是安全的。那么究竟 redis 是如何判断当前是否有安全迭代器在运行，进而来禁止 rehash 操作的呢？我们首先回顾一下 dict 的结构：

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2]; // 两个 table 的指针
    long rehashidx;  // rehash 标志，如果是 - 1 则没有在 rehash
    unsigned long iterators; // 当前运行的安全迭代器的数量
} dict;

我们看到，字典结构中的 iterators 字段用来描述安全迭代器的数量。如果有一个安全迭代器在运行，那么这个字段就会 ++。这样，在迭代的过程中，字典会变得相对稳定，避免了一个元素被遍历多次的问题。如果当前有一个安全迭代器在运行，iterator 字段必然不会为 0。当这个字段为 0 的时候，才能进行 rehash 操作：

static void _dictRehashStep(dict *d) {if (d->iterators == 0) dictRehash(d,1);
}

其实，除了安全迭代器这种简单粗暴地禁止 rehash 操作之外，redis 还提供了 SCAN 这种更高级的遍历方式。它通过一种更为复杂以及巧妙的算法，来保证了即使在 rehash 过程中，也能保证遍历的结果不重不漏。这就保证了 rehash 操作以及遍历操作能够并发执行，同时也避免了 keys 在遍历当键空间很大的时候超高的时间复杂度会导致 redis 阻塞的问题，大大提高了效率。

那么继续思考，仅仅不进行 rehash 操作就能够保证迭代器是安全的了吗？由于 redis 是单进程的应用，所以我们在执行 keys 命令的时候，会阻塞其他所有命令的执行。所以，在迭代器进行遍历的时候，我们外部是无法通过执行命令，来对键空间字典进行增删改操作的。但是 redis 内部的一些时间事件会有修改字典的可能性。比如：每隔一段时间扫描某个键是否已经过期，过期了则把它从键空间中删除。这一点，我认为即使是安全迭代器，也是无法避免可能在遍历期间对字典进行操作的的。比如在遍历期间，redis 某个时间事件把还没有遍历到的元素删除了，那么后续迭代器再去继续遍历，就无法遍历到这个元素了。那么如何解决这个问题呢？除非 redis 内部根本不在遍历期间触发事件并执行处理函数，否则这些操作所导致遍历结果的细微误差，redis 是无法避免的。

抛开上面这些细节，我们接下来看一下具体的遍历逻辑。首先我们需要初始化安全迭代器：

dictIterator *dictGetIterator(dict *d)
{dictIterator *iter = zmalloc(sizeof(*iter));

    iter->d = d;
    iter->table = 0;
    iter->index = -1;
    iter->safe = 0;
    iter->entry = NULL;
    iter->nextEntry = NULL;
    return iter;
}

如果是安全迭代器，除了需要初始化以上字段之外，还需要将 safe 字段设置为 1：

dictIterator *dictGetSafeIterator(dict *d) {dictIterator *i = dictGetIterator(d); // 调用上面的方法初始化其余字段

    i->safe = 1; // 初始化 safe 字段
    return i;
}

回到开始的 keys 命令，它调用的就是 dictGetSafeIterator()函数来初始化一个安全迭代器。接下来，keys 命令会循环调用 dictNext()方法对所有键空间字典中的元素做遍历：

dictEntry *dictNext(dictIterator *iter)
{while (1) {
    
        // 进入这个 if 的两种情况：// 1. 这是迭代器第一次运行
        // 2. 当前索引链表中的节点已经迭代完
        if (iter->entry == NULL) {

            // 指向被遍历的哈希表，默认为第一个哈希表
            dictht *ht = &iter->d->ht[iter->table];

            // 仅仅第一次遍历时执行（index 初始化值为 -1）if (iter->index == -1 && iter->table == 0) {
            
                // 如果是安全迭代器（safe == 1），那么更新 iterators 计数器
                if (iter->safe)
                    iter->d->iterators++;
                // 如果是不安全迭代器，那么计算指纹
                else
                    iter->fingerprint = dictFingerprint(iter->d);
            }
            
            // 更新索引，继续遍历下一个 bucket 上的元素
            iter->index++;

            // 如果迭代器的当前索引大于当前被迭代的哈希表的大小
            // 那么说明这个哈希表已经迭代完毕
            if (iter->index >= (signed) ht->size) {
                // 如果正在进行 rehash 操作，说明第二个哈希表也正在使用中
                // 那么继续对第二个哈希表进行遍历
                if (dictIsRehashing(iter->d) && iter->table == 0) {
                    iter->table++;
                    iter->index = 0;
                    ht = &iter->d->ht[1];
                // 如果没有 rehash，则不需要遍历第二个哈希表
                } else {break;}
            }

            // 如果进行到这里，说明这个哈希表并未遍历完成
            // 更新节点指针，指向下个索引链表的表头节点（index 已经 ++ 过了）iter->entry = ht->table[iter->index];
        } else {
            // 执行到这里，说明正在遍历某个 bucket 上的链表（为了解决冲突会在一个 bucket 后面挂接多个 dictEntry，组成一个链表）iter->entry = iter->nextEntry;
        }

        // 如果当前节点不为空，那么记录下该节点的下个节点的指针（即 next）// 因为安全迭代器在运行的时候，可能会将迭代器返回的当前节点删除，这样就找不到 next 指针了
        if (iter->entry) {
            iter->nextEntry = iter->entry->next;
            return iter->entry;
        }
    }

    // 遍历完成
    return NULL;
}

具体的遍历过程已以注释的形式给出了。代码中又有一个新的概念：fingerprint 指纹，下面我们讨论一下指纹的概念。

在 dictNext()遍历函数中，有这样一段代码：

if (iter->safe) { // 如果是安全迭代器（safe == 1），那么更新 iterators 计数器
     iter->d->iterators++;
} else { // 如果是不安全迭代器，那么计算指纹
     iter->fingerprint = dictFingerprint(iter->d);
}

我们看到，当迭代器是非安全的情况下，它会验证一个指纹。顾名思义，非安全的意思就是在遍历的时候可以进行 rehash 操作，这样就会导致遍历结果可能出现重复等问题。为了正确地识别这种问题，redis 采用了指纹机制，即在遍历之前采集一次指纹，在遍历完成之后再次采集指纹。如果两次指纹比对一致，就说明遍历结果没有因为 rehash 操作的影响而改变。那么具体如何去验证指纹呢？验证指纹的本质其实就是判断字典是否因为 rehash 操作发生了变化：

long long dictFingerprint(dict *d) {long long integers[6], hash = 0;
    int j;

    integers[0] = (long) d->ht[0].table;
    integers[1] = d->ht[0].size;
    integers[2] = d->ht[0].used;
    integers[3] = (long) d->ht[1].table;
    integers[4] = d->ht[1].size;
    integers[5] = d->ht[1].used;

    for (j = 0; j < 6; j++) {hash += integers[j];
        /* For the hashing step we use Tomas Wang's 64 bit integer hash. */
        hash = (~hash) + (hash << 21); // hash = (hash << 21) - hash - 1;
        hash = hash ^ (hash >> 24);
        hash = (hash + (hash << 3)) + (hash << 8); // hash * 265
        hash = hash ^ (hash >> 14);
        hash = (hash + (hash << 2)) + (hash << 4); // hash * 21
        hash = hash ^ (hash >> 28);
        hash = hash + (hash << 31);
    }
    return hash;
}

我们看到，指纹验证就是基于字典的 table、size、used 等字段来进行的。如果这几个字段发生了改变，就代表 rehash 操作正在执行或已执行完毕。一旦有 rehash 操作在执行，那么有可能就会导致遍历结果受到影响。所以，非安全迭代器的指纹验证能够很好地发现 rehash 操作对遍历结果产生影响的可能性。

命令语法

源码分析

扩展

安全迭代器与非安全迭代器

怎么做才会安全

安全迭代器一定安全吗

迭代器遍历的过程

指纹的作用

Just My Socks（注册教程内含优惠码）