想要返回 redis 当前数据库中的所有 key 应该怎么办? 用 keys 命令? 在 key 非常多的情况下, 该命令会导致单线程 redis 服务器执行时间过长, 后续命令得不到响应, 同时对内存也会造成一定的压力, 严重降低 redis 服务的可用性
为此 redis 2.8.0 及以上版本提供了多个 scan 相关命令, 用以针对不同数据结构 (如数据库, 集合, 哈希, 有序集合) 提供相关遍历功能
SCAN http://redisdoc.com/key/scan.html#scan 命令及其相关的 SSCAN http://redisdoc.com/set/sscan.html#sscan 命令, HSCAN http://redisdoc.com/hash/hscan.html#hscan 命令和 ZSCAN http://redisdoc.com/sorted_set/zscan.html#zscan 命令都用于增量地迭代 (incrementally iterate) 一集元素(a collection of elements)
SCAN http://redisdoc.com/key/scan.html#scan 命令用于迭代当前数据库中的数据库键
SSCAN http://redisdoc.com/set/sscan.html#sscan 命令用于迭代集合键中的元素
HSCAN http://redisdoc.com/hash/hscan.html#hscan 命令用于迭代哈希键中的键值对
ZSCAN http://redisdoc.com/sorted_set/zscan.html#zscan 命令用于迭代有序集合中的元素(包括元素成员和元素分值)
SCAN
命令格式: SCAN cursor [MATCH pattern] [COUNT count]
SCAN http://redisdoc.com/key/scan.html#scan 命令是一个基于游标的迭代器(cursor based iterator): SCAN http://redisdoc.com/key/scan.html#scan 命令每次被调用之后, 都会向用户返回一个新的游标, 用户在下次迭代时需要使用这个新游标作为 SCAN http://redisdoc.com/key/scan.html#scan 命令的游标参数, 以此来延续之前的迭代过程
当 SCAN http://redisdoc.com/key/scan.html#scan 命令的游标参数被设置为 0 时, 服务器将开始一次新的迭代, 而当服务器向用户返回值为 0 的游标时, 表示迭代已结束
SSCAN http://redisdoc.com/set/sscan.html#sscan / HSCAN http://redisdoc.com/hash/hscan.html#hscan /ZSCAN http://redisdoc.com/sorted_set/zscan.html#zscan 与 SCAN 命令除命令格式有细微不同以及在非哈希表实现下的遍历方式不同外, 其他均类似, 不再赘述, 具体请点击链接查询
保证: 从完整遍历开始直到完整遍历结束期间, 一直存在于数据集内的所有元素都会被完整遍历返回
缺点: 1)同一个元素可能会被返回多次, 在 rehash 缩小后遍历或者 rehash 缩小过程中遍历可能发生此情况 (个人理解) 2) 如果一个元素是在迭代过程中被添加到数据集的, 又或者是在迭代过程中从数据集中被删除的, 那么这个元素可能会被返回, 也可能不会, 这是不确定的
注: 以上内容摘自 http://redisdoc.com/key/scan.html
对于 SCAN 命令和底层采用了哈希表实现的集合, 哈希, 有序集合, 遍历时采用了同样的 scan 算法(都会调用 dictScan 函数),dictScan 函数短小精悍, 正是本文尝试解释的核心, 如下
- unsigned long dictScan(dict *d,// 待遍历哈希表
- unsigned long v,//cursor 值, 此次遍历位置, 初始为 0
- dictScanFunction *fn,// 单个条目遍历函数, 根据条目类型, copy 条目对象, 以便加入到返回对象中
- dictScanBucketFunction* bucketfn,//null
- void *privdata)// 返回对象
- {
- dictht *t0, *t1;
- const dictEntry *de, *next;
- unsigned long m0, m1;
- if (dictSize(d) == 0) return 0;// 如果 dict 为空, 直接返回
- if (!dictIsRehashing(d)) {// 如果此刻哈希表没有在 rehashing, 只有 ht[0]有数据
- t0 = &(d->ht[0]);// 将 ht[0]作为遍历表
- m0 = t0->sizemask;// 遍历表的 sizemask, 即以遍历表的 size 为底取模, 如表大小为 8, 则 m0 为 111
- /* 遍历 cursor 所在位置的所有条目 */
- if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);// 这行 if 条件为 false, 不会执行
- de = t0->table[v & m0];
- while (de) {// 遍历当前 cursor 位置的所有条目, 即 hash key 取模 hash table 大小相同的所有条目
- next = de->next;
- fn(privdata, de);
- de = next;
- }
- /* 作用是将 v 也就是 cursor 的高位置为 1, 低位不变, 如 v 为 001, 则改为 61 个 1 再加 001 */
- v |= ~m0;
- /* 将 cursor 高位 0 变成 1 或者(连续高位 1 都变成 0 且第一个 0 变为 1) */
- v = rev(v);// 将 cursor 做二进制逆序, 也就是变成 100+61 个 1
- v++;// 末位加 1, 也就是 101+61 个 0
- v = rev(v);// 将 cursor 做二进制逆序, 也就是 61 个 0+101
- } else {// 哈希表正在 rehashing
- t0 = &d->ht[0];
- t1 = &d->ht[1];
- /* 确保 t0 小 t1 大 */
- if (t0->size> t1->size) {
- t0 = &d->ht[1];
- t1 = &d->ht[0];
- }
- m0 = t0->sizemask;//t0 表 sizemask, 如表大小为 8, 则 m0 为 7, 即 0111
- m1 = t1->sizemask;//t1 表 sizemask, 如表大小为 64, 则 m1 为 63, 即 00111111
- /* 将 cursor 位置的所有条目都添加进去 */
- if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);// 不执行
- de = t0->table[v & m0];
- while (de) {// 将 t0 的所有条目都加进去
- next = de->next;
- fn(privdata, de);
- de = next;
- }
- /* 遍历小表 cursor 位置可能会 rehash 到大表的所有条目,
- * 如 cursor 为 1, 小表大小为 8, 大表大小为 64, 则 0,8,16,24,32,40,48,56 等位置的条目都会被添加返回
- */
- do {
- /* 添加大表 v 位置的所有元素, 注意 v 位置跟着 while 循环不断变化 */
- if (bucketfn) bucketfn(privdata, &t1->table[v & m1]);// 不执行
- de = t1->table[v & m1];
- while (de) {// 添加 v 位置的所有条目
- next = de->next;
- fn(privdata, de);
- de = next;
- }
- /* 作用同上, 只不过换成了大表的元素, 也就是小表 cursor 位置可能扩展到大表的所有位置 */
- v |= ~m1;
- v = rev(v);
- v++;
- v = rev(v);
- /* 如上举例, m0 为 3 位 1,m1 为 6 位 1, 二者做异或, 也就是将二者不同的高位置为 1,
- * 其他前后的 61 位均为 0, 然后遍历 v 在二者不同高位的所有可能,
- * 当 v 重新回到 0 时, 跳出 while 循环 , 也就是将 m0 可能 rehash 到的 m1 位置的条目全部返回
- */
- } while (v & (m0 ^ m1));
- }
- return v;
- }
这个算法非常精妙, 看了挺久才明白点意思, 如有不当之处, 欢迎拍砖
哈希表有多种状态, 遍历时有可能处于
哈希扩展后
收缩后
正在 rehashing(扩展 or 收缩)中
这就使得 scan 算法面临的情况很复杂, 怎样遍历完所有元素 (遍历过程中没有发生变化的元素保证遍历完) 且尽可能少的返回重复元素是个难题 三种状态具体的遍历流程图示推演发个传送门: Redis Scan 迭代器遍历操作原理(二)-dictScan 反向二进制迭代器 http://chenzhenianqing.com/articles/1101.html (网上搜的, 流程很长, 慎点, 但是有一些不错的图)
具体算法流程也可参见上面的源码注释
算法思想(把收缩看成反向的扩张)
1, 假设 hash 表大小从 N 扩张为 2^M x N(哈希表大小只可能为 2 的幂数, N 也为 2 的幂数), 那么原先 hash 表的 i 元素可能被分布到 i + j x N where j <- [0, 2^M-1]位置, 如 N 为 4,M 为 3, 则 i(原先为 1)可能被分散到 1,1+1x4,1+2x4...,1+7x4 位置, 注意这些位置, 它们后面的 log(N)位是相同的, 也就是前面的 M 位不同, 如
- 00001
- 00101
- 01001
- ...
- 11101
如果在扩展后遍历的过程中能将后面两位相同都为 01 的位置都忽略, 也就是只要后面 N 位相同的遍历完了, 意味着前面 M 位的所有可能性也都列举完了, 即总是先把前面的可能性穷举完, 再穷举后面的位, 那么扩展后的 slot(如 1 对应的 1,5,9...,29)就不必重新再重新遍历一遍了, 收缩是类似的, 只不过收缩后的位置可能包含原哈希表高位尚未穷举完的可能性, 需要再次遍历
2, 怎么先遍历高位的可能性, dictScan 给出了反向二进制迭代算法(总是先将最高位置取反, 穷举高位的可能性, 依次向低位推进, 这种变换方式确保了所有元素都会被遍历到):
将第一个遇到的高位 0 对应的位置置 1(即变换前后二者拥有最多的从右向左连续相同低位, 也就是模相同的范围最大), 在该规则下, 32 大小哈希表, 00001 遍历后的下一个位置是 10001, 如果下次遍历 10001 时哈希表收缩成 16 大小, 则会重新遍历 0001 位置(10001 与 16 取模),00001 和 10001 都收缩到了该位置, 这种情况下元素可能重复返回; 如果 32 扩展为 64, 则 00001 扩张为 000001/100001 两个位置, 由于高位穷举的原则, 则后续这些位置不会再次处理, 降低了元素重复返回的概率
或将前面的连续 1 置为 0, 第一个 0 置为 1, 如 10001 下一个是 01001, 即开始穷举下一个高位的可能性
3,rehashing 这种情况, 需要在遍历完小表 cursor 位置后将小表 cursor 位置可能 rehash 到的大表所有位置全部遍历一遍, 然后再返回遍历元素和下一小表遍历位置
来源: https://juejin.im/post/5b262159e51d45587f49f6f4