Redis內部資料結構Dict的實現方法

2022-05-20 19:07:35

一、dict是什麼

不知道大家在用Redis的時候有沒有注意到，我們在使用大多數Redis命令的時候，都會讓你輸入一個key，後面才會讓你輸入具體的值。

我們本篇文章所述的dict在Redis中最主要的作用就是用於維護Redis資料庫中所有Key、value對映的資料結構，也就是我們在輸入set、zadd等命令時輸入的key與後面值的對映。321，上程式碼。程式碼來源(dict.h)。如下程式碼所示，dict結構體裡面有一個dictht 陣列，dictht 裡面的dictEntry 就是具體存放key、value對映關係的。

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;
typedef struct dictht {
    dictEntry **table;
    unsigned long size; //  hashtable 容量
    unsigned long sizemask;  // size -1
    unsigned long used;  // hashtable 元素個數   used / size =1
} dictht;
typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];// ht[0] , ht[1] =null
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

小貼紙：dictEntry 中用到了union聯合體這種結構。也就是多個變數的結構同時使用一塊記憶體區域，區域的取值大小為該結構中長度最大的變數的值。這有利於減少記憶體碎片，提高記憶體利用率，在Java中的壓縮指標技術就用到了聯合體。

二、dict資料結構

1.結構梳理

我們仔細看上面程式碼中的結構，小編可以直接告訴你，其實它就是一個雜湊表結構，在Java中相當於一個HashMap，因為Redis需要保證快速響應，所以選擇雜湊表作為儲存結構是一個不錯的決定。我們這裡只一起了解結構中存具體資料的部分。

dictEntry：其實它就是一個連結串列結構，裡面維護了key、value。
dictht ：它維護了一個dictEntry 指標陣列。雖然我們肉眼能看到定義的是指標的指標，dictEntry **table。但其實指標的指標是指向了dictEntry 陣列指標的首地址。Redis原始碼裡大多會這麼用 table[index]。指標這塊有點繞，可以暫時直接認為它就是一個指標陣列。
dict： dict裡面維護了一個dictht ht[2] 陣列，相當於兩個dictht 結構。為什麼要存兩個dictht 結構呢。因為既然是雜湊表那就要涉及到擴容，redis是單執行緒的，不可能一下子將所有的資料都轉移到新的雜湊表中，這樣可能會造成服務長時間不可用，所以它退而求其次，選擇了"漸進式擴容"。

小貼紙：Redis中的漸進式擴容，採用的是在記憶體中放置兩個雜湊表結構，無需擴容時，使用的是雜湊表0，在擴容期間，將擴容標識設定為true，當有新資料進來的時候，發現正在擴容，就會在將新資料直接放入雜湊表1。而表0中的資料會在每次有請求命令並且請求的資料在表0中時，將請求命令涉及到的資料直接掛到表1上。在擴容期間如果執行查詢命令會查詢表0+表1的資料。

當然，Redis如果一直不執行命令的話。它也會有一個後臺定時任務，對字典進行主動搬遷，它不會對未完成的事置之不理

// 伺服器定時任務
void databaseCron() {
    ...
    if (server.activerehashing) {
        for (j = 0; j < dbs_per_call; j++) {
            int work_done = incrementallyRehash(rehash_db);
            if (work_done) {
                /* If the function did some work, stop here, we'll do
                 * more at the next cron loop. */
                break;
            } else {
                /* If this db didn't need rehash, we'll try the next one. */
                rehash_db++;
                rehash_db %= server.dbnum;
            }
        }
    }
}

2. 擴容條件

當hash表中元素的個數等於陣列長度時，就會開始擴容，擴容的新陣列是原陣列的2倍。
當Redis發生其他情況沒有在元素個數等於陣列長度時擴容，那麼Redis會有一個強制擴容的條件，就是元素個數達到陣列長度5倍時進行強制擴容。

/* Expand the hash table if needed */
static int _dictExpandIfNeeded(dict *d)
{
    /* Incremental rehashing already in progress. Return. */
    if (dictIsRehashing(d)) return DICT_OK;

    /* If the hash table is empty expand it to the initial size. */
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    /* 元素個數大於等於陣列長度&&（能擴容(bgsave時儘量不擴容)或元素大於5倍時強制擴容）
	 * static unsigned int dict_force_resize_ratio = 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);
    }
    return DICT_OK;
}

3. 縮容條件

既然有擴容，當前就有縮容，要不佔那麼大記憶體不是浪費嗎？

當元素小於陣列長度的10%時進行縮容。

int htNeedsResize(dict *dict) {
    long long size, used;

    size = dictSlots(dict);
    used = dictSize(dict);
    return (size > DICT_HT_INITIAL_SIZE &&
            (used*100/size < HASHTABLE_MIN_FILL));
}

dict結構的實現相對來說比較簡單，本文就介紹到這。

到此這篇關於Redis內部資料結構Dict的實現方法的文章就介紹到這了,更多相關redis dict資料結構內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！