Dict基本結(jié)構(gòu)

Dict我們可以想象成目錄，要翻看什么內(nèi)容，直接通過目錄能找到頁(yè)數(shù)，翻過去看。如果沒有目錄，我們需要一頁(yè)一頁(yè)往后翻，這樣時(shí)間復(fù)雜度就與遍歷的O(n)一樣了，而用了Dict我們就可以在O(1)的時(shí)間復(fù)雜度內(nèi)快速找到鍵對(duì)應(yīng)的值。說(shuō)到這里，大家會(huì)覺得Dict與JAVA中的哈希表功能差不多，其實(shí)，Redis的Dict數(shù)據(jù)結(jié)構(gòu)底層實(shí)現(xiàn)正是哈希表，不過維護(hù)了2個(gè)哈希表。Redis實(shí)現(xiàn)Dict數(shù)據(jù)結(jié)構(gòu)創(chuàng)建了三個(gè)重要的結(jié)構(gòu)體，分別是dict、dictht和dictEntry。下面先給出Dict的整體結(jié)構(gòu)幫助大家更好的理解一下：

dict

typedef struct dict{
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx;
    unsigned long iterators;
} dict;

• ht[2]：表示在一個(gè)Dict結(jié)構(gòu)中，包含有兩個(gè)dictht的結(jié)構(gòu)，也就是我們說(shuō)的兩張哈希表。
• rehashidx：是dict在rehash時(shí)的偏移索引，具體如何工作在后邊的rehash過程中會(huì)詳細(xì)講。

dictht

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

• table：指向?qū)嶋Hhash存儲(chǔ)。存儲(chǔ)可以看做是一個(gè)數(shù)組，所以是*table表示。（源碼中的**table是一個(gè)二級(jí)指針，也就是指向dictEntry*的指針）。
• size：哈希表的大小。實(shí)際就是dictEntry有多少元素空間。
• sizemask：哈希表大小的掩碼表示，總是等于size-1.這個(gè)屬性和哈希值一起決定一個(gè)鍵應(yīng)該被放到table數(shù)組的哪個(gè)索引上面，索引計(jì)算規(guī)則是index=hash&sizemask，前提是size的大小是二次方冪，這一點(diǎn)與JAVA哈希表底層計(jì)算索引是一樣的原理。
• used：表示已經(jīng)使用的節(jié)點(diǎn)數(shù)量。通過這個(gè)字段可以很方便地查詢到目前dict元素總量。

dictEntry

typedef struct dictEntry{
     void *key;
     union{
          void *val;
          uint64_tu64;
          int64_ts64;
     }v;
     struct dictEntry *next;
}dictEntry

• *key：存儲(chǔ)鍵。
• v：用來(lái)存儲(chǔ)具體的值，可以看到，值可以是一個(gè)指針，可以是uint64_t整數(shù)，也可以是int64_t整數(shù)。
• *next：用于采用拉鏈法將相同索引的dictEntry串起來(lái)，解決哈希沖突問題。（采用的是頭插法，JAVA中JDK8之后采用的是尾插法，留個(gè)小問題，為什么JAVA中不延續(xù)使用頭插法？）

Dict的漸進(jìn)式擴(kuò)容機(jī)制

想必大家有一個(gè)疑問，為什么Dict底層要維護(hù)兩張哈希表，實(shí)際存儲(chǔ)的話使用一張哈希表不就可以了嗎。其實(shí)，第二張哈希表的存在是為了給第一張哈希表的擴(kuò)容提供支持。下面我們來(lái)詳細(xì)介紹一下Dict中哈希表的漸進(jìn)式擴(kuò)容流程和擴(kuò)容時(shí)機(jī)。

Dict漸進(jìn)式擴(kuò)容流程

首先，當(dāng)向字典添加新元素時(shí)，發(fā)現(xiàn)第一張哈希表ht[0]需要擴(kuò)容，就會(huì)進(jìn)行rehash操作，為第二張哈希表ht[1]分配空間。ht[1]表的大小為大于等于ht[0]表used值的2倍的2次方冪。舉個(gè)例子，如果ht[0]中已經(jīng)使用的節(jié)點(diǎn)數(shù)量為500，那么擴(kuò)容時(shí)ht[1]被分配的空間是1024而不是1000。這么做是為了維護(hù)擴(kuò)容后表的大小始終是2次方冪。

接著，dict的rehashidx由靜默狀態(tài)（-1）變?yōu)殚_始工作狀態(tài)（0）。

最后，遷移ht[0]中的數(shù)據(jù)到ht[1]，也就是將數(shù)據(jù)從舊表中遷移到新表中。在rehash進(jìn)行期間，每次對(duì)dict執(zhí)行增刪改查操作，程序會(huì)順帶遷移當(dāng)前rehashidx在ht[0]上對(duì)應(yīng)的數(shù)據(jù)，并更新偏移索引。與此同時(shí)，部分情況周期函數(shù)也會(huì)進(jìn)行遷移。如果rehashidx剛好在一個(gè)已刪除的空位置上，那么是直接返回還是嘗試往下找？我們來(lái)看一下dictRehash函數(shù)的源碼：

//int empty_visits = n*10;//Max number of empty buckets to visit.

while(d->ht[0].table[d->rehashidx] == NULL) {
    d->rehashidx++;
    if (--empty_visits == 0) return 1;
}

可以看到，答案是會(huì)繼續(xù)往下去找，但是有個(gè)上限是n*10，即最多再找這么多次，n是傳進(jìn)來(lái)的參數(shù)，調(diào)用的時(shí)候?qū)嶋H值為1，即最多往后再找10個(gè)，這么做是防止因?yàn)檫B續(xù)碰到空位置導(dǎo)致主線程操作被阻塞。

隨著字典操作的不斷執(zhí)行，最終在某個(gè)時(shí)間點(diǎn)上，ht[0]的所有鍵值對(duì)都會(huì)被rehash到ht[1]，此時(shí)再將ht[1]和ht[0]指針對(duì)象互換，同時(shí)將rehashidx設(shè)置為-1，表示rehash工作已經(jīng)完成。這個(gè)事情也是在rehash函數(shù)做的，每次遷移完一個(gè)元素，會(huì)檢查是否已經(jīng)完成了整個(gè)遷移：

if (d->ht[0].used == 0) {
    zfree(d->ht[0].table);
    d->ht[0] = d->ht[1];
    _dictReset(&d->ht[1]);
    d->rehashidx = -1;
    return 0;
}

總結(jié)一下，漸進(jìn)式擴(kuò)容的核心就是刪改查操作時(shí)順帶遷移，其中增的操作直接增到新表中。

Dict漸進(jìn)式擴(kuò)容時(shí)機(jī)

Redis提出了一個(gè)負(fù)載因子的概念（與JAVA中的負(fù)載因子不同），用于表示目前Dict的使用情況，是情況良好還是已經(jīng)堵塞不堪。設(shè)負(fù)載椅子為F，那么負(fù)載因子計(jì)算公式為F=ht[0].used/ht[0].size,也就是使用空間大小和總空間大小的比值。Redis會(huì)根據(jù)負(fù)載因子的情況來(lái)進(jìn)行擴(kuò)容。

當(dāng)負(fù)載因子的值小于1時(shí)，認(rèn)為dict的使用情況良好，不需要進(jìn)行擴(kuò)容。

當(dāng)負(fù)載因子的值大于等于1時(shí)，說(shuō)明此時(shí)的dict空間已經(jīng)非常緊張了，新增的數(shù)據(jù)會(huì)發(fā)生哈希沖突在鏈表上堆疊。如果此時(shí)服務(wù)器沒有執(zhí)行BGSAVE或者BGREWRITEAOF這兩個(gè)復(fù)制命令，就會(huì)立刻進(jìn)行擴(kuò)容，反之則不會(huì)立刻擴(kuò)容。

當(dāng)負(fù)載因子的值大于5時(shí)，說(shuō)明此時(shí)的dict中哈希沖突已經(jīng)非常嚴(yán)重了，哈希表的搜索性能嚴(yán)重退化向鏈表。此時(shí)不管服務(wù)器是否在執(zhí)行復(fù)制命令，都會(huì)立刻對(duì)哈希表進(jìn)行擴(kuò)容操作。

Dict為什么采用漸進(jìn)式擴(kuò)容機(jī)制？

在JAVA中，哈希表其實(shí)也有擴(kuò)容操作，并且是在單張表上完成的rehash操作。但是對(duì)于Redis中的Dict來(lái)說(shuō)，兩者存放的數(shù)據(jù)量不在一個(gè)量級(jí)上，由于Redis是單線程的，如果對(duì)dict中存放的大量數(shù)據(jù)進(jìn)行一次性rehash，那么耗費(fèi)的時(shí)間會(huì)非常久，從而造成主線程的長(zhǎng)時(shí)間阻塞。為了性能考慮，Dict采用空間換時(shí)間的方法，多花費(fèi)一張表的空間，配合漸進(jìn)式擴(kuò)容機(jī)制，幾乎完全消除rehash可能造成的主線程阻塞。

Dict的漸進(jìn)式縮容機(jī)制

擴(kuò)容是數(shù)據(jù)太多裝不下，那么對(duì)應(yīng)的縮容就是空間太富裕造成了浪費(fèi)?？s容的過程其實(shí)和擴(kuò)容是相似的，也是漸進(jìn)式縮容，這里就不詳細(xì)展開了。

同樣的，Redis也通過負(fù)載因子來(lái)控制什么時(shí)候縮容：

當(dāng)負(fù)載因子大于等于0.1時(shí)，認(rèn)為dict的空間合適，不需要進(jìn)行縮容。

當(dāng)負(fù)載因子小于0.1時(shí)，認(rèn)為dict的空間太大造成浪費(fèi)，進(jìn)行縮容。ht[1]的大小為第一個(gè)大于等于ht[0]中used值的2次方冪（最小為4，如果已經(jīng)是4了那就保持不變）。

同樣的，如果有BGSAVE或者BGREWRITEAOF這兩個(gè)復(fù)制操作正在執(zhí)行，縮容也會(huì)受影響，不會(huì)進(jìn)行。

總結(jié)

Dict數(shù)據(jù)結(jié)構(gòu)提供了快速索引數(shù)據(jù)的能力，其結(jié)構(gòu)的設(shè)計(jì)和漸進(jìn)式擴(kuò)容的設(shè)計(jì)很值得大家學(xué)習(xí)。

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

最新評(píng)論