0. preconditoin
本文简要介绍Redis Scan原理，在阅读本文前，你需要知道Redis有哪些命令包含scan，以及如何使用scan命令
index = hash(key) & sizemask <=> index = hash(key) % size
1. simple example of HSCAN
redis ip:port> hscan key 0 1) "0"2) 1) "1640797170" 2) "10004"
上面是一个hscan的简单例子，命令包含三个部分 =={command, key, cursor}==，返回两个部分=={cursor, value}==，其中cursor表示下一次遍历key的游标，下一次遍历需要用到redis返回的游标
Redis的Scan操作有如下两个主要特点
- 迭代结果可重复
- 整个迭代过程，没有变化过的key（增加或删除）一定会出现在结果中
2. simple implementation of SCAN
unsigned long scan(dict *d, unsigned long cursor, ...) { if (cursor >= d->ht[0].size) { return 0; // complete scan } bucket = d->ht[0].table[cursor]; // move all element of this bucket to reply cursor++; return cursor;} 上面这段伪代码展示最简单的实现方法，其原理如下：
- 假设整个SCAN期间，没有Key的变更（添加或删除）
- 从0开始，每次从哈希表中取一个槽，并返回这个槽所有元素
- cursor自增并返回，下次从这个cursor继续
- 如果遍历完整个哈希表，则重置cursor=0表示便利结束
当然，上面是理想的情况，实际情况可能是当cursor走到 size / 2 附近时Redis发生rehash，导致整个哈希表的长度变为了原来的一半，那么根据根据上面的条件 cursor >= d->ht[0].size，cursor只要达到原哈希表的一半就结束的遍历，这样会导致接近一半的元素没有被访问到，例如：
befor rehash: d->ht[0].size = 16, cursor = 8
after rehash: d->ht[0].size = 8, cursor = 8
result: stop scan
3. simple improve
unsigned long scan(dict *d, unsigned long cursor, ...) { if (cursor >= d->ht[0].size) { cursor = d->ht[0].size - 1; } bucket = d->ht[0].table[cursor]; // move all element of this bucket to reply cursor--; if (cursor < 0) { cursor = d->ht[0].size - 1; } return cursor;} 步骤如下：
- 从0开始遍历，每此返回一个槽的所有元素
- cursor自减
- 如果cursor小于零，则从哈希表的末尾开始往头遍历
- cursor为0表示遍历结束
很明显，这样处理的好处就是在哈希表折半的时候，如果cursor>d->ht[0].size时，可以从新哈希表的末尾继续往头遍历，防止丢失元素。而缺点就是会有大量的元素被重复遍历，不过这可以在应用层面进行处理，相比于丢失数据，冗余反而更容易让人接受
4. improve
上面的两种方法其实只针对了一种情况，那就是哈希表的折半，如果哈希表倍增，你会发现采用自增法会导致数据冗余，而递减法会导致数据丢失
那么有没有一种办法可以保证无论哈希表折半或是倍增时都不会丢失数据呢？
我们可以先来分析一下在rehash过程中，数据究竟发生了怎样的变化
- 首先我们需要知道redis的 hash size = 2^N，即表长永远是2的幂次方
- 每次rehash，表长一定是 size */ 2^N，即增长或缩减2的幂次方倍
- hash运算是模运算，即 hash % 8 = 1 or hash % 8 = 5 <=> hash % 4 = 1
从上面两种例子可以得出，当我们采用cursor递增策略的时候，如果size缩小，会有导致大量数据丢失的可能，例如：
size = 16, cursor = 1(此时0已经遍历完)，缩小后，size=8, cursor=1, index(8) and index(0) 聚合到了index(0)，我们继续从index(1)开始遍历，会丢失index(8)的数据
为了防止index(8)的数据丢失，我们可以先遍历完所有可能聚合到index(0)的槽，然后在从下一个没有遍历的索引开始遍历
unsigned long scan(dict *d, unsigned long cursor, ...) { if (cursor >= d->ht[0].size) { return 0; //compelete scan } bak = cursor; while (bak < d->ht[0].size) { // move all element of this bucket to client back = back + d->ht[0].size / 2; } cursor++; return cursor;} 假设 size = 16, 那我们的遍历顺序是 0->8->1->9->2->10->X 此时哈希表size缩小到8
接下来的遍历顺序就是 X->3->7->4->5->6->7->0
因为 8,9,10,11,12,13,14,15分别映射到了0,1,2,3,4,5,6,7， 我们已经遍历了0,1,2,8,9,10的数据，接下来从3开始，就可以遍历所有数据而不会有大量遗漏
不过由于我们无法判断每个槽是否已经被遍历，所以这样处理会导致哈希表后半部分的数据被重复遍历至少一次，这样就会导致大量数据冗余，且效率也会有所影响
5. Reverse Binary Iteration
假设size为8， 那么按照上面的算法，得到的遍历顺序将是 0->4->1->5->2->6->3->7->4->5->6->7->0 它其实由多个遍历组合构成 ：
0->41->52->63->74->5->6->7->000 (duplicated)
转换成二进制：
000->100 => 0->4001->101 => 1->5010->110 => 2->6011->111 => 3->7100->101->110->111->000 (duplicated)
如果我们变换一下其中某几对的顺序：
000->100 => 0->4010->110 => 2->6001->101 => 1->5011->111 => 3->7100->101->110->111->000 (duplicated)
然后构成一条新的遍历链 000->100->010->110->001->101->011->111->000
000 => 0100 => 4010 => 2110 => 6001 => 1101 => 5011 => 3111 => 7000 => 0
我们可以发现按照新的遍历顺序，其二进制表示具有一个明细的特点： 从左往右递增
用这种方便构成的遍历链，具有我们上一种发法的优点：保证不会有大量数据遗漏， 同时它保留了我们已经遍历的状态，根据简单变换既可以推算出下一个未遍历的索引，减少了数据的大量冗余与整个遍历所消耗的时间
这种遍历算法，就是Redis的dictScan的核心算法Reverse Binary Iteration(反向二进制迭代)
6. examples
-
当字典大小不变的时候，假设hash size = 8, 那么遍历顺序为
0->4->2->6->1->5->3->7->0，与顺序遍历没有什么区别-
当遍历过程中字典扩大，假设hash size = 8, rehash之后，hash size = 16，我们已经遍历了
0,4,2,6,1,5,3后此时cursor=7（111），然后在新表中得到的遍历顺序为7->15->0所以我们实际的遍历顺序是0->4->2->6->1->5->3->7->15->0也就是说rehash之后我们只遍历了新表的index(7) and index(15)我们把新表重新映射会旧表，就会发现新表中除了index(7)和index(15)之外，我们已经遍历了所有元素了
-
0->4->2->6->1->5->3->7-15->0000->100->010->110->001->101->011->111->rehash->0111->1111->0
-
当字典大小缩小的时候，假设hash size = 16, rehash之后hash size= 8，我们已经遍历了
0,8,4后cursor=12（1100），然后在新表中的遍历顺序为4->2->6->1->5->3->7->0，完整的遍历链如下;0->8->4->12->4->2->6->1->5->3->7->00000->1000->0100->1100->rehash->100->010->110->001->101->011->111->000
-
当Redis处理rehashing状态时，此时处理的思路就是先扫描较小的表，再扫描较大的表
从图中可以看到，如果hash表直接从size=8增加8倍到size=64，那么index(0) 将被分散到新表的index(0, 8, 16, 24, 32, 40, 48, 56)，用二进制可以更明显的看出规律
000 => 0 size = 8000000 => 0 size = 64100000 => 32010000 => 16110000 => 48001000 => 8101000 => 40011000 => 24111000 => 56
可以看出，扩增8倍其实就是左边增加3位，新旧元素的映射其实就是左边3位的所有组合+旧索引
所以此时的遍历顺序可以简单描述为 xxx000, xxx100, xxx010, xxx110, xxx001, xxx101, xxx011, xxx111, xxx000, 其中xxx为[000, 001, 010, 011, 100, 101, 110, 111]
xxx000xxx100xxx010xxx110xxx001xxx101xxx011xxx111xxx000
7. Redis Source Code
unsigned long dictScan(dict *d, unsigned long v, dictScanFunction *fn, dictScanBucketFunction* bucketfn, void *privdata){ dictht *t0, *t1; const dictEntry *de, *next; unsigned long m0, m1; if (dictSize(d) == 0) return 0; if (!dictIsRehashing(d)) { t0 = &(d->ht[0]); m0 = t0->sizemask; /* Emit entries at cursor */ if (bucketfn) bucketfn(privdata, &t0->table[v & m0]); de = t0->table[v & m0]; while (de) { next = de->next; fn(privdata, de); de = next; } /* Set unmasked bits so incrementing the reversed cursor * operates on the masked bits */ v |= ~m0; /* Increment the reverse cursor */ v = rev(v); v++; v = rev(v); } else { t0 = &d->ht[0]; t1 = &d->ht[1]; /* Make sure t0 is the smaller and t1 is the bigger table */ if (t0->size > t1->size) { t0 = &d->ht[1]; t1 = &d->ht[0]; } m0 = t0->sizemask; m1 = t1->sizemask; /* Emit entries at cursor */ if (bucketfn) bucketfn(privdata, &t0->table[v & m0]); de = t0->table[v & m0]; while (de) { next = de->next; fn(privdata, de); de = next; } /* Iterate over indices in larger table that are the expansion * of the index pointed to by the cursor in the smaller table */ do { /* Emit entries at cursor */ if (bucketfn) bucketfn(privdata, &t1->table[v & m1]); de = t1->table[v & m1]; while (de) { next = de->next; fn(privdata, de); de = next; } /* Increment the reverse cursor not covered by the smaller mask.*/ v |= ~m1; v = rev(v); v++; v = rev(v); /* Continue while bits covered by mask difference is non-zero */ } while (v & (m0 ^ m1)); } return v;}