主頁 > 知識庫 > Redis字典實現(xiàn)、Hash鍵沖突及漸進式rehash詳解

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

熱門標簽:宿遷便宜外呼系統(tǒng)平臺 魔獸2青云地圖標注 山東外呼銷售系統(tǒng)招商 十堰營銷電銷機器人哪家便宜 日本中國地圖標注 北京400電話辦理收費標準 貴州電銷卡外呼系統(tǒng) 鄭州人工智能電銷機器人系統(tǒng) 超呼電話機器人

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

Redis字典實現(xiàn)

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

typedef struct dictEntry
{
	// 鍵
	void *key;

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

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

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

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

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

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

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

字典

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

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

	// 哈希表
	dictht ht[2];

	// rehash 索引
	// 當rehash不在進行時, 值為-1
	int rehashidx;
} dict;

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

哈希算法

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

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

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

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

redis使用的是MurmurHash算法,優(yōu)點是:輸入的鍵是有規(guī)律的時候,算法仍然能給出很好的隨機分布性,計算速度也快。

解決hash沖突

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

rehash

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

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

為了維持負載因子在一個合理的范圍,程序會對哈希表的大小進行相應(yīng)的擴展或收縮,條件如下:

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

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

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

漸進式hash

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

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

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

您可能感興趣的文章:
  • redis中hash表內(nèi)容刪除的方法代碼
  • Python操作redis實例小結(jié)【String、Hash、List、Set等】
  • Redis String 類型和 Hash 類型學習筆記與總結(jié)
  • Redis教程(四):Hashes數(shù)據(jù)類型
  • SpringBoot+Redis實現(xiàn)數(shù)據(jù)字典的方法
  • python redis存入字典序列化存儲教程
  • redis中Hash字典操作的方法

標簽:北京 吉安 臺州 朝陽 江蘇 楊凌 果洛 大慶

巨人網(wǎng)絡(luò)通訊聲明:本文標題《Redis字典實現(xiàn)、Hash鍵沖突及漸進式rehash詳解》,本文關(guān)鍵詞  Redis,字典,實現(xiàn),Hash,鍵,沖突,;如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問題,煩請?zhí)峁┫嚓P(guān)信息告之我們,我們將及時溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò),涉及言論、版權(quán)與本站無關(guān)。
  • 相關(guān)文章
  • 下面列出與本文章《Redis字典實現(xiàn)、Hash鍵沖突及漸進式rehash詳解》相關(guān)的同類信息!
  • 本頁收集關(guān)于Redis字典實現(xiàn)、Hash鍵沖突及漸進式rehash詳解的相關(guān)信息資訊供網(wǎng)民參考!
  • 推薦文章