在 Redis 中有多個數(shù)據(jù)集,數(shù)據(jù)集采用的數(shù)據(jù)結(jié)構(gòu)是哈希表,用以存儲鍵值對。默認所有的客戶端都是使用第一個數(shù)據(jù)集,一個數(shù)據(jù)集對應(yīng)一個哈希表。如果客戶端有需要可以使用 select 命令來選擇不同的數(shù)據(jù)集。Redis 在初始化服務(wù)器的時候就會初始化所有的數(shù)據(jù)集:
void initServer() {
......
// 分配數(shù)據(jù)集空間
server.db = zmalloc(sizeof(redisDb)*server.dbnum);
......
// 初始化redis 數(shù)據(jù)集
/* Create the Redis databases, and initialize other internal state. */
for (j = 0; j < server.REDIS_DEFAULT_DBNUM; j++) { // 初始化多個數(shù)據(jù)庫
// 哈希表,用于存儲鍵值對
server.db[j].dict = dictCreate(&dbDictType,NULL);
// 哈希表,用于存儲每個鍵的過期時間
server.db[j].expires = dictCreate(&keyptrDictType,NULL);
......
}
......
}
我們來看看哈希表的數(shù)據(jù)結(jié)構(gòu)是怎么樣的:
http://wiki.jikexueyuan.com/project/redis/images/redis9.png" alt="" />
數(shù)據(jù)集采用的數(shù)據(jù)結(jié)構(gòu)是哈希表,數(shù)據(jù)真正存儲在哈希表中,用開鏈法解決沖突問題,struct dictht 即為一個哈希表。但在 Redis 哈希表數(shù)據(jù)結(jié)構(gòu) struct dict 中有兩個哈希表,下文將兩個哈希表分別稱為第一個和第二個哈希表,Redis 提供兩個哈希表是為了能夠在不中斷服務(wù)的情況下擴展(expand)哈希表,這是很有趣的一部分。
// 可以把它認為是一個鏈表,提示,開鏈法
typedef struct dictEntry {
void *key;
union {
\\ val 指針可以指向一個redisObject
void *val;
uint64_t u64;
int64_t s64;
} v;
struct dictEntry *next;
} dictEntry;
// 要存儲多種多樣的數(shù)據(jù)結(jié)構(gòu),勢必不同的數(shù)據(jù)有不同的哈希算法,不同的鍵值比較算法,
// 不同的析構(gòu)函數(shù)。
typedef struct dictType {
// 哈希函數(shù)
unsigned int (*hashFunction)(const void *key);
void *(*keyDup)(void *privdata, const void *key);
void *(*valDup)(void *privdata, const void *obj);
// 比較函數(shù)
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
// 鍵值析構(gòu)函數(shù)
void (*keyDestructor)(void *privdata, void *key);
void (*valDestructor)(void *privdata, void *obj);
} dictType;
// 一般哈希表數(shù)據(jù)結(jié)構(gòu)
/* This is our hash table structure. Every dictionary has two of this as we
* implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
// 兩個哈希表
dictEntry **table;
// 哈希表的大小
unsigned long size;
// 哈希表大小掩碼
unsigned long sizemask;
// 哈希表中數(shù)據(jù)項數(shù)量
unsigned long used;
} dictht;
// 哈希表(字典)數(shù)據(jù)結(jié)構(gòu),Redis 的所有鍵值對都會存儲在這里。其中包含兩個哈希表。
typedef struct dict {
// 哈希表的類型,包括哈希函數(shù),比較函數(shù),鍵值的內(nèi)存釋放函數(shù)
dictType *type;
// 存儲一些額外的數(shù)據(jù)
void *privdata;
// 兩個哈希表
dictht ht[2];
// 哈希表重置下標(biāo),指定的是哈希數(shù)組的數(shù)組下標(biāo)
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
// 綁定到哈希表的迭代器個數(shù)
int iterators; /* number of iterators currently running */
} dict;
Redis 為每個數(shù)據(jù)集配備兩個哈希表,能在不中斷服務(wù)的情況下擴展哈希表。平時哈希表擴展的做法是,為新的哈希表另外開辟一個空間,將原哈希表的數(shù)據(jù)重新計算哈希值,以移動到新哈希表。如果原哈希表數(shù)據(jù)過多,中間大量的計算過程較好費大量時間,這段時間 Redis 將不能提供服務(wù)。
Redis 擴展哈希表的做法有點小聰明:為第二個哈希表分配新空間,其空間大小為原哈希表鍵值對數(shù)量的兩倍(是的,沒錯),接著逐步將第一個哈希表中的數(shù)據(jù)移動到第二個哈希表;待移動完畢后,將第二個哈希值賦值給第一個哈希表,第二個哈希表置空。在這個過程中,數(shù)據(jù)會分布在兩個哈希表,這時候就要求在 CURD 時,都要考慮兩個哈希表。而這里,將第一個哈希表中的數(shù)據(jù)移動到第二個哈希表被稱為重置哈希(rehash)。
在 CURD 的時候會執(zhí)行一步的重置哈希表操作,在服務(wù)器定時程序 serverCorn() 中會 執(zhí)行一定時間的重置哈希表操作。為什么在定時程序中重置哈希表了,還 CURD 的時候還 要呢?或者反過來問。一個可能的原因是 Redis 做了兩手準(zhǔn)備:在服務(wù)器空閑的時候,定 時程序會完成重置哈希表;在服務(wù)器過載的時候,更多重置哈希表操作會落在 CURD 的服 務(wù)上。 下面是重置哈希表的函數(shù),其主要任務(wù)就是選擇哈希表中的一個位置上的單鏈表,重 新計算哈希值,放到第二個哈希表。
int dictRehash(dict *d, int n) {
// 重置哈希表結(jié)束,直接返回
if (!dictIsRehashing(d)) return 0;
while(n--) {
dictEntry *de, *nextde;
// 第一個哈希表為空,證明重置哈希表已經(jīng)完成,將第二個哈希表賦值給第一個,
// 結(jié)束
/* Check if we already rehashed the whole table... */
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;
}
/* 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)d->rehashidx);
// 找到哈希表中不為空的位置
while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;
de = d->ht[0].table[d->rehashidx];
// 此位置的所有數(shù)據(jù)移動到第二個哈希表
/* Move all the keys in this bucket from the old to the new hash HT */
while(de) {
unsigned int h;
nextde = de->next;
/* Get the index in the new hash table */
// 計算哈希值
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
// 頭插法
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
// 更新哈希表中的數(shù)據(jù)量
d->ht[0].used--;
d->ht[1].used++;
de = nextde;
}
// 置空
d->ht[0].table[d->rehashidx] = NULL;
// 指向哈希表的下一個位置
d->rehashidx++;
}
return 1;
}
在 Redis 添加替換的時候,都先要查看數(shù)據(jù)集中是否已經(jīng)存在該鍵,也就是一個查找的過程,如果一個 Redis 命令導(dǎo)致過多的查找,會導(dǎo)致效率低下??赡苁菫榱藫P長避短,即高讀性能和低寫性能,Redis 中數(shù)據(jù)的添加和替換效率不高,特別是替換效率低的惡心。
http://wiki.jikexueyuan.com/project/redis/images/redis10.png" alt="" />
在 redis SET 命令的調(diào)用鏈中,添加鍵值對會導(dǎo)致了 2 次的鍵值對查找;替換鍵值對最多會導(dǎo)致 4 次的鍵值對查找。在 dict 的實現(xiàn)中,dictFind() 和_dictIndex() 都會導(dǎo)致鍵值對的查找,詳細可以參看源碼。所以,從源碼來看,經(jīng)常在 Redis 上寫不是一個明智的選擇。
在 RDB 和 AOF 持久化操作中,都需要迭代哈希表。哈希表的遍歷本身難度不大,但因為每個數(shù)據(jù)集都有兩個哈希表,所以遍歷哈希表的時候也需要注意遍歷兩個哈希表:第一個哈希表遍歷完畢的時候,如果發(fā)現(xiàn)重置哈希表尚未結(jié)束,則需要繼續(xù)遍歷第二個哈希表。
// 迭代器取下一個數(shù)據(jù)項的入口
dictEntry *dictNext(dictIterator *iter)
{
while (1) {
if (iter->entry == NULL) {
dictht *ht = &iter->d->ht[iter->table];
// 新的迭代器
if (iter->index == -1 && iter->table == 0) {
if (iter->safe)
iter->d->iterators++;
else
iter->fingerprint = dictFingerprint(iter->d);
}
iter->index++;
// 下標(biāo)超過了哈希表大小,不合法
if (iter->index >= (signed) ht->size) {
// 如果正在重置哈希表,Redis 會嘗試在第二個哈希表上進行迭代,
// 否則真的就不合法了
if (dictIsRehashing(iter->d) && iter->table == 0) {
// 正在重置哈希表,證明數(shù)據(jù)正在從第一個哈希表整合到第二個哈希表,
// 則指向第二個哈希表
iter->table++;
iter->index = 0;
ht = &iter->d->ht[1];
} else {
// 否則迭代完畢,這是真正不合法的情況
break;
}
}
// 取得數(shù)據(jù)項入口
iter->entry = ht->table[iter->index];
} else {
// 取得下一個數(shù)據(jù)項人口
iter->entry = iter->nextEntry;
}
// 迭代器會保存下一個數(shù)據(jù)項的入口,因為用戶可能會刪除此函數(shù)返回的數(shù)據(jù)項
// 入口,如此會導(dǎo)致迭代器失效,找不到下一個數(shù)據(jù)項入口
if (iter->entry) {
/* We need to save the 'next' here, the iterator user
* may delete the entry we are returning. */
iter->nextEntry = iter->entry->next;
return iter->entry;
}
}
return NULL;
}