Dict 優(yōu)點(diǎn)在于，它能以 O(1) 的復(fù)雜度快速查詢數(shù)據(jù)。怎么做到的呢？將 key 通過(guò) Hash 函數(shù)的計(jì)算，就能定位數(shù)據(jù)在表中的位置，因?yàn)楣１韺?shí)際上是數(shù)組，所以可以通過(guò)索引值快速查詢到數(shù)據(jù)。

但是存在的風(fēng)險(xiǎn)也是有，在哈希表大小固定的情況下，隨著數(shù)據(jù)不斷增多，那么哈希沖突的可能性也會(huì)越高。

解決哈希沖突的方式，有很多種。

Redis 采用了「鏈?zhǔn)焦！箒?lái)解決哈希沖突，在不擴(kuò)容哈希表的前提下，將具有相同哈希值的數(shù)據(jù)串起來(lái)，形成鏈接起，以便這些數(shù)據(jù)在表中仍然可以被查詢到。

接下來(lái)，詳細(xì)說(shuō)說(shuō) Dict 的結(jié)構(gòu)設(shè)計(jì)

Dict 的結(jié)構(gòu)

Dict 由三部分組成，分別是：dict、dictht、dicEntry

dictht

dictht 的結(jié)構(gòu)如下：

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

• dictEntry **table，哈希表數(shù)組
• unsigned long size，哈希表大小（取值為 2n2^n2n）
• unsigned long sizemask，哈希表大小掩碼，用于計(jì)算索引值，總是等于 size−1size - 1size−1
• unsigned long used，該哈希表已有的節(jié)點(diǎn)數(shù)量

dicEntry

dicEntry 結(jié)構(gòu)如下

void *key;/*鍵*/
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v; /*值*/
    struct dictEntry *next;/*下一個(gè) entry 的指針*/
} dictEntry;

• dicEntry 和 dictht 之間的組織方式如下圖所示

• 當(dāng)我們向 Dict 添加鍵值對(duì)時(shí)，Redis 首先根據(jù) key 計(jì)算出 hash值（h），然后利用 h & sizemask 來(lái)計(jì)算元素應(yīng)該存儲(chǔ)到數(shù)組中的哪個(gè)索引位置。我們存儲(chǔ) k1=v1，假設(shè) k1 的哈希值 h =1，則 1&3 = 1，因此 k1=v1 要存儲(chǔ)到數(shù)組角標(biāo) 1 位置。
• 如果計(jì)算出來(lái)的數(shù)組角標(biāo)值相同，也就是說(shuō)，出現(xiàn)了 *哈希沖突，redis 采用 ”鏈?zhǔn)焦?ldquo; 的方式，將具有相同哈希值的數(shù)據(jù)串起來(lái)，形成鏈結(jié)構(gòu)，這也就是為什么會(huì)有 struct dictEntry next 這個(gè)成員變量存在

?? 為什么是 h & sizemask ？ 在根據(jù) hash 值（h）來(lái)計(jì)算應(yīng)該把 entry 放在哪個(gè)數(shù)組下標(biāo)位置時(shí)，你可能會(huì)好奇，為什么不是使用 h%size ，而是使用 h&sizemask，而他們?yōu)槭裁纯梢缘贸鲆粯拥慕Y(jié)果。
實(shí)際上，當(dāng)散列表的大小為 2n2^n2n 時(shí)，h%sizemask 的結(jié)果與 h%size 是相同的（這里不做證明）。讓我們以 size 為 8 的散列表為例：

• size = 8，對(duì)應(yīng)的 sizemask = 7 (111的二進(jìn)制表示)
• h = 18 (10010的二進(jìn)制表示)
• h%size = 18%8 = 2
• h&sizemask = 18&7 = 2

dict

在實(shí)際使用哈希表時(shí)，Redis 沒(méi)有使用 dictht ，而是定義一個(gè) dict 結(jié)構(gòu)體，如下

typedef struct dict {
    dictType *type; /* dict類型，內(nèi)置不同的hash函數(shù) */
    void *privdata; /* 私有數(shù)據(jù)，在做特殊hash運(yùn)算時(shí)用 */
    dictht ht[2] ;/* 個(gè)Dict包含兩個(gè)哈希表，其中一個(gè)是當(dāng)前數(shù)據(jù)，另一個(gè)一般是空，rehash時(shí)使用 */
    long rehashidx; /* rehash的進(jìn)度，-1表示未進(jìn)行 */
    int16_t pauserehash; /* rehash是否暫停，1則暫停，0則繼續(xù) */
} dict;

• 在上面這個(gè)結(jié)構(gòu)體中，我們發(fā)現(xiàn)，type 、privdata 是跟哈希運(yùn)算有關(guān)系的，但是其他三個(gè)成員變量，又是用來(lái)做什么的呢？為什么又要定義兩個(gè) dictht 呢？這跟我們下面要說(shuō)的 rehash 操作有關(guān)系

Dict 的 rehash

前面我們提到，redis 使用鏈?zhǔn)焦?lái)解決 hash 沖突問(wèn)題。但是，鏈?zhǔn)焦Ｒ泊嬖诰窒扌裕蔷褪?strong>隨著鏈表長(zhǎng)度的增加，Hash 表在一個(gè)位置上查詢哈希項(xiàng)的耗時(shí)就會(huì)增加，從而增加了 Hash 表的整體查詢時(shí)間，這樣也會(huì)導(dǎo)致 Hash 表的性能下降。這時(shí)，redis 使用 rehash 來(lái)解決這個(gè)問(wèn)題。

Redis 如何實(shí)現(xiàn) rehash

Redis 實(shí)現(xiàn) rehash 的基本思路是這樣的：

• 首先，Redis 準(zhǔn)備了兩個(gè)哈希表，用于 rehash 時(shí)交替保存數(shù)據(jù)。

  • 前面我們提到，redis 在實(shí)際使用時(shí)，定義了一個(gè) dict 結(jié)構(gòu)體。這個(gè)結(jié)構(gòu)體中有一個(gè)數(shù)組（*ht[2] *），包含了兩個(gè) Hash 表（dictht ） *ht[0] *和 *ht[1] *。

• 其次，在正常服務(wù)請(qǐng)求階段，所有的鍵值對(duì)寫入哈希表 ht[0]。

• 接著，當(dāng)進(jìn)行 rehash 時(shí)，鍵值對(duì)被遷移到哈希表 ht[1]中。

• 最后，當(dāng)遷移完成后，ht[0]的空間會(huì)被釋放，并把 ht[1] 的地址賦值給 ht[0]，ht[1] 的表大小設(shè)置為 0。這樣一來(lái)，又回到了正常服務(wù)請(qǐng)求的階段，ht[0] 接收和服務(wù)請(qǐng)求，ht[1] 作為下一次 rehash 時(shí)的遷移表。

什么時(shí)候進(jìn)行 rehash

• 當(dāng)我們往 Redis 中寫入新的鍵值對(duì)或是修改鍵值對(duì)時(shí)，Redis 都會(huì)判斷下是否需要進(jìn)行 rehash。而 rehash 的觸發(fā)條件則是

  • 條件 1 ：ht[0] 承載的元素個(gè)數(shù)已經(jīng)超過(guò)了 ht[0] 的大小，也即d->ht[0].used >= d->ht[0].size，同時(shí) Hash 表可以進(jìn)行擴(kuò)容。
  • 條件 2 ：ht[0] 承載的元素個(gè)數(shù)，是 ht[0] 的大小的 dict_force_resize_ratio 倍，也即 d->ht[0].used/d->ht[0].size > dict_force_resize_ratio 其中，dict_force_resize_ratio 的默認(rèn)值是 5。

rehash 的新 size 是多大?

如果是擴(kuò)容，則新 size 為第一個(gè)大于等于 dict.ht[0].used+1 的2n2^n2n 如果是收縮，則新 size 為第一個(gè)大于等于 dict.ht[0].used 的 2n2^n2n（不得小于4）

漸進(jìn)式 rehash

• Hash 表在執(zhí)行 rehash 時(shí)，由于 Hash 表空間擴(kuò)大，原本映射到某一位置的鍵可能會(huì)被映射到一個(gè)新的位置上，因此，很多鍵就需要從原來(lái)的位置拷貝到新的位置。而在鍵拷貝時(shí)，由于 Redis 主線程無(wú)法執(zhí)行其他請(qǐng)求，所以鍵拷貝會(huì)阻塞主線程，這樣就會(huì)產(chǎn)生 rehash 開銷。為了降低 rehash 開銷，Redis 就提出了漸進(jìn)式 rehash 的方法。

rehash 的步驟

• 給 ht[1] 分配空間；
• 在 rehash 進(jìn)行期間，在rehash過(guò)程中，新增操作，則直接寫入 ht[1]，查詢、修改和刪除則會(huì)在dict.ht[0] 和 dict.ht[1] 依次查找并執(zhí)行。這樣可以確保 ht[0] 的數(shù)據(jù)只減不增。
• 隨著處理客戶端發(fā)起的哈希表操作請(qǐng)求數(shù)量越多，最終在某個(gè)時(shí)間點(diǎn)會(huì)把 ht[0] 的所有 key-value 遷移到 ht[1]，從而完成 rehash 操作。

這樣就巧妙地把一次性大量數(shù)據(jù)遷移工作的開銷，分?jǐn)偟搅硕啻翁幚碚?qǐng)求的過(guò)程中，避免了一次性 rehash 的耗時(shí)操作。

以上就是淺析Redis底層數(shù)據(jù)結(jié)構(gòu)Dict的詳細(xì)內(nèi)容，更多關(guān)于Redis數(shù)據(jù)結(jié)構(gòu)Dict的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論