字典在redis的應(yīng)用
字典在我們平時(shí)的編程中是一種非常常見的數(shù)據(jù)結(jié)構(gòu)筒主，它有著結(jié)構(gòu)簡(jiǎn)單撕捍，查找快速的優(yōu)點(diǎn)迈嘹，而在redis中削彬，字典的應(yīng)用更是十分廣泛。redis本身是一個(gè)key-value型的nosql數(shù)據(jù)庫秀仲，因此數(shù)據(jù)庫本身就是由字典而構(gòu)成的融痛，數(shù)據(jù)庫的curd都是在此基礎(chǔ)上進(jìn)行的。除此之外神僵，redis的map類型也是由字典這個(gè)結(jié)構(gòu)實(shí)現(xiàn)的雁刷。
字典的實(shí)現(xiàn)
c語言不像我們平時(shí)用習(xí)慣的高級(jí)編程語言一樣，它沒有內(nèi)置字典結(jié)構(gòu)挑豌，因此redis自身實(shí)現(xiàn)了一套字典結(jié)構(gòu)安券，下面我們來簡(jiǎn)單分析下實(shí)現(xiàn)字典的幾個(gè)結(jié)構(gòu)體。
1. 哈希表
typedef struct dictht {
// 哈希表數(shù)組
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩碼氓英，用于計(jì)算索引值
// 總是等于 size - 1
unsigned long sizemask;
// 該哈希表已有節(jié)點(diǎn)的數(shù)量
unsigned long used;
} dictht;
這里要注意的就是侯勉，table字段是一個(gè)可以保存多個(gè)dictEntry的數(shù)組，也就是一個(gè)哈希表里面會(huì)有多個(gè)哈希的實(shí)體類铝阐，也可以成為哈希節(jié)點(diǎn)址貌。
2. 哈希節(jié)點(diǎn)
typedef struct dictEntry {
// 鍵
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 指向下個(gè)哈希表節(jié)點(diǎn)，形成鏈表
struct dictEntry *next;
} dictEntry;
v字段表示哈希節(jié)點(diǎn)的值徘键，使用union結(jié)構(gòu)體表示這個(gè)值可以使void指針類型练对，也可以是uint64_t或者int64_t整數(shù)，這里我猜想是為了其他操作系統(tǒng)而做的一個(gè)兼容吧吹害。盡管大部分哈希函數(shù)具有很強(qiáng)的防碰撞性螟凭，但是也會(huì)遇到哈希值相同的鍵值對(duì)，這個(gè)時(shí)候next字段就發(fā)揮作用了它呀，它會(huì)把相同哈希值的鍵值對(duì)整理成一個(gè)單向鏈表結(jié)構(gòu)來方便查找螺男。
3. 字典
typedef struct dict {
// 類型特定函數(shù)
dictType *type;
// 私有數(shù)據(jù)
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引
// 當(dāng) rehash 不在進(jìn)行時(shí)，值為 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
// 目前正在運(yùn)行的安全迭代器的數(shù)量
int iterators; /* number of iterators currently running */
} dict;
type字段提供了一組類型的操作函數(shù)：
typedef struct dictType {
// 計(jì)算哈希值的函數(shù)
unsigned int (*hashFunction)(const void *key);
// 復(fù)制鍵的函數(shù)
void *(*keyDup)(void *privdata, const void *key);
// 復(fù)制值的函數(shù)
void *(*valDup)(void *privdata, const void *obj);
// 對(duì)比鍵的函數(shù)
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
// 銷毀鍵的函數(shù)
void (*keyDestructor)(void *privdata, void *key);
// 銷毀值的函數(shù)
void (*valDestructor)(void *privdata, void *obj);
} dictType;
這組函數(shù)可以讓不同類型的鍵值對(duì)能夠使用不同的方法進(jìn)行復(fù)制纵穿、對(duì)比等操作下隧，真正讓redis實(shí)現(xiàn)了多態(tài)字典。
我們還可以見到谓媒，字典結(jié)構(gòu)體內(nèi)部包含了兩個(gè)哈希表的數(shù)組淆院，為什么需要兩個(gè)哈希表呢？這就引入了一個(gè)rehash的概念了句惯。
字典的rehash
當(dāng)哈希表中的哈希節(jié)點(diǎn)土辩，也就是鍵值對(duì)的數(shù)量越來越多或者越來越少的時(shí)候，原來分配的哈希表將會(huì)進(jìn)行伸縮宗弯，redis會(huì)維護(hù)一個(gè)哈希表的負(fù)載因子脯燃，其中計(jì)算方式是：負(fù)載因子=哈希表的使用數(shù)量/哈希表的長(zhǎng)度
當(dāng)符合以下兩個(gè)條件任何一個(gè)的時(shí)候就會(huì)進(jìn)行reshash操作:
- 服務(wù)器沒有執(zhí)行
BGSAVE或者BGREWRITEAOF命令，并且這個(gè)負(fù)載因子大于等于1的時(shí)候蒙保。 - 服務(wù)器在執(zhí)行
BGSAVE或者BGREWRITEAOF命令辕棚，并且負(fù)載因子超過5。
為什么在執(zhí)行備份命令的時(shí)候邓厕，負(fù)載因子要比沒有執(zhí)行備份的時(shí)候大呢逝嚎？原因就是redis在執(zhí)行BGSAVE之類的備份命令時(shí)候，會(huì)fork一個(gè)子進(jìn)程進(jìn)行備份详恼，而目前大部分操作系統(tǒng)都會(huì)采用copy on write也就是寫時(shí)復(fù)制的技術(shù)补君，如果此時(shí)過多的去進(jìn)行rehash會(huì)導(dǎo)致內(nèi)存占用過多。
rehash的步驟：
- 為哈希表數(shù)組
ht[1]進(jìn)行空間分配昧互。分配的原則是：擴(kuò)容則分配ht[0].used*2挽铁，收縮則分配ht[0]*used/2伟桅。 - 重新計(jì)算
ht[0]中的所有鍵值對(duì)，然后逐步遷移到ht[1]中叽掘。 - 當(dāng)
ht[0]所有鍵值對(duì)都遷移完畢之后楣铁，釋放ht[0]所占空間，把ht[1]取代到ht[0]的位置更扁，并且新創(chuàng)建一個(gè)空白的哈希表盖腕，也就是新的ht[1]，整個(gè)rehash步驟到此結(jié)束浓镜。
漸進(jìn)式rehash
上面我們簡(jiǎn)單介紹了rehash的步驟溃列，但是如果真是那么簡(jiǎn)單去實(shí)現(xiàn)的話，其實(shí)是有缺陷的膛薛。試想想听隐，如果哈希表中擁有大量的鍵值對(duì)，一次性去進(jìn)行rehash把大量的鍵值對(duì)進(jìn)行遷移相叁，勢(shì)必會(huì)導(dǎo)致性能低下遵绰，并且影響redis的讀寫性能甚至導(dǎo)致服務(wù)被停止。因此增淹，rehash是漸進(jìn)的椿访，并且是不能影響正常的redis讀寫服務(wù)的。以下就是漸進(jìn)式rehash的一個(gè)過程：
- 為
ht[1]分配空間虑润，分配的規(guī)則上面已經(jīng)寫了成玫，這里就不再重復(fù)描述。 - 此時(shí)字典會(huì)擁有
ht[0]和ht[1]兩個(gè)哈希表拳喻，字段rehashidx就能產(chǎn)生作用了哭当。rehashidx默認(rèn)值是-1，當(dāng)它變?yōu)?說明rehash正式開始冗澈。 -
rehash開始钦勘，redis會(huì)把ht[0]中rehashidx索引中的鍵值對(duì)進(jìn)行rehash到ht[1]，每次rehash完成都會(huì)讓rehashidx遞增1亚亲，然后重復(fù)這個(gè)過程彻采。 - 在這個(gè)過程中，我們難免會(huì)對(duì)redis進(jìn)行增刪改查的操作捌归，這個(gè)時(shí)候同時(shí)擁有兩個(gè)哈希表的作用就發(fā)揮出來了肛响。對(duì)于查找、刪除惜索、修改操作特笋，redis會(huì)現(xiàn)在
ht[0]中進(jìn)行，如果找不到才會(huì)到ht[1]進(jìn)行對(duì)應(yīng)操作巾兆，而增加這些操作則會(huì)直接在ht[1]中進(jìn)行猎物，主要是讓ht[0]只減不增虎囚，這樣到了某個(gè)時(shí)刻，ht[0]的所有鍵值對(duì)一定會(huì)全部遷移到ht[1]蔫磨。
領(lǐng)悟
redis這個(gè)字典的結(jié)構(gòu)實(shí)現(xiàn)清晰明了溜宽，特別是其中的rehash機(jī)制很值得我去學(xué)習(xí)，這個(gè)對(duì)于一些數(shù)據(jù)遷移并且不能影響正常服務(wù)的編程實(shí)現(xiàn)非常有借鑒意義质帅。
文章參考自：<<Redis設(shè)計(jì)與實(shí)現(xiàn)>> 第二版
