scan遇上rehash

2020-03-27 ❐redis

缘起

面试时被问到，redis如果你想要找到所有test_开头的键值时，一般使用什么命令我当时想也不想，keys命令啊面试官一脸失望的问我，有没有用过scan命令我赶紧说用过用过但是当时心里特别害怕，生怕问这两者的区别，不过好在没有继续往下问，嘿嘿不过面试后，我隐隐好奇，这两者到底有什么区别，为什么都推荐用scan这个命令？

背景

keys和scan的区别

KEYS parttern：查找所有符合给定模式pattern的key。

KEYS指令一次性返回所有匹配的key。
key的数量过大会使服务卡顿。

SCAN cursor [MATCH pattern] [COUNT count]：查找给定数量内个数的符合给定模式pattern的key。

基于游标的迭代器，需要基于上一次的游标延续之前的迭代过程。
以0作为游标开始一次新的迭代，直到命令返回游标0完成一次遍历。
不保证每次执行都返回给定数量的元素，支持模糊查询。
一次返回的数量不可控，只能是大概率符合COUNT参数。
返回的游标不一定是递增的，可能会获取到重复key，需要在外部程序去重。

keys会导致的问题

首先我们看下redis的网络模型IO多路复用

IO多路复用

简单来说，IO多路复用是一场一对多的群架，相较于多进程与多线程网络模型，io多路复用使用一个进程（一个线程）遍历处理多个socket的请求，准确来说，是交由操作系统来进行socket的遍历操作 20190528115137282_1712659801 总的来说分为三步：

fd拷贝（用户空间 -> 系统空间）
遍历fd
返回就绪的fd
进程处理就绪fd请求

首先我们知道，redis是一个基于内存的单进程单线程（基于IO多路复用）的kv数据库在redis2.8之前，能满足这一需求的是keys命令，但是他会导致两个问题：

没有limit，只能一次性的获取所有符合条件的结果，换句话说如果你的命令输入错误，可能会有成百上千的输出
单进程单线程的redis，一个O(N)的算法，如果执行时间很长，很可能会直接导致redis服务的阻塞

这谁顶得住啊，我如果需要在线上执行一个查询命令，即使命令没有输错，但是如果结果集很大，都有可能导致redis的一个节点阻塞

问题

为什么实现不了limit （时间复杂度）

那么我就会问，为什么不能支持limit操作呢，这样即使我的操作是O(N)的，我可以通过把limit设置的比较小，循环多次取，这样可以减少对服务的影响。但是为什么实现不了呢，这与redis的底层结构有关，我们知道redis的键值对底层是以dict这一内部数据结构组织的，那我们就看看dict这一结构为什么不好实现这一功能

dict结构

dict结构
typedef struct dict {
    //类型特定函数
    dictType *type;
    //私有数据
    void *privData;
    //哈希表
    dictht ht[2];
    //rehash索引
    //当rehash不进行时，值为-1
    int trehashidx;
}

可以看到，一个dict存在两个hash表结构（本质是数组）

哈希表结构
typedef struct dictht {
    //哈希表数组
    dictEntry **table;
    //哈希表大小
    unsigned long size；
    //哈希表大小掩码，用于计算索引值，总之等于size-1
    unsigned long sizemask;
    //该哈希表已有节点的数量
    unsigned long used;
}

table是一个数组，数组中的每个元素都是指向dictEntry结构的指针，每个dictEntry保存这一个键值对

hash节点结构
typedef struct dictEntry {
        //键
        void *key;
        //值
        union {
            void *val;
            uint64_tu64;
            int64_ts64;
        }v;
        //指向下一个hash节点，形成链表
        struct dictEntry *next;
} dictEntry;

这里可以看到，redis使用了拉链法来处理hash冲突

我们可以看到上面的结构，每个dict都会存在两张hash表。由于存在哈希冲突，另外一张表的作用是在装载因子（used/size）过大或过小时，进行rehash时使用的。首先，rehash会对hash表的size进行调整（增大或者缩小，但都保持2^n）, 且这个过程是渐进式的. 也就是说，这个过程可能会持续很长一段时间，问题就出在这个地方。

rehash导致的问题

如果我们的keys同学支持了limit，上一次游标如果是100.下次从100开始继续获取时，在这个间隔中dict可能正在进行rehash操作，101对应的键值对可能已经迁移到了另一张hash表中，如果仍然按照现有的游标来进行便利，会发生什么呢接下来我们就来复现一下这个问题：首先我们知道，一般的hash表实现方式，

//键值
string key = "USER_PHONE_123";
//根据键值计算hash值
hash_id = hashFunc(key);
//计算hash表掩码
mask = size(hash_table) - 1;
//获取hash值对应的索引值
idx = hash_id % mask;

可以看到，基本操作是hash值与掩码值取模，换算为二进制，即时hash_id |= ~mask 举个例子，如果table_size为8时，则所有的hash_id二进制形式的后三位则为其索引值。如果按照正常的顺序进行迭代，哈希表容量分别为8和16时，idx的迭代过程如下：

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

哈希表的扩展

字典扩展情况下，当前字典哈希表的容量为8，假设在迭代完索引010的bucket之后，按理说下一个应该迭代011，此时注意了，如果这个时候我去上了个厕所，在这期间，字典容量扩容成了16。而011这个索引，在扩容为16的情况下，变为了0011或者1011，而之前已经迭代过得索引是 000，001，010 扩展到16之后，分别对应的是， 0000，1000 0001，1001 0010，1010 此时如果将游标移到0011和1011分别进行迭代的话，会依次迭代 0100，0101，0110，0111，1000，1001，1010，1011，1100，1101，1110，1111，0000 可以看到，其中0000，1000，1001，1010的bucket被重复迭代了

哈希表的收缩

字典收缩情况下，当前字典哈希表容量为16，假设在迭代完0100之后，我又去上了个厕所，这期间字典收缩为了8，下一个要迭代的bucket为0101，在容量为8时，下一个要迭代的bucket是101. 容量为16时，尚未迭代的索引为： 0101，0110，0111，1000，1001，1010，1011，1100，1101，1110，1111 而这些索引收缩后，分配到新的bucket中的索引为： 000，001，010，011，100，101，110，111 目前的索引为101，那么这个索引之前的 000，001，010，011，100 这些索引就不会迭代到了。因此某些节点被漏掉了。

这下我们就知道了，为什么keys同学没有办法支持limit了

那么，scan命令是如何保证在rehash过程中，迭代返回的数据不会遗漏呢？

解决

直到有一天，有个叫Pieter Noordhuis的男人，提出了一个叫做reverse binary iteration的算法，简单来说就是反转二进制迭代。这个算法，其实作者本人也没有明确的证明出这个算法的正确性。

antirez: Hello @pietern! I’m starting to re-evaluate the idea of an iterator for Redis, and the first item in this task is definitely to understand better your pull request and implementation. I don’t understand exactly the implementation with the reversed bits counter… I wonder if there is a way to make that more intuitive… so investing some more time into this, and if I fail I’ll just merge your code trying to augment it with more comments… Hard to explain but awesome. pietern： Although I don’t have a formal proof for these guarantees, I’m reasonably confident they hold. I worked through every hash table state (stable, grow, shrink) and it appears to work everywhere by means of the reverse binary iteration (for lack of a better word).

具体可以参考Add SCAN command #579 这一长篇的讨论，详细阐述了这个反转二进制迭代的算法：

反转二进制算法

首先可以看下scan命令的主要源码：

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

可以把源码中的主要逻辑拆出来，进行一个简单的测试，先观察下其主要行为

#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位，其余位全为1
        v |= ~m0;
        //二进制进行翻转
        v = rev(v);
        //对二进制进行加1操作
        v++;
        //再次翻转
        v = rev(v);
        printBits(v, tablesize);
    }while (v != 0);
    printf("\n");
}


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

打印出迭代过程为：

$ 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算法的主要思想是，每次想游标的最高位加1，并向地位方向进位。比如0010的下一个数是1001，1101的下一位是0011。为什么要采用这种操作呢？我们还是看下采用这种迭代方法过程中，dict进行rehash的情况

哈希表的扩展

当hash表的容量为8时，进行迭代操作，当迭代了010游标之后，我起身去上了个厕所，这个时候dict进行了rehash，且容量扩展到了16。正常来说，下一个要迭代的索引是011，该索引扩展到新的哈希表中对应的索引为0011，1011，且这两个索引是相邻的。容量为8时，迭代过的索引为 000，100，010 扩展容量为16时，之前迭代过的索引会转移到以下索引的bucket中： 0000，1000，0100，1100，0010，1010 而这些索引，都是在0011和1011之前，换句话说，按照现在得到的索引向下迭代时，不会有遗漏的bucket

哈希表的收缩

当hash表的容量为16时，我们同样进行迭代操作，当迭代了0100索引之后，我起身上了个厕所，这个期间dict进行了rehash，且容量收缩为了8，下一个要迭代的索引为1100，而容量为8时，下一个要迭代的索引为100. 容量为16时，已经迭代过的索引为 0000，1000，0100 对应容量为8的hash表，其索引为 000，000，100 且这些索引都在100这个索引之前，换句话说，按照现在得到的索引向下迭代时，也不会漏掉bucket。

总结

目前来看，scan命令可以保证返回结果的完整性，但是少数情况下会存在元素的重复，这一点可以由应用层处理

本文源码基于redis3.0

至此，我们了解到了这种reverse binary iteration算法的原理，撒花~

两者区别 rehash时机和频率惰性rehash