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