redis 源码难点:字典的遍历 dictScan

目录

1 问题

dict.c 中的 dictScan 函数,用来遍历字典,迭代其中的每个元素。该函数使用的算法十分精妙

遍历一个稳定的字典,当然不是什么难事,但 Redis 中的字典因为有 rehash 的过程,使字典可能扩展,也可能收缩。这就带来了问题,如果在两次遍历中间,字典的结构发生了变化(扩展或缩小),字典中的元素所在的位置相应的会发生变化,那如何保证字典中原有的元素都可以被遍历?又如何能尽可能少的重复迭代呢?

这就是该算法的精妙所在,使用该算法,可以做到下面两点:

  • 开始遍历那一刻的所有元素,只要不被删除,肯定能被遍历到,不管字典扩展还是缩小;
  • 该算法可能会返回重复元素,但是已经把返回重复元素的可能性降到了最低;

2 算法核心原理

该算法使用了游标 v 来遍历字典,它表示本次要访问的哈希表 bucket 的索引。bucket 中保存了一个 entry 链表(哈希表用的是链地址法来解决键冲突),因此每次迭代都会把该 bucket 的链表中的所有元素都遍历一遍。

第一次迭代时,v 置为 0,来调用 dictScan 函数。然后该函数会返回一个游标,该游标作为下一次遍历的 v 再次调用 dictScan,最终,dictScan 函数返回 0 表示迭代结束。

首先看一下游标 v 的演变过程,也是该算法的核心。这里 v 的演变是采用了 reverse binary iteration 方法,也就是每次是向 v 的二进制最高位加 1,并向低位方向进位。

下面具体解释,首先,提取 dictScan 写一个简单的测试函数,用来看游标 v 的演变过程:

#include <stdio.h>

// 对 v 进行二进制逆序操作
unsigned long rev(unsigned long v) {
    unsigned long s = 8 * sizeof(v);
    unsigned long mask = ~0;
    while ((s >>= 1) > 0) {
        mask ^= (mask << s);
        v = ((v >> s) & mask) | ((v << s) & ~mask);
    }
    return v;
}

void printBits(unsigned long v, int tablesize)
{
    int cnt = 0;
    while(tablesize >> ++cnt);
    for(int i = cnt-2; i >= 0; --i)
        printf("%lu", (v >> i) & 1);
}

void test_dictScan_cursor(int tablesize)
{
    unsigned long v;
    unsigned long m0;

    v = 0;
    m0 = tablesize-1;
    printBits(v, tablesize);

    do
    {
        printf(" -> ");
        v |= ~m0;
        v = rev(v);
        v++;
        v = rev(v);
        printBits(v, tablesize);
    }while (v != 0);
    printf("\n");
}


int main()
{
    test_dictScan_cursor(8);
    test_dictScan_cursor(16);
    return 0;
}

参数 tablesize 表示哈希表的大小(redis 中,哈希表在内存中申请的空间大小 tablesize 必为 2n,m0 是哈希表索引的掩码,所以必为 tablesize-1)。printBits 用来打印 v 的低 n 二进制位,n 等于log2(tablesize)。

以 tablesize 为 8 和 16 分别运行该函数,结果如下:

$ gcc main.c -o main
$ ./main
000 -> 100 -> 010 -> 110 -> 001 -> 101 -> 011 -> 111 -> 000
0000 -> 1000 -> 0100 -> 1100 -> 0010 -> 1010 -> 0110 -> 1110 -> 0001 -> 1001 -> 0101 -> 1101 -> 0011 -> 1011 -> 0111 -> 1111 -> 0000

这就是 reverse binary iteration 方法,也就是每次是向 v 的最高位加 1,并向低位方向进位。比如 1101 的下一个数是 0011,因为 1101 的前三个数为 110,最高位加 1,并且向低位进位就是 001,所以最终得到 0011。

算法的详细计算过程如下:

  • v |= ~m0; 用于保留 v 的低 n 位数,其余位全置为 1
  • v = rev(v); 将 v 的二进制位进行翻转,所以,v的低 n 位数成了高 n 位数,并且进行了翻转
  • v++; v 自增 1
  • v = rev(v); 再次二进制翻转

因此,最终得到的新 v,就是向最高位加 1,且向低位方向进位

3 为什么要采用这种算法

这样设计的原因就在于,字典中的哈希表有可能扩展(redis 中扩展指的是调整哈希表大小,使 load-factor <= 0.5 附近),也有可能收缩(redis 中收缩指的是调整哈希表大小,使 load-factor <= 1 附近)。在字典不稳定的情况下,既要遍历到所有没被删除的元素,又要尽可能较少的重复遍历。

下面详细解释一下这样设计的好处,以及为什么不是按照普通的 0, 1, 2, … 这样的正常顺序进行迭代?

计算一个哈希表节点索引的方法 是 hash(key)&mask。哈希表容量为 8,则 mask 为 111,因此,节点的索引值就取决于哈希值的低 3 bit,设索引值是 abc。如果哈希表容量为 16,则 mask 为 1111,该节点的哈希值不变,而索引值是 ?abc,其中 ? 取 0 或 1 中的一个,也就是说,该节点在容量为 16 的哈希表中,索引要么是 0abc 要么是 1abc。以此类推,如果哈希表容量为32,则该节点的索引可能是 00abc,01abc,10abc 或者 11abc 中的一个。

3.1 该算法的迭代过程

重新看一下该算法中,哈希表容量分别为 8 和 16 时,v 的迭代过程:

000 -> 100 -> 010 -> 110 -> 001 -> 101 -> 011 -> 111 -> 000
0000 -> 1000 -> 0100 -> 1100 -> 0010 -> 1010 -> 0110 -> 1110 -> 0001 -> 1001 -> 0101 -> 1101 -> 0011 -> 1011 -> 0111 -> 1111 -> 0000

3.1.1 哈希表扩展

哈希表容量为 8 时,第 i 个 v 的值(0 <= i <=7),扩展到容量为 16 的哈希表中,对应的值是 2i 和 2i+1,它们是相邻的,这点很重要。

首先是字典扩展的情况,假设当前字典哈希表容量为 8,在迭代完索引为 010 的 bucket 之后,下一个索引值为 110。假设在下一次迭代前,字典哈希表容量扩展成了 16。110 这个索引,在容量为 16 的情况下,就成了 0110,因此开始迭代索引为 0110 的 bucket 中的节点。

在容量为 8 时,已经迭代过的索引分别是:000,100,010。哈希表容量扩展到 16 后,在这些索引的 bucket 中的节点,分布到新的 bucket 中,新 bucket 的索引将会是:0000,1000,0100,1100,0010,1010。而这些,正好是将要迭代的 0110 之前的索引,从 0110 开始,按照容量为 16 的哈希表的索引迭代下去,这样既不会漏掉节点,也不会迭代重复的节点。

3.1.2 哈希表收缩

再看一下字典哈希表收缩的情况,也就是由 16 收缩为 8。在容量为 16 时,迭代完索引 0100 之后,下一个索引为 1100,假设此时哈希表容量收缩为 8。1100 这个索引,在容量为 8 的情况下,就成了 100。因此开始迭代索引为 100 的 bucket 中的节点。

在容量为 16 时,已经迭代过的索引是:0000,1000,0100,哈希表容量收缩后,这些索引的 bucket 中的节点,分布到新的 bucket 中,新 bucket 的索引将会是:000 和 100。现在要从索引为 100 的 bucket 开始迭代,这样不会漏掉节点,但是之前容量为 16 时,索引为 0100 中的节点会被重复迭代,然而,也就仅 0100 这一个 bucket 中的节点会重复而已。

原哈希表容量为 x,收缩后容量为 y,则最多会有 x/y – 1 个原 bucket 的节点会被重复迭代。比如由 16 缩小为 8,则最多就有 1 个 bucket 节点会重复迭代,要是由 32 缩小为 8,则最多会有3个。

当然也有可能不产生重复迭代,还是从 16 收缩为 8 的情况,如果已经迭代完 1100,下一个索引为 0010,此时容量收缩为 8,下一个索引就成了010。

容量为 16 时,已经迭代过的索引为 0000,1000,0100,1100,容量收缩后,这些索引对应到新的索引是 000 和 100,正好是 010 之前的索引,从 010 开始,按照容量为 8 的索引走下去,不会漏掉节点,也不会重复迭代节点。

所以说这种算法,保证了:能迭代完所有节点而不会漏掉;又能尽可能较少的重复遍历。

3.2 普通的顺序迭代过程

如果按照正常的顺序迭代,哈希表容量分别为 8 和 16 时,v 的迭代过程如下:

000 -> 001 -> 010 -> 011 -> 100 -> 101 -> 110 -> 111 -> 000     
0000 -> 0001 -> 0010 -> 0011 -> 0100 -> 0101 -> 0110 -> 0111 -> 1000 -> 1001 -> 1010 -> 1011 -> 1100 -> 1101 -> 1110 -> 1111 -> 0000  

3.2.1 哈希表扩展

字典扩展的情况,当前字典哈希表容量为 8,假设在迭代完索引为 010 的 bucket 之后,下一个索引为 011。迭代 011 之前,字典容量扩展成了 16。011 这个索引,在容量为 16 的情况下,就成了 0011,因此开始迭代索引为 0011 的 bucket 中的节点。

在容量为 8 时,已经迭代过的索引是:000,001,010。哈希表容量扩展到 16 后,这些索引的 bucket 中的节点,会分布到新的 bucket 中,新 bucket 的索引将会是:0000,1000,0001,1001,0010 和 1010。现在要开始迭代的索引为 0011,而 1000,1001,1010 这些 bucket 中的节点在后续还是会遍历到,这就产生了重复遍历。

虽然这种情况不会发生漏掉节点的情况,但是肯定会有重复的情况发生,而且容量变化发生的时机越晚,重复遍历的节点越多,比如容量为 8 时,迭代完 110 后,下一个索引为 111,容量扩展为 16 后,这个索引就成了 0111。

容量为 8 时,已经迭代过的索引为 000,001,010,011,100,101,110,扩展到容量为 16 的哈希表中,这些 bucket 中的节点会分布到索引为:0000,1000,0001,1001,0010,1010,0011,1011,0100,1100,0101,1101,0110,1110。现在容量为16,要开始迭代索引为0111,而 1000,1001,1010,1011 和 1110 这些节点后续还会遍历到,重复的节点增多了。

3.2.2 哈希表收缩

再看一下容量缩小的情况,容量由 16 缩小为 8。在容量为 16 时,迭代完 0100 之后,下一个为 0101,此时容量缩小为 8。0101 在容量为 8 的情况下,就成了101。

在容量为 16 时,尚未迭代过的索引是:0101,0110,0111,1000,1001,1010,1011,1100,1101,1110,1111。这些索引,在哈希表容量缩小后,分配到新的 bucket 中,索引将会是:000,001,010,011,100,101,110,111。现在要开始迭代的索引为 101,那 101 之前的 000,001,010,011,100 这些索引就不会迭代了,这样,原来的某些节点就被漏掉了。

另外,还是从 16 收缩为 8 的情况,如果已经迭代完 1100,下一个为 1101,在容量为 8 的情况下,就成了 101。

容量为 16 时,已经迭代过的索引为 0000,0001,0010,0011,0100,0101,0110,0111,1000,1001,1010,1011,1100。这些索引,在哈希表容量收缩后,分配到新的 bucket 中,索引分别是:000,001,010,011,100,101,110,111。容量变为 8 后,从 101 开始,很明显,原来已经迭代过的 0101,0110,0111 就会产生重复迭代。

因此,顺序迭代不是一个满足要求的迭代方法。

4 dictScan 源码

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

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

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

        de = t0->table[v & m0];
        while (de) {
            fn(privdata, de);
            de = de->next;
        }

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

        if (t0->size > t1->size) {
            t0 = &d->ht[1];
            t1 = &d->ht[0];
        }

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

        de = t0->table[v & m0];
        while (de) {
            fn(privdata, de);
            de = de->next;
        }

        do {
            de = t1->table[v & m1];
            while (de) {
                fn(privdata, de);
                de = de->next;
            }

            v = (((v | m0) + 1) & ~m0) | (v & m0);  // 就是对 v 的低 m1-m0 位加 1,并保留 v 的低 m0 位

        } while (v & (m0 ^ m1));  // 循环条件 v &(m0 ^ m1),表示直到 v 的低 m1-m0 位到低 m1 位之间全部为 0 为止。
    }

    v |= ~m0;

    v = rev(v);
    v++;
    v = rev(v);

    return v;
}

如果字典当前没有 rehash,则比较简单,直接根据 v 找到需要迭代的 bucket 索引,针对该 bucket 中链表中的所有节点,调用用户提供的 fn 函数。

如果字典当前正在 rehash,则需要先遍历较小的哈希表,然后是较大的哈希表。

首先使 t0 指向小表,t1 指向大表;m0 为小表的 mask,m1 为大表的 mask。

根据 v&m0,找到 t0 中需要迭代的 bucket,然后迭代其中的每个节点即可。

接下来的代码稍显复杂,但是,本质上,就是 t0 中,索引为 v&m0 的 bucket 中的所有节点,再其扩展到 t1 中后,遍历其所有可能的 bucket 中的节点。语言不好描述,举个例子就明白了:若 t0 长度为 8,则 m0 为 111,v&m0 就是保留 v 的低三位,假设为 abc。若 t1 长度为 32,则 m1 为 11111,该过程就是:遍历完 t0 中索引为 abc 的 bucket 之后,接着遍历 t1 中,索引为 00abc、01abc、10abc、11abc 的 bucket 中的节点。

提取核心代码逻辑来进行测试:

void test_dictScan_iter(int smalltablesize, int largetablesize)
{
    unsigned long v;
    unsigned long m0, m1;

    v = 0;
    m0 = smalltablesize-1;
    m1 = largetablesize-1;

    do
    {
        printf("\nsmall v is: ");
        printBits(v, smalltablesize);
        printf("\n");

        do
        {
            printf("large v is: ");
            printBits(v, largetablesize);
            printf("\n");

            v = (((v | m0) + 1) & ~m0) | (v & m0);
        }while (v & (m0 ^ m1));

        v |= ~m0;
        v = rev(v);
        v++;
        v = rev(v);
    }while (v != 0);
}

int main()
{
    test_dictScan_iter(8, 32);
    return 0;
}

结果如下:

$ ./main

small v is: 000
large v is: 00000
large v is: 01000
large v is: 10000
large v is: 11000

small v is: 100
large v is: 00100
large v is: 01100
large v is: 10100
large v is: 11100

small v is: 010
large v is: 00010
large v is: 01010
large v is: 10010
large v is: 11010

small v is: 110
large v is: 00110
large v is: 01110
large v is: 10110
large v is: 11110

small v is: 001
large v is: 00001
large v is: 01001
large v is: 10001
large v is: 11001

small v is: 101
large v is: 00101
large v is: 01101
large v is: 10101
large v is: 11101

small v is: 011
large v is: 00011
large v is: 01011
large v is: 10011
large v is: 11011

small v is: 111
large v is: 00111
large v is: 01111
large v is: 10111
large v is: 11111

本笔记系统由 时中贺 搭建和维护,使用 Emacs Org mode 编辑和构建
email: shi_zhonghe@163.com