Redis的核心数据结构dict（字典）是支撑字符串键空间、哈希对象、集合对象等功能的底层基石。这个结构最值得称道的设计之一，就是渐进式rehash。哈希表在扩容或缩容时，理论上需要把旧表所有节点重新计算哈希值再挂到新表上，如果字典里存了上千万个键，一次性搬运会让Redis这个单线程服务出现明显卡顿。Redis的解法是把整个迁移过程拆成无数个微小的步骤，分摊到每一次操作里慢慢做。这篇文章结合源码逐一拆解这个机制的实现细节。
一、dict的核心数据结构
要理解渐进式rehash，先得弄清楚dict长什么样。在dict.h中，字典结构由四个字段组成，其中最关键的是两个dictht哈希表和一个rehashidx索引。正常情况下只用ht[0]这一张表，ht[1]只在rehash进行中才会派上用场。
typedef struct dict {
dictType *type; // 类型特定函数，比如哈希函数、键比较函数
void *privdata; // 私有数据，传给类型特定函数的可选参数
dictht ht[2]; // 两张哈希表，rehash期间新旧共存
long rehashidx; // rehash进度，-1表示当前没有进行rehash
int iterators; // 当前运行中的安全迭代器数量
} dict;
typedef struct dictht {
dictEntry **table; // 哈希桶数组
unsigned long size; // 桶数量，总是2的幂
unsigned long sizemask; // size-1，用于取模定位桶下标
unsigned long used; // 已有节点数量
} dictht;
rehashidx是整个机制的灵魂。当它等于-1时，表示字典处于稳定状态，所有数据都在ht[0]里；一旦扩容开始，这个值被置为0，表示接下来要从ht[0]的第0个桶开始搬数据。每搬完一个桶，rehashidx就加1，直到ht[0]的全部数据搬空，rehashidx被重置回-1，ht[1]接管ht[0]的位置，一次rehash才算彻底结束。
另外值得留意的是sizemask的用法。Redis定位桶下标时用的是位运算hash & sizemask，这要求size必须是2的幂，位运算比取模快得多，这也是每次扩容都是翻倍的原因之一。
二、扩容与缩容的触发条件
是否需要rehash由_dictExpandIfNeeded函数判断，核心逻辑是计算负载因子，即used除以size。触发条件主要有以下几种情况：
- 没有执行BGSAVE或BGREWRITEAOF时，负载因子大于等于1就扩容；
- 正在执行BGSAVE或BGREWRITEAOF时，负载因子要大于等于5才扩容，这是为了尽量减少子进程存活期间的写时复制内存拷贝；
- dictCanResize开关被关闭时，同样使用高阈值5；
- 缩容则在serverCron定期检查时触发，当字典的填充率低于10%（used小于size的十分之一）时，收缩到恰好容纳used个节点的最小2的幂。
新表大小的计算规则很简单：扩容时取第一个大于等于used*2的2的幂，比如used是5000，则新size为16384。缩容时的目标大小同样是满足条件的最小2的幂，但不会小于初始的4。
这里有个容易被忽略的细节：为什么后台进程存在时要提高阈值？因为fork产生的子进程会共享父进程的物理内存页，Redis利用写时复制来节省内存。如果这时大量扩容rehash，每次写操作都会触发内存页复制，反而让内存占用暴涨。所以Redis宁可容忍更高的冲突率，也要推迟扩容。这个设计体现了对操作系统内存机制的深度理解。
三、渐进式迁移的完整流程
扩容决策做出后，dictExpand会为ht[1]分配空间并把rehashidx置为0，此后字典进入rehash状态。真正的搬运动作由_dictRehashStep和dictRehash两个函数配合完成。
int dictRehash(dict *d, int n) {
int empty_visits = n * 10; // 最多访问的空桶数量
while (n-- && d->ht[0].used != 0) {
dictEntry *de, *nextde;
// 跳过连续的空桶，避免长时间空转
while (d->ht[0].table[d->rehashidx] == NULL) {
d->rehashidx++;
if (--empty_visits == 0) return 1;
}
de = d->ht[0].table[d->rehashidx];
// 把该桶下所有节点搬到ht[1]
while (de) {
uint64_t h;
nextde = de->next;
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
d->ht[0].used--;
d->ht[1].used++;
de = nextde;
}
d->ht[0].table[d->rehashidx] = NULL;
d->rehashidx++;
}
// 检查是否已经搬完
if (d->ht[0].used == 0) {
zfree(d->ht[0].table);
d->ht[0] = d->ht[1];
_dictReset(&d->ht[1]);
d->rehashidx = -1;
return 0; // 表示rehash全部完成
}
return 1; // 表示尚未完成
}
渐进式的推进时机分布在两处。第一处是_dictRehashStep，它每次只搬一个桶，会在每次增删改查操作（dictAdd、dictFind、dictDelete等）调用时顺带执行，前提是没有安全迭代器在运行。第二处是serverCron里的定时任务dictRehashMilliseconds，默认每次执行1毫秒，在这1毫秒内尽可能多地搬100个桶一批的数据，即使字典完全空闲没有客户端访问，也能靠定时任务完成迁移。
注意代码里的empty_visits机制：如果ht[0]里有大片连续空桶（极端情况下可能几百万个），逐桶扫描会非常浪费时间，所以Redis规定单次rehash最多跳过n*10个空桶，超了就直接返回，把机会留给下一次调用。这是对最坏情况的一种防御。
四、rehash期间各类操作的走向
双表共存期间，所有操作的代码路径都要照顾两张表，这是渐进式rehash带来的复杂性：
查找操作：先根据rehashidx判断是否处于rehash状态，是的话先查ht[0]，找不到再查ht[1]，两张表都要算一遍哈希、走一遍链表。对应的实现在dictFind中，通过dictRehashStep在每次查找时还顺带搬一个桶。
新增操作：只往ht[1]插入，绝不再写ht[0]，这样保证ht[0]的used单调递减，迁移必然收敛。这个规则在dictAddRaw里体现为计算下标时直接使用ht[1]的sizemask。
删除和更新：先在ht[0]找，找不到再切到ht[1]，找到哪张表就在哪张表上操作。更新值不需要移动节点，只有删除会影响used计数。
迭代器：普通迭代器在遍历期间假设字典结构不变，所以持有迭代器时会禁止执行rehash step；安全迭代器则允许修改数据，但同样会暂停渐进式迁移。SCAN命令遍历大字典时依赖反转二进制游标算法来保证在rehash过程中不漏键、尽量少重复，这也是渐进式设计在命令层面配套的方案。
综合来看，这套机制用很小的代码复杂度换来了巨大的收益：无论字典多大，任何一次操作的耗时都是有上界的，Redis的主线程永远不会被一次哈希表扩容卡住。理解了dict的渐进式rehash，再看Redis的SCAN、随机事件采样、缩容逻辑等周边设计，都会豁然开朗。