聊聊 Redis 中的字典設(shè)計(jì)與實(shí)現(xiàn)
Redis作為非關(guān)系數(shù)據(jù)庫(kù)，其底層采用了字典(也稱(chēng)為映射)保存鍵值對(duì)。本文會(huì)基于源碼分析的方式帶你了解redis中這一常見(jiàn)數(shù)據(jù)結(jié)構(gòu)的精巧設(shè)計(jì)，希望對(duì)你有幫助。
哈希表的數(shù)據(jù)結(jié)構(gòu)
我們簡(jiǎn)單說(shuō)明一下redis字典數(shù)據(jù)結(jié)構(gòu)特征：
- 用table管理當(dāng)前存儲(chǔ)鍵值對(duì)而table本質(zhì)上就是一個(gè)數(shù)組
- 數(shù)組的大小可采用一個(gè)size字段維護(hù)
- 添加一個(gè)鍵值時(shí)，會(huì)通過(guò)sizemask進(jìn)行按位與運(yùn)算得到table數(shù)組的某個(gè)索引位置并將其存儲(chǔ)，然后自增一下哈希表的used字段，標(biāo)識(shí)當(dāng)前數(shù)組元素+1。
可能上文說(shuō)的比較抽象，我們不妨舉個(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ù)組索引位置。
- 查看該位置是否有元素，如果沒(méi)有則直接添加，反之追加到該dictEntry的后面，這也就是我們常說(shuō)的鏈地址法。
- used字段自增一下，表示當(dāng)前哈希表有一個(gè)元素。
我們可以在dict.h看到上文所提及的哈希表和字典中每一個(gè)元素的數(shù)據(jù)結(jié)構(gòu)：
typedef struct dictht {
//存儲(chǔ)鍵值對(duì)的哈希表
dictEntry **table;
//當(dāng)前哈希表的大小
unsignedlong size;
//計(jì)算哈希值的掩碼值
unsignedlong sizemask;
//當(dāng)前哈希表的節(jié)點(diǎn)數(shù)
unsignedlong used;
} dictht;
//記錄鍵值對(duì)的數(shù)據(jù)結(jié)構(gòu)dictEntry
typedefstruct dictEntry {
//指向鍵的指針
void *key;
//通過(guò)共用體存儲(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)
上文我們講解了哈希結(jié)構(gòu)，而哈希表在極端算法情況下會(huì)造成大量鍵值對(duì)沖突碰撞的情況，導(dǎo)致查詢(xún)效率由原來(lái)的O(1)變?yōu)镺(n)，所以為了保證針對(duì)沖突的數(shù)組進(jìn)行優(yōu)化，redis的字典采用的雙數(shù)組的方式管理鍵值對(duì)，所以這一小節(jié)我們著重說(shuō)明redis如何基于字典管理兩個(gè)哈希表空間。
對(duì)應(yīng)的我們也可以在dict.h看到dict 的定義，可以看到字典維護(hù)哈希表字段ht是一個(gè)空間為2的數(shù)組：
typedef struct dict {
//.......
//定義2個(gè)哈希表
dictht ht[2];
//-1時(shí)表示當(dāng)前哈希表處于漸進(jìn)式哈希
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
//.......
} dict;如下圖所示，可以看到dict的數(shù)據(jù)結(jié)構(gòu)定義了大小為2的哈希表數(shù)組，當(dāng)某個(gè)哈希表碰撞激烈需要進(jìn)行調(diào)整時(shí)，就會(huì)采用漸進(jìn)式哈希算法將鍵值對(duì)存到dictht[1]，并通過(guò)rehashidx標(biāo)志為-1表示當(dāng)前處于漸進(jìn)式哈希階段：
字典的初始化創(chuàng)建
進(jìn)行鍵值對(duì)創(chuàng)建時(shí)，dictCreate會(huì)進(jìn)行必要的內(nèi)存分配，然后進(jìn)入初始化工作：
- 初始化兩個(gè)哈希表空間。
- 設(shè)置類(lèi)型特定函數(shù)type ，這個(gè)type 包含了各種類(lèi)型哈希值計(jì)算、值復(fù)制以及鍵比對(duì)等各種方法的指針。
- 設(shè)置私有數(shù)據(jù)privdata 。
- 初始化rehashidx 為-1表示未進(jìn)行漸進(jìn)式再哈希。
對(duì)應(yīng)的我們可以在dict.c中看到dictCreate函數(shù)的源代碼：
/* 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è)置類(lèi)型特定函數(shù)和私有數(shù)據(jù)
d->type = type;
d->privdata = privDataPtr;
//初始化漸進(jìn)式哈希標(biāo)識(shí)
d->rehashidx = -1;
d->iterators = 0;
return DICT_OK;
}元素的插入
字典的插入操作大體流程也很市面上常見(jiàn)的哈希表實(shí)現(xiàn)差不多，通過(guò)哈希算法(MurmurHash2)定位元素插入的位置再進(jìn)行插入操作，唯一有所區(qū)別的是，redis版本字典的鏈地址法解決沖突的上的優(yōu)化，為了保證哈希定位的位置存在元素時(shí)能夠快速插入，redis字典的插入采用的是頭插法，即將最新的元素作為鏈表頭元素插入:
與之對(duì)應(yīng)的我們給出代碼的入口，也就是dict.c下的dictAdd方法，可以看到其內(nèi)部是通過(guò)完成鍵的添加，只有key插入成功后才會(huì)通過(guò)setVal方法維護(hù)插入的entry的值：
int dictAdd(dict *d, void *key, void *val)
{
//通過(guò)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)單的概念)，通過(guò)_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)
returnNULL;
//定位要存儲(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;
}漸進(jìn)式哈希驅(qū)逐解決頻繁哈希碰撞
隨著我們不斷的新增鍵值對(duì)，當(dāng)前的哈希算法得到的索引位置很大概率會(huì)出現(xiàn)哈希沖突，即每次定位到的索引位置都很大概率存在元素，這也就是我們的常說(shuō)的哈希沖突，這就是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索引開(kāi)始漸進(jìn)式再哈希，ht[1]就會(huì)基于ht[0]數(shù)組長(zhǎng)度創(chuàng)建一個(gè)其2倍的數(shù)組空間，后續(xù)的新插入的元素也都會(huì)根據(jù)哈希算法將元素插入到ht[1]中。
對(duì)于舊有存在的元素，考慮到整個(gè)哈希表可能存在不可預(yù)估數(shù)量的鍵值對(duì)，redis的字典會(huì)通過(guò)漸進(jìn)式哈希的方式在元素每次進(jìn)行增刪改查操作時(shí)將舊有元素逐批次遷移到ht[1]中，一旦所有元素全部遷移到ht[1]后，哈希表就會(huì)將ht[1]指向的哈希表指針賦值給ht[0]，并將ht[0]原有哈希表釋放。
了解整體的設(shè)計(jì)之后，我們就可以從源碼角度印證這個(gè)問(wèn)題了，可以看到字典在每次進(jìn)行哈希索引定位時(shí)都會(huì)調(diào)用_dictKeyIndex方法，而該方法內(nèi)部則有一個(gè)_dictExpandIfNeeded操作，其內(nèi)部就會(huì)根據(jù)我們上文所說(shuō)的閾值判斷當(dāng)前哈希表是否需要進(jìn)行擴(kuò)容:
static int _dictKeyIndex(dict *d, constvoid *key)
{
unsignedint 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ò)容判斷的邏輯，也就是我們上文所說(shuō)的符合兩個(gè)擴(kuò)容條件：
- 數(shù)組0使用空間大于等于數(shù)組長(zhǎng)度且dict_can_resize為1(持久化結(jié)束或者未進(jìn)行持久化這個(gè)值都不會(huì)被設(shè)置為1)，若為1則是允許resize操作。
- 數(shù)組0使用空間大于等于數(shù)組長(zhǎng)度，且數(shù)組0使用空間已經(jīng)打到數(shù)組長(zhǎng)度的5倍。
只要符合上述的條件，該函數(shù)就會(huì)調(diào)用dictExpand觸發(fā)擴(kuò)容，并將rehashidx設(shè)置為0即代表從數(shù)組0的索引0位置嘗試漸進(jìn)式驅(qū)逐：
static int _dictExpandIfNeeded(dict *d)
{
//......
/**
* 如果數(shù)組0使用空間大于等于數(shù)組長(zhǎng)度則判斷：
* 1. dict_can_resize是否為1(持久化結(jié)束或者未進(jìn)行持久化這個(gè)值都不會(huì)被設(shè)置為1)，若為1則是允許resize操作
* 2. 數(shù)組0使用空間是否是數(shù)組長(zhǎng)度的5倍
* 若符合上述要求，則調(diào)用dictExpand將數(shù)組1設(shè)置為數(shù)組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;
}此時(shí)我們?cè)倩乜粗暗逆I值對(duì)插入操作，它會(huì)根據(jù)dictIsRehashing判斷rehashidx是否為0以確定是否處于漸進(jìn)式再哈希，從而調(diào)用_dictRehashStep進(jìn)入漸進(jìn)式哈希操作在鍵值對(duì)維護(hù)：
dictEntry *dictAddRaw(dict *d, void *key)
{
int index;
dictEntry *entry;
dictht *ht;
//dictIsRehashing會(huì)判斷當(dāng)前是否處于再哈希階段，若符合要求則進(jìn)行一次ht[0]哈希表元素驅(qū)逐操作
if (dictIsRehashing(d)) _dictRehashStep(d);
//保存鍵值對(duì)操作
//......
return entry;
}我們直接查看_dictRehashStep內(nèi)部的實(shí)現(xiàn)就可以看到一個(gè)dictRehash的函數(shù)，它就是漸進(jìn)式哈希的核心實(shí)現(xiàn)，該方法會(huì)從0開(kāi)始每次驅(qū)逐10個(gè)元素到ht[1]中：
int dictRehash(dict *d, int n) {
//基于傳入的n得出訪(fǎng)問(wèn)空bucket的最大次數(shù)，默認(rèn)為1*10=10
int empty_visits = n*10;
if (!dictIsRehashing(d)) return0;
while(n-- && d->ht[0].used != 0) {
dictEntry *de, *nextde;
assert(d->ht[0].size > (unsignedlong)d->rehashidx);
//基于empty_visits 循環(huán)找到第一個(gè)非空的bucket
while(d->ht[0].table[d->rehashidx] == NULL) {
d->rehashidx++;
if (--empty_visits == 0) return1;
}
//定位到需要驅(qū)逐元素的bucket
de = d->ht[0].table[d->rehashidx];
//計(jì)算當(dāng)前元素在ht[1]中的位置并驅(qū)逐過(guò)去
while(de) {
unsignedint h;
nextde = de->next;
//計(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++;
//de指向下一個(gè)元素，進(jìn)行下一輪迭代
de = nextde;
}
d->ht[0].table[d->rehashidx] = NULL;
d->rehashidx++;
}
//used 為0說(shuō)明所有元素驅(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;
return0;
}
return1;
}查詢(xún)操作
有了上述的基礎(chǔ)后，我們查看查詢(xún)操作就比較簡(jiǎn)單了，其步驟比較固定：
- 計(jì)算key的哈希值。
- 計(jì)算對(duì)應(yīng)索引位置到ht[0]定位，如果找到了直接返回。
- 如果沒(méi)找到，查看當(dāng)前是否處于擴(kuò)容階段，若是則到ht[1]進(jìn)行哈希定位，若找到直接返回。
- 上述操作都未找到該元素，直接返回null。
dictEntry *dictFind(dict *d, const void *key)
{
//......
//計(jì)算哈希值
h = dictHashKey(d, key);
//通過(guò)哈希算法定位索引，到哈希表進(jìn)行查詢(xú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)) returnNULL;
}
returnNULL;
}刪除操作
同理我們最后給出刪除操作的源碼，也查詢(xún)操作一樣，定位到元素后，將其從索引位置中解除該元素和前驅(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 */
}
