聊聊 Redis 中的字典設(shè)計(jì)與實(shí)現(xiàn)
Redis作為非關(guān)系數(shù)據(jù)庫(kù)，其底層采用了字典(也稱為映射)保存鍵值對(duì)。本文會(huì)基于源碼分析的方式帶你了解redis中這一常見數(shù)據(jù)結(jié)構(gòu)的精巧設(shè)計(jì)，希望對(duì)你有幫助。
哈希表的基本數(shù)據(jù)結(jié)構(gòu)
字典用table管理當(dāng)前存儲(chǔ)鍵值對(duì)的數(shù)組，這個(gè)數(shù)組的大小可有size這個(gè)字段知曉，每當(dāng)我們有一個(gè)鍵值對(duì)要存儲(chǔ)到字典時(shí)就會(huì)通過sizemask進(jìn)行按位與運(yùn)算得到table數(shù)組的某個(gè)索引位置將當(dāng)前鍵值對(duì)存儲(chǔ)，然后自增一個(gè)used標(biāo)識(shí)當(dāng)前有一個(gè)節(jié)點(diǎn)加入。
可能上文說的比較抽象，我們不妨舉個(gè)例子，假設(shè)我們現(xiàn)在鍵入如下指令:
HSET student xiaoming 18redis完成命令解析后，定位到student這個(gè)key對(duì)應(yīng)的字段空間的字典，找到當(dāng)前正在使用的哈希表，按照如下步驟完成鍵值對(duì)存儲(chǔ)：
- 計(jì)算xiaoming的哈希值。
- 將計(jì)算出的哈希值和sizemask即3，也就是數(shù)組的索引范圍進(jìn)行按位與運(yùn)算，得到對(duì)應(yīng)的數(shù)組索引位置。
- 查看該位置是否有元素，如果沒有則直接添加，反之追加到該dictEntry的后面，這也就是我們常說的鏈地址法。
- used字段自增一下，表示當(dāng)前哈希表有一個(gè)元素。
我們可以在dict.h看到上文所提及的哈希表和字典中每一個(gè)元素的數(shù)據(jù)結(jié)構(gòu)：
typedef struct dictht {
//存儲(chǔ)鍵值對(duì)的哈希表
dictEntry **table;
//當(dāng)前哈希表的大小
unsigned long size;
//計(jì)算哈希值的掩碼值
unsigned long sizemask;
//當(dāng)前哈希表的節(jié)點(diǎn)數(shù)
unsigned long used;
} dictht;
//記錄鍵值對(duì)的數(shù)據(jù)結(jié)構(gòu)dictEntry
typedef struct dictEntry {
//指向鍵的指針
void *key;
//通過共用體存儲(chǔ)值
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
//next指針指向下一個(gè)dictEntry
struct dictEntry *next;
} dictEntry;字典的數(shù)據(jù)結(jié)構(gòu)
哈希表在極端算法情況下會(huì)造成大量鍵值對(duì)沖突碰撞的情況，導(dǎo)致查詢效率由原來的O(1)變?yōu)镺(n)，所以為了保證針對(duì)沖突的數(shù)組進(jìn)行優(yōu)化，redis的字典采用的雙數(shù)組的方式管理鍵值對(duì)。
如下圖所示，可以看到dict的數(shù)據(jù)結(jié)構(gòu)定義了大小為2的哈希表數(shù)組，當(dāng)某個(gè)哈希表碰撞激烈需要進(jìn)行調(diào)整時(shí)，就會(huì)采用漸進(jìn)式哈希算法將鍵值對(duì)存到dictht[1]，并通過rehashidx標(biāo)志為-1表示當(dāng)前處于漸進(jìn)式哈希階段：
對(duì)應(yīng)的我們也可以在dict.h看到dict 的定義：
typedef struct dict {
//.......
//定義2個(gè)哈希表
dictht ht[2];
//-1時(shí)表示當(dāng)前哈希表處于漸進(jìn)式哈希
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
//.......
} dict;字典的創(chuàng)建
進(jìn)行鍵值對(duì)創(chuàng)建時(shí)，dictCreate會(huì)進(jìn)行必要的內(nèi)存分配，然后進(jìn)入初始化工作：
- 初始化兩個(gè)哈希表空間。
- 設(shè)置類型特定函數(shù)type ，這個(gè)type 包含了各種類型哈希值計(jì)算、值復(fù)制以及鍵比對(duì)等各種方法的指針。
- 設(shè)置私有數(shù)據(jù)privdata 。
- 初始化rehashidx 為-1表示未進(jìn)行漸進(jìn)式再哈希。
對(duì)應(yīng)的我們可以在dict.c中看到這段源代碼：
/* Create a new hash table */
dict *dictCreate(dictType *type,
void *privDataPtr)
{
//內(nèi)存分配
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]);
//設(shè)置類型特定函數(shù)和私有數(shù)據(jù)
d->type = type;
d->privdata = privDataPtr;
//初始化漸進(jìn)式哈希標(biāo)識(shí)
d->rehashidx = -1;
d->iterators = 0;
return DICT_OK;
}元素的插入
字典的插入操作大體流程也很市面上常見的哈希表實(shí)現(xiàn)差不多，通過哈希算法(MurmurHash2)定位元素插入的位置再進(jìn)行插入操作，唯一有所區(qū)別的是，redis版本字典的鏈地址法解決沖突的上的優(yōu)化，為了保證哈希定位的位置存在元素時(shí)能夠快速插入，redis字典的插入采用的是頭插法，即將最新的元素作為鏈表頭元素插入:
與之對(duì)應(yīng)的我們給出代碼的入口，也就是dict.c下的dictAdd方法，可以看到其內(nèi)部是通過完成鍵的添加，只有key插入成功后才會(huì)通過setVal方法維護(hù)插入的entry的值：
int dictAdd(dict *d, void *key, void *val)
{
//通過dictAddRaw完成key的插入
dictEntry *entry = dictAddRaw(d,key);
//如果插入成功再維護(hù)value
if (!entry) return DICT_ERR;
dictSetVal(d, entry, val);
return DICT_OK;
}dictAddRaw邏輯也比較簡(jiǎn)單，先檢查當(dāng)前的字典表是否因?yàn)榇罅繘_突而處理漸進(jìn)式哈希(關(guān)于漸進(jìn)式哈希后文會(huì)詳細(xì)講解，這里也補(bǔ)充一些簡(jiǎn)單的概念)，通過_dictKeyIndex定位到當(dāng)前元素插入的索引位置，采用頭插法將其插入到對(duì)應(yīng)索引位置的鏈表首部:
dictEntry *dictAddRaw(dict *d, void *key)
{
int index;
dictEntry *entry;
dictht *ht;
//是否處于漸進(jìn)式哈希階段
if (dictIsRehashing(d)) _dictRehashStep(d);
//定位索引位置
if ((index = _dictKeyIndex(d, key)) == -1)
return NULL;
//定位要存儲(chǔ)元素的哈希表位置
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
//分配內(nèi)存空間
entry = zmalloc(sizeof(*entry));
//采用頭插法將元素插入到對(duì)應(yīng)哈希表的索引位置上
entry->next = ht->table[index];
ht->table[index] = entry;
//當(dāng)前插入元素?cái)?shù)加一
ht->used++;
/* Set the hash entry fields. */
dictSetKey(d, entry, key);
return entry;
}哈希沖突及其對(duì)應(yīng)解決方案(漸進(jìn)式哈希驅(qū)逐)
隨著我們不斷的新增鍵值對(duì)，當(dāng)前的哈希算法得到的索引位置很大概率會(huì)出現(xiàn)哈希沖突，即每次定位到的索引位置都很大概率存在元素，這也就是我們的常說的哈希沖突，這就是redis的字典默認(rèn)會(huì)初始化兩張哈希表的原因所在。
符合以下兩個(gè)條件時(shí)，字典就會(huì)觸發(fā)擴(kuò)容機(jī)制:
- 未進(jìn)行BGSAVE命令或者BGREWRITEAOF持久化操作，且當(dāng)前哈希表元素?cái)?shù)和哈希表空間大小一樣。
- 正進(jìn)行BGSAVE命令或者BGREWRITEAOF持久化操作，當(dāng)且哈希表元素?cái)?shù)是哈希表空間的5倍。
觸發(fā)擴(kuò)容時(shí)，字典會(huì)將rehashidx設(shè)置為0意為當(dāng)前因?yàn)榇罅繘_突碰撞而從0索引開始漸進(jìn)式再哈希，ht[1]就會(huì)開辟一個(gè)ht[0]數(shù)組長(zhǎng)度2倍的數(shù)組空間，后續(xù)的新插入的元素也都會(huì)根據(jù)哈希算法將元素插入到ht[1]中。
對(duì)于舊有存在的元素，考慮到整個(gè)哈希表可能存在不可預(yù)估數(shù)量的鍵值對(duì)，redis的字典會(huì)通過漸進(jìn)式哈希的方式在元素每次進(jìn)行增刪改查操作時(shí)將舊有元素遷移到ht[1]中，一旦所有元素全部遷移到ht[1]后，哈希表就會(huì)將ht[1]指向的哈希表指針賦值給ht[0]，并將ht[0]原有哈希表釋放。
了解整體的設(shè)計(jì)之后，我們就可以從源碼角度印證這個(gè)問題了，可以看到字典在每次進(jìn)行哈希索引定位時(shí)都會(huì)調(diào)用_dictKeyIndex方法，而該方法內(nèi)部則有一個(gè)_dictExpandIfNeeded操作，其內(nèi)部就會(huì)根據(jù)我們上文所說的閾值判斷當(dāng)前哈希表是否需要進(jìn)行擴(kuò)容:
static int _dictKeyIndex(dict *d, const void *key)
{
unsigned int h, idx, table;
dictEntry *he;
//判斷當(dāng)前哈希表是否需要進(jìn)行擴(kuò)容操作
if (_dictExpandIfNeeded(d) == DICT_ERR)
return -1;
//獲取當(dāng)前key的哈希值
h = dictHashKey(d, key);
//計(jì)算哈希值
for (table = 0; table <= 1; table++) {
//計(jì)算索引
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;
}
//如果不處于漸進(jìn)式哈希階段，則直接將該索引值返回，后續(xù)元素直接存入ht[0]表中，反之進(jìn)入下一個(gè)循環(huán)計(jì)算當(dāng)前元素在ht[1]表的索引
if (!dictIsRehashing(d)) break;
}
return idx;
}我們繼續(xù)步入_dictExpandIfNeeded即可看到擴(kuò)容判斷的邏輯，也就是我們上文所說的符合兩個(gè)擴(kuò)容條件之一時(shí)就會(huì)觸發(fā)擴(kuò)容：
static int _dictExpandIfNeeded(dict *d)
{
//如果正處于漸進(jìn)式哈希則直接返回
if (dictIsRehashing(d)) return DICT_OK;
//......
//如果當(dāng)前有子進(jìn)程進(jìn)行持久化操作則dict_can_resize為false，所以當(dāng)字典元素?cái)?shù)大于等于哈希表大小且未進(jìn)行持久化，或進(jìn)行持久化操作且元素?cái)?shù)是哈希表的5倍時(shí)才會(huì)進(jìn)行擴(kuò)容操作，dictExpand會(huì)將rehashidx設(shè)置為0，告知當(dāng)前哈希表進(jìn)行擴(kuò)容需要進(jìn)行漸進(jìn)式再哈希
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;
}此時(shí)我們?cè)倩乜粗暗逆I值對(duì)插入操作，它會(huì)根據(jù)dictIsRehashing判斷rehashidx是否為0，從而調(diào)用_dictRehashStep進(jìn)入漸進(jìn)式哈希操作在鍵值對(duì)維護(hù)：
dictEntry *dictAddRaw(dict *d, void *key)
{
int index;
dictEntry *entry;
dictht *ht;
//如果處于再哈希階段，若符合要求則進(jìn)行一次ht[0]哈希表元素驅(qū)逐操作
if (dictIsRehashing(d)) _dictRehashStep(d);
//保存鍵值對(duì)操作
//......
return entry;
}我們直接查看_dictRehashStep內(nèi)部的實(shí)現(xiàn)就可以看到一個(gè)dictRehash的方法，它就是漸進(jìn)式哈希的核心實(shí)現(xiàn)，可以看到該方法會(huì)從0開始每次驅(qū)逐10個(gè)元素到ht[1]中：
int dictRehash(dict *d, int n) {
//基于傳入的n得出訪問空bucket的最大次數(shù)，默認(rèn)為1*10=10
int empty_visits = n*10; /* Max number of empty buckets to visit. */
if (!dictIsRehashing(d)) return 0;
while(n-- && d->ht[0].used != 0) {
dictEntry *de, *nextde;
/* Note that rehashidx can't overflow as we are sure there are more
* elements because ht[0].used != 0 */
assert(d->ht[0].size > (unsigned long)d->rehashidx);
//基于empty_visits 循環(huán)找到第一個(gè)非空的bucket
while(d->ht[0].table[d->rehashidx] == NULL) {
d->rehashidx++;
if (--empty_visits == 0) return 1;
}
//定位到需要驅(qū)逐元素的bucket
de = d->ht[0].table[d->rehashidx];
/* Move all the keys in this bucket from the old to the new hash HT */
//計(jì)算當(dāng)前元素在ht[1]中的位置并驅(qū)逐過去
while(de) {
unsigned int h;
nextde = de->next;
/* Get the index in the new hash table */
//計(jì)算當(dāng)前元素在新哈希表的索引位置
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
//基于頭插法，將舊元素指向新哈希表的第一個(gè)元素，構(gòu)成鏈表
de->next = d->ht[1].table[h];
//節(jié)點(diǎn)空間指向舊元素
d->ht[1].table[h] = de;
//舊有哈希表元素?cái)?shù)減去1
d->ht[0].used--;
//新的哈希值元素空間加上1
d->ht[1].used++;
//進(jìn)行下一輪迭代
de = nextde;
}
d->ht[0].table[d->rehashidx] = NULL;
d->rehashidx++;
}
/* Check if we already rehashed the whole table... */
//used 為0說明所有元素驅(qū)逐完成，將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;
}查詢操作
有了上述的基礎(chǔ)后，我們查看查詢操作就比較簡(jiǎn)單了，其步驟比較固定:
- 計(jì)算key的哈希值。
- 計(jì)算對(duì)應(yīng)索引位置到ht[0]定位，如果找到了直接返回。
- 如果沒找到，查看當(dāng)前是否處于擴(kuò)容階段，若是則到ht[1]進(jìn)行哈希定位，若找到直接返回。
- 上述操作都未找到該元素，直接返回null。
dictEntry *dictFind(dict *d, const void *key)
{
//......
//計(jì)算哈希值
h = dictHashKey(d, key);
//通過哈希算法定位索引，到哈希表進(jìn)行查詢
for (table = 0; table <= 1; table++) {
idx = h & d->ht[table].sizemask;
he = d->ht[table].table[idx];
//遍歷當(dāng)前索引位置的元素，找到比對(duì)一致的返回
while(he) {
if (dictCompareKeys(d, key, he->key))
return he;
he = he->next;
}
//上一步?jīng)]找到則判斷是否處于擴(kuò)容，若處于擴(kuò)容則進(jìn)入下一個(gè)循環(huán)到ht[1]表找，反之直接返回null
if (!dictIsRehashing(d)) return NULL;
}
return NULL;
}刪除操作
同理我們最后給出刪除操作的源碼，也查詢操作一樣，定位到元素后，將其從索引位置中解除該元素和前驅(qū)節(jié)點(diǎn)關(guān)系即可:
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) {
//找到比對(duì)一致的鍵值對(duì)
if (dictCompareKeys(d, key, he->key)) {
//解除該元素和前驅(qū)節(jié)點(diǎn)的關(guān)系
if (prevHe)
prevHe->next = he->next;
else
d->ht[table].table[idx] = he->next;
//釋放當(dāng)前節(jié)點(diǎn)
if (!nofree) {
dictFreeKey(d, he);
dictFreeVal(d, he);
}
zfree(he);
//元素?cái)?shù)減去1
d->ht[table].used--;
return DICT_OK;
}
prevHe = he;
he = he->next;
}
if (!dictIsRehashing(d)) break;
}
return DICT_ERR; /* not found */
}
