|
Dict在redis中是最為核心的一個數(shù)據(jù)結(jié)構(gòu)，因為它承載了redis里的所有數(shù)據(jù)，你可以簡單粗暴的認為redis就是一個大的dict，里面存儲的所有的key-value。
redis中dict的本質(zhì)其實就是一個hashtable，所以它也需要考慮所有hashtable所有的問題，如何組織K-V、如何處理hash沖突、擴容策略及擴容方式……。實際上Redis中hashtable的實現(xiàn)方式就是普通的hashtable，但Redis創(chuàng)新的引入了漸進式hash以減小hashtable擴容是對性能帶來的影響，接下來我們就來看看redis中hashtable的具體實現(xiàn)。
Redis中Dict的實現(xiàn)
dict的定義在dict.h中，其各個字段及其含義如下：
typedef struct dict {
dictType *type; // dictType結(jié)構(gòu)的指針，封裝了很多數(shù)據(jù)操作的函數(shù)指針，使得dict能處理任意數(shù)據(jù)類型（類似面向?qū)ο笳Z言的interface，可以重載其方法）
void *privdata; // 一個私有數(shù)據(jù)指針(privdata),由調(diào)用者在創(chuàng)建dict的時候傳進來。
dictht ht[2]; // 兩個hashtable，ht[0]為主，ht[1]在漸進式hash的過程中才會用到。
long rehashidx; /* 增量hash過程過程中記錄rehash執(zhí)行到第幾個bucket了，當(dāng)rehashidx == -1表示沒有在做rehash */
unsigned long iterators; /* 正在運行的迭代器數(shù)量 */
} dict;
重點介紹下dictType *type字段(個人感覺命名為type不太合適)，其作用就是為了讓dict支持各種數(shù)據(jù)類型，因為不同的數(shù)據(jù)類型需要對應(yīng)不同的操作函數(shù)，比如計算hashcode 字符串和整數(shù)的計算方式就不一樣， 所以dictType通過函數(shù)指針的方式，將不同數(shù)據(jù)類型的操作都封裝起來。從面相對象的角度來看，可以把dictType當(dāng)成dict中各種數(shù)據(jù)類型相關(guān)操作的interface，各個數(shù)據(jù)類型只需要實現(xiàn)其對應(yīng)的數(shù)據(jù)操作就行。 dictType中封裝了以下幾個函數(shù)指針。
typedef struct dictType {
uint64_t (*hashFunction)(const void *key); // 對key生成hash值
void *(*keyDup)(void *privdata, const void *key); // 對key進行拷貝
void *(*valDup)(void *privdata, const void *obj); // 對val進行拷貝
int (*keyCompare)(void *privdata, const void *key1, const void *key2); // 兩個key的對比函數(shù)
void (*keyDestructor)(void *privdata, void *key); // key的銷毀
void (*valDestructor)(void *privdata, void *obj); // val的銷毀
} dictType;
dict中還有另外一個重要的字段dictht ht[2]，dictht其實就是hashtable，但這里為什么是ht[2]? 這就不得不提到redis dict的漸進式hash，dict的hashtable的擴容不是一次性完成的，它是先建立一個大的新的hashtable存放在ht[1]中，然后逐漸把ht[0]的數(shù)據(jù)遷移到ht[1]中，rehashidx就是ht[0]中數(shù)據(jù)遷移的進度，漸進式hash的過程會在后文中詳解。
這里我們來看下dictht的定義：
typedef struct dictht {
dictEntry **table; // hashtable中的連續(xù)空間
unsigned long size; // table的大小
unsigned long sizemask; // hashcode的掩碼
unsigned long used; // 已存儲的數(shù)據(jù)個數(shù)
} dictht;
其中dictEntry就是對dict中每對key-value的封裝，除了具體的key-value，其還包含一些其他信息，具體如下：
typedef struct dictEntry {
void *key;
union { // dictEntry在不同用途時存儲不同的數(shù)據(jù)
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next; // hash沖突時開鏈，單鏈表的next指針
} dictEntry;
dict中的hashtable在出現(xiàn)hash沖突時采用的是開鏈方式，如果有多個entry落在同一個bucket中，那么他們就會串成一個單鏈表存儲。
如果我們將dict在內(nèi)存中的存儲繪制出來，會是下圖這個樣子。
擴容
在看dict幾個核心API實現(xiàn)之前，我們先來看下dict的擴容，也就是redis的漸進式hash。 何為漸進式hash？redis為什么采用漸進式hash？漸進式hash又是如何實現(xiàn)的？
要回答這些問題，我們先來考慮下hashtable擴容的過程。如果熟悉java的同學(xué)可能知道，java中hashmap的擴容是在數(shù)據(jù)元素達到某個閾值后，新建一個更大的空間，一次性把舊數(shù)據(jù)搬過去，搬完之后再繼續(xù)后續(xù)的操作。如果數(shù)據(jù)量過大的話，HashMap擴容是非常耗時的，所有有些編程規(guī)范推薦new HashMap時最好指定其容量，防止出現(xiàn)自動擴容。
但是redis在新建dict的時候，沒法知道數(shù)據(jù)量大小，如果直接采用java hashmap的擴容方式，因為redis是單線程的，勢必在擴容過程中啥都干不了，阻塞掉后面的請求，最終影響到整個redis的性能。如何解決？ 其實也很簡單，就是化整為零，將一次大的擴容操作拆分成多次小的步驟，一步步來減少擴容對其他操作的影響，其具體實現(xiàn)如下：
上文中我們已經(jīng)看到了在dict的定義中有個dictht ht[2]，dict在擴容過程中會有兩個hashtable分別存儲在ht[0]和ht[1]中，其中ht[0]是舊的hashtable，ht[1]是新的更大的hashtable。
/* 檢查是否dict需要擴容 */
static int _dictExpandIfNeeded(dict *d)
{
/* 已經(jīng)在漸進式hash的流程中了，直接返回 */
if (dictIsRehashing(d)) return DICT_OK;
/* If the hash table is empty expand it to the initial size. */
if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
/* 當(dāng)配置了可擴容時，容量負載達到100%就擴容。配置不可擴容時，負載達到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))
{
return dictExpand(d, d->ht[0].used*2); // 擴容一倍容量
}
return DICT_OK;
}
Redis在每次查找某個key的索引下標(biāo)時都會檢查是否需要對ht[0]做擴容，如果配置的是可以擴容 那么當(dāng)hashtable使用率超過100%(uesed/size)就觸發(fā)擴容，否則使用率操作500%時強制擴容。執(zhí)行擴容的代碼如下：
/* dict的創(chuàng)建和擴容 */
int dictExpand(dict *d, unsigned long size)
{
/* 如果size比hashtable中的元素個數(shù)還小，那size就是無效的，直接返回error */
if (dictIsRehashing(d) || d->ht[0].used > size)
return DICT_ERR;
dictht n; /* 新的hashtable */
// 擴容時新table容量是大于當(dāng)前size的最小2的冪次方，但有上限
unsigned long realsize = _dictNextPower(size);
// 如果新容量和舊容量一致，沒有必要繼續(xù)執(zhí)行了，返回err
if (realsize == d->ht[0].size) return DICT_ERR;
/* 新建一個容量更大的hashtable */
n.size = realsize;
n.sizemask = realsize-1;
n.table = zcalloc(realsize*sizeof(dictEntry*));
n.used = 0;
// 如果是dict初始化的情況，直接把新建的hashtable賦值給ht[0]就行
if (d->ht[0].table == NULL) {
d->ht[0] = n;
return DICT_OK;
}
// 非初始化的情況，將新表賦值給ht[1], 然后標(biāo)記rehashidx 0
d->ht[1] = n;
d->rehashidx = 0; // rehashidx表示當(dāng)前rehash到ht[0]的下標(biāo)位置
return DICT_OK;
}
這里dictExpand只是創(chuàng)建了新的空間，將rehashidx標(biāo)記為0(rehashidx==-1表示不在rehash的過程中)，并未對ht[0]中的數(shù)據(jù)遷移到ht[1]中。數(shù)據(jù)遷移的邏輯都在_dictRehashStep()中。 _dictRehashStep()是只遷移一個bucket，它在dict的查找、插入、刪除的過程中都會被調(diào)到，每次調(diào)用至少遷移一個bucket。 而dictRehash()是_dictRehashStep()的具體實現(xiàn)，代碼如下：
/* redis漸進式hash，采用分批的方式，逐漸將ht[0]依下標(biāo)轉(zhuǎn)移到ht[2],避免了hashtable擴容時大量
* 數(shù)據(jù)遷移導(dǎo)致的性能問題
* 參數(shù)n是指這次rehash只做n個bucket */
int dictRehash(dict *d, int n) {
int empty_visits = n*10; /* 最大空bucket數(shù)量，如果遇到empty_visits個空bucket，直接結(jié)束當(dāng)前rehash的過程 */
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);
while(d->ht[0].table[d->rehashidx] == NULL) {
d->rehashidx++;
if (--empty_visits == 0) return 1; // 如果遇到了empty_visits個空的bucket，直接結(jié)束
}
// 遍歷當(dāng)前bucket中的鏈表，直接將其移動到新的hashtable中
de = d->ht[0].table[d->rehashidx];
/* 把所有的key從舊的hash桶移到新的hash桶中 */
while(de) {
uint64_t h;
nextde = de->next;
/* 獲取到key在新hashtable中的下標(biāo) */
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
d->ht[0].used--;
d->ht[1].used++;
de = nextde;
}
d->ht[0].table[d->rehashidx] = NULL;
d->rehashidx++;
}
/* 檢測是否已對全表做完了rehash */
if (d->ht[0].used == 0) {
zfree(d->ht[0].table); // 釋放舊ht所占用的內(nèi)存空間
d->ht[0] = d->ht[1]; // ht[0]始終是在用ht，ht[1]始終是新ht，ht0全遷移到ht1后會交換下
_dictReset(&d->ht[1]);
d->rehashidx = -1;
return 0; // 如果全表hash完，返回0
}
/* 還需要繼續(xù)做hash返回1 */
return 1;
}
可以看出，rehash就是分批次把ht[0]中的數(shù)據(jù)搬到ht[1]中，這樣將原有的一個大操作拆分為很多個小操作逐步進行，避免了redis發(fā)生dict擴容是瞬時不可用的情況，缺點是在redis擴容過程中會占用倆份存儲空間，而且占用時間會比較長。
核心API
插入
/* 向dict中添加元素 */
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;
}
/* 添加和查找的底層實現(xiàn)：
* 這個函數(shù)只會返回key對應(yīng)的entry，并不會設(shè)置key對應(yīng)的value，而是把設(shè)值權(quán)交給調(diào)用者。
*
* 這個函數(shù)也作為一個API直接暴露給用戶調(diào)用，主要是為了在dict中存儲非指針類的數(shù)據(jù)，比如
* entry = dictAddRaw(dict,mykey,NULL);
* if (entry != NULL) dictSetSignedIntegerVal(entry,1000);
*
* 返回值:
* 如果key已經(jīng)存在于dict中了，直接返回null，并把已經(jīng)存在的entry指針放到&existing里。否則
* 為key新建一個entry并返回其指針。
*/
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
long index;
dictEntry *entry;
dictht *ht;
if (dictIsRehashing(d)) _dictRehashStep(d);
/* 獲取到新元素的下標(biāo)，如果返回-1標(biāo)識該元素已經(jīng)存在于dict中了，直接返回null */
if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
return NULL;
/* 否則就給新元素分配內(nèi)存，并將其插入到鏈表的頭部(一般新插入的數(shù)據(jù)被訪問的頻次會更高)*/
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
entry = zmalloc(sizeof(*entry));
entry->next = ht->table[index];
ht->table[index] = entry;
ht->used++;
/* 如果是新建的entry，需要把key填進去 */
dictSetKey(d, entry, key);
return entry;
}
插入過程也比較簡單，就是先定位bucket的下標(biāo)，然后插入到單鏈表的頭節(jié)點，注意這里也需要考慮到rehash的情況，如果是在rehash過程中，新數(shù)據(jù)一定是插入到ht[1]中的。
查找
dictEntry *dictFind(dict *d, const void *key)
{
dictEntry *he;
uint64_t h, idx, table;
if (dictSize(d) == 0) return NULL; /* dict為空 */
if (dictIsRehashing(d)) _dictRehashStep(d);
h = dictHashKey(d, key);
// 查找的過程中，可能正在rehash中，所以新老兩個hashtable都需要查
for (table = 0; table <= 1; table++) {
idx = h & d->ht[table].sizemask;
he = d->ht[table].table[idx];
while(he) {
if (key==he->key || dictCompareKeys(d, key, he->key))
return he;
he = he->next;
}
// 如果ht[0]中沒找到，且不再rehas中，就不需要繼續(xù)找了ht[1]了。
if (!dictIsRehashing(d)) return NULL;
}
return NULL;
}
查找的過程比較簡單，就是用hashcode做定位，然后遍歷單鏈表。但這里需要考慮到如果是在rehash過程中，可能需要查找ht[2]中的兩個hashtable。
刪除
/* 查找并刪除一個元素，是dictDelete()和dictUnlink()的輔助函數(shù)。*/
static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
uint64_t h, idx;
dictEntry *he, *prevHe;
int table;
if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL;
if (dictIsRehashing(d)) _dictRehashStep(d);
h = dictHashKey(d, key);
// 這里也是需要考慮到rehash的情況，ht[0]和ht[1]中的數(shù)據(jù)都要刪除掉
for (table = 0; table <= 1; table++) {
idx = h & d->ht[table].sizemask;
he = d->ht[table].table[idx];
prevHe = NULL;
while(he) {
if (key==he->key || dictCompareKeys(d, key, he->key)) {
/* 從列表中unlink掉元素 */
if (prevHe)
prevHe->next = he->next;
else
d->ht[table].table[idx] = he->next;
// 如果nofree是0，需要釋放k和v對應(yīng)的內(nèi)存空間
if (!nofree) {
dictFreeKey(d, he);
dictFreeVal(d, he);
zfree(he);
}
d->ht[table].used--;
return he;
}
prevHe = he;
he = he->next;
}
if (!dictIsRehashing(d)) break;
}
return NULL; /* 沒找到key對應(yīng)的數(shù)據(jù) */
}
其它API
其他的API實現(xiàn)都比較簡單，我在dict.c源碼中做了大量的注釋，有興趣可以自行閱讀下，我這里僅列舉并說明下其大致的功能。
dict *dictCreate(dictType *type, void *privDataPtr); // 創(chuàng)建dict
int dictExpand(dict *d, unsigned long size); // 擴縮容
int dictAdd(dict *d, void *key, void *val); // 添加k-v
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing); // 添加的key對應(yīng)的dictEntry
dictEntry *dictAddOrFind(dict *d, void *key); // 添加或者查找
int dictReplace(dict *d, void *key, void *val); // 替換key對應(yīng)的value，如果沒有就添加新的k-v
int dictDelete(dict *d, const void *key); // 刪除某個key對應(yīng)的數(shù)據(jù)
dictEntry *dictUnlink(dict *ht, const void *key); // 卸載某個key對應(yīng)的entry
void dictFreeUnlinkedEntry(dict *d, dictEntry *he); // 卸載并清除key對應(yīng)的entry
void dictRelease(dict *d); // 釋放整個dict
dictEntry * dictFind(dict *d, const void *key); // 數(shù)據(jù)查找
void *dictFetchValue(dict *d, const void *key); // 獲取key對應(yīng)的value
int dictResize(dict *d); // 重設(shè)dict的大小，主要是縮容用的
/************ 迭代器相關(guān) *********** */
dictIterator *dictGetIterator(dict *d);
dictIterator *dictGetSafeIterator(dict *d);
dictEntry *dictNext(dictIterator *iter);
void dictReleaseIterator(dictIterator *iter);
/************ 迭代器相關(guān) *********** */
dictEntry *dictGetRandomKey(dict *d); // 隨機返回一個entry
dictEntry *dictGetFairRandomKey(dict *d); // 隨機返回一個entry，但返回每個entry的概率會更均勻
unsigned int dictGetSomeKeys(dict *d, dictEntry **des, unsigned int count); // 獲取dict中的部分數(shù)據(jù)
其他的API見代碼dict.c和dict.h.
本文是Redis源碼剖析系列博文，同時也有與之對應(yīng)的Redis中文注釋版，有想深入學(xué)習(xí)Redis的同學(xué)，歡迎star和關(guān)注。
Redis中文注解版?zhèn)}庫：https://github.com/xindoo/Redis
Redis源碼剖析專欄：https:///s/1h
如果覺得本文對你有用，歡迎一鍵三連。
本文來自https://blog.csdn.net/xindoo
|
