Redis scan 在 rehash 过程中的行为研究

dict rehash

Redis 使用 C 语言编写，基于数组和哈希函数等实现了基本的字典结构，在数据增删的过程中，哈希表会存在扩容及缩容的问题，需要进行 rehash。Redis 是单进程模式，当数据库中键值对数量特别大，整个 rehash 过程将非常缓慢，会造成服务长时间不可用，Redis 采用了一种渐进式 rehash 的方式，即：

  1. 在增删改查前，如果正在进行 rehash，则只对一个节点进行 rehash 操作；
  2. 服务空闲时，如果需要进行 rehash 则进行批量 rehash（每次执行 1 毫秒批量操作 100 个节点）。

经过多次 rehash 操作后，旧表中的数据会全部迁入新表中。

Redis scan

在生产环境中，一般不能使用 keys 等操作，Redis 提供了间断式遍历操作 scan。由于 scan 是一种迭代操作，在迭代过程中字典可能会发生 rehash 过程：同一个槽位中的链表节点，经过 rehash 操作后可能会散列到不同的槽位中，不同槽位中的链表节点，也可能会被 rehash 到同一槽位中，因此，scan 过程中如果发生了 rehash 操作，输出的节点可能会重复，需要通过一定的手段避免这种情况。

根据 rehash 的时机，我们可以将情况分为两类：

  1. 两次迭代期间发生了 rehash 操作，字典进行了扩容或缩容；
  2. 某次或某几次操作中散列表正在进行 rehash 操作。

第一种情况，迭代器只在变更后的新表上进行操作；第二种情况，字典在 rehash 过程中，旧表的数据正在向新表进行迁移，需要同时处理两张表。

两次迭代期间发生 rehash

我们从扩容缩容的特点来分析 rehash 前后节点的变化，Redis 字典扩容及缩容都是按照倍数进行调整：

  1. 扩容时新申请内存空间为当前容量的两倍；
  2. 缩容时新申请内存空间为大于 used 的最小 2^N 整数。

扩容时，部分存在 hash 冲突的点会被散列到不同的槽位中，因此如果一个槽位在扩容前被输出了，那在扩容后，会有对应的两个槽位不应该被再次访问，Redis 采用了高位加 1 的方式来实现，设当前访问的槽位下标为 v，则访问的下一个位置的算法如下：

v |= ~m0;
v = rev(v);    // 二进制逆转
v += 1;
v = rev(v);    // 二进制逆转

举例说明，假设字典容量为 4，原始表的访问顺序为：

00->10->01->11，即 0->2->1->3

在访问 10 之前发生了扩容，容量变为 8，由于字典扩容的特点，扩容后，旧槽位中的链表节点 xx 会被散列到新槽位 0xx 和 1xx，我们将 xx 节点扩展为 0xx 和 1xx，由于 00 已经访问过，因此新表中 000 及 100 不能再被访问了，因为 00 中的节点在 rehash 后会被散列到 000 和 100 槽位中，我们使用高位加 1 的方式将新的访问顺序表示出来：

010->110->001->101->011->111

因此，Redis 利用了扩容后容量变化的特点，通过高位加 1 的方式确定访问位置，合理地规避了槽位多次访问造成的数据重复问题，不过无法完全避免缩容后输出的数据没有重复。

迭代时正在 rehash

rehash 过程中同时存在两张表，但两张表不存在重复数据，Redis 对小表使用高位加 1 的方式进行遍历，同时对大表进行遍历，从前面的分析很容易得知，小表的一个槽位对应大表中的两个槽位。

参考资料：

  1. Redis 5 设计与源码分析 —— 陈雷

Redis NoSQL