Redis 8 - 對象編碼之字典

Redis 8 - 對象編碼之字典

目錄

1 字典的實作

2 插入算法

3 rehash 與 漸進式 rehash

總結

字典，是一種用于儲存鍵值對的抽象資料結構。由于 C 語言沒有内置字典這種資料結構，是以 Redis 建構了自己的字典實作。

在 Redis 中，就是使用字典來實作資料庫底層的。對資料庫的 CURD 操作也是建構在對字典的操作之上。

除了用來表示資料庫之外，字典還是哈希鍵的底層實作之一。當一個哈希鍵包含的鍵值對比較多，又或者鍵值對中的元素都是比較長的字元串時，Redis 就會适應字典作為哈希鍵的底層實作。

Redis 的字典使用哈希表作為底層實作。一個哈希表裡面可以有多個哈希表節點，而每個哈希表節點就儲存了字典中的一個鍵值對。

1.1 哈希表

Redis 字典所使用的哈希表結構：

typedef struct dictht {

dictEntry **table;      // 哈希表數組
unsigned long size;     // 哈希表大小
unsigned long sizemask; // 哈希表大小掩碼，用來計算索引
unsigned long used;     // 哈希表現有節點的數量           

} dictht;

table 屬性是一個數組。數組中的每個元素都是一個指向 dictEntry 結構的指針，每個 dictEntry 結構儲存着一個鍵值對。

size 屬性記錄了哈希表的大小，也即是 table 數組的大小。

used 屬性記錄了哈希表目前已有節點（鍵值對）的數量。

sizemask 屬性的值總數等于 size-1，這個屬性和哈希值一起決定一個鍵應該被放到 table 數組中哪個索引上。

圖 1 展示了一個大小為 4 的空哈希表。

大小為4的空哈希表

1.2 哈希表節點

哈希表節點使用 dictEntry 結構表示，每個 dictEntry 結構中都儲存着一個鍵值對：

typedef struct dictEntry {

void *key;              // 鍵
union {
    void *val;          // 值類型之指針
    uint64_t u64;       // 值類型之無符号整型
    int64_t s64;        // 值類型之有符号整型
    double d;           // 值類型之浮點型
} v;                    // 值
struct dictEntry *next; // 指向下個哈希表節點，形成連結清單           

} dictEntry;

key 屬性儲存着鍵，而 v 屬性則儲存着值。

next 屬性是指向另一個哈希表節點的指針。這個指針可以将多個哈希值相同的鍵值對連接配接在一起，以此來解決鍵沖突的問題。

圖 2 展示了通過 next 指針，将兩個索引相同的鍵 k1 和 k0 連接配接在一起的情況。

連接配接在一起的鍵 k1 和 k0

1.3 字典

字典的結構：

typedef struct dict {

dictType *type; // 類型特定函數
void *privdata; // 私有資料
dictht ht[2];   // 哈希表(兩個)
long rehashidx; // 記錄 rehash 進度的标志。值為 -1 表示 rehash 未進行
int iterators;  // 目前正在疊代的疊代器數           

} dict;

dictType 的結構如下：

typedef struct dictType {

// 計算哈希值的函數
unsigned int (*hashFunction)(const void *key);
// 複制鍵的函數
void *(*keyDup)(void *privdata, const void *key);
// 複制值的函數
void *(*valDup)(void *privdata, const void *obj);
// 對比鍵的函數
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
// 銷毀鍵的函數
void (*keyDestructor)(void *privdata, void *key);
// 銷毀值的函數
void (*valDestructor)(void *privdata, void *obj);           

} dictType;

type 屬性和 privdata 屬性是針對不同類型的鍵值對，為建立多态字典而設定的。其中：

type 屬性是一個指向 dictType 結構的指針，每個 dictType 結構儲存了一簇用于操作特定類型鍵值對的函數。Redis 會為用途不用的字典設定不同的類型特定函數。

privdata 屬性儲存了需要傳給那些類型特定函數的可選參數。

而 ht 屬性是一個包含兩個哈希表的數組。一般情況下，字典隻使用 ht[0]，隻有在對 ht[0] 進行 rehash 時才會使用 ht[1]。

rehashidx 屬性，它記錄了 rehash 目前的進度，如果目前沒有進行 rehash，它的值為 -1。至于什麼是 rehash，别急，後面會詳細說明。

圖 3 是沒有進行 rehash 的字典：

沒有進行 rehash 的字典

當在字典中添加一個新的鍵值對時，Redis 會先根據鍵值對的鍵計算出哈希值和索引值，然後再根據索引值，将包含新鍵值對的哈希表節點放到哈希表數組指定的索引上。具體算法如下：

使用字典設定的哈希函數，計算 key 的哈希值

hash = dict->type->hashFunction(key);

使用哈希表的 sizemask 屬性和哈希值，計算出索引值

根據不同情況，使用 ht[0] 或 ht[1]

index = hash & dict[x].sizemask;

圖 4 - 空字典

如圖 4，如果把鍵值對 [k0, v0] 添加到字典中，插入順序如下：

hash = dict-type->hashFunction(k0);

index = hash & dict->ht[0].sizemask; # 8 & 3 = 0

計算得出，[k0, v0] 鍵值對應該被放在哈希表數組索引為 0 的位置上，如圖 5：

圖 5 - 添加 k0-v0 後的字典

2.1 鍵沖突

當有兩個或以上數量的鍵被配置設定到了哈希表數組的同一個索引上面時，我們認為這些鍵發生了建沖突。

Redis 的哈希表使用鍊位址法來解決建沖突。每個哈希表節點都有一個 next 指針，多個哈希表節點可以用 next 指針構成一個單向連結清單，被配置設定到同一個索引的多個節點用 next 指針連結成一個單向連結清單。

舉個栗子，假設我們要把 [k2, v2] 鍵值對添加到圖 6 所示的哈希表中，并且計算得出 k2 的索引值為 2，和 k1 沖突，是以，這裡就用 next 指針将 k2 和 k1 所在的節點連接配接起來，如圖 7。

圖 6 - 一個包含兩個鍵值對的哈希表

圖 7 - 使用連結清單解決 k2 和 k1 沖突

随着對字典的操作，哈希表報錯的鍵值對會逐漸增多或者減少，為了讓哈希表的負載因子維持在一個合理的範圍之内，當哈希表報錯的鍵值對數量太多或者太少時，程式需要對哈希表進行相應的擴容或收縮。這個擴容或收縮的過程，我們稱之為 rehash。

對于負載因子，可以通過以下公式計算得出：

負載因子 = 哈希表已儲存節點數量 / 哈希表大小

load_factor = ht[0].used / ht[0].size;

3.1 哈希表的擴容與收縮

擴容

對于哈希表的擴容，源碼如下：

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);           

}

當以下條件被滿足時，程式會自動開始對哈希表執行擴充操作：

伺服器目前沒有進行 rehash；

哈希表已儲存節點數量大于哈希表大小；

dict_can_resize 參數為 1，或者負載因子大于設定的比率（預設為 5）；

收縮

哈希表的收縮，源碼如下：

int htNeedsResize(dict *dict) {

long long size, used;
size = dictSlots(dict); // ht[2] 兩個哈希表的大小之和
used = dictSize(dict);  // ht[2] 兩個哈希表已儲存節點數量之和
# DICT_HT_INITIAL_SIZE 預設為 4，HASHTABLE_MIN_FILL 預設為 10。
return (size > DICT_HT_INITIAL_SIZE &&
        (used*100/size < HASHTABLE_MIN_FILL));           

void tryResizeHashTables(int dbid) {

if (htNeedsResize(server.db[dbid].dict))
    dictResize(server.db[dbid].dict);
if (htNeedsResize(server.db[dbid].expires))
    dictResize(server.db[dbid].expires);           

當 ht[] 哈希表的大小之和大于 DICT_HT_INITIAL_SIZE（預設 4），且已儲存節點數量與總大小之比小于 4，HASHTABLE_MIN_FILL（預設 10，也就是 10%），會對哈希表進行收縮操作。

3.2 rehash

擴容和收縮哈希表都是通過執行 rehash 操作來完成，哈希表執行 rehash 的步驟如下：

為字典的 ht[1] 哈希表配置設定空間，這個哈希表的空間大小取決于要執行的操作，以及 ht[0] 目前包含的鍵值對數量。

如果執行的是擴容操作，那麼 ht[1] 的大小為**第一個大于等于 ht[0].usedx2 的 2^n。

如果執行的是收縮操作，那麼 ht[1] 的大小為第一個大于等于 ht[0].used 的 2^n。

将儲存在 ht[0] 中的所有鍵值對 rehash 到 ht[1] 上面：rehash 指的是重新計算鍵的哈希值和索引值，然後将鍵值對都遷移到 ht[1] 哈希表的指定位置上。

當 ht[0] 包含的所有鍵值對都遷移到 ht[1] 後，此時 ht[0] 變成空表，釋放 ht[0]，将 ht[1] 設定為 ht[0]，并在 ht[1] 新建立一個空白哈希表，為下一次 rehash 做準備。

示例：

圖 8 - 将要執行 rehash 的字典

假設程式要對圖 8 所示字典的 ht[0] 進行擴充操作，那麼程式将執行以下步驟：

1）ht[0].used 目前的值為 4，那麼 4*2 = 8，而 2^3 恰好是第一個大于等于 8 的，2 的 n 次方。是以程式會将 ht[1] 哈希表的大小設定為 8。圖 9 是 ht[1] 在配置設定空間之後的字典。

圖 9 - 為字典的 ht1 哈希表配置設定空間

2）将 ht[0] 包含的四個鍵值對都 rehash 到 ht[1]，如圖 10。

圖 10 - ht0 所有鍵值對都遷移到 ht1

3）釋放 ht[0]，并将 ht[1] 設定為 ht[0]，然後為 ht[1] 配置設定一個空白哈希表。如圖 11：

圖 11 - 完成 rehash 之後的字段

至此，對哈希表的擴容操作執行完畢，程式成功将哈希表的大小從原來的 4 改為了 8。

3.3 漸進式 rehash

對于 Redis 的 rehash 而言，并不是一次性、集中式的完成，而是分多次、漸進式地完成，是以也叫漸進式 rehash。

之是以采用漸進式的方式，其實也很好了解。當哈希表裡儲存了大量的鍵值對，要一次性的将所有鍵值對全部 rehash 到 ht[1] 裡，很可能會導緻伺服器在一段時間内隻能進行 rehash，不能對外提供服務。

是以，為了避免 rehash 對伺服器性能造成影響，Redis 分多次、漸進式的将 ht[0] 裡面的鍵值對 rehash 到 ht[1]。

漸進式 rehash 就用到了索引計數器變量 rehashidx，詳細步驟如下：

為 ht[1] 配置設定空間，讓字典同時持有 ht[0] 和 ht[1] 兩個哈希表。

在字段中維持一個索引計數器變量 rehashidx，并将它的值設定為 0，表示開始 rehash。

在 rehash 期間，每次對字典執行 CURD 操作時，程式除了執行指定的操作外，還會将 ht[0] 哈希表在 rehashidx 索引上的所有鍵值對移動到 ht[1]，當 rehash 完成後，程式将 rehashidx 的值加一。

随着不斷操作字典，最終在某個時間點上，ht[0] 的所有鍵值對都會被 rehash 到 ht[1]，這時程式将 rehashidx 屬性的值設為 -1，表示 rehash 已完成。

漸進式 rehash 才有分而治之的方式，将 rehash 鍵值對所需要的計算工作均攤到對字典的 CURD 操作上，進而避免了集中式 rehash 帶來的問題。

此外，字典在進行 rehash 時，删除、查找、更新等操作會在兩個哈希表上進行。例如，在字典張查找一個鍵，程式會現在 ht[0] 裡面進行查找，如果沒找到，再去 ht[1] 上查找。

要注意的是，新增的鍵值對一律隻儲存在 ht[1] 裡，不在對 ht[0] 進行任何添加操作，保證了 ht[0] 包含的鍵值對數量隻減不增，随着 rehash 操作最終變成空表。

圖 12 至 圖 17 展示了一次完整的漸進式 rehash 過程：

1）未進行 rehash 的字典

圖 12 - 未進行 rehash 的字典

2） rehash 索引 0 上的鍵值對

圖 13 - rehash 索引 0 上的鍵值對

3）rehash 索引 1 上的鍵值對

圖 14 - rehash 索引 1 上的鍵值對

4）rehash 索引 2 上的鍵值對

圖 15 - rehash 索引 2 上的鍵值對

5）rehash 索引 3 上的鍵值對

圖 16 - rehash 索引 3 上的鍵值對

6）rehash 執行完畢

圖 17 - rehash 執行完畢

字段被廣泛用于實作 Redis 的各種功能，其中包括資料庫和哈希鍵。

Redis 中的字典使用哈希表作為底層實作，每個字典帶有兩個哈希表，一個平時使用，一個僅在 rehash 時使用。

哈希表使用鍊位址法來解決鍵沖突，被配置設定到同一個索引上的多個鍵值對會連接配接成一個單向連結清單。

在對哈希表進行擴容或收縮操作時，使用漸進式完成 rehash。

喜歡就給個大拇指吧！

原文位址

https://www.cnblogs.com/BeiGuo-FengGuang/p/11301070.html