首頁 > 軟體

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操作結束

縮容

字典有擴容也有縮容,從字典中刪除key後,若字典中的元素個數與字典陣列大小滿足一定關係,會觸發縮容操作,縮絨條件是:

雜湊陣列長度大於預設值DICT_HT_INITIAL_SIZE (4),且節點數量 與 字典雜湊表數位大小的比例 小於10%

縮容後新陣列長度為hash表中元素個數

總結

以上為個人經驗,希望能給大家一個參考,也希望大家多多支援it145.com。


IT145.com E-mail:sddin#qq.com