快捷導(dǎo)航

redis中hash數(shù)據(jù)結(jié)構(gòu)及說(shuō)明

更新時(shí)間：2023年01月18日 15:08:35 作者：酒劍隨馬@

這篇文章主要介紹了redis中hash數(shù)據(jù)結(jié)構(gòu)及說(shuō)明，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教

hash的數(shù)據(jù)結(jié)構(gòu)

hash底層數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)包括兩種：ziplist和字典當(dāng)
保存的所有鍵值對(duì)字符串長(zhǎng)度小于 64 字節(jié)并且鍵值對(duì)數(shù)量小于 512 時(shí)使用ziplist ，否則使用字典的方式

ziplist底層實(shí)現(xiàn)

ziplist是為了提高存儲(chǔ)效率而設(shè)計(jì)的一種特殊編碼的雙向鏈表。它可以存儲(chǔ)字符串或者整數(shù)，存儲(chǔ)整數(shù)時(shí)是采用整數(shù)的二進(jìn)制而不是字符串形式存儲(chǔ)。

他能在O(1)的時(shí)間復(fù)雜度下完成list兩端的push和pop操作。

但是因?yàn)槊看涡薷牟僮鞫夹枰匦路峙鋤iplist的內(nèi)存，所以實(shí)際復(fù)雜度和ziplist的內(nèi)存使用量相關(guān)

ziplist 中包含有zlbytes、zltail、zllen、entry、zlend等屬性

zlbytes：表示整個(gè)ziplist所占的空間大小，占4個(gè)字節(jié)
zltail：壓縮列表尾元素相對(duì)于壓縮列表起始地址的偏移量，占4個(gè)字節(jié)
zllen：壓縮列表的元素?cái)?shù)目，占兩個(gè)字節(jié)；那么當(dāng)壓縮列表的元素?cái)?shù)目超過(guò)(2^16)-1怎么處理呢？此時(shí)通過(guò)zllen字段無(wú)法獲得壓縮列表的元素?cái)?shù)目，必須遍歷整個(gè)壓縮列表才能獲取到元素?cái)?shù)目
zlend：壓縮列表的結(jié)尾，占一個(gè)字節(jié)，恒為0xFF（255）
entry：壓縮列表存儲(chǔ)的元素，可以為字節(jié)數(shù)組或者整數(shù)

entry 中包含有previous_entry_length、encoding、content等屬性

previous_entry_length：記錄前一個(gè)節(jié)點(diǎn)的長(zhǎng)度

該屬性根據(jù)前一個(gè)節(jié)點(diǎn)的大小不同可以是1個(gè)字節(jié)或者5個(gè)字節(jié)；如果數(shù)值小于254，那就只用一個(gè)字節(jié)來(lái)表示長(zhǎng)度，如果長(zhǎng)度大于等于254就用5個(gè)字節(jié)，第一個(gè)字節(jié)是固定值254(FE)來(lái)標(biāo)識(shí)這是個(gè)特殊的數(shù)據(jù)，剩下的4個(gè)字節(jié)來(lái)表示實(shí)際的長(zhǎng)度

為什么要這么設(shè)計(jì)？

壓縮列表目的是為了盡可能的節(jié)省存儲(chǔ)空間，數(shù)據(jù)進(jìn)行緊鄰存儲(chǔ)在一塊連續(xù)的內(nèi)存區(qū)域中；壓縮表中元素的長(zhǎng)度的是不同的，且為了減少存儲(chǔ)空間，并沒(méi)有保存前后節(jié)點(diǎn)的指針，無(wú)法通過(guò)后退指針來(lái)找到上一個(gè)元素，而通過(guò)保存上一個(gè)節(jié)點(diǎn)的長(zhǎng)度，用當(dāng)前的地址減去這個(gè)長(zhǎng)度，就可以很容易的獲取到了上一個(gè)節(jié)點(diǎn)的位置，通過(guò)一個(gè)一個(gè)節(jié)點(diǎn)向前回溯，來(lái)達(dá)到從表尾往表頭遍歷的操作

encoding：數(shù)據(jù)的編碼形式（字符串還是數(shù)字，長(zhǎng)度是多少）
content：實(shí)際存儲(chǔ)的數(shù)據(jù)

修改操作耗費(fèi)性能：ziplist在內(nèi)存中是高度緊湊的連續(xù)存儲(chǔ)，這意味著它對(duì)修改并不友好，如果要對(duì)ziplist做修改類(lèi)的操作，那就需重新分配新的內(nèi)存來(lái)存儲(chǔ)新的ziplist，代價(jià)很大

ziplist其實(shí)是一個(gè)邏輯上的雙向鏈表，可以快速找到頭節(jié)點(diǎn)和尾節(jié)點(diǎn)，然后每個(gè)節(jié)點(diǎn)(entry)中也包含指向前/后節(jié)點(diǎn)的"指針"，但作者為了將內(nèi)存節(jié)省到極致，摒棄了傳統(tǒng)的鏈表設(shè)計(jì)(前后指針需要16字節(jié)的空間，而且會(huì)導(dǎo)致內(nèi)存碎片化嚴(yán)重)，設(shè)計(jì)出了內(nèi)存非常緊湊的存儲(chǔ)格式。

內(nèi)存是省下來(lái)了，但操作復(fù)雜性也更新的復(fù)雜度上來(lái)了

字典

底層實(shí)現(xiàn)

字典（dict）：其中包含長(zhǎng)度為2的哈希表數(shù)組dictht，rehashIdx(默認(rèn)-1)如果為-1說(shuō)明當(dāng)前沒(méi)有擴(kuò)容，如果不為 -1 則表示正在進(jìn)行擴(kuò)容，記錄了原h(huán)ash表需rehash的數(shù)組下標(biāo)

hash表數(shù)組中，ht[0] 在第一次往字典中添加鍵值時(shí)分配內(nèi)存空間，而另一個(gè) ht[1] 將會(huì)在hash表中數(shù)組擴(kuò)容/縮容才會(huì)進(jìn)行空間分配

hash表(dictht)：字典dictht數(shù)組元素，其中包括了

1 數(shù)據(jù) dictEntry 類(lèi)型的數(shù)組，每個(gè)數(shù)組的 item 可能都指向一個(gè)鏈表

2 數(shù)組長(zhǎng)度 size

3 sizemask 等于 size - 1

4 當(dāng)前 dictEntry 數(shù)組中包含總共多少節(jié)點(diǎn)

hash表數(shù)組中元素(dictEntry)：真正的數(shù)據(jù)節(jié)點(diǎn)，包括 key、value 和 next 節(jié)點(diǎn)

整體結(jié)構(gòu)如下所示：

擴(kuò)容

擴(kuò)容時(shí)機(jī)：在dict->rehashidx == -1 , 也就是字典沒(méi)有正在進(jìn)行擴(kuò)容/縮容的前提下，以下三種情況下對(duì)哈希表進(jìn)行擴(kuò)容并標(biāo)記 dict->rehashidx 字段為0，且擴(kuò)展的哈希表的數(shù)組大小是第一個(gè)hash表長(zhǎng)度的 2倍

字典已使用節(jié)點(diǎn)數(shù)和數(shù)組大小之間的比率至少為 1：1，并且 dict_can_resize 為true
已使用節(jié)點(diǎn)數(shù)和字典大小之間的比率超過(guò) dict_force_resize_ratio,該值默認(rèn)為5
哈希表剛初始化完，是個(gè)空表，給哈希數(shù)組設(shè)置默認(rèn)大小 DICT_HT_INITIAL_SIZE （4）

擴(kuò)容方式：為ht[1]分配長(zhǎng)度為ht[0]2倍長(zhǎng)度，rehashIdx設(shè)置為0表示正在進(jìn)行擴(kuò)容rehash，采取漸進(jìn)式rehash

redis對(duì)一個(gè)字典的rehash操作，不是一次性把該字典 dict->ht[0] 哈希表上所有哈希數(shù)組里的哈希數(shù)組元素全部重新哈希到 dict->ht[1]

而是將全部的rehash操作分散到對(duì)該字典操作的各個(gè)命令上了，每次進(jìn)行"一步"哈希操作(增加k/v，刪除k/v，查找key，隨機(jī)返回key)

下標(biāo)從dict->rehashidx開(kāi)始，在 dict->ht[0].table 數(shù)組中找到第一個(gè)不為NULL的項(xiàng)
將該項(xiàng)鏈表上的所有元素全部hash映射到 ditct->ht[1] 上
每重新映射一個(gè)元素， dict->ht[0].used --, dict->ht[1].used ++
該項(xiàng)鏈表處理完后，將 dict->rehashidx ++

如果 dict->ht[0].used == 0，說(shuō)明 dict->ht[0]中的元素已全部rehash到dict->ht[1],釋放dict->ht[0].table 數(shù)組，設(shè)置 dict->ht[0] = dict->ht[1]，重置 dict->ht[1]的字段，設(shè)置 dict->rehashidx = -1，rehash操作結(jié)束