字典又稱
符號(hào)表,關(guān)聯(lián)數(shù)組,映射, 是一種用于保存鍵值對(duì)的抽象數(shù)據(jù)結(jié)構(gòu)Redis構(gòu)建了自己的字典實(shí)現(xiàn), eg. set msg 'test'會(huì)構(gòu)建
key為msg,value為test的鍵值對(duì).除了表示數(shù)據(jù)庫之外, 字典還是hash鍵的底層實(shí)現(xiàn)之一(另外一種是ziplist)
字典實(shí)現(xiàn)
hash表
Redis字典所使用的哈希表由 dict.h/dictht 結(jié)構(gòu)定義
typedef struct dictht {
dictEntry **table; // hash表數(shù)組
unsigned long size; // hash表大小
unsigned long sizemask; // hash表大小掩碼, 用于計(jì)算hash索引值, 總是=size-1
unsigned long used; // 已有節(jié)點(diǎn)數(shù)量
}dictht;
hash表節(jié)點(diǎn)
typedef struct dictEntry {
void *key; // 鍵
union {
void *val;
unit64_tu64;
int64_ts64;
}v; // 值
struct dictEntry *next;// 指向下個(gè)hash節(jié)點(diǎn)狠怨、形成鏈表
}
key屬性保存著鍵值對(duì)中的鍵、而v屬性則保存著鍵值對(duì)中的值, 它可以是一個(gè)指針, 或者是uint64_t類型的整數(shù), 或者是 int64_t的整數(shù)
next屬性是指向另一個(gè)節(jié)點(diǎn)的指針, 這個(gè)指針可以將多個(gè)hash值相同的鍵值對(duì)連接在一起, 解決鍵沖突問題
字典
Redis中的字典由 dict.h/dict 結(jié)構(gòu)定義
typedef struct dict {
dictType *type; // 類型特定函數(shù)
void *privdata; // 私有數(shù)據(jù)
dictht ht[2]; // hash表
in trehashidx; // rehash索引, 當(dāng)rehash不在進(jìn)行時(shí)、值為-1
} dict;
type屬性是一個(gè)指向 dictType結(jié)構(gòu)的指針, 每個(gè) dictType結(jié)構(gòu)保存了一簇用于操作特定類型鍵值對(duì)的函數(shù), Redis會(huì)為不同類型的字典設(shè)置不同類型的特定函數(shù)
privdata屬性則保存了需要傳給那些特定類型函數(shù)的可選參數(shù)
type和privdata是針對(duì)不同類型的鍵值對(duì), 為創(chuàng)建多態(tài)字典設(shè)置的
typedef struct dictType {
unsigned int (*hashFunction)(const void *key); // 計(jì)算hash值的函數(shù)
void *(*keyDup)(void *privdata, const void *key); // 復(fù)制鍵的函數(shù)
void *(valDup)(void *privdata, const void *obj); // 復(fù)制值的函數(shù)
int (*keyCompare)(void *privdata, const void *key1, const void *key2); // 對(duì)比鍵的函數(shù)
void (*keyDestructor)(void *privdata, void *key); // 銷毀鍵的函數(shù)
void (*valDestructor)(void *privdata, void *obj); // 銷毀值的函數(shù)
}dictType;
ht屬性是一個(gè)包含兩個(gè)項(xiàng)的數(shù)組, 數(shù)組中的每個(gè)項(xiàng)都是一個(gè)dictht哈希表, 一般只使用ht[0], ht[1]只會(huì)在對(duì)ht[0] 進(jìn)行rehash時(shí)使用.
rehashidx記錄當(dāng)前rehash的進(jìn)度, 若沒有在進(jìn)行rehash, 則值為 -1
完整的dict結(jié)構(gòu)
hash算法
Redis計(jì)算hash值的方式如下:
hash = dict->type->hashFunction(key); // 使用hash字典設(shè)置的hash函數(shù)衰齐、計(jì)算key的hash值
index = hash & dict->ht[x].sizemask; // 根據(jù)sizemask和hash值、計(jì)算出hash索引
解決鍵沖突
當(dāng)有兩個(gè)或以上數(shù)量的鍵被分配到hash表數(shù)組同一個(gè)索引上時(shí), 稱為鍵沖突 collision, Redis的hash表使用 鏈地址法(separate chaining)來解決沖突, 每個(gè)hash表節(jié)點(diǎn)上有一個(gè)next指針, 多個(gè)hash表節(jié)點(diǎn)使用next指針構(gòu)成單鏈表
dictEntry總是將新增節(jié)點(diǎn)添加到鏈表頭部(時(shí)間復(fù)雜度為 O(1)), 因?yàn)闆]有tail指針.
rehash
隨著操作的不斷進(jìn)行、hash表維護(hù)的鍵值對(duì)會(huì)增加或減少, 為了讓hash表的負(fù)載因子(load factor)維持在一個(gè)合理的額范圍, 當(dāng)hash表保存鍵值對(duì)數(shù)量太大或太小時(shí), 程序需要對(duì)hash表擴(kuò)容或縮容, 擴(kuò)容或縮容通過rehash進(jìn)行, Rehash步驟如下:
- 為字典的ht[1]hash表分配空間, hash表的空間大小取決于要執(zhí)行的操作, 及ht[0]當(dāng)前包含的鍵值對(duì)的數(shù)量(即: ht[0].used 屬性值), 若為擴(kuò)容, ht[1] 為第一個(gè)大于等于 (ht[0].used
*2)d的*2n; 若為縮容, ht[1] 為第一個(gè)大于等于 (ht[0].used) 的 2n - 將ht[0]中的所有鍵值對(duì)rehash到ht[1]上,
rehash是指: 重新計(jì)算鍵的hash值和索引值, 然后將鍵值對(duì)放到ht[1]hash表的對(duì)應(yīng)位置 - 當(dāng)ht[0]包含的所有鍵值對(duì)遷移到ht[1]之后(ht[0]變?yōu)榭毡?, 釋放ht[0], 將ht[1]設(shè)置為 ht[0], 并在 ht[1]新創(chuàng)建一個(gè)空白hash表, 為下一次rehash做準(zhǔn)備
eg. 擴(kuò)容操作:
ht[0].used = 4, 4*2=8, 恰好是第一個(gè)大于等于4的2的n次方, 所以rehash后、ht[1]size為8
縮容操作:
ht[0].used = 4, 4=22, 恰好是第一個(gè)大于等于4的2的n次方, rehash后 ht[1].size = 4
hash表的擴(kuò)展與收縮
滿足下述任意條件時(shí), 會(huì)自動(dòng)擴(kuò)展:
server 當(dāng)前未執(zhí)行
bgsave或者bgrewriteaof, 且hash表的負(fù)載因子大于等于1-
server 當(dāng)前正在執(zhí)行
bgsave或者bgrewriteaof, 且 hash表的負(fù)載因子大于等于 5(持久化時(shí)蚣录、優(yōu)先持久化操作)
load_factor = ht[0].used / ht[0].size; // 負(fù)載因子 = hash表已保存節(jié)數(shù)量 / hash表大小
若bgsave或者bgrewriteaof執(zhí)行時(shí), Redis需要?jiǎng)?chuàng)建當(dāng)前服務(wù)器進(jìn)程的子進(jìn)程, 大多數(shù)操作系統(tǒng)使用寫時(shí)復(fù)制(copy-on-write)優(yōu)化子進(jìn)程使用效率, 所以子進(jìn)程存在期間, Server會(huì)提高rehash操作的負(fù)載因子, 盡可能避免此時(shí)rehash, 避免不必要的內(nèi)存寫入操作, 最大限度的節(jié)省內(nèi)存.
另外:
hash表的負(fù)載因子小于0.1時(shí), 程序會(huì)自動(dòng)縮容
漸進(jìn)式rehash
其實(shí), hash表的rehash操作、不是一次集中完成的, 而是多次迭代進(jìn)行的. 因?yàn)槿?ht[0]里保存的key有百萬計(jì), 甚至更多, 一次rehash導(dǎo)ht[1], 龐大的計(jì)算量可能會(huì)導(dǎo)致Server一段時(shí)間的停止服務(wù).
漸進(jìn)式rehash步驟如下:
- 為ht[1]分配空間, 讓字典同時(shí)持有ht[0] 和 ht[1]兩個(gè)hash表
- 在字典中維護(hù)一個(gè)索引計(jì)數(shù)器變量
rehashidx, 設(shè)置為0, 表示rehash已經(jīng)開始 - 在
rehash期間, 每次對(duì)字典add,del,findorupdate操作, 程序除了執(zhí)行指定操作外, 還會(huì)順帶將 ht[0] hash表在rehashidx索引上的所有鍵值對(duì) rehash 到 ht[1], rehash完成眷篇、將rehashidx++. - 隨字典操作的不斷執(zhí)行萎河、某個(gè)時(shí)間點(diǎn), ht[0]的所有鍵值對(duì)rehash到ht[1], rehash完成、將
rehashidx設(shè)為-1.
漸進(jìn)式rehash過程中會(huì)維護(hù) ht[0] 和 ht[1] 兩個(gè)hash表, 字典的刪除、查找虐杯、更新等操作都會(huì)在兩個(gè)hash表上進(jìn)行, eg. 查找: 會(huì)先在 ht[0] 上查找玛歌、若未找到則 到 ht[1] 上查找
但: 插入操作只會(huì)在 ht[1] 上操作
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
字典API
| 函數(shù) | 作用 | 時(shí)間復(fù)雜度 |
|---|---|---|
| dictCreate | 創(chuàng)建一個(gè)新的字典 | O(1) |
| dictAdd | 將給定鍵值對(duì)添加到字典 | O(1) |
| dictReplace | 添加or替換 | O(1) |
| dictFetchValue | 返回給定鍵的值 | O(1) |
| dictGetRandomKey | 隨機(jī)返回一個(gè)鍵值對(duì) | O(1) |
| dictRelease | 釋放給定字典, 及字典中包含的所有鍵值對(duì) | O(N), N為值的數(shù)量 |
dict總結(jié)
- 廣泛用于實(shí)現(xiàn)Redis的各種功能, 包括數(shù)據(jù)庫和hash鍵
- 作為hash表的底層實(shí)現(xiàn), 每個(gè)字典有兩個(gè)hash表、一個(gè)平時(shí)使用, 一個(gè) rehash 時(shí)使用
- 使用
Murmurhash2計(jì)算key的hash值 - 使用鏈地址法解決鍵沖突擎椰、同一個(gè)索引上的多個(gè)鍵值對(duì)連接成一個(gè)單鏈表
- rehash是漸進(jìn)式完成支子、非一次性工作
