redis 源码分析3 间断遍历的实现

全量遍历问题，会导致整个redis不可用，所以就引入了间断遍历

dictscan实现间断遍历

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;
}

间断遍历有三种情况：

1） 从迭代开始到结束， 散列表没有进行rehash操作。
2） 从迭代开始到结束， 散列表进行了扩容或缩容操作， 且恰好为两次迭代间隔期间完成了rehash操作。
3） 从迭代开始到结束， 某次或某几次迭代时散列表正在进行rehash操作

间断遍历的原理

其中最重要的一点要掌握的，就是字典的扩容和缩容后，原来的数据在新的字典中的位置会在哪里？

比如扩容前，假设长度从4 扩展到8，原来在0位置的元素的，在新的哈希表中，只能在0或者4的位置，算法就是利用了这种特性，来实现不重复遍历和不漏遍历。缩容的原理也一样。

 其中，我就列举其中的一种情况，来看算法是怎么实现规避这种重复的遍历的现象

假设现在的容量位4，在第三次迭代时，哈希表发生了扩容到8，

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

数组的掩码为m0=0x11， ~m0=0x100
则前两次遍历如下：

 这时候重新rehash

数组的掩码m0=0x111，~m0=0x1000

 此时就已经结束遍历结束了，我们看看总共遍历了哪几个

旧的hash表：0 2

新的hash表：1 5 3 7

这时候是不是觉得是不是漏了？

其实，我们从新的hash表的角度看，其实遍历旧hash表的0 2，其实时遍历了新的hash表的 0 4 2 6，因为0-> 0 4 , 2-> 2 6，所以实际上就实现了0 4 2 6 1 5 3 7的全遍历。

其他情况类似。这就是这个reverse binary iteration（反向二进制迭代算法）。