深度圖解 Redis Hash（散列表）實(shí)現(xiàn)原理-魔扣目錄

redis 的散列表Dict 由數(shù)組 + 鏈表構(gòu)成，數(shù)組的每個(gè)元素占用的槽位叫做哈希桶，當(dāng)出現(xiàn)散列沖突的時(shí)候就會(huì)在這個(gè)桶下掛一個(gè)鏈表，用“拉鏈法”解決散列沖突的問題。

1、是什么

Redis Hash（散列表）是一種 field-value pAIrs（鍵值對）集合類型，類似于 Python/ target=_blank class=infotextkey>Python 中的字典、JAVA 中的 HashMap。一個(gè) field 對應(yīng)一個(gè) value，你可以通過 field 在 O(1) 時(shí)間復(fù)雜度查 field 找關(guān)聯(lián)的 field，也可以通過 field 來更新或者刪除這個(gè)鍵值對。

Redis 的散列表 dict 由數(shù)組 + 鏈表構(gòu)成，數(shù)組的每個(gè)元素占用的槽位叫做哈希桶，當(dāng)出現(xiàn)散列沖突的時(shí)候就會(huì)在這個(gè)桶下掛一個(gè)鏈表，用“拉鏈法”解決散列沖突的問題。

簡單地說就是將一個(gè) key 經(jīng)過散列計(jì)算均勻的映射到散列表上。

圖 2-18

2、修煉心法

Hash 數(shù)據(jù)類型底層存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)實(shí)際上有兩種。

dict 結(jié)構(gòu)。
在 7.0 版本之前使用 ziplist，之后被 listpack 代替。

通常情況下使用 dict 數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)，每個(gè) field-value pairs 構(gòu)成一個(gè) dictEntry 節(jié)點(diǎn)來保存。

只有同時(shí)滿足以下兩個(gè)條件的時(shí)候，才會(huì)使用 listpack（7.0 版本之前使用 ziplist）數(shù)據(jù)結(jié)構(gòu)來代替 dict 存儲(chǔ)，把 key-value 鍵值對按照 field 在前 value 在后，緊密相連的方式放到一次把每個(gè)鍵值對放到列表的表尾。

每個(gè)鍵值對中的 field 和 value 的字符串字節(jié)大小都小于hash-max-listpack-value 配置的值（默認(rèn) 64）。
field-value pairs 鍵值對數(shù)量小于 hash-max-listpack-entries配置的值（默認(rèn) 512）。

每次向散列表寫數(shù)據(jù)的時(shí)候，都會(huì)調(diào)用 t_hash.c 中的hashTypeConvertListpack()函數(shù)來判斷是否需要轉(zhuǎn)換底層數(shù)據(jù)結(jié)構(gòu)。

當(dāng)插入和修改的數(shù)據(jù)不滿足以上兩個(gè)條件時(shí)，就把散列表底層存儲(chǔ)結(jié)構(gòu)轉(zhuǎn)換成 dict結(jié)構(gòu)。需要注意的是，不能由 dict 退化成 listpack。

雖然使用了 listpack 就無法實(shí)現(xiàn) O(1) 時(shí)間復(fù)雜度操作數(shù)據(jù)，但是使用 listpack 能大大減少內(nèi)存占用，而且數(shù)據(jù)量比較小，性能并不是有太大差異。

為了對上層屏蔽散列表底層使用了不同數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)，所以抽象了一個(gè) hashTypeIterator 迭代器來實(shí)現(xiàn)散列表的查詢。

Hashes 數(shù)據(jù)類型使用 listpack 作為存儲(chǔ)數(shù)據(jù)時(shí)的情況，如圖 2-19 所示。

圖 2-19

listpack 數(shù)據(jù)結(jié)構(gòu)在之前的已經(jīng)介紹過，接下來帶你揭秘 dict 到底長啥樣。

Redis 數(shù)據(jù)庫就是一個(gè)全局散列表。正常情況下，我只會(huì)使用 ht_table[0]散列表，圖 2-20 是一個(gè)沒有進(jìn)行 rehash 狀態(tài)下的字典。

圖 2-20

dict 字典在源代碼 dict.h中使用 dict 結(jié)構(gòu)體表示。

struct dict {
    dictType *type;
  // 真正存儲(chǔ)數(shù)據(jù)的地方，分別存放兩個(gè)指針
    dictEntry **ht_table[2];
    unsigned long ht_used[2];

    long rehashidx;

    int16_t pauserehash;
    signed char ht_size_exp[2];
};

dictType *type，存放函數(shù)的結(jié)構(gòu)體，定義了一些函數(shù)指針，可以通過設(shè)置自定義函數(shù)，實(shí)現(xiàn) dict 的 key 和 value 存放任何類型的數(shù)據(jù)。
重點(diǎn)看 dictEntry **ht_table[2]，存放了兩個(gè) dictEntry 的二級指針，指針分別指向了一個(gè) dictEntry 指針的數(shù)組。
ht_used[2]，記錄每個(gè)散列表使用了多少槽位（比如數(shù)組長度 32，使用了 12）。
rehashidx，用于標(biāo)記是否正在執(zhí)行 rehash 操作，-1 表示沒有進(jìn)行 rehash。如果正在執(zhí)行 rehash，那么其值表示當(dāng)前 rehash 操作執(zhí)行的 ht_table[0] 散列表 dictEntry 數(shù)組的索引。
pauserehash 表示 rehash 的狀態(tài)，大于 0 時(shí)表示 rehash 暫停了，小于 0 表示出錯(cuò)了。

繼續(xù)看 dictEntry，數(shù)組中每個(gè)元素都是 dictEntry 類型，就是這玩意存放了鍵值對，表示字典的一個(gè)節(jié)點(diǎn)。

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

*key指針指向鍵值對中的鍵，實(shí)際上指向一個(gè) SDS 實(shí)例。
v是一個(gè) union 聯(lián)合體，表示鍵值對中的值，同一時(shí)刻只有一個(gè)字段有值，用聯(lián)合體的目是節(jié)省內(nèi)存。

*val 如果值是非數(shù)字類型，那就使用這個(gè)指針存儲(chǔ)。
uint64_t u64，值是無符號整數(shù)的時(shí)候使用這個(gè)字段存儲(chǔ)。
int64_t s64，值是有符號整數(shù)時(shí)，使用該字段存儲(chǔ)。
double d，值是浮點(diǎn)數(shù)是，使用該字段存儲(chǔ)。

*next指向下一個(gè)節(jié)點(diǎn)指針，當(dāng)散列表數(shù)據(jù)增加，可能會(huì)出現(xiàn)不同的 key 得到的哈希值相等，也就是說多個(gè) key 對應(yīng)在一個(gè)哈希桶里面，這就是哈希沖突。Redis 使用拉鏈法，也就是用鏈表將數(shù)據(jù)串起來。

MySQL：“為啥 ht_table[2] 存放了兩個(gè)指向散列表的指針？用一個(gè)散列表不就夠了么。”

默認(rèn)使用 ht_table [0] 進(jìn)行讀寫數(shù)據(jù)，當(dāng)散列表的數(shù)據(jù)越來越多的時(shí)候，哈希沖突嚴(yán)重會(huì)出現(xiàn)哈希桶的鏈表比較長，導(dǎo)致查詢性能下降。

我為了唯快不破想了一個(gè)法子，當(dāng)散列表保存的鍵值對太多或者太少的時(shí)候，需要通過 rehash（重新散列）對散列表進(jìn)行擴(kuò)容或者縮容。

擴(kuò)容和縮容

為了高性能，減少哈希沖突，我會(huì)創(chuàng)建一個(gè)大小等于 ht_used[0] * 2的散列表 ht_table[1]，也就是每次擴(kuò)容時(shí)根據(jù)散列表 ht_table [0]已使用空間擴(kuò)大一倍創(chuàng)建一個(gè)新散列表ht_table [1]。反之，如果是縮容操作，就根據(jù)ht_table [0]已使用空間縮小一倍創(chuàng)建一個(gè)新的散列表。
重新計(jì)算鍵值對的哈希值，得到這個(gè)鍵值對在新散列表 ht_table [1]的桶位置，將鍵值對遷移到新的散列表上。
所有鍵值對遷移完成后，修改指針，釋放空間。具體是把 ht_table[0]指針指向擴(kuò)容后的散列表，回收原來小的散列表內(nèi)存空間，ht_table[1]指針指向NULL，為下次擴(kuò)容或者縮容做準(zhǔn)備。

MySQL：“什么時(shí)候會(huì)觸發(fā)擴(kuò)容？”

當(dāng)前沒有執(zhí)行 BGSAVE或者 BGREWRITEAOF命令，同時(shí)負(fù)載因子大于等于 1。也就是當(dāng)前沒有 RDB 子進(jìn)程和 AOF 重寫子進(jìn)程在工作，畢竟這倆操作還是比較容易對性能造成影響的，就不擴(kuò)容火上澆油了。
正在執(zhí)行 BGSAVE或者 BGREWRITEAOF命令，負(fù)載因子大于等于 5。（這時(shí)候哈希沖突太嚴(yán)重了，再不觸發(fā)擴(kuò)容，查詢效率太慢了）。

負(fù)載因子 = 散列表存儲(chǔ) dictEntry 節(jié)點(diǎn)數(shù)量 / 散列表桶個(gè)數(shù)。完美情況下，每個(gè)哈希桶存儲(chǔ)一個(gè) dictEntry 節(jié)點(diǎn)，這時(shí)候負(fù)載因子 = 1。

MySQL：“需要遷移數(shù)據(jù)量很大，rehash 操作豈不是會(huì)長時(shí)間阻塞主線程？”

為了防止阻塞主線程造成性能問題，我并不是一次性把全部的 key 遷移，而是分多次，將遷移操作分散到每次請求中，避免集中式 rehash 造成長時(shí)間阻塞，這個(gè)方式叫漸進(jìn)式 rehash。

在執(zhí)行漸進(jìn)式 rehash 期間，dict 會(huì)同時(shí)使用 ht_table[0] 和 ht_table[1]兩個(gè)散列表，rehash 具體步驟如下。

將 rehashidx設(shè)置成 0，表示 rehash 開始執(zhí)行。
在 rehash 期間，服務(wù)端每次處理客戶端對 dict 散列表執(zhí)行添加、查找、刪除或者更新操作時(shí)，除了執(zhí)行指定操作以外，還會(huì)檢查當(dāng)前 dict 是否處于 rehash 狀態(tài)，是的話就把散列表ht_table[0]上索引位置為 rehashidx 的桶的鏈表的所有鍵值對 rehash 到散列表 ht_table[1]上，這個(gè)哈希桶的數(shù)據(jù)遷移完成，就把 rehashidx 的值加 1，表示下一次要遷移的桶所在位置。
當(dāng)所有的鍵值對遷移完成后，將 rehashidx設(shè)置成 -1，表示 rehash 操作已完成。