将哈希表迁移分散到多次操作
Redis 7.2.0 的字典扩缩容保留新旧两张哈希表，逐桶迁移，降低一次性搬迁全部条目的停顿。
相关概念
工程问题#
大字典重新分配桶后，若立刻迁移所有条目，会把整段搬迁成本集中到一次操作。
实际实现#
rehashidx 记录迁移位置；常规查找和更新可推进迁移，迁移期间按需查询两张表，最终释放旧桶数组。
处理流程#
- 分配新桶数组并进入迁移状态。
- 普通字典操作触发一个迁移步骤。
- 把选中桶的整条冲突链移入新表。
- 旧表清空后完成表切换。
源码片段#
固定版本 · 原文摘录src/dict.c7.2.0 · L668–L688
668dictEntry *dictFind(dict *d, const void *key)669{670 dictEntry *he;671 uint64_t h, idx, table;672673 if (dictSize(d) == 0) return NULL; /* dict is empty */674 if (dictIsRehashing(d)) _dictRehashStep(d);675 h = dictHashKey(d, key);676 for (table = 0; table <= 1; table++) {677 idx = h & DICTHT_SIZE_MASK(d->ht_size_exp[table]);678 he = d->ht_table[table][idx];679 while(he) {680 void *he_key = dictGetKey(he);681 if (key == he_key || dictCompareKeys(d, key, he_key))682 return he;683 he = dictGetNext(he);684 }685 if (!dictIsRehashing(d)) return NULL;686 }687 return NULL;688}dictFind
普通查找先尝试推进一次 rehash，然后按需查询旧表和新表；不在迁移状态时只查第一张表。_dictRehashStep 在迁移未暂停时调用 dictRehash(d,1)，其计量单位是桶，桶内可能有多个条目。
完整 dictFind 函数，展示渐进迁移如何接入在线查询。搬迁桶的循环、迁移暂停和最后释放旧表在同文件其它函数。
收益与取舍#
工程分析带来的收益
- 把大量搬迁工作摊到多次操作。
- 迁移期间仍可查找和更新条目。
付出的代价
- 过渡期同时持有两套桶数组。
- 一步迁移一个桶，长冲突链仍可能增加单次耗时。
可比较的选择
一次性 rehash状态管理更简单，但迁移工作集中，容易产生延迟尖峰。
版本与适用范围#
每步按桶而非单个键计量，且限制空桶扫描；迁移可被暂停，不能把渐进迁移描述成后台线程或硬实时延迟保证。
参考来源#
源码、官方文档与原始论文01
Redis 7.2.0 渐进迁移与双表查找
源码7.2.0src/dict.c · dictRehash; _dictRehashStep; dictFind; dictRehashMilliseconds
相关实现与比较#
4 个相关案例QEMU TCG 用 QHT 保存 TranslationBlock 索引，帮助复用与当前客体执行状态一致的翻译结果。
附源码片段 · 缓存与复用
libvirt 为 Domain 对象维护 UUID 与名称两个哈希索引，两个入口指向同一个对象。
附源码片段 · 索引与查找
把上下文身份编码进块哈希，让重复请求共享已经计算的 KV cache。
附源码片段 · 缓存与复用
Redis 有序集合既要按成员查分数，也要按分数和名次遍历；较大集合通过两种索引服务这些访问方式。
附源码片段 · 索引与查找