Redis 迭代器(间断遍历)

我们都知道 redis 是单进程、单线程、一个命令执行完、才会执行下一个命令、如果数据库中有海量的数据、当使用 keys 命令,会直接造成服务器的短暂不可用等现象,所以在 redis 2.8.0 之后新增了 scan 操作,也就是 间断遍历。

核心代码在 dict.c中的 dictScan中。

unsigned long dictScan(dict *d,
                       unsigned long v,
                       dictScanFunction *fn,
                       dictScanBucketFunction* bucketfn,
                       void *privdata)
{
    dictht *t0, *t1;
    const dictEntry *de, *next;
    unsigned long m0, m1;

    if (dictSize(d) == 0) return 0;

    if (!dictIsRehashing(d)) {
        t0 = &(d->ht[0]);
        m0 = t0->sizemask;

        /* Emit entries at cursor */
        if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
        de = t0->table[v & m0];
        while (de) {
            next = de->next;
            fn(privdata, de);
            de = next;
        }

        /* Set unmasked bits so incrementing the reversed cursor
         * operates on the masked bits */
        v |= ~m0;

        /* Increment the reverse cursor */
        v = rev(v);
        v++;
        v = rev(v);

    } else {
        t0 = &d->ht[0];
        t1 = &d->ht[1];

        /* Make sure t0 is the smaller and t1 is the bigger table */
        if (t0->size > t1->size) {
            t0 = &d->ht[1];
            t1 = &d->ht[0];
        }

        m0 = t0->sizemask;
        m1 = t1->sizemask;

        /* Emit entries at cursor */
        if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
        de = t0->table[v & m0];
        while (de) {
            next = de->next;
            fn(privdata, de);
            de = next;
        }

        /* Iterate over indices in larger table that are the expansion
         * of the index pointed to by the cursor in the smaller table */
        do {
            /* Emit entries at cursor */
            if (bucketfn) bucketfn(privdata, &t1->table[v & m1]);
            de = t1->table[v & m1];
            while (de) {
                next = de->next;
                fn(privdata, de);
                de = next;
            }

            /* Increment the reverse cursor not covered by the smaller mask.*/
            v |= ~m1;
            v = rev(v);
            v++;
            v = rev(v);

            /* Continue while bits covered by mask difference is non-zero */
        } while (v & (m0 ^ m1));
    }

    return v;
}

redis为了做到不遗漏数据且尽量不重复数据,采用了一种叫做 reverse binary iteration(二进制反转) 的方法来进行简短遍历。

核心代码:

 v |= ~m1;
 v = rev(v);
 v++;
 v = rev(v);

1. 从迭代开始到结束,散列表没有进行 rehash 操作、没有扩容、缩容操作。

gdb

image

v的值,分别依次为 0、2、1、3。

打印的结果如下:

image.png

2、从迭代开始到结束,没有进行 rehash操作,但是进行了扩容和缩容操作。

3、从迭代开始到结束,进行了rehash操作。

 在rehash中,会同时存在两种表,一张为ht[0],一张为ht[1],因为两个并都存在数据,redis先对小的表进行数据遍历,然后在对大表进行数据遍历。
do {
            /* Emit entries at cursor */
            if (bucketfn) bucketfn(privdata, &t1->table[v & m1]);
            de = t1->table[v & m1];
            while (de) {
                next = de->next;
                fn(privdata, de);
                de = next;
            }

            /* Increment the reverse cursor not covered by the smaller mask.*/
            v |= ~m1;
            v = rev(v);
            v++;
            v = rev(v);

            /* Continue while bits covered by mask difference is non-zero */
        } while (v & (m0 ^ m1));

总结:redis 采用了一种叫做 reverse binary iteration(二进制反转)的算法,巧妙的利用这个规律,避免了重复数据和遗漏数据。

评论

暂无评论