字典
Redis 中的字典 由 dict.h/dict 結(jié)構(gòu)表示:
typedef struct dict {
dictType *type; //類型特定函數(shù)
void *privdata; //私有數(shù)據(jù)
dictht ht[2]; //哈希表
int rehashdx; //rehash 索引,當 rehash 不在進行時,值為-1
} dict;
type 和 privdata 是針對不同類型的鍵值對,為創(chuàng)建多態(tài)字典而設(shè)置的
type指向一個 dictType 結(jié)構(gòu)的指針, 每個dictType 結(jié)構(gòu)保存了一簇用于操作特作特定類型鍵值對的函數(shù), Redis 會為用途不同的字典設(shè)置不同的類型特定函數(shù).
而pridata 則保存了需要傳給那些特定類型函數(shù)看可選參數(shù).
ht 屬性,包含兩個數(shù)組,數(shù)組的每一項都是一個 dictht 哈希表,一般情況下字典只使用ht[0] 哈希表,ht[1]哈希表只會在對哈希表進行 rehash 時使用.
rehashidex 記錄了 rehash 當前的進度,如果沒有進行 rehash, 值就為-1.
哈希表
Redis 字典所使用的哈希表由 dict.h/dictht 結(jié)構(gòu)定義:
typedef struct dictht {
dictEntry **table; //哈希表數(shù)組
unsigned long size; //哈希表大小
unsigned long sizemask; //用于計算索引值,
//總是等于 size - 1
unsigned long used; //哈希表已有節(jié)點數(shù)量
} dictht;
table 屬性是一個數(shù)組, 數(shù)組中每個元素都是一個指向 dictEntry 結(jié)構(gòu)的指針, 每個 dictEntry 結(jié)構(gòu)保存著一個鍵值對.
size 屬性記錄了哈希表的大小,也就是 table 數(shù)組的大小
sizemask 屬性和哈希值一起決定一個鍵應(yīng)該被放到 table 數(shù)組的哪個索引上面
哈希表節(jié)點
哈希表節(jié)點使用 dictEntry 表示,每個 dictEntry 結(jié)構(gòu)保存著一個鍵值對
typedef struct dictEntry {
void *key; //鍵
union { //值
void *val;
uint_64 u64;
int64_t s64;
} v;
sturct dictEntry *next; //指向下個哈希表節(jié)點,形成鏈表
} dictEntry;
注意這里 v 屬性保存著鍵值對中的值,其中的鍵值可以是指針,或是 uint_64 整數(shù),又或者是 int64_t 整數(shù).
next 屬性是指向另一個哈希表節(jié)點的指針,這個指針將多個哈希值相同的鍵值對連接在一起,以此來解決鍵值沖突(collision)問題.
下圖展示了一個普通狀態(tài)下的字典(沒有 rehash 進行)
哈希算法
Redis 使用 MurmurHash2 算法 來計算鍵的哈希值.
Redis 計算哈希值和索引的方法如下:
hash = dict->type->hashFunction(k);
index = hash & dict->ht[0].sizemask
解決鍵沖突
當有兩個或兩個以上的鍵被分配到了哈希表數(shù)組的同一索引上時,稱這些鍵發(fā)生了沖突( collision)
Redis 的哈希表使用鏈地址法來解決沖突,每個哈希表節(jié)點都有一個 next 指針,多個哈希表節(jié)點可以用 next 指針構(gòu)成一個單項鏈表,被分配到同一個索引上的多個節(jié)點可以用這個對單向鏈表連接起來,這就解決了鍵沖突的問題.
如前面的字典示意圖所示, 鍵 k0 和 k1 的索引值均為1,這里只需用 next 指針將兩個節(jié)點連接起來.
,因為dictEntry 節(jié)點組成的鏈表沒有表尾指針,為了 速度考慮,程序總是將新節(jié)點調(diào)價到鏈表的表頭位置,排在其他已有節(jié)點的前面,這樣插入的復雜度為$ O(1)$.
Rehash
隨著操作的不斷進行, 哈希表保存的鍵值對會逐漸地增多或減少,為了讓哈希表的負載因子維持在一個合理的范圍之內(nèi),當哈希表保存的鍵值對數(shù)量太多或者太少時, 程序需要對哈希表的大小進行相應(yīng)的擴展或者收縮.這個過程叫做rehash.
Redis 對字典的哈希表執(zhí)行 rehash 的步驟如下:
- 為字典的 ht[1] 哈希表分配空間,空間的大小取決于要執(zhí)行的操作,以及 ht0]當前包含的鍵值對數(shù)量( used 屬性值):
- 如果執(zhí)行的是擴展操作,那么 ht[1] 的大小為第一個大于等于 ht0].used*2的 $2^n$ .
- 如果執(zhí)行的是收縮操作,那么ht[1]的大小為打一個大于等于 ht[0].used 的$2^n$.
- 將保存在 ht[0] 中所有鍵值對 rehash 到 ht[1] 上面: 任何事指的是重新計算鍵的哈希值和索引值,然后鍵鍵值對放到 ht[1] 哈希表的指定位置.
- 當 ht[0] 包含的所有鍵值對都遷移到了 ht[1] 之后, 釋放 ht[0], 再將 ht[1] 設(shè)置為 ht[0],并在 ht[1] 后面創(chuàng)建一個空白的哈希表.
舉個例子,假設(shè)程序要對下圖的 `ht[0] 進行擴展操作
ht[0].used 當前值為4 , $2^3$ 恰好是第一個大于等于 4*2 的值,所以 ht[1] 哈希表的大小設(shè)置為8,下圖展示了 ht[1] 分配了空間之后字典的樣子.
將 ht[0] 包含的四個鍵值對 rehash 到 ht[1], 圖下圖所示:
釋放 ht[0], 將 ht[1] 設(shè)置為 ht[0]. 再分配一個空哈希表. 哈希表的大小由原來的4 擴展至8.
漸進式 rehash
上一節(jié)說過, 擴展或收縮哈希表需要將 ht[0] 里的所有鍵值對 rehash 到 ht[1] 中,但是這個 rehash
動作并不是一次性,集中式完成的,而是分多次,漸進式完成的.
這么做的原因是,當哈希表里保存的鍵值對多至百萬甚至億級別時,一次性地全部 rehash 的話,龐大的計算量會對服務(wù)器性能造成嚴重影響.
以下是漸進式 rehash 的步驟:
- 為 ht[1] 分配空間
- 在字典中維持一個索引計數(shù)器變量 rehashidx, 將它的值設(shè)置為0,表示 rehash 正式開始
- 在 rehash 進行期間,每次對字典進行增刪改查時,順帶將 ht[0] 在 rehashidx 索引上的所有鍵值對 rehash 到 ht[1] 中,同時將 rehashidx 加 1.
- 隨著操作不斷進行,最終在某個時間點上, ht[0] 所有的鍵值對全部 rehash 到 ht[1] 上,這是講 rehashidx 屬性置為 -1,,表示 rehash操作完成.
- 在漸進式 rehash 執(zhí)行期間,新添加到字典的鍵值對一律保存到 ht[1] 里,不會對 ht[0] 做添加操作,這一措施保證了 ht[0]只減不增,并隨著 rehash 進行, 最終編程空表.
