【Redis / 缓存内核】Dict 与渐进 rehash：双 ht 与摊销扩容

对象模型与 SDS 里，键名是 SDS、值是 robj*；二者都挂在数据库的 dict 上——db->dict 存数据键，db->expires 存 TTL 元数据（第 7 篇）。Hash、Set 的大编码内部还有嵌套 dict。若把 Redis 想成「内存数据结构服务器」，dict 就是几乎所有集合的底座。

教科书哈希表扩容常描述为：分配新表 → 全量搬桶 → 切换指针，停顿与元素数成正比。Redis 采用 双表渐进 rehash：扩容期间 ht[0] 与 ht[1] 并存，每次 dictAdd / dictFind 顺带搬迁少量桶，把尖刺摊进日常命令。本文基于 Redis OSS 7.4.2 src/dict.c、src/dict.h，并与 哈希表内部：开放寻址、链式、Robin Hood 对照——那边讲流派与 benchmark，本篇只钉 Redis 链式 dict 的工程不变量。

一、dict 结构：链式桶与双表

// src/dict.h — Redis 7.4.2
struct dict {
    dictType *type;
    dictEntry **ht_table[2];
    unsigned long ht_used[2];
    long rehashidx;           /* -1 表示未 rehash */
    unsigned pauserehash : 15;
    signed char ht_size_exp[2]; /* size = 1<<exp */
    int16_t pauseAutoResize;
    void *metadata[];
};

查找时哈希 \(h = \text{hash}(key)\)，桶下标 \(idx = h \ \& \ (2^{exp}-1)\)，沿链表比较。Redis 7.x 对指针键可用 keys_are_odd 等优化（注释在 dictType），主路径仍是链式。

stateDiagram-v2
  [*] --> Single: ht[1] empty, rehashidx=-1
  Single --> Rehashing: dictExpand triggers
  Rehashing --> Single: ht[0] freed, ht[1] becomes ht[0]
  note right of Rehashing
    ht_table[0] old buckets
    ht_table[1] new buckets
    rehashidx scans old table
  end note

二、何时触发扩容与收缩

dictExpandIfNeeded 在插入前由 _dictExpandIfNeeded 调用（pauseAutoResize == 0 时）：

// src/dict.c — 逻辑摘要
int dictExpandIfNeeded(dict *d) {
    if (dictIsRehashing(d)) return DICT_OK;
    if (DICTHT_SIZE(d->ht_size_exp[0]) == 0)
        dictExpand(d, DICT_HT_INITIAL_SIZE);

    /* 负载因子达到 1:1，或「强制」阈值 4:1 */
    if ((dict_can_resize == DICT_RESIZE_ENABLE &&
         d->ht_used[0] >= DICTHT_SIZE(d->ht_size_exp[0])) ||
        (dict_can_resize != DICT_RESIZE_FORBID &&
         d->ht_used[0] >= dict_force_resize_ratio * DICTHT_SIZE(d->ht_size_exp[0])))
    {
        if (dictTypeResizeAllowed(d, d->ht_used[0] + 1))
            dictExpand(d, d->ht_used[0] + 1);
    }
    return DICT_OK;
}

要点：

• 正常扩容线：元素数 \(\geq\) 桶数（负载因子 \(\geq 1\)），新表大小为「下一个覆盖 used+1 的 2 的幂」。
• 强制线：dict_force_resize_ratio = 4——在 DICT_RESIZE_AVOID 模式下，只有负载 \(\geq 4\) 才仍扩容（注释：避免 rehash 但防止极端冲突链）。
• 收缩：dictShrinkIfNeeded 在元素数 \(\leq\) 桶数 \(/ 8\) 时考虑缩表（最小保持 DICT_HT_INITIAL_SIZE）。

dictTypeResizeAllowed 允许模块 dict 拒绝扩容（例如 RDB 加载时控制内存尖刺）。

三、渐进 rehash 的步进语义

dictExpand / _dictRehashStep 启动双表：rehashidx = 0，ht_table[1] 分配新桶。

核心搬迁在 dictRehash(d, n)——每次最多处理 \(n\) 个非空旧桶（空桶只递增 rehashidx，且 empty_visits = n*10 防止旧表极稀疏时死循环）：

// src/dict.c — dictRehash 片段
int dictRehash(dict *d, int n) {
    if (dict_can_resize == DICT_RESIZE_FORBID || !dictIsRehashing(d)) return 0;
    /* DICT_RESIZE_AVOID 时，扩容倍数不足 4x 可暂停 rehash */
    ...
    while(n-- && d->ht_used[0] != 0) {
        while(d->ht_table[0][d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        rehashEntriesInBucketAtIndex(d, d->rehashidx);
        d->rehashidx++;
    }
    return !dictCheckRehashingCompleted(d);
}

命令路径上的摊销：dictFind、dictAdd、dictReplace 等在访问前若 dictIsRehashing，先执行：

static void _dictRehashStep(dict *d) {
    if (d->pauserehash == 0) dictRehash(d,1);
}

若当前桶下标 idx >= rehashidx 且 ht[0][idx] 非空，优先 _dictBucketRehash(d, idx)（cache-friendly：搬用户正在碰的桶）。否则退一步 _dictRehashStep。

查找需查 两张表：

for (table = 0; table <= 1; table++) {
    if (table == 0 && (long)idx < d->rehashidx) continue; /* 已搬走的旧桶跳过 */
    idx = h & DICTHT_SIZE_MASK(d->ht_size_exp[table]);
    ...
}

rehashidx 之前的 ht[0] 桶保证为空——这是增量 rehash 的不变量。

时间片 rehash：dictRehashMicroseconds(d, us) 循环 dictRehash(d,100) 直到超过微秒预算，供 cron 或主动消化 backlog 使用。

四、DICT_RESIZE_AVOID 与 fork 期行为

全局 dict_can_resize 三态：ENABLE / AVOID / FORBID。子进程做 RDB 快照时，父进程常设 AVOID，避免 COW 期间大量分配新桶页导致 copy-on-write 写放大（第 9 篇 RDB 展开）。

在 AVOID 下：

• 扩容：仅当新表 \(\geq 4\times\) 旧表才继续 rehash（dictRehash 内判断）。
• 收缩：仅当旧表 \(\geq 32\times\) 新表才缩（1 / (HASHTABLE_MIN_FILL * 4)，HASHTABLE_MIN_FILL = 8）。

这是 延迟 rehash 与 内存/延迟 的显式权衡：fork 期间宁可容忍更长冲突链，也不制造海量新页。

pauserehash / pauseAutoResize 供迭代器、某些迁移路径暂停步进，防止不安全并发修改（单线程命令仍靠这些标志避免 rehash 与扫描打架）。

五、与 algorithms/07 及经典模型的关系

哈希表内部 对比了链式、线性探测、Robin Hood、Swiss Table 等。Redis dict 明确走 链式 + 2 的幂桶数 + 增量 rehash，没有开放寻址的探测簇，也没有 Swiss Table 的 control byte SIMD 查找。

谱系：增量 rehash 思想在动态哈希文献与工业实现中反复出现（Perl 哈希、Java HashMap 的树化是另一条线）。Redis 的贡献在于与 事件循环单线程、BGSAVE COW、expires dict 同步 rehash 绑在一起，形成可运维默认。

争论：一派认为链式哈希在 负载因子 1 甚至 4 时长链恶化 CPU（algorithms/07 的 benchmark 在均匀随机键下测的是另一套实现）；另一派指出 Redis 键空间常高度偏斜、大量小 dict（expires、小 set）桶数不大，链长短于最坏分析。没有跨 workload 的单一答案——热点桶 仍是慢查询与 LATENCY DOCTOR 线索（第 15 篇）。

开放问题：Redis 7+ 的 kvstore、多 DB 字典分层是否在将来替代部分 dict 用法，属于实现演进问题；读源码仍以 dict.c 为基准。

六、常见误解

七、三句话小结

1. Redis dict 是链式哈希 + 双表：扩容时 ht[0]→ht[1] 渐进搬迁，rehashidx 之前旧桶必空。
2. 每次 查找/插入 顺带 dictRehash(d,1) 或搬当前桶，把 \(O(n)\) 尖刺摊进请求路径；dictRehashMicroseconds 供主动消化。
3. fork / RDB 期 DICT_RESIZE_AVOID 抬高扩容阈值，用更长链换更少 COW 页——与 algorithms/07 的「负载因子与冲突」应用在同一问题的不同维度。

参考资料

A 级（源码）

• Redis OSS 7.4.2：src/dict.c（dictExpandIfNeeded、dictRehash、_dictRehashStep）、src/dict.h（struct dict）
• Redis OSS 7.4.2：src/db.c（db->dict 查找路径）、src/expire.c（expires dict 同步 rehash，第 7 篇）

B 级

• Redis 官方文档：Internals — Dict（与源码对照阅读）

站内交叉

• 哈希表内部：开放寻址、链式、Robin Hood
• 对象模型与 SDS · 紧凑编码

返回 系列目录 ｜ 上一篇：对象模型与 SDS ｜ 下一篇：紧凑编码