redis中hash資料結構及說明

2023-01-20 14:02:18

hash的資料結構

hash底層資料結構的實現包括兩種：ziplist和字典當
儲存的所有鍵值對字串長度小於 64 位元組並且鍵值對數量小於 512 時使用ziplist ，否則使用字典的方式

ziplist底層實現

ziplist是為了提高儲存效率而設計的一種特殊編碼的雙向連結串列。它可以儲存字串或者整數，儲存整數時是採用整數的二進位制而不是字串形式儲存。

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

但是因為每次修改操作都需要重新分配ziplist的記憶體，所以實際複雜度和ziplist的記憶體使用量相關

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

zlbytes：表示整個ziplist所佔的空間大小，佔4個位元組
zltail：壓縮列表尾元素相對於壓縮列表起始地址的偏移量，佔4個位元組
zllen：壓縮列表的元素數目，佔兩個位元組；那麼當壓縮列表的元素數目超過(2^16)-1怎麼處理呢？此時通過zllen欄位無法獲得壓縮列表的元素數目，必須遍歷整個壓縮列表才能獲取到元素數目
zlend：壓縮列表的結尾，佔一個位元組，恆為0xFF（255）
entry：壓縮列表儲存的元素，可以為位元組陣列或者整數

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

previous_entry_length：記錄前一個節點的長度

該屬性根據前一個節點的大小不同可以是1個位元組或者5個位元組；如果數值小於254，那就只用一個位元組來表示長度，如果長度大於等於254就用5個位元組，第一個位元組是固定值254(FE)來標識這是個特殊的資料，剩下的4個位元組來表示實際的長度

為什麼要這麼設計？

壓縮列表目的是為了儘可能的節省儲存空間，資料進行緊鄰儲存在一塊連續的記憶體區域中；壓縮表中元素的長度的是不同的，且為了減少儲存空間，並沒有儲存前後節點的指標，無法通過後退指標來找到上一個元素，而通過儲存上一個節點的長度，用當前的地址減去這個長度，就可以很容易的獲取到了上一個節點的位置，通過一個一個節點向前回溯，來達到從表尾往表頭遍歷的操作

encoding：資料的編碼形式（字串還是數位，長度是多少）
content：實際儲存的資料

修改操作耗費效能：ziplist在記憶體中是高度緊湊的連續儲存，這意味著它對修改並不友好，如果要對ziplist做修改類的操作，那就需重新分配新的記憶體來儲存新的ziplist，代價很大

ziplist其實是一個邏輯上的雙向連結串列，可以快速找到頭節點和尾節點，然後每個節點(entry)中也包含指向前/後節點的"指標"，但作者為了將記憶體節省到極致，摒棄了傳統的連結串列設計(前後指標需要16位元組的空間，而且會導致記憶體碎片化嚴重)，設計出了記憶體非常緊湊的儲存格式。

記憶體是省下來了，但操作複雜性也更新的複雜度上來了

字典

底層實現

字典（dict）：其中包含長度為2的雜湊表陣列dictht，rehashIdx(預設-1)如果為-1說明當前沒有擴容，如果不為 -1 則表示正在進行擴容，記錄了原hash表需rehash的陣列下標

hash表陣列中，ht[0] 在第一次往字典中新增鍵值時分配記憶體空間，而另一個 ht[1] 將會在hash表中陣列擴容/縮容才會進行空間分配

hash表(dictht)：字典dictht陣列元素，其中包括了

1 資料 dictEntry 型別的陣列，每個陣列的 item 可能都指向一個連結串列

2 陣列長度 size

3 sizemask 等於 size - 1

4 當前 dictEntry 陣列中包含總共多少節點

hash表陣列中元素(dictEntry)：真正的資料節點，包括 key、value 和 next 節點

整體結構如下所示：

擴容

擴容時機：在dict->rehashidx == -1 , 也就是字典沒有正在進行擴容/縮容的前提下，以下三種情況下對雜湊表進行擴容並標記 dict->rehashidx 欄位為0，且擴充套件的雜湊表的陣列大小是第一個hash表長度的 2倍

字典已使用節點數和陣列大小之間的比率至少為 1：1，並且 dict_can_resize 為true
已使用節點數和字典大小之間的比率超過 dict_force_resize_ratio,該值預設為5
雜湊表剛初始化完，是個空表，給雜湊陣列設定預設大小 DICT_HT_INITIAL_SIZE （4）

擴容方式：為ht[1]分配長度為ht[0]2倍長度，rehashIdx設定為0表示正在進行擴容rehash，採取漸進式rehash

redis對一個字典的rehash操作，不是一次性把該字典 dict->ht[0] 雜湊表上所有雜湊陣列裡的雜湊陣列元素全部重新雜湊到 dict->ht[1]

而是將全部的rehash操作分散到對該字典操作的各個命令上了，每次進行"一步"雜湊操作(增加k/v，刪除k/v，查詢key，隨機返回key)

下標從dict->rehashidx開始，在 dict->ht[0].table 陣列中找到第一個不為NULL的項
將該項連結串列上的所有元素全部hash對映到 ditct->ht[1] 上
每重新對映一個元素， dict->ht[0].used --, dict->ht[1].used ++
該項連結串列處理完後，將 dict->rehashidx ++

如果 dict->ht[0].used == 0，說明 dict->ht[0]中的元素已全部rehash到dict->ht[1],釋放dict->ht[0].table 陣列，設定 dict->ht[0] = dict->ht[1]，重置 dict->ht[1]的欄位，設定 dict->rehashidx = -1，rehash操作結束