Redis字典實(shí)現(xiàn)、Hash鍵沖突及漸進(jìn)式rehash詳解

本筆記參考《Redis設(shè)計(jì)與實(shí)現(xiàn)》 P24~ 37

Redis字典實(shí)現(xiàn)

哈希表節(jié)點(diǎn)結(jié)構(gòu)

typedef struct dictEntry
{
	// 鍵
	void *key;

	// 值 : 可以是一個(gè)指針，或者是一個(gè)uint64/int64 的整數(shù)
	union {
		void *val;
		uint64_t u64;
		int64_t s64
	} v;

	// 指向下一個(gè)哈希表節(jié)點(diǎn)，形成鏈表 ： 該指針可以將多個(gè)哈希值相同的鍵值對(duì)連接在一起，以此解決鍵沖突的問題。
	struct dictEntry *next;
} dictEntry;

哈希表結(jié)構(gòu)

typedef struct dictht
{
	// 哈希表數(shù)據(jù)
	dictEntry **table;

	// 哈希表集合大小
	unsigned long size;

	// 哈希表大小掩碼，用于計(jì)算索引值
	// 總是等于 size - 1
	unsigned long sizemask;

	// 哈希表已有節(jié)點(diǎn)數(shù)量
	unsigned long used;
} dictht;

字典

typedef struct dict 
{
	// 類型特定函數(shù)
	dicType *type;

	// 私有數(shù)據(jù)
	void *privdata;

	// 哈希表
	dictht ht[2];

	// rehash 索引
	// 當(dāng)rehash不在進(jìn)行時(shí)， 值為-1
	int rehashidx;
} dict;

type屬性和privdata屬性針對(duì)不同類型的鍵值對(duì)，為多態(tài)字典而設(shè)置。
ht是包含兩個(gè)項(xiàng)的數(shù)組，每個(gè)元素都是一個(gè)dictht哈希表，一般情況下字典之是喲個(gè)ht[0],ht[1]會(huì)在對(duì)ht[0]進(jìn)行rehash的時(shí)候使用。
rehashidx記錄了rehash目前的進(jìn)度，如果目前沒有在進(jìn)行rehash，值為-1。

哈希算法

• 使用字典設(shè)置的哈希函數(shù)，計(jì)算key的hashvalue
  

hash = dict->type->hashFunction(key);

• 使用哈希表的sizemask屬性和哈希值，計(jì)算出索引值
• 根據(jù)不同的情況，ht[x]可以是ht[0]或ht[1]
  

index = hash dict->ht[x].sizemask;

redis使用的是MurmurHash算法，優(yōu)點(diǎn)是：輸入的鍵是有規(guī)律的時(shí)候，算法仍然能給出很好的隨機(jī)分布性，計(jì)算速度也快。

解決hash沖突

當(dāng)有兩個(gè)或以上的key分配到了hash table數(shù)組的同一個(gè)index上，稱為發(fā)生了collision。
Redis采用鏈地址法解決沖突，每個(gè)hash table節(jié)點(diǎn)都有一個(gè)next指針，多個(gè)hash table節(jié)點(diǎn)可以用next指針構(gòu)成一個(gè)單向鏈表。為了速度考慮，程序總是會(huì)將新節(jié)點(diǎn)插入到鏈表頭位置。

rehash

隨著操作不斷執(zhí)行，哈希表保存的key value對(duì)會(huì)逐漸增加和減少。哈希表有一個(gè)統(tǒng)計(jì)參數(shù)load factor，即負(fù)載因子，公式如下：

# 負(fù)載因子 = 哈希表已經(jīng)保存的節(jié)點(diǎn)數(shù)量 / 哈希表大小
load_factor = ht[0].used / ht[0].size;

為了維持負(fù)載因子在一個(gè)合理的范圍，程序會(huì)對(duì)哈希表的大小進(jìn)行相應(yīng)的擴(kuò)展或收縮，條件如下：

1、服務(wù)器目前沒有執(zhí)行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的負(fù)載因子 >= 1

2、服務(wù)器正在執(zhí)行BGSAVE命令或者BGREWRITEAOF命令，且負(fù)載因子 >= 5

• 在執(zhí)行BGSAVE命令或者BGREWRITEAOF命令過程中，Redis需要?jiǎng)?chuàng)建當(dāng)前服務(wù)器進(jìn)程的子進(jìn)程，大多的OS采用寫時(shí)復(fù)制技術(shù)優(yōu)化子進(jìn)程的使用效率，所以子進(jìn)程存在期間，**服務(wù)器會(huì)提高執(zhí)行擴(kuò)展操作的負(fù)載因子，避免在子進(jìn)程存在期間進(jìn)行哈希表的擴(kuò)展操作，避免不必要的內(nèi)存寫入操作，最大限度節(jié)約內(nèi)存。**當(dāng)負(fù)載因子小于0.1時(shí)，程序自動(dòng)對(duì)哈希表進(jìn)行收縮操作。
• 此時(shí)就會(huì)進(jìn)行擴(kuò)展收縮，規(guī)則如下：
• 這里就是rehash(重新散列)操作了：
• 1、為字典的ht[1]哈希表分配內(nèi)存空間，空間大小取決于要執(zhí)行的操作，以及ht[0]當(dāng)前包含的鍵值對(duì)數(shù)量（ht[0].used）
• 如果是擴(kuò)展操作，ht[1]的大小為 >= ht[0].used * 2的 2的冪次方
• 如果是收縮操作，ht[1]的大小為 >= ht[0].used 的 2的冪次方
• 2、將保存在ht[0]中的所有鍵值對(duì)rehash到ht[1]上：即重新計(jì)算key的hashValue以及indexValue，然后將鍵值對(duì)放到ht[1]的指定位置
• 3、當(dāng)ht[0]包含的所有鍵值對(duì)都遷移到ht[1]之后，ht[0]變?yōu)榭毡?，釋放ht[0]，將ht[1]置為ht[0]，在ht[1]重新分配一個(gè)空白的哈希表，為下一次rehash做準(zhǔn)備

漸進(jìn)式hash

rehash的動(dòng)作并不是一次性集中完成的，而是分多次漸進(jìn)完成。
如果哈希表中村的鍵值對(duì)數(shù)量很多，一次性將鍵值對(duì)全部rehash到ht[1]的計(jì)算量十分龐大，可能會(huì)導(dǎo)致服務(wù)器在一段時(shí)間內(nèi)停止服務(wù)。
漸進(jìn)式rehash采取分而治之的方法，將rehash鍵值對(duì)所需要的計(jì)算工作分?jǐn)偟矫看螌?duì)字典的CRUD操作上，從而避免了集中式rehash帶來的龐大計(jì)算量。
詳細(xì)步驟如下：
1、為ht[1]分配空間，讓字典同時(shí)持有ht[0]和ht[1]兩個(gè)哈希表
2、在字典中維護(hù)一個(gè)索引計(jì)數(shù)器：rehashidx，將值設(shè)置為0，表示rehash工作正式開始。
3、在rehash進(jìn)行期間，每次對(duì)字典的CRUD操作，程序除了執(zhí)行指定操作以外，順帶將ht[0]哈希表在rehashidx索引上的所有鍵值對(duì)rehash到ht[1]上，當(dāng)rehash操作完成后，程序?qū)ehashidx值++
4、重復(fù)迭代操作執(zhí)行后，ht[0]的數(shù)據(jù)全部rehash到ht[1]上，將rehashidx設(shè)為-1，表明rehash操作已經(jīng)完成

需要注意的地方
在rehash的過程中，對(duì)于字典的刪除、查找、更新操作會(huì)在兩個(gè)哈希表上執(zhí)行。如想要查找一個(gè)鍵，現(xiàn)在ht[0]中找，沒有找到再去ht[1]
對(duì)于insert操作來說，新添加到字典的鍵值對(duì)會(huì)一律保存到ht[1]中，不然還得多一次搬運(yùn)。

到此這篇關(guān)于Redis字典實(shí)現(xiàn)、Hash鍵沖突以及漸進(jìn)式rehash的文章就介紹到這了,更多相關(guān)Redis 漸進(jìn)式rehash內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！