Redis字典底層原理設計與實現

在 Redis 中，字典（或雜湊表）是其內部數據結構的基礎之一。Redis 使用字典來實現鍵值對儲存、集合、雜湊、ZSET 等資料型別。理解 Redis 的字典設計和實現有助於更好地掌握 Redis 的效能和工作原理。

字典的定義

Redis 的字典主要由兩個結構體定義：dict 和 dictEntry。以下是它們的簡化結構：

dictEntry 結構

每個 dictEntry 是一個鍵值對條目，包括指向下一個條目的指標（用於解決雜湊衝突）。

typedef struct dictEntry {
    void *key;                  // 鍵
    union {
        void *val;              // 值
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;     // 連結到下一個條目，用於衝突連結串列
} dictEntry;

dict 結構

dict 是字典的主體，包含雜湊表和其他必要的資訊。

typedef struct dictht {
    dictEntry **table;          // 雜湊表陣列
    unsigned long size;         // 雜湊表大小
    unsigned long sizemask;     // 雜湊表大小掩碼，用於計算索引
    unsigned long used;         // 已使用的槽數量
} dictht;

typedef struct dict {
    dictType *type;             // 型別特定函式
    void *privdata;             // 私有資料
    dictht ht[2];               // 兩個雜湊表，用於漸進式 rehash
    long rehashidx;             // 重新雜湊的進度，如果沒有進行則為 -1
    unsigned long iterators;    // 當前執行的迭代器數量
} dict;

雜湊演算法

Redis 使用了 MurmurHash2 演算法進行雜湊計算，這是一種速度快、雜湊均勻的雜湊演算法。

衝突解決

當發生雜湊衝突時，Redis 使用鏈地址法（Separate Chaining），即透過連結串列將多個鍵值對儲存在同一個槽中。

漸進式 Rehashing

爲了避免在一次性擴充套件或收縮雜湊表時可能帶來的延遲，Redis 採用了漸進式 rehashing 技術。rehashing 過程如下：

1. 觸發條件：當雜湊表中的鍵值對數量達到一定閾值時，Redis決定需要擴充套件或收縮雜湊表。

2. 分配新表：Redis建立一個新的雜湊表，這個表的大小是當前雜湊表大小的兩倍或更小（用於收縮）。

3. 標記遷移狀態：在字典結構中標記正在進行漸進式Rehash，並記錄當前遷移的位置（通常從0開始）。

4. 漸進式遷移：每次對雜湊表進行讀寫操作時（如查詢、插入或刪除），Redis不僅執行該操作，還會順便將舊雜湊表中的部分鍵值對遷移到新雜湊表中。具體的遷移量取決於操作的複雜度和系統負載，遷移單位：bucket

5. 更新位置：每次遷移後，更新當前遷移的位置指標，指向下一個待遷移的區域。

6. 完成遷移：當所有鍵值對都遷移完畢後，Redis用新雜湊表替換舊雜湊表，並結束漸進式Rehash狀態。

優點

• 避免卡頓：透過將Rehash過程分散到多個操作中，避免了一次性大規模遷移可能帶來的系統卡頓。

• 保持響應效能：即使在進行Rehash期間，系統也可以處理其他請求，保持高響應效能。

• 漸進遷移：逐步遷移確保每次操作只需少量額外開銷，不會顯著影響系統整體效能。

字典操作

基本的字典操作包括插入、查詢和刪除。這些操作在 Redis 原始碼的 dict.c 檔案中實現。以下是一些關鍵函式的簡要說明：

插入操作

插入一個鍵值對到字典中：

int dictAdd(dict *d, void *key, void *val) {
    dictEntry *entry = dictAddRaw(d, key, NULL);
    if (!entry) return DICT_ERR;
    dictSetVal(d, entry, val);
    return DICT_OK;
}

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing) {
    /* ...檢查是否需要 rehash，並進行相應操作... */
    /* ...計算鍵的雜湊值，並找到對應的槽位... */
    entry = zmalloc(sizeof(*entry));
    entry->next = d->ht[0].table[index];
    d->ht[0].table[index] = entry;
    d->ht[0].used++;
    dictSetKey(d, entry, key);
    return entry;
}

查詢操作

根據鍵查詢對應的值：

dictEntry *dictFind(dict *d, const void *key) {
    unsigned int h, idx, table;
    dictEntry *he;

    if (d->ht[0].size == 0) return NULL; /* 空字典 */
    if (dictIsRehashing(d)) _dictRehashStep(d); /* 如果正在進行 rehash，則執行單步 rehash */

    for (table = 0; table <= 1; table++) {
        h = dictHashKey(d, key);
        idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        while(he) {
            if (dictCompareKeys(d, key, he->key))
                return he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) return NULL; /* 沒有找到且沒有在 rehash，提前返回 */
    }
    return NULL; /* 沒有找到 */
}

刪除操作

從字典中刪除一個鍵值對：

int dictDelete(dict *d, const void *key) {
    return dictGenericDelete(d, key, 1);
}

static int dictGenericDelete(dict *d, const void *key, int nofree) {
    unsigned int h, idx, table;
    dictEntry *he, *prevHe;

    if (d->ht[0].size == 0) return DICT_ERR; /* 空字典 */
    if (dictIsRehashing(d)) _dictRehashStep(d);

    for (table = 0; table <= 1; table++) {
        h = dictHashKey(d, key);
        idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        prevHe = NULL;
        while (he) {
            if (dictCompareKeys(d, key, he->key)) {
                if (prevHe)
                    prevHe->next = he->next;
                else
                    d->ht[table].table[idx] = he->next;
                if (!nofree) {
                    dictFreeKey(d, he);
                    dictFreeVal(d, he);
                }
                zfree(he);
                d->ht[table].used--;
                return DICT_OK;
            }
            prevHe = he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return DICT_ERR; /* 沒有找到 */
}

漸進式 Rehash

漸進式Rehash的觸發

Redis決定是否需要Rehash主要透過以下函式：

int _dictExpandIfNeeded(dict *d) {
    // 如果正在進行Rehash，直接返回
    if (dictIsRehashing(d)) return DICT_OK;

    // 如果負載因子超過閾值，則觸發擴充套件
    if (d->ht[0].used >= d->ht[0].size && (d->ht[0].used / d->ht[0].size > HASHTABLE_MAX_LOAD_FACTOR)) {
        return dictExpand(d, d->ht[0].size * 2);
    }
    return DICT_OK;
}

初始化Rehash

當決定進行Rehash時，會分配一個新的雜湊表，並開始遷移：

int dictExpand(dict *d, unsigned long size) {
    // 分配新雜湊表
    dictht n; 
    unsigned long realsize = _dictNextPower(size);
    n.size = realsize;
    n.sizemask = realsize - 1;
    n.table = zcalloc(realsize * sizeof(dictEntry*));
    n.used = 0;

    // 將新表賦值給ht[1]
    d->ht[1] = n;
    d->rehashidx = 0; // 開始進行Rehash
    return DICT_OK;
}

漸進式資料遷移

在每次對雜湊表進行操作時，會順便遷移一些資料：

void _dictRehashStep(dict *d) {
    if (d->iterators == 0) dictRehash(d, 1); // 每次遷移一個bucket
}

int dictRehash(dict *d, int n) {
    if (!dictIsRehashing(d)) return 0;

    while (n--) {
        dictEntry *de, *nextde;

        // 如果所有資料都遷移完畢
        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;
        }

        // 找到第一個非空bucket
        while (d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;

        de = d->ht[0].table[d->rehashidx];
        while(de) {
            nextde = de->next;

            // 重新計算鍵在新表中的位置，並插入
            unsigned int 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++;
    }
    return 1;
}

結束Rehash

當所有資料都遷移完畢後，需要將新雜湊表替換舊雜湊表，並重置相關狀態：

if (d->ht[0].used == 0) {
    zfree(d->ht[0].table);
    d->ht[0] = d->ht[1];
    _dictReset(&d->ht[1]);
    d->rehashidx = -1;
}