前言

哈希結(jié)構(gòu)是一個在計算機中非常常見的結(jié)構(gòu)。哈希結(jié)構(gòu)可以讓我們在O(1)時間復(fù)雜度查找元素并且對其操作，并且增刪改查性能并不會隨著數(shù)據(jù)量的增多而改變。反而數(shù)據(jù)量的增大，會出現(xiàn)兩個關(guān)鍵問題，一個是哈希沖突，另一個是rehash。而在Redis中，使用拉鏈法來解決哈希沖突，使用漸進式rehash來降低rehash的性能開銷。

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

在Redis 6.2.4中，dict.h是這樣定義的。

typedef struct dictEntry {
    void *key;
    //只能為其中任意的一個
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;
/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
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];
    long rehashidx; //-1未進行rehash 
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;

它們的關(guān)系是這樣的

什么是哈希沖突

我們把存儲數(shù)據(jù)的地方看成一個個桶（Bucket），當(dāng)數(shù)據(jù)量超出桶容量或者Hash函數(shù)給出的桶號相同的時候，便會出現(xiàn)哈希沖突。解決辦法就是，采用鏈表的方式，將同一個Bucket位置上的元素連接起來。這樣也會有一個弊端，鏈表太長，開銷又大了起來。所以必定不會無休止的鏈下去，一定要做rehash。

Redis的漸進式rehash

Hash 表在執(zhí)行 rehash 時，由于 Hash 表空間擴大，原本映射到某一位置的鍵可能會被映射到一個新的位置上，因此，很多鍵就需要從原來的位置拷貝到新的位置。而在鍵拷貝時，由于 Redis 主線程無法執(zhí)行其他請求，所以鍵拷貝會阻塞主線程，這樣就會產(chǎn)生 rehash 開銷。而為了降低 rehash 開銷，Redis 就提出了漸進式 rehash 的方法。觀察dict結(jié)構(gòu)，它存儲了兩個相同的dictht， 在正常情況下，所有的數(shù)據(jù)都存儲在ht[0]中。在進行rehash時，會先將數(shù)據(jù)遷移到ht[1]中，等到所有數(shù)據(jù)都遷移完成時，將ht[1] 賦值給ht[0]，并且釋放掉ht[0]空間。

rehash的觸發(fā)條件

Redis 用來判斷是否觸發(fā) rehash 的函數(shù)是**_dictExpandIfNeeded**。所以接下來我們就先看看，_dictExpandIfNeeded 函數(shù)中進行擴容的觸發(fā)條件；

//如果Hash表為空，將Hash表擴為初始大小
if (d->ht[0].size == 0) 
   return dictExpand(d, DICT_HT_INITIAL_SIZE);
//如果Hash表承載的元素個數(shù)超過其當(dāng)前大小，并且可以進行擴容，或者Hash表承載的元素個數(shù)已是當(dāng)前大小的5倍
if (d->ht[0].used >= d->ht[0].size &&(dict_can_resize ||
              d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
{
    return dictExpand(d, d->ht[0].used*2);
}

• 哈希表的 LoadFactor >= 1，并且服務(wù)器沒有執(zhí)行 BGSAVE（RDB快照） 或者 BGREWRITEAOF（AOF重寫） 等后臺進程；
• 哈希表的 LoadFactor > 5 ，表明當(dāng)前的負(fù)載太嚴(yán)重了，需要立即進行擴容；（LoadFactor = used / size）

我們再來看下 Redis 會在哪些函數(shù)中，調(diào)用 _dictExpandIfNeeded 進行判斷。通過在dict.c文件中查看 _dictExpandIfNeeded 的被調(diào)用關(guān)系，我們可以發(fā)現(xiàn)，_dictExpandIfNeeded 是被 _dictKeyIndex 函數(shù)調(diào)用的，而 _dictKeyIndex 函數(shù)又會被 dictAddRaw 函數(shù)調(diào)用，然后 dictAddRaw 會被以下三個函數(shù)調(diào)用。

• dictAdd：用來往 Hash 表中添加一個鍵值對。
• dictReplace：用來往 Hash 表中添加一個鍵值對，或者鍵值對存在時，修改鍵值對。
• dictAddorFind：直接調(diào)用 dictAddRaw。

因此，當(dāng)我們往 Redis 中寫入新的鍵值對或是修改鍵值對時，Redis 都會判斷下是否需要進行 rehash。

擴容擴多大？

在 Redis 中，rehash 對 Hash 表空間的擴容是通過調(diào)用 dictExpand 函數(shù)來完成的。dictExpand 函數(shù)的參數(shù)有兩個，一個是要擴容的 Hash 表，另一個是要擴到的容量，下面的代碼就展示了 dictExpand 函數(shù)的原型定義：

int dictExpand(dict *d, unsigned long size);

那么，對于一個 Hash 表來說，我們就可以根據(jù)前面提到的 _dictExpandIfNeeded 函數(shù)，來判斷是否要對其進行擴容。而一旦判斷要擴容，Redis 在執(zhí)行 rehash 操作時，對 Hash 表擴容的思路也很簡單，就是如果當(dāng)前表的已用空間大小為 size，那么就將表擴容到 size2 的大小。

如下所示，當(dāng) _dictExpandIfNeeded 函數(shù)在判斷了需要進行 rehash 后，就調(diào)用 dictExpand 進行擴容。這里你可以看到，rehash 的擴容大小是當(dāng)前 ht[0]已使用大小的 2 倍。

dictExpand(d, d->ht[0].used*2);

而在 dictExpand 函數(shù)中，具體執(zhí)行是由 _dictNextPower 函數(shù)完成的，以下代碼顯示的 Hash 表擴容的操作，就是從 Hash 表的初始大小（DICT_HT_INITIAL_SIZE），不停地乘以 2，直到達到目標(biāo)大小。

static unsigned long _dictNextPower(unsigned long size)
{
    //哈希表的初始大小
    unsigned long i = DICT_HT_INITIAL_SIZE;
    //如果要擴容的大小已經(jīng)超過最大值，則返回最大值加1
    if (size >= LONG_MAX) return LONG_MAX + 1LU;
    //死循環(huán)直到找到不大于的最小值
    while(1) {
        //如果擴容大小大于等于最大值，就返回截至當(dāng)前擴到的大小
        if (i >= size)
            return i;
        //每一步擴容都在現(xiàn)有大小基礎(chǔ)上乘以2
        i *= 2;
    }
}

為什么叫漸進式

漸進式 rehash 的意思就是 Redis 并不會一次性把當(dāng)前 Hash 表中的所有鍵，都拷貝到新位置，而是會分批拷貝，每次的鍵拷貝只拷貝 Hash 表中一個 bucket 中的哈希項。這樣一來，每次鍵拷貝的時長有限，對主線程的影響也就有限了。

具體過程

關(guān)鍵函數(shù)dictRehash部分代碼

//入?yún)ⅲ篸ict , 需要遷移的元素個數(shù)
int dictRehash(dict *d, int n) {
    int empty_visits = n*10; /* Max number of empty buckets to visit. */
    if (!dictIsRehashing(d)) return 0;
	//遷移元素，直到遷移完畢或者遷移完n個
    while(n-- && d->ht[0].used != 0) {
        //....這段代碼在下面分析
    }
    /* Check if we already rehashed the whole table... */
    //判斷遷移是否完成
    if (d->ht[0].used == 0) {
    	//釋放ht[0]
        zfree(d->ht[0].table);
        //將ht[0] 指向 ht[1]
        d->ht[0] = d->ht[1];
        //讓ht[1]重新指向null
        _dictReset(&d->ht[1]);
        //表示rehash暫停
        d->rehashidx = -1;
        //返回遷移完成
        return 0;
    }
	//還需要繼續(xù)遷移
    /* More to rehash... */
    return 1;
}

那么，每次遷移幾個元素呢？

這就要提到rehashidx了。rehashidx 變量表示的是當(dāng)前 rehash 在對哪個 bucket 做數(shù)據(jù)遷移。比如，當(dāng) rehashidx 等于 0 時，表示對 ht[0]中的第一個 bucket 進行數(shù)據(jù)遷移；當(dāng) rehashidx 等于 1 時，表示對 ht[0]中的第二個 bucket 進行數(shù)據(jù)遷移，以此類推。

而 dictRehash 函數(shù)的主循環(huán)，首先會判斷 rehashidx 指向的 bucket 是否為空，如果為空，那就將 rehashidx 的值加 1，檢查下一個 bucket。

所以，漸進式 rehash 在執(zhí)行時設(shè)置了一個變量 empty_visits，用來表示已經(jīng)檢查過的空 bucket，當(dāng)檢查了一定數(shù)量的空 bucket 后，這一輪的 rehash 就停止執(zhí)行，轉(zhuǎn)而繼續(xù)處理外來請求，避免了對 Redis 性能的影響。下面的代碼顯示了這部分邏輯。

while(n-- && d->ht[0].used != 0) {
    //如果當(dāng)前要遷移的bucket中沒有元素
    while(d->ht[0].table[d->rehashidx] == NULL) {
        //
        d->rehashidx++;
        if (--empty_visits == 0) return 1;
    }
    ...
}

而如果 rehashidx 指向的 bucket 有數(shù)據(jù)可以遷移，那么 Redis 就會把這個 bucket 中的哈希項依次取出來，并根據(jù) ht[1]的表空間大小，重新計算哈希項在 ht[1]中的 bucket 位置，然后把這個哈希項賦值到 ht[1]對應(yīng) bucket 中。

這樣，每做完一個哈希項的遷移，ht[0]和 ht[1]用來表示承載哈希項多少的變量 used，就會分別減一和加一。當(dāng)然，如果當(dāng)前 rehashidx 指向的 bucket 中數(shù)據(jù)都遷移完了，rehashidx 就會遞增加 1，指向下一個 bucket。下面的代碼顯示了這一遷移過程。

 while(n-- && d->ht[0].used != 0) {
   dictEntry *de, *nextde;
    /* Note that rehashidx can't overflow as we are sure there are more
     * elements because ht[0].used != 0 */
    assert(d->ht[0].size > (unsigned long)d->rehashidx);
    while(d->ht[0].table[d->rehashidx] == NULL) {
        d->rehashidx++; 
        if (--empty_visits == 0) return 1;
    }
    de = d->ht[0].table[d->rehashidx];
    /* Move all the keys in this bucket from the old to the new hash HT */
    while(de) {
        uint64_t h;
        nextde = de->next;
        /* Get the index in the new hash table */
        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++;
}

還有一個問題，n的大小是多少?從下面這個函數(shù)可以看到，是1。每次僅僅遷移一個元素，之后變?nèi)?zhí)行主要操作。

static void _dictRehashStep(dict *d) {
    if (d->pauserehash == 0) dictRehash(d,1);
}

看看有哪些函數(shù)調(diào)用了_dictRehashStep，Ctrl+F找一下。它們發(fā)現(xiàn)分別是：dictAddRaw，dictGenericDelete，dictFind，dictGetRandomKey，dictGetSomeKeys。其中，dictAddRaw 和 dictGenericDelete 函數(shù)，分別對應(yīng)了往 Redis 中增加和刪除鍵值對，而后三個函數(shù)則對應(yīng)了在 Redis 中進行查詢操作。調(diào)用關(guān)系如下圖。

總結(jié)

什么是漸進式rehash？為什么要設(shè)計兩個ht？
Redis核心命令執(zhí)行是單線程的，所以一次性遷移全部數(shù)據(jù)開銷很大并且會阻塞服務(wù)。在需要rehash的時候，不會立即將全部數(shù)據(jù)進行遷移，而是通過輔助表來慢慢進行遷移，每次遷移1個元素，進行正常服務(wù)的時候，在ht[1]中進行添加操作，其他操作在ht[0]和ht[1]中一起進行。

rehashidx有什么用？
為-1的時候表示沒有rehash，為0的時候表示要遷移ht[0]中0號元素到ht[1]中，后續(xù)依次類推

rehash觸發(fā)條件？
擴容或者收縮

dict的伸縮：

• 當(dāng)LoadFactor大于5或者LoadFactor大于1并且沒有子進程任務(wù)時，Dict擴容
• 當(dāng)LoadFactor小于0.1時，Dict收縮
• 擴容大小為第一個大于等于used + 1的2^n
• 收縮大小為第一個大于等于used 的2^n
• dict采用漸進式rehash，每次訪問Dict時執(zhí)行一次rehash

到此這篇關(guān)于Redis中哈希結(jié)構(gòu)(Dict)的實現(xiàn)的文章就介紹到這了,更多相關(guān)Redis 哈希結(jié)構(gòu) 內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論