Redis Hash 源碼
- dict.h：定義 Hash 表的結(jié)構(gòu)、哈希項，和 Hash 表的各種函數(shù)操作
- dict.c：函數(shù)的具體實現(xiàn)
Redis Hash 數(shù)據(jù)結(jié)構(gòu)
在 dict.h 文件中，Hash 表是一個二維數(shù)組（dictEntry **table）。
typedef struct dictht {
// 二維數(shù)組
dictEntry **table;
// Hash 表大小
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
dictEntry **table 是個二維數(shù)組，其中第一維是 bucket，每一行就是 bucket 指向的元素列表（因為鍵哈希沖突，Redis 采用了鏈?zhǔn)焦＃?/p>
為了實現(xiàn)鏈?zhǔn)焦?，Redis 的 dictEntry 結(jié)構(gòu)中，除了包含鍵和值的指針，還包含了一個指向下一個哈希項的指針 next。
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;
整體的哈希流程都是老生常談了，和 Java 幾乎是一樣的，這里就不敘述了。
Redis rehash 原理
為什么要 rehash？
為了性能。如果哈希表 bucket 的數(shù)量是 1，但是里面有了 1000 個元素，不管怎么樣都變成了一個鏈表，查詢效率變得很低。同理，當(dāng)哈希表里元素的個數(shù)比 bucket 數(shù)量多很多的時候，效率也會低很多。
Redis dict 數(shù)據(jù)結(jié)構(gòu)
Redis 實際使用的是 dict 數(shù)據(jù)結(jié)構(gòu)，內(nèi)部用兩個 dictht（ht[0] 和 ht[1]），用于 rehash 使用。
typedef struct dict {
……
// 兩個 Hash 表，交替使用，用于 rehash 操作
dictht ht[2];
// Hash 表是否進(jìn)行 rehash 的標(biāo)識，-1 表示沒有進(jìn)行 rehash
long rehashidx;
……
} dict;
Redis rehash 過程
- 正常請求階段，所有的鍵值對都寫入哈希表 ht[0]
- 進(jìn)行 rehash 時，鍵值對被遷移到 ht[1]
- 遷移完成后，是否 ht[0] 空間，把 ht[1] 的地址賦值給 ht[0]，ht[1] 的表大小設(shè)置為 0
什么時候觸發(fā) rehash？
- ht[0] 大小=0
- ht[0] 里的元素個數(shù)已經(jīng)超過 ht[0] 大小 && Hash 表可以擴容
- ht[0] 里的元素個數(shù)，是 ht[0] 大小的 5 倍（dict_force_resize_ratio）（類似于 Java 里 HashMap 的負(fù)載因子）
static int _dictExpandIfNeeded(dict *d)
{
/* Incremental rehashing already in progress. Return. */
if (dictIsRehashing(d)) return DICT_OK;
// Hash 表為空，將 Hash 表擴展為初始大小 DICT_HT_INITIAL_SIZE（4）
if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
// Hash 表當(dāng)前的元素數(shù)量超過表的大小 && （可以擴容 || 當(dāng)前數(shù)量是表大小的 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) &&
dictTypeExpandAllowed(d))
{
return dictExpand(d, d->ht[0].used + 1);
}
return DICT_OK;
}
上面代碼中有個參數(shù) dict_can_resize，設(shè)置函數(shù)為：
void dictEnableResize(void) {
dict_can_resize = 1;
}
void dictDisableResize(void) {
dict_can_resize = 0;
}
這兩個函數(shù)被封裝在了 server.c 中的 updateDictResizePolicy：
void updateDictResizePolicy(void) {
if (!hasActiveChildProcess())
dictEnableResize();
else
dictDisableResize();
}
/* Return true if there are active children processes doing RDB saving,
* AOF rewriting, or some side process spawned by a loaded module. */
int hasActiveChildProcess() {
return server.child_pid != -1;
}
我們可以看到，hasActiveChildProcess 函數(shù)是判斷 Redis 存在 RDB 子進(jìn)程、AOF 子進(jìn)程是否存在?？梢钥吹?dict_can_resize 只有在不存在 RDB 子進(jìn)程、AOF 子進(jìn)程時才為 TRUE。
那 _dictExpandIfNeeded 是在哪里調(diào)用的呢？
rehash 擴容多大？
_dictExpandIfNeeded 里調(diào)用了擴容函數(shù) dictExpand。
/* return DICT_ERR if expand was not performed */
int dictExpand(dict *d, unsigned long size) {
return _dictExpand(d, size, NULL);
}
int _dictExpand(dict *d, unsigned long size, int* malloc_failed)
{
……
dictht n; /* the new hash table */
unsigned long realsize = _dictNextPower(size);
……
}
里面有一個 _dictNextPower 函數(shù)，啥都不說了，都在注釋里。
static unsigned long _dictNextPower(unsigned long size) {
unsigned long i = DICT_HT_INITIAL_SIZE;
// 要擴容的大小已經(jīng)超過了最大值
if (size >= LONG_MAX) return LONG_MAX + 1LU;
// 要擴容的大小沒有超過最大值，找到第一個比 size 大的 2^i
while (1) {
if (i >= size)
return i;
i *= 2;
}
}
漸進(jìn)式 rehash
為什么需要漸進(jìn)式 rehash？
Hash 表空間很大，全量 rehash 時間會很長，阻塞 Redis 主線程。為了降低 rehash 開銷，Redis 使用了「漸進(jìn)式 rehash」。
具體一點
漸進(jìn)式 rehash 并不是一次性把當(dāng)前 Hash 表的所有鍵，都拷貝到新的位置，而是「分批拷貝」，每次只拷貝 Hash 表中一個 bucket 中的哈希項。
int dictRehash(dict *d, int n) {
int empty_visits = n*10; /* Max number of empty buckets to visit. */
if (!dictIsRehashing(d)) return 0;
// 循環(huán) n 次后停止，或 ht[0] 遷移完成
while(n-- && d->ht[0].used != 0) {
dictEntry *de, *nextde;
assert(d->ht[0].size > (unsigned long) d->rehashidx);
// 如果要遷移的 bucket 中沒有元素
while (d->ht[0].table[d->rehashidx] == NULL) {
d->rehashidx++;
if (--empty_visits == 0) return 1;
}
// 獲取待遷移的 ht[0] 的 bucket
de = d->ht[0].table[d->rehashidx];
/* Move all the keys in this bucket from the old to the new hash HT */
while (de) {
uint64_t h;
// 獲取下一個遷移項
nextde = de->next;
// 計算 de 在 ht[1](擴容后)中的位置
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
// 將當(dāng)前的哈希項放到擴容后的 ht[1] 中
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
d->ht[0].used--;
d->ht[1].used++;
//指向下一個哈希項
de = nextde;
}
// 當(dāng)前 bucket 已經(jīng)沒有哈希項了，將該 bucket 設(shè)置為 null
d->ht[0].table[d->rehashidx] = NULL;
// 將 rehash+1，下次遷移下一個 bucket
d->rehashidx++;
}
// 判斷 ht[0] 是否已經(jīng)全部遷移
if (d->ht[0].used == 0) {
// ht[0] 已經(jīng)全部遷移到 ht[1] 了，釋放 ht[0]
zfree(d->ht[0].table);
// ht[0] 指向 ht[1]
d->ht[0] = d->ht[1];
// 重置 ht[1] 大小為 0
_dictReset(&d->ht[1]);
//設(shè)置全局哈希表的 rehashidx=-1，表示 rehash 結(jié)束
d->rehashidx = -1;
return 0;
}
// ht[0] 中仍然有元素沒有遷移完
return 1;
}
幾點說明：
- rehashidx 表示當(dāng)前 rehash 在對哪個 bucket 做數(shù)據(jù)遷移，每次遷移完對應(yīng) bucket 時，會將 rehashidx+1。
- empty_visits 表示連續(xù) bucket 為空的情況，此時漸進(jìn)式 rehash 不會一直遞增檢查 rehashidx，因為一直檢測會阻塞主線程，Redis 主線程就無法處理其他請求了。
那么 rehash 是在什么哪些步驟進(jìn)行操作的呢？查看源碼發(fā)現(xiàn) dictRehash 是在 _dictRehashStep 函數(shù)中調(diào)用的，且傳入的 n=1。
static void _dictRehashStep(dict *d) {
if (d->pauserehash == 0) dictRehash(d,1);
}
而 _dictRehashStep 分別被 5 個方法調(diào)用了：
- dictAddRaw
- dictGenericDelete
- dictFind
- dictGetRandomKey
- dictGetSomeKeys
下面是 dictAddRaw 部分代碼：
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
……
if (dictIsRehashing(d)) _dictRehashStep(d);
……
}
下面是 dictAdd 部分代碼：
int dictAdd(dict *d, void *key, void *val)
{
dictEntry *entry = dictAddRaw(d,key,NULL);
if (!entry) return DICT_ERR;
dictSetVal(d, entry, val);
return DICT_OK;
}
Redis 源碼簡潔剖析系列
Java 編程思想-最全思維導(dǎo)圖-GitHub 下載鏈接，需要的小伙伴可以自取~
原創(chuàng)不易，希望大家轉(zhuǎn)載時請先聯(lián)系我，并標(biāo)注原文鏈接。
