前言

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

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

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

typedef struct dictEntry {
    void *key;
    //只能為其中任意的一個(gè)
    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未進(jìn)行rehash 
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;

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

什么是哈希沖突

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

Redis的漸進(jìn)式rehash

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

rehash的觸發(fā)條件

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

//如果Hash表為空，將Hash表擴(kuò)為初始大小
if (d->ht[0].size == 0) 
   return dictExpand(d, DICT_HT_INITIAL_SIZE);
//如果Hash表承載的元素個(gè)數(shù)超過(guò)其當(dāng)前大小，并且可以進(jìn)行擴(kuò)容，或者Hash表承載的元素個(gè)數(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ù)器沒(méi)有執(zhí)行 BGSAVE（RDB快照） 或者 BGREWRITEAOF（AOF重寫(xiě)） 等后臺(tái)進(jìn)程；
• 哈希表的 LoadFactor > 5 ，表明當(dāng)前的負(fù)載太嚴(yán)重了，需要立即進(jìn)行擴(kuò)容；（LoadFactor = used / size）

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

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

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

擴(kuò)容擴(kuò)多大？

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

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

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

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

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

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

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

為什么叫漸進(jìn)式

漸進(jìn)式 rehash 的意思就是 Redis 并不會(huì)一次性把當(dāng)前 Hash 表中的所有鍵，都拷貝到新位置，而是會(huì)分批拷貝，每次的鍵拷貝只拷貝 Hash 表中一個(gè) bucket 中的哈希項(xiàng)。這樣一來(lái)，每次鍵拷貝的時(shí)長(zhǎng)有限，對(duì)主線(xiàn)程的影響也就有限了。

具體過(guò)程

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

//入?yún)ⅲ篸ict , 需要遷移的元素個(gè)數(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個(gè)
    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;
}

那么，每次遷移幾個(gè)元素呢？

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

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

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

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

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

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

 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++;
}

還有一個(gè)問(wèn)題，n的大小是多少?從下面這個(gè)函數(shù)可以看到，是1。每次僅僅遷移一個(gè)元素，之后變?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ù)，分別對(duì)應(yīng)了往 Redis 中增加和刪除鍵值對(duì)，而后三個(gè)函數(shù)則對(duì)應(yīng)了在 Redis 中進(jìn)行查詢(xún)操作。調(diào)用關(guān)系如下圖。

總結(jié)

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

rehashidx有什么用？
為-1的時(shí)候表示沒(méi)有rehash，為0的時(shí)候表示要遷移ht[0]中0號(hào)元素到ht[1]中，后續(xù)依次類(lèi)推

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

dict的伸縮：

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

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

最新評(píng)論