Dict 優(yōu)點在于，它能以 O(1) 的復(fù)雜度快速查詢數(shù)據(jù)。怎么做到的呢？將 key 通過 Hash 函數(shù)的計算，就能定位數(shù)據(jù)在表中的位置，因為哈希表實際上是數(shù)組，所以可以通過索引值快速查詢到數(shù)據(jù)。

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

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

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

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

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，哈希表大小掩碼，用于計算索引值，總是等于 size−1size - 1size−1
• unsigned long used，該哈希表已有的節(jié)點數(shù)量

dicEntry

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

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

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

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

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

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

dict

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

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

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

Dict 的 rehash

前面我們提到，redis 使用鏈?zhǔn)焦斫鉀Q hash 沖突問題。但是，鏈?zhǔn)焦Ｒ泊嬖诰窒扌?，那就?strong>隨著鏈表長度的增加，Hash 表在一個位置上查詢哈希項的耗時就會增加，從而增加了 Hash 表的整體查詢時間，這樣也會導(dǎo)致 Hash 表的性能下降。這時，redis 使用 rehash 來解決這個問題。

Redis 如何實現(xiàn) rehash

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

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

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

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

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

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

什么時候進行 rehash

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

  • 條件 1 ：ht[0] 承載的元素個數(shù)已經(jīng)超過了 ht[0] 的大小，也即d->ht[0].used >= d->ht[0].size，同時 Hash 表可以進行擴容。
  • 條件 2 ：ht[0] 承載的元素個數(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 是多大?

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

漸進式 rehash

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

rehash 的步驟

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

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

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

最新評論