首页 > C/C++, Redis > 让人爱恨交加的Redis Scan遍历操作原理

让人爱恨交加的Redis Scan遍历操作原理

2018年5月19日 发表评论 阅读评论 11051次阅读    

还记得,深夜,你在Redis 命令行里敲入"keys *" 后,线上开始报警,然后只能举起双手焦急的等待几千万key被慢慢扫描几十分钟还没结果,束手无策的时候,你跟所有redis用户拥有同样的心声:“就不能温柔点让我遍历一遍所有的数据吗?”
要知道,遍历一下数据库里面的所有数据,是多么理所应当的要求,这在mysql等关系型数据库眼里是多么的不可理解的。

终于,Redis在2.8.0版本新增了众望所归的scan操作

从此再也不用担心敲入了keys*, 然后等着老板的痛骂了···命令的官方介绍在这里, 中文版由huangz同学细心翻译了,作者Antirez的介绍在这里:Finally Redis collections are iterable (又想到了之前他那次机器down机的事故了,感兴趣的google)。
不过,故事还没结束,不像一般的遍历操作那么简单,Redis的SCAN操作由于其整体的数据设计,无法提供特别准的scan操作,仅仅是一个** “Can ‘ t guarantee , just do my best” **的实现,优缺点如下:
优点:
- 提供键空间的遍历操作,支持游标,复杂度O(1), 整体遍历一遍只需要O(N)
- 提供结果模式匹配
- 支持一次返回的数据条数设置,但仅仅是个hints,有时候返回的会多;
- 弱状态,所有状态只需要客户端需要维护一个游标;
缺点:
- 无法提供完整的快照遍历,也就是中间如果有数据修改,可能有些涉及改动的数据遍历不到
- 每次返回的数据条数不一定,极度依赖内部实现;
- 返回的数据可能有重复,应用层必须能够处理重入逻辑;

所以结论是Scan是一个不错的但也让人又爱又恨的命令···。

下面来介绍一下代码,着急的同学直接下拉到最后就行
首先scanCommand 函数处理简单的scan操作,其他类似hscan函数跟这个的区别就是hscan需要取获取一遍key对应的空间或者说域,他们主要都是借用了通用的scan操作函数:scanGenericCommand 。
scanGenericCommand 函数分4步:
- 解析参数,比如count, match匹配参数;
- 做真正的key扫描
- 进行结果的过滤
- 将收集到的数据返回给客户端
Redis为了性能考虑,对于小数据结构会转换为ziplist,intset数据结构因此需要区分这2类,对于后者,由于其本身比较小,因此可完全可以在这一次scan操作的时候返还所有的数据,反正不大的。另外一类就是正常的hash表所代表的扫描了,其扫描路径比较复杂。

dictScan扫描key

    /* Handle the case of a hash table. */
    ht = NULL;
    //···键扫描
//由于redis的ziplist, intset等类型数据量挺少,所以可用一次返回的。下面的else if 做这个事情。全部返回一个key 。
    if (ht) {
//一般的存储,不是intset, ziplist
        void *privdata[2];
        privdata[0] = keys;
        privdata[1] = o;
        do {
//一个个扫描,从cursor开始,然后调用回调函数将数据设置到keys返回数据集里面。
            cursor = dictScan(ht, cursor, scanCallback, privdata);
        } while (cursor && listLength(keys) < count);     } else if (o->type == REDIS_SET) {
        int pos = 0;
        int64_t ll;
//将这个set里面的数据全部返回,因为它是压缩的intset,会很小的。
        while(intsetGet(o->ptr,pos++,&ll))
            listAddNodeTail(keys,createStringObjectFromLongLong(ll));
        cursor = 0;
    } else if (o->type == REDIS_HASH || o->type == REDIS_ZSET) {
//那么一定是ziplist了,字符串表示的数据结构,不会太大。
        unsigned char *p = ziplistIndex(o->ptr,0);
        unsigned char *vstr;
        unsigned int vlen;
        long long vll;
        while(p) {
//扫描整个键,然后全部返回这一条。并且返回cursor为0表示没东西了。其实这个就等于没有遍历
            ziplistGet(p,&vstr,&vlen,&vll);
            listAddNodeTail(keys,
                 (vstr != NULL) ? createStringObject((char*)vstr,vlen) : createStringObjectFromLongLong(vll));
            p = ziplistNext(o->ptr,p);
        }
        cursor = 0;
    } else {
        redisPanic("Not handled encoding in SCAN.");
    }

上面简单的地方在于如果这个键是已REDIS_SET或者REDIS_HASH或者REDIS_ZSET行事存储的话,那么只需要扫描所有的键,然后一个个将其加入到临时的列表里面,以备返回给客户端。随后第三步就是进行结果的过滤了,一般就是用match参数代表的字符串去做匹配,看是否需要过滤数据。

最难的地方在于dictScan 函数,里面是各种位运算,也是redis SCAN操作最有价值(也是最难懂的部分)。

dictScan 原理

关于这个算法的源头,来自于githup这里:"Add SCAN command #579" https://github.com/antirez/redis/pull/579 ,长篇的讨论,确实难懂····建议看看这帖子,antirez 跟pietern 关于这个奇怪算法的讨论···
这个算法的作者是:Pieter Noordhuis,作者称其为:reverse binary iteration ,不知道我一对一翻译为“反向二进制迭代器”可不可以,不过any way ··作者自己也没有明确的证明其真假:

antirez: Hello @pietern! I’m starting to re-evaluate the idea of an iterator for Redis····
pietern: Although I don’t have a formal proof for these guarantees, I’m reasonably confident they hold. ···

下面从零开始讲一下redis的迭代器应该怎么设计,以及为什么不这么设计,而要这么设计·····

0.可用性 保证(Guarantees)

  • 迭代结果可以重复;
  • 整个迭代过程中,没有变化(增加删除)过的key必须出现在结果中;
  • redis的key是用hash存在的,key分布在数组的槽位内,下标从0到2^N,并且采用链表解决冲突。
  • hash会自动扩容或者缩小,并且每次 都是按2^N变化的。具体可以参阅:Redis源码学习-Dict/hash 字典(http://chenzhenianqing.cn/articles/845.html)。

1.最简单暴力的方法:顺序迭代

这个简单,从0到2^N下标扫描一次,每次返回一个slot(槽位,也就是数组的一项,下同)或者多个slot的数据,这样实现非常简单,在不发生rehash的时候,这种方法没问题,能够完成前面的要求。,但有以下问题:
1. 如果后来字典扩容了,比如2,4倍长度,那么能够保证一定能找出没变化的key,但是却会出现大量重复。
比如当前的key数组大小是8,后来变为16了,比如从0,1,2,3““顺序扫描,如果数组发生扩容,那么前面的0,1,2,3 slot里面的数据会发生一部分迁移到对应的8,9,10,11 slot里面去,并且这个量挺大;
2. 如果字典缩小了,比如从16缩小到8, 原先scan已经遍历了0,1,2,3 ,然后发生缩小,这样后来迭代停止在7号slot,但是8,9,10,11这几个slot的数据会分别合并到0,1,2,3里面去,从而scan就没有扫描出这部分元素出来,无法保证可用性;
3. 在发生rehashing的过程中,这个肯定有问题的。

中间的改进版本:

为了避免上面第一种方法中第1个问题,也就是大量重复的问题,我们可以改进为这样迭代扫描:如果字典大小为8, 那么扫描的时候,总是这么扫描:0,4, 1,5, 2,6, 3,7, 也就是访问完i 后,再访问i+2^(N-1), 这样如果已经访问过0,4, 1,5 了,当访问完2号slot之后,发生了扩容,变成了字典大小是6, 那么我们不需要再次去访问8,9号了,原因是8,9号里面的数据一定是从0和1里面迁移过去的。
但很可惜,这样还是无法解决字典缩小的时候没有访问问题,比如访问完0后,发生字典缩小,原来8号的数据迁移到了0号,然后按照算法,会去访问4号的。这样就会有问题。

2.redis的反向二进制位迭代器原理

先从直观感觉上,跟第二种方法类似的跳跃扫描,但是redis的方法更加完善。下面一步步的来介绍一下redis的SCAN原理。
首先我们知道,这个迭代操作有下面几种情况需要注意:
- 字典大小不变的时候;
- 字典大小扩容的时候 ;
- 字典大小缩小的时候;
- 发生rehash的时候;
对于最简单的时候,也就是没有发生字典大小变化,那么最简单了,按照redis现在的方式处理如下,然后再扩展到redis怎么处理变化的时候。
先看一下代码:

unsigned long dictScan(dict *d, unsigned long v, dictScanFunction *fn, void *privdata){
    if (!dictIsRehashing(d)) {//没有在做rehash,所以只有第一个表有数据的
        t0 = &(d->ht[0]);
        m0 = t0->sizemask;
//槽位大小-1,因为大小总是2^N,所以sizemask的二进制总是后面都为1,
//比如16个slot的字典,sizemask为00001111
        /* Emit entries at cursor */
        de = t0->table[v & m0];//找到当前这个槽位,然后处理数据
        while (de) {
//将这个slot的链表数据全部入队,准备返回给客户端。
            fn(privdata, de);
            de = de->next;
        }
    } else {
        do {
//扫描大点的表里面的槽位,注意这里是个循环,会将小表没有覆盖的slot全部扫描一次的
            de = t1->table[v & m1];
            while (de) {
                fn(privdata, de);
                de = de->next;
            }
//下面的意思是,还需要扩展小点的表,将其后缀固定,然后看高位可以怎么扩充。
//其实就是想扫描一下小表里面的元素可能会扩充到哪些地方,需要将那些地方处理一遍。
//后面的(v & m0)是保留v在小表里面的后缀。
//((v | m0) + 1) & ~m0) 是想给v的扩展部分的二进制位不断的加1,来造成高位不断增加的效果。
            v = (((v | m0) + 1) & ~m0) | (v & m0);
        } while (v & (m0 ^ m1));//终止条件是 v的高位区别位没有1了,其实就是说到头了。
    }
    v |= ~m0;
//按位取反,其实相当于v |= m0-1 , ~m0也就是11110000,
//这里相当于将v的不相干的高位全部置为1,待会再进行翻转二进制位,然后加1,然后再转回来
    v = rev(v);
    v++;
    v = rev(v);
//下面将v的每一位倒过来再加1,再倒回去,这是什么意思呢,
//其实就是要将有效二进制位里面的高位第一个0位设置置为1,因为现在是0嘛
    return v;
}

字典大小不变扫描

假设字典大小为16,那么redis 的slot扫描顺序为:
字典大小不变
细心的可以发现一个规律,就是可以两两分组,并且互相相差正好是16/2= 8。 对,这个是为了后面设计的。
我们来看一下其二进制位的变化,如下,可以看出其两两的差异在于高位不一样,算法会依次从高位开始尝试0和1的变化:
字典大小不变2
来说一下它的好处,这种方法还可以这样描述:

依次从高位(有效位)开始,不断尝试将当前高位设置为1,然后变动更高位为不同组合,以此来扫描整个字典数组。
这里我们肯定是一定能够扫描完整个数组的,不会漏。但其最大的好处在于,从高位扫描的时候,扫描的临近的2个元素都是相关的就是说同模的,比如0%4 == 4%4, 1%4 == 5%1 , 因此想到其实hash的时候,跟模是很相关的。
我们可以来走一遍代码,正常情况下,SCAN从0开始,假设字典大小为8,那么dictScan代码中字典肯定不是在做rehashing,所以进入第一个if,直接将table[v & 8] 里面的链表节点返回给客户端。然后计算下一个scan的游标,计算代码如下:

//v == 0 ,也就是0000 0000 , m0是size == 8时的掩码,也就是0000 0111
v |= ~m0; //~m0按位取反,为1111 1000 , 跟v做或得到v的新值为  1111 1000
v = rev(v);//将V的每一位反过来,得到 0001 1111
v++; //这个是关键,加1,注意其效果,得到0010 0000 , 什么意思呢?对一个数加1,其实就是将这个数的低位的连续1变为0,然后将最低的一个0变为1,其实就是将最低的一个0变为1
v = rev(v);//再次反过来,得到了:0000 0100  , 十进制就是4 , 正好跟上面的吻合

这里来体味一下,上面反转,然后加1,然后再反转,整体效果其实就是想将有效位中,从高位开始的第一个0之上的1变为0,将第一个碰到的0变为1, 或者说尝试将0变为1的slot。
更细致的说,上面的例子,是将0变为了1,效果就是scan的游标从0升为4,升到一个对应的高槽位去。下面来看一下从高槽位回到低位的过程,也就是将高位1设置会0,的过程:

//v == 4 ,也就是0000 0100 , m0是size == 8时的掩码,也就是0000 0111
v |= ~m0; //~m0按位取反,为1111 1000 , 跟v做或得到v的新值为  1111 1100
v = rev(v);//将V的每一位反过来,得到 0011 1111
v++; //这个是关键,加1,注意其效果,得到0100 0000
v = rev(v);//再次反过来,得到了:0000 0010  , 十进制就是2

注意上面本来游标等于0000 0100 , 到最后的结果变为,从高位开始,第一个1变为了0,随后的0变为了1. 其实就是说,从4,降到了2,也就是开始新的一个搭配。因为最高位已经尝试过了,0->4是将最高位的0变为1的过程,现在应该轮到次高位了。不太明白的话可以再一步步走一遍,在纸上写一下整个计算过程,多几次就清楚了。
这种情况下既能够保证未改动的key一定存在,并且只会存在一次;

当字典大小扩大的时候扫描

这里假设变化之前,字典大小为8,后来扩大为16了。具体的流程为:
0. scan 0 扫描,后来依次扫描了0,最后游标返回为4 ;
1. 发生字典扩容以及rehashing,并且完成了;
2. 客户端发送scan 4的指令过来;
当前的情况如下:
当字典大小扩大的时候
原先0号下 链表的元素被分拆到了0或者8号新slot, 取决于对应key的hash值第4位为0还是1,;但这个在上面的第一步返回给客户端了,所以后续的迭代是不需要返回的。
至于4号,此时scan 4, 那么redis会先将4的下标的链表元素返回给客户端,然后计算下一个slot,注意此时的计算不一样了,因为有效位掩码不一样了,多加了一位高位1. 因此这次返回的游标不再是2,而应该是12了。看下面的计算过程:

//v == 4 ,也就是0000 0100 , m0是size == 16时的掩码了,所以就是0000 1111
v |= ~m0; //~m0按位取反,为1111 0000 , 跟v做或得到v的新值为  1111 0100
v = rev(v);//将V的每一位反过来,得到 0010 1111
v++; //这个是关键,加1,注意其效果,得到0011 0000 , 也就是讲上面的0010 1111的后面所有的连续1换成0,第一个1换成1
v = rev(v);//再次反过来,得到了:0000 1100  , 十进制就是4+8 = 12.

根据上面的计算,访问4之后,自然的就过度懂啊了8,而不是之前的12,因为之前的4号的数据迁移到了4或者8号,必须扫描迁移到8号的元素,否则就会出现漏掉的key。这种情况下,访问到的key不会多也不会小,因为原先访问的0现在分到了0和8,但已经访问过了,因此自然的从4号开始访问就行了。
这里再考虑一下第二种情况,如果扩容后,游标不是在4上,而是在2上,也就是在一个高位为0的上面,假设已经访问完了0,4,返回游标2,此时发生了扩容并且已经完成,size变为16了。此时0和4都不需要访问了。下一个访问2号,并且计算下一个slot是多少:

//v == 2 ,也就是0000 0010 , m0是size == 16时的掩码了,所以就是0000 1111
v |= ~m0; //~m0按位取反,为1111 0000 , 跟v做或得到v的新值为  1111 0010
v = rev(v);//将V的每一位反过来,得到 0100 1111
v++; //这个是关键,加1,注意其效果,得到0101 0000 , 也就是讲上面的0100 1111的后面所有的连续1换成0,第一个1换成1
v = rev(v);//再次反过来,得到了:0000 1010  , 十进制就是2+8 = 10.

由于0,4号slot已经访问完毕,当前还没有访问的4号,也已经发生了迁移,有一部分高位为1的跑到了2+8 = 10 号slot 上面了。所以扫描完2后,需要自然的去迭代10号下标,不漏掉一个key。后续10号访问完成后,应该将是:6,然后14,一次继续就行了。跟上面的类似。
总结一下,对于字典大小扩大的情况,redis是是这样解决的:先访问n号slot,然后再访问n+2^N,因为这里面的元素其实都是从老的8个size的2号slot拆分到了2个slot,后面就需要访问这2个地方才行。正好这个算法支持这个。
这一点,redis scan保证了什么呢?保证了没有发生增删的操作的key一定能够找到;
在这种情况下,没变过的key一定能够返回,数据不会出现2次;

当字典大小缩小的时候扫描

这块跟扩大的时候类似,就多说了。
总结一下当数组发生缩小的时候,会发生的事情:照样能够保证key没变动过的数据一定能够扫描出来返回; 另外由于要高位会合并到低位的slot里面,所以会发生重复,重复的数据是原先在4里面的所有数据。

在rehashing的过程中扫描

前面讨论的情况都是没有遇到在rehashing的过程中,都是扩容或者缩小的时候都没有请求到来。这里来简单讨论一下发生rehashing的过程中,接受到的SCAN该怎么处理;
redis处理这个情形的方法很简单: 干脆就一次查找字典里面的2个表,一个临时扩容,一个就是主要的dict。免得中间的状态基本无法维护;所以这种情况下,redis会先扫描数据项小一点的表,然后就扫描大的表,将其2份数据和在一起返回给客户端。这样简单粗暴,但绝对靠谱。这种情况下,是不会出现丢数据,和重复的情况的。
但从dictScan 函数里面可以看到,为了处理rehashing,里面对于大点的表的处理有一个比较关键的地方,如下代码:

     do {
//扫描大点的表里面的槽位,注意这里是个循环,会将小表没有覆盖的slot全部扫描一次的
         de = t1->table[v & m1];
         while (de) {
             fn(privdata, de);
             de = de->next;
         }
//下面的意思是,还需要扩展小点的表,将其后缀固定,然后看高位可以怎么扩充。
//其实就是想扫描一下小表里面的元素可能会扩充到哪些地方,需要将那些地方处理一遍。
//后面的(v & m0)是保留v在小表里面的后缀。
//((v | m0) + 1) & ~m0) 是想给v的扩展部分的二进制位不断的加1,来造成高位不断增加的效果。
         v = (((v | m0) + 1) & ~m0) | (v & m0);
     } while (v & (m0 ^ m1));//终止条件是 v的高位区别位没有1了,其实就是说到头了。

上面的代码是个do-while循环,终止条件是游标v与 m0和m1的不同的位 之间没有相同的二进制位了。这里我们知道m0和m1一定都是低位全部为1的,因为字典大小为2^N。这样m0^m1的异或结果就是m1的相对m0超过的高位部分,打个比方,第一个ht表的大小为8,第二个为64, 那么m0 == 0000 0111, m1 == 0011 1111 , m0^m1 的结果是: 0011 1000,如下图:
在rehashing的过程中
其实就是想扫描m1和m0相差的那些高位。可能有人不禁会问,这个相差的高位不是只有1位么?其实不是的,rehashing的时候是可能2个表相差很大的。比如8 和64 。
上面do-while的前面部分是遍历第一个slot,小一点的。其实redis这里不管rehashing的方向,只管大小,反过来也是一样的。简化了逻辑;扫描完小一点的表后,需要将大一点的表进行扫描。

那么需要扫描哪些呢?答案是:所有可能从当前的小表的游标v所指的slot扩展迁移过去的slot,都需要扫描。比如当前的游标v等于0, 小表大小为8,大的表为64,那么需要扫描大表的这几个位置:0, 8, 16, 32。 原因是因为可能t0(小表)里面的一部分元素已经发生了迁移,仅仅扫描t0不够,还要扫描哪些可能的迁移目的地(来源,一样的)。如下所示,t0到t1大小从8变化到64之后,原来在0号slot的元素可能会迁移到了0, 8, 16, 24,32这几个t1的slot中。所以我们需要扫描这几个槽位,一次将其返回给客户端,免得夜长梦多,下次找不到地方了。
在rehashing的过程中
仔细观察可以发现,,他们都有个共同特点,从其二进制位中可以看出来:
在rehashing的过程中
也就是低位总是跟dictScan的参数v一样,高位从0开始不断加1 遍历,其实就是形成同模的效果,后缀一样,前缀不断变化加1,达到扫描所有可能的迁移slot,将其遍历返回给客户端。
这个遍历最主要的一行就是:

v = (((v | m0) + 1) & ~m0) | (v & m0);

下面简单分析一下它到底干了什么:
- 前面部分:(((v | m0) + 1) & ~m0) , v|m0就是将v的低位全部设置为1(这里所说的低位指t0的mask覆盖的位,高位指m1相对于m0独有的位。((v | m0) + 1)后面的+1 就是将(v | m0) 的值加1,也就是给v的高位部分加1。
- 后面的& ~m0效果就是去掉v的前面的二进制位。最后的(v & m0) 其实就是提取出v的低位部分。两边或起来,其实语义就是:保留v的低位,高位不断加1,赋值给v;这样V能带着低位不变,高位每次加1。高明!
这下清楚了,rehashing的时候会返回t0的槽位,以及t1里面所有可能发生迁移到的槽位。

总结

  1. SCAN操作能够保证 一直没变动过的元素一定能够在扫描结束的之前返回给客户端,这一点在不同情况下都可以实现;
  2. 当发生字典大小缩小的时候,如果接受到一个scan cursor, 游标位于高位为1的部分,那么会被有效位掩码给注释最高位,从而从重新读取之前已经访问过的元素,这种情况下回发生数据重复,但应该有限;
    整体来看redis的SCAN操作是很不错的,能够在hash的数据结构里面,不锁定库,稳定提供读写操作的前提下,提供比较稳定可靠的SCAN操作,不过大家再使用的时候最好知道他的优缺点,别太依靠scan做要求一致性太高的操作。
    后端服务开发就是这样,可选的框架,开源实现很多,最好知其所以然并高效利用其优点,少被缺点坑了最关键。

* PS, 不知道哪位同学能否分享一下《那些年,我们踏过的坑》 ^.^ *

Share
分类: C/C++, Redis 标签: ,
  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.

注意: 评论者允许使用'@user空格'的方式将自己的评论通知另外评论者。例如, ABC是本文的评论者之一,则使用'@ABC '(不包括单引号)将会自动将您的评论发送给ABC。使用'@all ',将会将评论发送给之前所有其它评论者。请务必注意user必须和评论者名相匹配(大小写一致)。