首页 > C/C++, Redis > Redis Scan迭代器遍历操作原理(一)–基础

Redis Scan迭代器遍历操作原理(一)–基础

2014年4月12日 发表评论 阅读评论 12272次阅读    

Redis在2.8.0版本新增了众望所归的scan操作,从此再也不用担心敲入了keys*, 然后举起双手看着键盘等待漫长的系统卡死了···

命令的官方介绍在这里, 中文版由huangz同学细心翻译了,作者Antirez的介绍在这里:Finally Redis collections are iterable (我又邪恶的想到了之前他那次机器down机的事故了···)。

具体的使用参考上面的链接即可,这里大概介绍一下Scan操作的实现原理。

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匹配参数;

第二部是需要去做真正的扫描键 的操作了,redis为了性能考虑,对于小数据结构会转换为ziplist,intset数据结构因此需要区分这2类,对于后者,由于其本身比较小,因此可完全可以在这一次scan操作的时候返还所有的数据,反正不大的。

另外一类就是正常的hash表所代表的扫描了,其扫描路径比较复杂,好吧,我看了好几次都没有看明白这到底是怎么扫描的,这几天啃也要啃出来!

    /* Handle the case of a hash table. */
    ht = NULL;
    if (o == NULL) {//键扫描
        ht = c->db->dict;
    } else if (o->type == REDIS_SET && o->encoding == REDIS_ENCODING_HT) {
        ht = o->ptr;
    } else if (o->type == REDIS_HASH && o->encoding == REDIS_ENCODING_HT) {
        ht = o->ptr;
        count *= 2; /* We return key / value for this type. */
    } else if (o->type == REDIS_ZSET && o->encoding == REDIS_ENCODING_SKIPLIST) {
        zset *zs = o->ptr;
        ht = zs->dict;
        count *= 2; /* We return key / value for this type. */
    }
//由于redis的ziplist, intset等类型数据量挺少,所以可用一次返回的。下面的else if 做这个事情。全部返回一个key 。
    if (ht) {//一般的存储,不是intset, ziplist
        void *privdata[2];

        /* We pass two pointers to the callback: the list to which it will
         * add new elements, and the object containing the dictionary so that
         * it is possible to fetch more data in a type-dependent way. */
        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;

        while(intsetGet(o->ptr,pos++,&ll))//将这个set里面的数据全部返回,因为它是压缩的intset,会很小的。
            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行事存储的话,那么只需要扫描所有的键,然后一个个将其加入到临时的列表里面,以备返回给客户端。

最难的地方在于dictScan 函数,里面是各种位运算。

随后第三步就是进行结果的过滤了,一般就是用match参数代表的字符串去做匹配,看是否需要过滤数据。

第四步就是将收集到的数据返回给客户端。然后就完成了请求。

dictScan  原理:

好吧,我看了2次,没看懂·····先做饭··

ps: 写着写着发现一篇文章写不完,所以令起一篇了:Redis Scan迭代器遍历操作原理(二)--dictScan反向二进制迭代器  , 希望能讲清楚.

Share
分类: C/C++, Redis 标签: ,
  1. kulv
    2017年10月22日13:41 | #1

    @螃蟹
    可以,谢谢了

  2. 螃蟹
    2015年2月28日14:58 | #2

    已经看懂了,再次给赞

  3. 螃蟹
    2015年2月28日11:11 | #3

    我可以把这篇博客转载走吗?

  4. 螃蟹
    2015年2月28日11:11 | #4

    没看懂为什么scan返回的结果会不完全,晕了~

  1. 2014年4月20日12:34 | #1

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