redis簡介（四）雜湊演算法和rehash

1. hash算法

添加一個鍵值對到redis時，首先要根據key算出hash值和索引，然後根據索引将新鍵值對的hash表節點關聯索引。

計算hash和索引，假設hash值為456（‭000111001000）， 掩碼為255‬（‭11111111‬）

則得到的索引為200（11001000）

#define dictHashKey(d, key) (d)->type->hashFunction(key)
unsigned int h;
dictEntry *he;
h = dictHashKey(ht, key) & ht->sizemask;
he = ht->table[h];
           

2. 解決hash沖突

如果兩個不同的key經過hash函數計算後，得到了相同的hash鍵，則說明鍵沖突了。redis使用拉鍊法解決沖突。每個節點有一個next指針，新的鍵值對沖突時，則将新的鍵值對dictEntry放在單連結清單的首部（注意不是尾部）。

typedef struct dictEntry {
    void *key;
    void *val;
    struct dictEntry *next;
} dictEntry;
           

通路時，依次周遊單連結清單

#define dictCompareHashKeys(ht, key1, key2) \
    (((ht)->type->keyCompare) ? \
        (ht)->type->keyCompare((ht)->privdata, key1, key2) : \
        (key1) == (key2))
        ......
    he = ht->table[h];
    while(he) {
        if (dictCompareHashKeys(ht, key, he->key))
            return -1;
        he = he->next;
    }
    return h;
           

3. rehash

随着時間的推移，hash表中鍵值對有可能會逐漸增多或是較少。讓redis的負載因子，維持在一個合理的範圍，有利于系統更好的管理記憶體資源。鍵值對過多或者過少的，就需要對哈希表進行動态擴容或者收縮，而這些操作都是通過rehash重新散列來實作的。

rehash大緻有以下三步

1. 重新為ht[1]配置設定空間，大小取決于ht[0].used的值。如果是擴容，ht[1]大小為(2^n)*ht[0].used。如果是收縮，ht[1]大小為2^n，這個2^n是第一個大于ht[0].used的2的n次幂。

2. 将ht[0]上的鍵值對重新計算哈希值和索引，然後鍵值對放到ht[1]上。

3. 釋放ht[0], 将ht[1] 設定為ht[0], 在ht[1]新建立一個空白哈希表。

在沒有執行bgsave時，負載計算公式， 負載因子 = 哈希表已儲存的節點數量 / 哈希表大小

4. 漸進式rehash

數量較少的情況下，rehash可以短時間内一次性完成，幾百個、幾千個對現在的計算機來說這都不是事兒。但是如果是百萬、千萬、億以上這個級别。可能就需要一段時間了。而這個過程中，又要保證服務不中斷，業務不受影響，那麼就得需要分批次、漸進式的rehash了。

主要4個步驟

1. 為ht[1]配置設定空間

2. 索引計數器rehashidx置零

3. 一次rehash之後，ht[0]上鍵值對放到ht[1],rehashidx加一

4. 全部rehash之後，rehashidx屬性設定為-1

在rehash期間，字典的删除、查找、修改等在兩個哈希表上進行。現在ht[0]裡面找，找不到再去ht[1]找。新增則直接在ht[1]增加。

參考

[1] redis設計與實作

[2] http://www.redis.cn/documentation.htm