Redis 中的字典是如何實現的？

寫在文章開頭

redis作為非關聯式資料庫，其底層採用了字典(也稱為對映)儲存鍵值對。本文會基於原始碼分析的方式帶你瞭解redis中這一常見數據結構的精巧設計，希望對你有幫助。

詳解redis中的字典的設計與實現

雜湊表的基本數據結構

字典用table管理當前儲存鍵值對的陣列，這個陣列的大小可有size這個欄位知曉，每當我們有一個鍵值對要儲存到字典時就會透過sizemask進行按位與運算得到table陣列的某個索引位置將當前鍵值對儲存，然後自增一個used標識當前有一個節點加入。

可能上文說的比較抽象，我們不妨舉個例子，假設我們現在鍵入如下指令:

HSET student  xiaoming 18

redis完成命令解析後，定位到student這個key對應的欄位空間的字典，找到當前正在使用的雜湊表，按照如下步驟完成鍵值對儲存：

1. 計算xiaoming的雜湊值。

2. 將計算出的雜湊值和sizemask即3，也就是陣列的索引範圍進行按位與運算，得到對應的陣列索引位置。

3. 檢視該位置是否有元素，如果沒有則直接新增，反之追加到該dictEntry的後面，這也就是我們常說的鏈地址法。

4. used欄位自增一下，表示當前雜湊表有一個元素。

我們可以在dict.h看到上文所提及的雜湊表和字典中每一個元素的數據結構：

typedef struct dictht {
 //儲存鍵值對的雜湊表
    dictEntry **table;
    //當前雜湊表的大小
    unsigned long size;
    //計算雜湊值的掩碼值
    unsigned long sizemask;
    //當前雜湊表的節點數
    unsigned long used;
} dictht;

//記錄鍵值對的數據結構dictEntry 
typedef struct dictEntry {
 //指向鍵的指標
    void *key;
    
    //透過共用體儲存值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    //next指標指向下一個dictEntry 
    struct dictEntry *next;
} dictEntry;

字典的數據結構

雜湊表在極端演算法情況下會造成大量鍵值對衝突碰撞的情況，導致查詢效率由原來的O(n)變為O(1)，所以爲了保證針對衝突的陣列進行最佳化，redis的字典採用的雙陣列的方式管理鍵值對，如下圖所示，可以看到dict的數據結構定義了大小為2的雜湊表陣列，當某個雜湊表碰撞激烈需要進行調整時就調整演算法將對應的鍵值對存到dictht[1]，並透過rehashidx標誌為-1表示當前處於漸進式雜湊階段：

對應的我們也可以在dict.h看到dict 的定義：

typedef struct dictht {
 //儲存鍵值對的雜湊表
    dictEntry **table;
    //當前雜湊表的大小
    unsigned long size;
    //計算雜湊值的掩碼值
    unsigned long sizemask;
    //當前雜湊表的節點數
    unsigned long used;
} dictht;

//記錄鍵值對的數據結構dictEntry 
typedef struct dictEntry {
 //指向鍵的指標
    void *key;
    
    //透過共用體儲存值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    //next指標指向下一個dictEntry 
    struct dictEntry *next;
} dictEntry;

字典的建立

進行鍵值對建立時，dictCreate會進行必要的記憶體分配，然後進入初始化工作：

1. 初始化兩個雜湊表空間。

2. 設定型別特定函式type ，這個type 包含了各種型別雜湊值計算、值複製以及鍵比對等各種方法的指標。

3. 設定私有資料privdata 。

4. 初始化rehashidx 為-1表示未進行漸進式再雜湊。

對應的我們可以在dict.c中看到這段原始碼：

/* Create a new hash table */
dict *dictCreate(dictType *type,
        void *privDataPtr)
{
 //記憶體分配
    dict *d = zmalloc(sizeof(*d));
 //字典初始化
    _dictInit(d,type,privDataPtr);
    return d;
}

/* Initialize the hash table */
int _dictInit(dict *d, dictType *type,
        void *privDataPtr)
{
 //重置雜湊表
    _dictReset(&d->ht[0]);
    _dictReset(&d->ht[1]);
    //設定型別特定函式和私有資料
    d->type = type;
    d->privdata = privDataPtr;
    //初始化漸進式雜湊標識
    d->rehashidx = -1;
    d->iterators = 0;
    return DICT_OK;
}

元素的插入

字典的插入操作大體流程也很市面上常見的雜湊表實現差不多，透過雜湊演算法(MurmurHash2)定位元素插入的位置再進行插入操作，唯一有所區別的是，redis版本字典的鏈地址法解決衝突的上的最佳化，爲了保證雜湊定位的位置存在元素時能夠快速插入，redis字典的插入採用的是頭插法，即將最新的元素作為連結串列頭元素插入:

與之對應的我們給出程式碼的入口，也就是dict.c下的dictAdd方法，可以看到其內部是透過完成鍵的新增，只有key插入成功後纔會透過setVal方法維護插入的entry的值：

int dictAdd(dict *d, void *key, void *val)
{
 //透過dictAddRaw完成key的插入
    dictEntry *entry = dictAddRaw(d,key);
 //如果插入成功再維護value
    if (!entry) return DICT_ERR;
    dictSetVal(d, entry, val);
    return DICT_OK;
}

dictAddRaw邏輯也比較簡單，先檢查當前的字典表是否因為大量衝突而處理漸進式雜湊(關於漸進式雜湊後文會詳細講解，這裏也補充一些簡單的概念)，透過_dictKeyIndex定位到當前元素插入的索引位置，採用頭插法將其插入到對應索引位置的連結串列首部:

dictEntry *dictAddRaw(dict *d, void *key)
{
    int index;
    dictEntry *entry;
    dictht *ht;
 //是否處於漸進式雜湊階段
    if (dictIsRehashing(d)) _dictRehashStep(d);

   //定位索引位置
    if ((index = _dictKeyIndex(d, key)) == -1)
        return NULL;

   //定位要儲存元素的雜湊表位置
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    //分配記憶體空間
    entry = zmalloc(sizeof(*entry));
    //採用頭插法將元素插入到對應雜湊表的索引位置上
    entry->next = ht->table[index];
    ht->table[index] = entry;
    //當前插入元素數加一
    ht->used++;

    /* Set the hash entry fields. */
    dictSetKey(d, entry, key);
    return entry;
}

雜湊衝突及其對應解決方案

隨著我們不斷的新增鍵值對，當前的雜湊演算法得到的索引位置很大機率會出現雜湊衝突，即每次定位到的索引位置都很大機率存在元素，這也就是我們的常說的雜湊衝突，這就是redis的字典預設會初始化兩張雜湊表的原因所在。 符合以下兩個條件時，字典就會觸發擴容機制:

1. 未進行BGSAPE命令或者BGREWRITEAOF持久化操作，且當前雜湊表元素數何雜湊表空間大小一樣。

2. 正進行BGSAPE命令或者BGREWRITEAOF持久化操作，當且雜湊表元素數是雜湊表空間的5倍。

觸發擴容時，字典會將rehashidx設定為0意為當前因為大量衝突碰撞而從0索引開始漸進式再雜湊，ht[1]就會開闢一個ht[0]即當前正在使用的雜湊表空間大小*2的空間，後續的新插入的元素也都會根據雜湊演算法將元素插入到ht[1]中。 對於舊有存在的元素，考慮到整個雜湊表可能存在不可預估數量的鍵值對，redis的字典會透過漸進式雜湊的方式在元素每次進行增刪改查操作時將舊有元素遷移到ht[1]中，一旦所有元素全部遷移到ht[1]後，雜湊表就會將ht[1]指向的雜湊表指標賦值給ht[0]，並將ht[0]原有雜湊表釋放。

瞭解整體的設計之後，我們就可以從原始碼角度印證這個問題了，可以看到字典在每次進行雜湊索引定位時都會呼叫_dictKeyIndex方法，而該方法內部則有一個_dictExpandIfNeeded操作，其內部就會根據我們上文所說的閾值判斷當前雜湊表是否需要進行擴容:

static int _dictKeyIndex(dict *d, const void *key)
{
    unsigned int h, idx, table;
    dictEntry *he;

    //判斷當前雜湊表是否需要進行擴容操作
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;
   //獲取當前key的雜湊值
    h = dictHashKey(d, key);
    //計算雜湊值
    for (table = 0; table <= 1; table++) {
     //計算索引
        idx = h & d->ht[table].sizemask;
  
        he = d->ht[table].table[idx];
        while(he) {
            if (dictCompareKeys(d, key, he->key))
                return -1;
            he = he->next;
        }
        //如果不處於漸進式雜湊階段，則直接將該索引值返回，後續元素直接存入ht[0]表中，反之進入下一個迴圈計算當前元素在ht[1]表的索引
        if (!dictIsRehashing(d)) break;
    }
    return idx;
}

我們繼續步入_dictExpandIfNeeded即可看到擴容判斷的邏輯，也就是我們上文所說的符合兩個擴容條件之一時就會觸發擴容：

static int _dictExpandIfNeeded(dict *d)
{
 //如果正處於漸進式雜湊則直接返回
    if (dictIsRehashing(d)) return DICT_OK;

   //......
   //如果當前有子程序進行持久化操作則dict_can_resize為false，所以當字典元素數大於等於雜湊表大小且未進行持久化，或進行持久化操作且元素數是雜湊表的5倍時纔會進行擴容操作，dictExpand會將rehashidx設定為0，告知當前雜湊表進行擴容需要進行漸進式再雜湊
    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;
}

此時我們再回看之前的鍵值對插入操作，它會根據dictIsRehashing判斷rehashidx是否為0，從而呼叫_dictRehashStep進入漸進式雜湊操作在鍵值對維護：

dictEntry *dictAddRaw(dict *d, void *key)
{
    int index;
    dictEntry *entry;
    dictht *ht;
 //如果處於再雜湊階段，若符合要求則進行一次ht[0]雜湊表元素驅逐操作
    if (dictIsRehashing(d)) _dictRehashStep(d);

   //儲存鍵值對操作
   //......
    return entry;
}

我們直接檢視_dictRehashStep內部的實現就可以看到一個dictRehash的方法，它就是漸進式雜湊的核心實現，可以看到該方法會從0開始每次驅逐10個元素到ht[1]中：

int dictRehash(dict *d, int n) {
 //驅逐10個元素
    int empty_visits = n*10; 
    if (!dictIsRehashing(d)) return 0;
    
 //將當前rehashidx中的元素驅逐到ht[1]中
    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;

        
        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        //當前索引位置為空，說明驅逐完成返回1，下次繼續
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        de = d->ht[0].table[d->rehashidx];
        //計算當前元素在ht[1]中的位置並驅逐過去
        while(de) {
            unsigned int 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++;
    }

  //used 為0說明所有元素驅逐完成，將ht[1]指向的雜湊表賦值給ht[0]，重置rehashidx ，並返回0
    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;
    }

    /* More to rehash... */
    return 1;
}

查詢操作

有了上述的基礎後，我們檢視查詢操作就比較簡單了，其步驟比較固定:

1. 計算key的雜湊值。

2. 計算對應索引位置到ht[0]定位，如果找到了直接返回。

3. 如果沒找到，檢視當前是否處於擴容階段，若是則到ht[1]進行雜湊定位，若找到直接返回。

4. 上述操作都未找到該元素，直接返回null。

dictEntry *dictFind(dict *d, const void *key)
{
    //......
    //計算雜湊值
    h = dictHashKey(d, key);
    //透過雜湊演算法定位索引，到雜湊表進行查詢
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        //遍歷當前索引位置的元素，找到比對一致的返回
        while(he) {
            if (dictCompareKeys(d, key, he->key))
                return he;
            he = he->next;
        }
        //上一步沒找到則判斷是否處於擴容，若處於擴容則進入下一個迴圈到ht[1]表找，反之直接返回null
        if (!dictIsRehashing(d)) return NULL;
    }
    return NULL;
}

刪除操作

同理我們最後給出刪除操作的原始碼，也查詢操作一樣，定位到元素後，將其從索引位置中解除該元素和前驅節點關係即可:

static int dictGenericDelete(dict *d, const void *key, int nofree)
{
 //......
 
    //定位元素
    h = dictHashKey(d, key);
 
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        prevHe = NULL;
        while(he) {
         //找到比對一致的鍵值對
            if (dictCompareKeys(d, key, he->key)) {
               //解除該元素和前驅節點的關係
                if (prevHe)
                    prevHe->next = he->next;
                else
                    d->ht[table].table[idx] = he->next;
                //釋放當前節點
                if (!nofree) {
                    dictFreeKey(d, he);
                    dictFreeVal(d, he);
                }
                zfree(he);
                //元素數減去1
                d->ht[table].used--;
                return DICT_OK;
            }
            prevHe = he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return DICT_ERR; /* not found */
}

小結

本文筆者從字典的數據結構和常見操作的角度對redis中字典的設計思想和最佳化思路進行深入的剖析，希望對你有幫助。

參考

《Redis設計與實現》