Redis source code analysis 3 implementation of discontinuous traversal

Total ergodic problem , Will lead to the whole redis Unavailable , So discontinuous traversal is introduced

dictscan Implement discontinuous traversal

dictscan The implementation of the

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

There are three cases of discontinuous traversal ：

1） From the beginning to the end of the iteration , Hash table is not rehash operation .
2） From the beginning to the end of the iteration , The hash table has been expanded or reduced , And just between the two iterations rehash operation .
3） From the beginning to the end of the iteration , Hash table is in progress during one or more iterations rehash operation

The principle of discontinuous traversal

One of the most important things to master , After the expansion and reduction of the dictionary , Where will the original data be in the new dictionary ？

For example, before capacity expansion , Suppose the length is from 4 Extended to 8, Originally in 0 Of the elements of location , In the new hash table , Only in 0 perhaps 4 The location of , The algorithm makes use of this feature , To achieve no repeat traversal and no leakage traversal . The principle of volume reduction is the same .

  among , I will list one of them , Let's see how the algorithm can avoid this repeated traversal phenomenon

Suppose the current capacity bit 4, In the third iteration , The hash table has been expanded to 8,

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

The mask of the array is m0=0x11, ~m0=0x100
Then the first two iterations are as follows ：

  It's time to start again rehash

The mask of the array m0=0x111,~m0=0x1000

  At this point, the traversal is over , Let's see what we have traversed in total

old hash surface ：0 2

new hash surface ：1 5 3 7

At this time, do you think it's missing ？

Actually , We have a new hash From the perspective of table , In fact, traverse the old hash Tabular 0 2, In fact, it traverses the new hash Tabular 0 4 2 6, because 0-> 0 4 , 2-> 2 6, So in fact, it is realized 0 4 2 6 1 5 3 7 Full traversal of .

Others are similar . This is this reverse binary iteration（ Inverse binary iterative algorithm ）.