Redis 核心資料結構解析（二）：字典與漸進式 Rehash 實現

Redis 字典架構概覽

Redis 字典實質上是雜湊表，採用「字典 + 雜湊表」兩層結構實現漸進式 rehash，類似 Java HashMap 但有關鍵差異：

• Java HashMap：單一類別內建雜湊表與擴容邏輯
• Redis：dicht 實現雜湊表，dict 持有兩個 dicht 陣列（ht[2]）實現 rehash

核心資料結構定義

雜湊表節點

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    struct dictEntry *next;  // 鏈表解決衝突
} dictEntry;

• key：鍵指標
• v：值聯合體（指標、無號/有號 64 位整數）
• next：指向下一個節點，形成鏈表處理哈希衝突

雜湊表

typedef struct dictht {
    dictEntry **table;       // 節點指標陣列
    unsigned long size;      // 陣列大小（2 的冪次）
    unsigned long sizemask;  // size - 1，用於索引計算：index = hash & sizemask
    unsigned long used;      // 已存節點數
} dictht;

字典

typedef struct dict {
    dictType *type;      // 類型特定函數表（哈希、複製、比較、銷毀）
    void *privdata;      // 傳遞給類型函數的私有資料
    dictht ht[2];        // 兩個雜湊表：ht[0] 正常使用，ht[1] rehash 時使用
    int rehashidx;       // rehash 進度索引，-1 表示未進行 rehash
} dict;

類型特定函數表

typedef struct dictType {
    unsigned int (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdata, const void *obj);
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

哈希算法與索引計算

Redis 使用 MurmurHash2 算法計算鍵的哈希值，索引計算：

index = hash & ht->sizemask;  // 等價於 hash % size，但更高效

相同哈希值落入同一索引時，透過 next 指標形成鏈表。

漸進式 Rehash 機制

觸發條件

• 擴容：負載因子 used / size >= 1（或 > 5 當有子進程執行 BGSAVE/BGREWRITEAOF 時）
• 縮容：負載因子 < 0.1

目標大小計算

• 擴容：size = 2^n >= used * 2 的最小 2 的冪次
• 縮容：size = 2^n >= used 的最小 2 的冪次

漸進式執行流程

1. 分配 ht[1] 為目標大小
2. 設定 rehashidx = 0 開始遷移
3. 每次字典操作（增刪改查）遷移 ht[0] 當前 rehashidx 索引的所有節點至 ht[1]
4. rehashidx++，直到遷移完成（rehashidx = -1，交換 ht[0]/ht[1]，釋放舊表）

Rehash 期間雙表共存行為

• 查詢：先查 ht[0]，再查 ht[1]
• 新增：僅寫入 ht[1]
• 刪除/更新：在對應表操作

此設計避免一次性遷移大量資料阻塞主執行緒，將擴容成本分攤到每個操作中。

關鍵設計優勢

• 值編碼優化：聯合體支援整數直存，避免指標間接存取
• 類型多態：dictType 函數表支援不同用途字典自訂行為
• 非阻塞 Rehash：漸進式遷移保證單執行緒 Redis 的即時性
• 記憶體效率：負載因子控制與縮容機制避免記憶體浪費