淺析Redis底層數據結構Dict

更新時間：2023年05月30日 09:23:12 作者：WARRIOR

Redis是一個鍵值型的數據庫，我們可以根據鍵實現(xiàn)快速的增刪改查，而鍵與值的映射關系正是通過Dict來實現(xiàn)的，當然?Dict?也是?Set?Hash?的實現(xiàn)方式，本文就詳細帶大家介紹一下Redis底層數據結構?Dict，,需要的朋友可以參考下

Dict 的結構

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

dictht

dictht 的結構如下：

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

dictEntry **table，哈希表數組
unsigned long size，哈希表大?。ㄈ≈禐?2n2^n2n）
unsigned long sizemask，哈希表大小掩碼，用于計算索引值，總是等于 size−1size - 1size−1
unsigned long used，該哈希表已有的節(jié)點數量

dicEntry

dicEntry 結構如下

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

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

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

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

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

dict

在實際使用哈希表時，Redis 沒有使用 dictht ，而是定義一個 dict 結構體，如下

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

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

Dict 的 rehash

前面我們提到，redis 使用鏈式哈希來解決 hash 沖突問題。但是，鏈式哈希也存在局限性，那就是隨著鏈表長度的增加，Hash 表在一個位置上查詢哈希項的耗時就會增加，從而增加了 Hash 表的整體查詢時間，這樣也會導致 Hash 表的性能下降。這時，redis 使用 rehash 來解決這個問題。

Redis 如何實現(xiàn) rehash

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

首先，Redis 準備了兩個哈希表，用于 rehash 時交替保存數據。
- 前面我們提到，redis 在實際使用時，定義了一個 dict 結構體。這個結構體中有一個數組（*ht[2] *），包含了兩個 Hash 表（dictht ） *ht[0] *和 *ht[1] *。
其次，在正常服務請求階段，所有的鍵值對寫入哈希表 ht[0]。
接著，當進行 rehash 時，鍵值對被遷移到哈希表 ht[1]中。
最后，當遷移完成后，ht[0]的空間會被釋放，并把 ht[1] 的地址賦值給 ht[0]，ht[1] 的表大小設置為 0。這樣一來，又回到了正常服務請求的階段，ht[0] 接收和服務請求，ht[1] 作為下一次 rehash 時的遷移表。

什么時候進行 rehash

當我們往 Redis 中寫入新的鍵值對或是修改鍵值對時，Redis 都會判斷下是否需要進行 rehash。而 rehash 的觸發(fā)條件則是
- 條件 1 ：ht[0] 承載的元素個數已經超過了 ht[0] 的大小，也即d->ht[0].used >= d->ht[0].size，同時 Hash 表可以進行擴容。
- 條件 2 ：ht[0] 承載的元素個數，是 ht[0] 的大小的 dict_force_resize_ratio 倍，也即 d->ht[0].used/d->ht[0].size > dict_force_resize_ratio 其中，dict_force_resize_ratio 的默認值是 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í)行其他請求，所以鍵拷貝會阻塞主線程，這樣就會產生 rehash 開銷。為了降低 rehash 開銷，Redis 就提出了漸進式 rehash 的方法。

rehash 的步驟

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

這樣就巧妙地把一次性大量數據遷移工作的開銷，分攤到了多次處理請求的過程中，避免了一次性 rehash 的耗時操作。

以上就是淺析Redis底層數據結構Dict的詳細內容，更多關于Redis數據結構Dict的資料請關注腳本之家其它相關文章！

您可能感興趣的文章: