Hash 表与渐进式 rehash

第九章：Hash 表与渐进式 rehash

9.1 dict 的三层结构

Redis 的字典（dict）是整个系统最核心的数据结构——主数据库本身就是一个 dict，存储所有键值对。理解它的结构是理解 Redis 性能特征的基础。

9.1.1 C 结构定义（dict.h）

/* 哈希表节点 — 存储一个键值对 */
typedef struct dictEntry {
    void *key;                /* 键（任意类型，通过 dictType 的函数指针访问） */
    union {
        void *val;            /* 通用值指针 */
        uint64_t u64;         /* 无符号整数值（无需额外 malloc） */
        int64_t s64;          /* 有符号整数值 */
        double d;             /* 浮点值 */
    } v;
    struct dictEntry *next;   /* 链地址法：同一桶中的下一个节点 */
    void *metadata[];         /* 扩展字段（dictType 决定大小） */
} dictEntry;

/* dictType — 函数指针集合，实现类似泛型的行为 */
typedef struct dictType {
    uint64_t (*hashFunction)(const void *key);     /* 计算哈希值 */
    void *(*keyDup)(dict *d, const void *key);     /* 复制 key */
    void *(*valDup)(dict *d, const void *obj);     /* 复制 value */
    int (*keyCompare)(dict *d, const void *key1,   /* 比较 key */
                      const void *key2);
    void (*keyDestructor)(dict *d, void *key);     /* 销毁 key */
    void (*valDestructor)(dict *d, void *obj);     /* 销毁 value */
    int (*expandAllowed)(size_t moreMem,            /* 是否允许扩容 */
                         double usedRatio);
    size_t (*dictEntryMetadataBytes)(dict *d);     /* metadata 大小 */
} dictType;

/* Redis 7.0+ 合并后的 dict 结构 */
typedef struct dict {
    dictType *type;            /* 操作函数集 */
    dictEntry **ht_table[2];   /* 两个哈希桶数组（rehash 时同时使用） */
    unsigned long ht_used[2];  /* 每个哈希表中的节点数 */
    long rehashidx;            /* -1=未在 rehash；>=0=当前正在迁移的桶索引 */
    /* 以下字段合并自旧版 dictht 结构 */
    int16_t pauserehash;       /* >0 时暂停 rehash（如安全迭代器持有期间） */
    signed char ht_size_exp[2];/* 桶数组大小的指数：size = 1 << ht_size_exp */
} dict;

注：Redis 7.0 将原来的 dictht 结构内联到 dict 中，消除了一层间接寻址。

9.1.2 内存布局可视化

dict struct（64字节）：
┌─────────────────────────────────────────────────────────────┐
│ type ptr(8) │ ht_table[0](8) │ ht_table[1](8) │ ht_used(16)│
│ rehashidx(8)│ pause(2) │ exp[0](1) │ exp[1](1)  │ padding   │
└─────────────────────────────────────────────────────────────┘
       │              │                │
       │              ▼                ▼（rehash 时使用）
       │    ┌──────────────────┐  ┌────────────────┐
       │    │ 桶数组（ht[0]）  │  │ 桶数组（ht[1]）│
       │    │ [0]→ entry → entry│  │ [0]→ entry     │
       │    │ [1]→ NULL        │  │ [1]→ NULL      │
       │    │ [2]→ entry       │  │ ...            │
       │    │ ...              │  │                │
       │    │ [n-1]→ NULL      │  │ [m-1]→ NULL   │
       │    └──────────────────┘  └────────────────┘
       ▼
  dictType（函数指针集）


dictEntry（链地址法冲突）：
┌──────┬────────────┬────────┬──────────┐
│ key* │ val union  │ next*  │ metadata │
│  8B  │    8B      │   8B   │  可变    │
└──────┴────────────┴────────┴──────────┘
   │                    │
   ▼                    ▼
  SDS key         下一个冲突节点（或 NULL）

9.2 哈希函数：SipHash-1-2

9.2.1 为什么需要抗哈希攻击

Redis 4.0 之前使用 MurmurHash2，这是一个快速但非密码学安全的哈希函数。攻击者可以构造大量哈希值相同的键，使所有键落入同一个桶，将 O(1) 的查找退化为 O(n)——哈希洪水攻击（Hash DoS）。

攻击示例（MurmurHash2 攻击 Python dict，2011年）：
  构造特定字符串集合，所有字符串哈希值相同
  POST 1万个这样的参数到 PHP/Python/Ruby Web 服务
  服务器 CPU 100%，响应时间从 ms 级升至 s 级

Redis 受影响场景：
  HSET 命令批量插入精心构造的 field 名
  所有 field 落入同一个哈希桶，O(1) 操作变 O(n)

9.2.2 SipHash-1-2 实现

/* siphash.c — Redis 内嵌实现 */
uint64_t siphash(const uint8_t *in, const size_t inlen, const uint8_t *k) {
    uint64_t v0 = UINT64_C(0x736f6d6570736575);  /* 初始化常量 */
    uint64_t v1 = UINT64_C(0x646f72616e646f6d);
    uint64_t v2 = UINT64_C(0x6c7967656e657261);
    uint64_t v3 = UINT64_C(0x7465646279746573);
    uint64_t k0 = U8TO64_LE(k);       /* 密钥前8字节 */
    uint64_t k1 = U8TO64_LE(k + 8);   /* 密钥后8字节 */
    uint64_t m;
    int i;
    
    v0 ^= k0; v1 ^= k1; v2 ^= k0; v3 ^= k1;
    
    /* 处理每个8字节块：1轮 SipRound */
    for (i = 0; i < inlen / 8; i++) {
        m = U8TO64_LE(in);
        in += 8;
        v3 ^= m;
        SIPROUND;           /* v0+=v1; v1=ROL(v1,13); v1^=v0; ... */
        v0 ^= m;
    }
    /* ... 处理尾部字节和最终化 */
}

Redis 在启动时生成一个随机的 16 字节密钥：

/* server.c */
void dictSetHashFunctionSeed(uint8_t *seed) {
    memcpy(dict_hash_function_seed, seed, sizeof(dict_hash_function_seed));
}

/* 启动时 */
getRandomBytes(hashseed, sizeof(hashseed));
dictSetHashFunctionSeed(hashseed);

每次 Redis 进程重启，哈希种子不同，攻击者无法预测哈希值分布。

9.3 扩容机制

9.3.1 扩容触发条件

/* dict.c — 检查是否需要扩容 */
static int _dictExpandIfNeeded(dict *d) {
    /* 正在 rehash 中，不再触发新的扩容 */
    if (dictIsRehashing(d)) return DICT_OK;

    /* 哈希表为空：初始化到最小容量 */
    if (DICTHT_SIZE(d->ht_size_exp[0]) == 0)
        return dictExpand(d, DICT_HT_INITIAL_SIZE);  /* = 4 */

    /* 触发扩容的条件：
       负载因子 = ht_used[0] / size(ht[0])
     */
    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] / DICTHT_SIZE(d->ht_size_exp[0]) >
             dict_force_resize_ratio))  /* dict_force_resize_ratio = 5 */
    {
        /* 新容量 = 第一个 >= used*2 的 2 的幂 */
        return dictExpand(d, d->ht_used[0] + 1);
    }
    return DICT_OK;
}

两个阈值的设计原因：

正常阈值（load factor >= 1）：
  每个桶平均1个元素，查找期望比较次数约为 1 + load_factor/2 ≈ 1.5
  此时扩容是合理的性能保证

持久化期间阈值（load factor >= 5）：
  BGSAVE/BGREWRITEAOF 使用 fork()
  fork() 后父子进程共享内存页（写时复制 COW）
  如果此时扩容，会触发大量 COW：
    - 新分配的桶数组是全新内存页 → 子进程看到旧数据，父进程看到新数据
    - 每个写操作都会触发一个 4KB 页的 COW
    - 大量 COW → 内存使用量翻倍 + 大量 page fault
  所以持久化期间容忍更高的 load factor，推迟扩容

9.3.2 新容量计算

/* 找到第一个 >= size 的 2 的幂，返回其指数 */
static signed char _dictNextExp(unsigned long size) {
    unsigned char e = DICT_HT_INITIAL_EXP;  /* = 2，对应 size=4 */
    if (size >= LONG_MAX) return (8*sizeof(long)-1);
    while (1) {
        if ((1ul << e) >= size) return e;
        e++;
    }
}

/* dictExpand 调用 _dictNextExp */
int dictExpand(dict *d, unsigned long size) {
    /* 计算新的桶数组大小 */
    signed char new_ht_size_exp = _dictNextExp(size);
    size_t newsize = DICTHT_SIZE(new_ht_size_exp);  /* 1 << new_ht_size_exp */

    /* 分配新哈希表（ht[1]） */
    dictEntry **new_ht_table = zcalloc(newsize * sizeof(dictEntry*));
    d->ht_table[1] = new_ht_table;
    d->ht_size_exp[1] = new_ht_size_exp;
    d->ht_used[1] = 0;
    d->rehashidx = 0;  /* 标记开始 rehash */
    return DICT_OK;
}

9.4 渐进式 rehash（核心设计）

9.4.1 为什么需要渐进式 rehash

假设有 100 万个键的哈希表需要扩容：

非渐进式（一次性 rehash）：
  申请 2M 桶的新数组 → 遍历所有 1M 个 entry → 重新插入 → 完成
  耗时：约 100ms-500ms（取决于服务器负载）
  期间：Redis 单线程被完全占用，所有客户端请求超时！

渐进式 rehash：
  每次操作时顺带迁移一个桶（单步）
  serverCron 每100ms批量迁移100个桶
  总迁移时间：摊还到正常操作中，无明显阻塞

9.4.2 单步渐进式 rehash

/* dict.c — 执行一步渐进式 rehash（迁移1个桶） */
int dictRehash(dict *d, int n) {
    int empty_visits = n * 10;  /* 最多访问 n*10 个空桶（避免长时间遍历空桶） */
    
    if (!dictIsRehashing(d)) return 0;

    while (n-- && d->ht_used[0] != 0) {
        dictEntry *de, *nextde;
        
        /* 跳过空桶（但限制最大空桶访问数） */
        while (d->ht_table[0][d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }

        /* 迁移 rehashidx 指向的整个桶（链表中的所有 entry） */
        de = d->ht_table[0][d->rehashidx];
        while (de) {
            uint64_t h;
            nextde = de->next;
            /* 在 ht[1] 中重新计算桶索引 */
            h = dictHashKey(d, de->key) & DICTHT_SIZE_MASK(d->ht_size_exp[1]);
            /* 头插法插入 ht[1] 的对应桶 */
            de->next = d->ht_table[1][h];
            d->ht_table[1][h] = de;
            d->ht_used[0]--;
            d->ht_used[1]++;
            de = nextde;
        }
        d->ht_table[0][d->rehashidx] = NULL;
        d->rehashidx++;
    }

    /* 检查是否 rehash 完成 */
    if (d->ht_used[0] == 0) {
        zfree(d->ht_table[0]);
        d->ht_table[0] = d->ht_table[1];
        d->ht_used[0] = d->ht_used[1];
        d->ht_size_exp[0] = d->ht_size_exp[1];
        _dictReset(d, 1);       /* 清空 ht[1] */
        d->rehashidx = -1;      /* rehash 完成 */
        return 0;
    }
    return 1;  /* rehash 还未完成 */
}

9.4.3 serverCron 批量迁移

/* server.c — 每次 serverCron 调用（每 100ms） */
int databasesCron(void) {
    /* 对所有数据库执行渐进式 rehash */
    if (server.activerehashing) {
        uint64_t elapsed_us = 0;
        for (j = 0; j < dbs_per_call; j++) {
            int work_done;
            /* incrementallyRehash：对单个 db 执行 1ms 内的 rehash */
            if (incrementallyRehash(rehash_db)) {
                /* 有工作完成，下次继续同一个 db */
                active_expire_cycle_db = rehash_db;
            }
        }
    }
}

/* 在1毫秒内尽量多地迁移桶 */
int incrementallyRehash(int dbid) {
    if (dictIsRehashing(server.db[dbid].dict)) {
        dictRehashMilliseconds(server.db[dbid].dict, 1);
        return 1;
    }
    /* ... 检查 expires dict */
}

/* 执行 ms 毫秒内的 rehash */
int dictRehashMilliseconds(dict *d, int ms) {
    if (d->pauserehash > 0) return 0;
    long long start = timeInMilliseconds();
    int rehashes = 0;
    while (dictRehash(d, 100)) {   /* 每次迁移100个桶 */
        rehashes += 100;
        if (timeInMilliseconds() - start > ms) break;
    }
    return rehashes;
}

9.4.4 rehash 期间的读写操作

读操作（查找）：

/* dict.c — 在 rehash 期间需要查两个哈希表 */
dictEntry *dictFind(dict *d, const void *key) {
    dictEntry *he;
    uint64_t h, idx, table;
    
    if (dictSize(d) == 0) return NULL;
    if (dictIsRehashing(d)) _dictRehashStep(d);  /* 顺带迁移1步 */

    h = dictHashKey(d, key);
    for (table = 0; table <= 1; table++) {  /* 查 ht[0] 和 ht[1] */
        idx = h & DICTHT_SIZE_MASK(d->ht_size_exp[table]);
        he = d->ht_table[table][idx];
        while (he) {
            if (key == he->key || dictCompareKeys(d, key, he->key))
                return he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;  /* 未 rehash 时只查 ht[0] */
    }
    return NULL;
}

写操作（插入）：

/* rehash 期间：新 key 只插入 ht[1]，保证 ht[0] 中的 key 只减不增 */
static long _dictKeyIndex(dict *d, const void *key, uint64_t hash,
                          dictEntry **existing) {
    unsigned long idx, table;
    dictEntry *he;
    if (existing) *existing = NULL;

    if (_dictExpandIfNeeded(d) == DICT_ERR) return -1;

    for (table = 0; table <= 1; table++) {
        idx = hash & DICTHT_SIZE_MASK(d->ht_size_exp[table]);
        he = d->ht_table[table][idx];
        while (he) {
            if (key == he->key || dictCompareKeys(d, key, he->key)) {
                if (existing) *existing = he;
                return -1;  /* key 已存在 */
            }
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;  /* 未 rehash 时只查 ht[0] */
    }
    /* 返回 ht[1] 的桶索引（rehash 时），否则返回 ht[0] 的桶索引 */
    table = dictIsRehashing(d) ? 1 : 0;
    return idx;
}

9.5 缩容机制

/* 缩容触发：load factor < 0.1 时 */
int htNeedsResize(dict *dict) {
    long long size, used;
    size = dictSlots(dict);
    used = dictSize(dict);
    return (size > DICT_HT_INITIAL_SIZE &&
            (used * 100 / size < HASHTABLE_MIN_FILL));  /* HASHTABLE_MIN_FILL = 10 */
}

/* server.c — 每次 serverCron 检查是否需要缩容 */
void tryResizeHashTables(int dbid) {
    if (htNeedsResize(server.db[dbid].dict))
        dictResize(server.db[dbid].dict);
    if (htNeedsResize(server.db[dbid].expires))
        dictResize(server.db[dbid].expires);
}

/* 缩容：新容量 = 第一个 >= used 的 2 的幂 */
int dictResize(dict *d) {
    unsigned long minimal;
    if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
    minimal = d->ht_used[0];
    if (minimal < DICT_HT_INITIAL_SIZE) minimal = DICT_HT_INITIAL_SIZE;
    return dictExpand(d, minimal);
}

9.6 迭代器安全性

9.6.1 安全迭代器 vs 非安全迭代器

/* 安全迭代器（dictGetIterator）：
   持有期间暂停 rehash，防止迁移导致遍历重复或遗漏
   使用场景：KEYS、HGETALL、DEBUG OBJECT 等需要完整遍历的命令 */
dictIterator *dictGetIterator(dict *d) {
    dictIterator *iter = zmalloc(sizeof(*iter));
    iter->d = d;
    iter->table = 0;
    iter->index = -1;
    iter->safe = 1;           /* 安全模式 */
    iter->entry = NULL;
    iter->nextEntry = NULL;
    return iter;
}

/* 开始迭代时：将 pauserehash++ */
dictEntry *dictNext(dictIterator *iter) {
    if (iter->index == -1 && iter->table == 0) {
        if (iter->safe)
            dictPauseRehashing(iter->d);  /* pauserehash++ */
        else
            iter->fingerprint = dictFingerprint(iter->d);
    }
    /* ... 遍历逻辑 */
}

/* 结束时：将 pauserehash-- */
void dictReleaseIterator(dictIterator *iter) {
    if (!(iter->index == -1 && iter->table == 0)) {
        if (iter->safe)
            dictResumeRehashing(iter->d);   /* pauserehash-- */
        else
            assert(iter->fingerprint == dictFingerprint(iter->d));
    }
    zfree(iter);
}

非安全迭代器（dictGetSafeIterator 的对立面）：

/* 非安全迭代器：允许 rehash 继续，但用 fingerprint 检测结构变化 */
uint64_t dictFingerprint(dict *d) {
    /* 将哈希表的关键状态（各指针、大小）混合成一个64位指纹 */
    uint64_t integers[6], hash = 0;
    integers[0] = (long)d->ht_table[0];
    integers[1] = d->ht_size_exp[0];
    integers[2] = d->ht_used[0];
    integers[3] = (long)d->ht_table[1];
    integers[4] = d->ht_size_exp[1];
    integers[5] = d->ht_used[1];
    /* SipHash 混合 integers → 64bit fingerprint */
    /* ... */
    return hash;
}
/* 释放时：assert fingerprint 未变，否则说明并发修改（不允许） */

使用场景：

安全迭代器（pauserehash 期间停止 rehash）：
  - KEYS pattern（全量 key 遍历）
  - HGETALL key
  - SMEMBERS key
  - 任何需要完整且无重复地遍历所有 entry 的操作

非安全迭代器（允许 rehash，仅检测修改）：
  - SCAN cursor pattern count（增量式遍历，允许重复和遗漏）
  - DEBUG 相关命令

9.7 Hash 对象的 listpack → hashtable 升级

9.7.1 升级触发

/* t_hash.c — 每次 HSET 后检查是否需要升级 */
void hashTypeTryConversion(robj *o, listTypeEntry *entry, ...) {
    if (o->encoding != OBJ_ENCODING_LISTPACK) return;

    /* 检查新 field 或 value 的长度 */
    if (sdslen(entry->sval) > server.hash_max_listpack_value)
        hashTypeConvert(o, OBJ_ENCODING_HT);

    /* 检查元素总数 */
    if (hashTypeLength(o) > server.hash_max_listpack_entries)
        hashTypeConvert(o, OBJ_ENCODING_HT);
}

/* 升级过程：将 listpack 中的所有键值对插入新 dict */
void hashTypeConvert(robj *o, int enc) {
    if (enc == OBJ_ENCODING_HT) {
        dict *dict;
        listpackTypeIterator *li;
        listpackTypeEntry entry;

        dict = dictCreate(&hashDictType);
        /* 遍历 listpack，逐个插入 dict */
        li = listTypeInitIterator(o, 0, LIST_TAIL);
        while (listTypeNext(li, &entry)) {
            sds key = listTypeGetValueObject(&entry, OBJ_HASH_KEY)->ptr;
            sds val = listTypeGetValueObject(&entry, OBJ_HASH_VALUE)->ptr;
            dictAdd(dict, key, val);
        }
        listTypeReleaseIterator(li);
        o->encoding = OBJ_ENCODING_HT;
        o->ptr = dict;
        /* 释放旧的 listpack */
    }
}

9.7.2 升级前后内存对比

Hash 对象（100个 field，每个 field=value=8字节）：

listpack 编码：
  Header: 6字节
  每对（field+value）: (1+8+1) + (1+8+1) = 20字节
  100对: 2000字节 + 6字节 header + 1字节 end = 2007字节 ≈ 2KB

hashtable 编码（dict）：
  dict struct: 64字节
  桶数组（128个桶，容纳100个entry）: 128 × 8 = 1024字节
  每个 dictEntry: key ptr(8) + val union(8) + next ptr(8) + metadata = 24字节
  100 个 entry: 100 × 24 = 2400字节
  100 个 SDS key: 100 × (3+8+1) = 1200字节
  100 个 SDS val: 100 × (3+8+1) = 1200字节
  总计: 64 + 1024 + 2400 + 1200 + 1200 = 5888字节 ≈ 5.75KB

内存比：hashtable ≈ 2.87 × listpack
→ 默认阈值 128 entries 的设计合理性得到验证

9.8 性能数据

9.8.1 rehash 对 QPS 的影响

测试环境：100万 key，dict 扩容（1M bucket → 2M bucket）
         平均每个 key 大小：32字节 key + 64字节 value

阶段1：rehash 开始前（正常状态）
  GET 吞吐量：350K QPS
  P99 延迟：0.3ms

阶段2：rehash 进行中（渐进式，serverCron 批量迁移）
  GET 吞吐量：310K QPS（-11%，查找需查两个 ht）
  P99 延迟：0.4ms（每次查找多一次 ht[1] 检查）
  rehash 完成时间：约 2-3 秒（serverCron 每100ms迁移100个桶，100万桶需10000次）

阶段3：rehash 完成后
  GET 吞吐量：350K QPS（恢复正常）
  P99 延迟：0.3ms

结论：
  - 渐进式 rehash 期间 QPS 下降约 10-15%
  - P99 延迟轻微上升（20-30%）
  - 无明显阻塞峰值（与非渐进式 rehash 的 100ms 阻塞相比）

9.8.2 哈希函数性能

SipHash-1-2 vs MurmurHash2 vs xxHash：

key=32字节，单次哈希：
  SipHash-1-2:  约 12ns（需要密钥混合）
  MurmurHash2:  约 5ns（无密钥）
  xxHash64:     约 3ns（无密钥）

SipHash 的额外代价：约 7ns/次
对于 300K QPS 的场景：300000 × 7ns = 2.1ms/s 的额外 CPU
占单核 CPU 的约 0.21%（可忽略）

安全代价极低，但防御效果显著：
  攻击者无法预测密钥，无法构造哈希碰撞攻击

9.9 小结

Redis dict 的渐进式 rehash 是单线程系统中处理大规模数据结构扩容的典范设计：

这套机制使 Redis 能够在不停机、不阻塞的情况下，从容处理数据规模从小到大的全过程。