首頁 > 軟體

Redis底層資料結構之dict、ziplist、quicklist詳解

2021-09-27 13:03:37

此前我們學習了常見的Reids資料型別,這些資料型別都需要底層的資料結構的支援,現在我們來看看Redis常見的底層資料結構:dict、ziplist、quicklist。

1 Redis dict

dict就是「字典」的意思,它是Redis中的一種使用的非常多的底層的資料結構,除了hash會使用欄位之外,整個 Redis 資料庫的所有 key 和 value 也組成了一個全域性字典dict,還有帶過期時間的 key 也是一個字典expires(儲存在 RedisDb 資料結構中)。

Redis 中的字典相當於 JDK1.7中的 HashMap,內部實現也差不多類似,都是通過 「陣列 + 連結串列」 的鏈地址法來解決部分雜湊衝突,同時這樣的結構也吸收了兩種不同資料結構的優點。

和JDK1.7中的hashmap不同的是,Reids的字典結構內部包含兩個hashtable變數,通常情況下只有一個hashtable有值,另一個為空表,但是在字典擴容縮容時,需要分配新的hashtable,並且使用了一種叫做漸進式搬遷(rehash)的機制來提高dict的縮放效率,這時候兩個hashtable分別儲存舊的和新的 hashtable,待搬遷結束後,舊的將被刪除,新的 hashtable 取而代之。

1.1 擴縮容的條件

正常情況下,當 hash 表中元素的個數等於陣列的長度時,就會開始擴容,擴容的新陣列是原陣列大小的2倍。不過如果 Redis 正在做 BGSAVE或者BGREWRITEAOF(持久化),為了減少記憶體佔用,Redis 儘量不去擴容,但是如果 hash 表非常滿了,達到了陣列長度的 5 倍了,這個時候就會強制擴容。

當 hash 表因為元素逐漸被刪除變得越來越稀疏時,Redis 會對 hash 表進行縮容來減少hash表的第一維陣列空間佔用。所用的條件是:元素個數低於陣列長度的10%,縮容不會考慮 Redis 是否在做 bgsave。

1.2 漸進式rehash操作

在擴容和收縮的時候,如果雜湊字典中有很多元素,一次性將這些鍵從ht0(正在使用的hashtable)全部rehash到ht1(另一個空的hashtable)的話,由於Redis是單執行緒模型,那麼可能會導致伺服器在一段時間內停止服務。所以,採用漸進式rehash的方式,資料的遷移並不是一步完成的,因此dict內部還有一個rehashidx屬性用來控制rehash,預設定為-1。

  • 為ht[1]分配空間,讓字典同時持有ht[0]和ht[1]兩個雜湊表。
  • 將rehashindex的值設定為0,表示rehash工作正式開始。
  • 在rehash期間,每次對字典執行增刪改查操作時,程式除了執行指定的操作以外,還會順帶將ht[0]雜湊表在rehashindex索引上的所有鍵值對rehash到ht[1],當一次rehash工作完成以後,rehashindex的值+1。
  • 隨著字典操作的不斷執行,最終會在某一時間段上ht[0]的所有鍵值對都會被rehash到ht[1],將rehashindex的值設定為-1,表示rehash操作結束。
  • 把ht[1]設定為ht[0],並重新在ht[1]上新建一個空表,為下次rehash做準備。

漸進式rehash採用的是一種分而治之的方式,它以bucket(桶)為基本單位進行漸進式的資料遷移,每步完成一個bucket的遷移,直至所有資料遷移完畢。這種方式將rehash的操作分攤在每一個的存取中,避免集中式rehash而帶來的龐大計算量。

在漸進式rehash的過程中,如果有刪除、修改、查詢操作,則會在兩個雜湊表ht[0]和ht[1]上進行,先操作ht[0],如果沒找到,再操作ht[1],則新增的資料則會被儲存在ht[1]中,ht[0]中包含的鍵值對數量會只減不增,並隨著 rehash 操作的執行而最終變成空表。

2 Redis ziplist

ziplist又名壓縮列表,見其名知其意,這種資料結構就比較節省記憶體空間,Redis中對於list(3.2版本之前)、hash、zset型別的資料,如果元素較少,並且每個列表項要麼就是小整數值,要麼就是長度比較短的字串,那麼Redis就會使用壓縮列表來儲存。

ziplist本身可以有序也可以無序。當作為list(3.2版本之前)和hash的底層實現時,節點之間沒有順序;當作為zset的底層實現時,節點之間會按照score大小順序排列,元素和score被分別儲存為兩個節點,元素在前,score在後。

ziplist的節省空間是相較於陣列而言的,ziplist和陣列一樣同樣採用一整塊連續的空間來儲存資料,陣列在實際儲存時,每一個元素所佔的實際大小是一樣的,並且是以最大的元素的大小為準,這樣就能進行快速的根據索引存取,而ziplist則允許每一個entry節點(對於陣列中的元素)所佔的實際大小不同,另外,節點之間沒有儲存前驅和後繼的指標,以此節約空間。

ziplist支援正序或者倒序的遍歷,往ziplist裡插入一個entry 時間複雜度 平均:O(n),最壞:O(n²),從ziplist裡刪除一個entry 時間複雜度 平均:O(n), 最壞:O(n²)。最壞為O(n²)是因為Redis連鎖更新導致的,但這種情況出現的概率不高。

ziplist和陣列類似,刪除和新增節點都可能涉及到其他節點位置的移動,因此只適用於元素資料量較少,並且每個列表項要麼就是小整數值,要麼就是長度比較短的字串的情況。

2.1 ziplist結構

Redis的ziplist採用一系列特殊編碼的連續記憶體塊,一個壓縮列表出了在頭部包含一些整體資訊之外,剩下的部分可以包含任意多個節點(entry)。

整體結構如下:

  1. zlbytes:32位元無符號整數,表示ziplist的整體長度(位元組)。在對ziplist重新分配記憶體或者計算zlend的位置時有用。
  2. zltail:32位元無符號整數,最後一個節點距離頭部的偏移量,通過該偏移量程式無需遍歷整個ziplist即可確定尾節點的地址,在反向遍歷ziplist或者pop尾部節點的時候很有用。
  3. zllen:16位元無符號整數,ziplist的節點(entry)個數。當小於值小於65535時,該值時準確的,等於65535(16位元的最大值)時,需要遍歷整個連結串列才能得到真實節點數量。
  4. entry:ziplist中的資料節點,長度不固定,自己的長度儲存在每一個entry節點內部。
  5. zlend:8位元無符號整數固定值為0xFF,用於標記ziplist的結尾。

 2.2 entry結構

ziplist的entry用於儲存正數或者字串(位元組陣列),且每個節點的長度都是不一樣的,因此節點的長度只能由這個節點自己來儲存,Redis的ziplist中,entry由三部分構成:

  • previous_entry_length:8bit或者40bit,用於記錄上一個節點的長度(位元組),為了方便反向遍歷ziplist。
  • encoding:當前節點資料的編碼規則,即data屬性的資料型別以及長度。
  • content:當前節點的值,可以是數位或字串(位元組陣列)。

previous_entry_length用於記錄上一個節點的長度(位元組),為了方便反向遍歷ziplist,其本身的長度可能是8bit或者40bit。

  1. 如果前一節點的長度小於254位元組,那麼prevlengh屬性的長度為1位元組,前一節點的長度就儲存在這一個位元組裡面,這樣更加節約記憶體。
  2. 如果前一節點的長度大於等於254位元組,那麼prevlengh屬性的總長度為5位元組,第一位元組被固定設定為0xFE(十進位制值254),而之後的四個位元組則用於儲存前一節點的長度。
  3. 第二種情況下,第一個位元組254而不用255(0xFF)是因為255是zlend的值,它用於判斷ziplist是否到達尾部。

content表示當前節點的值,可以是數位或字串(位元組陣列),encoding 表示當前節點資料的編碼規則,即data屬性的資料型別以及長度,其中encoding其中高2位用來區分整數節點和字串節點(高2位為11時是整數節點),根據值的型別不同,一共有九種編碼型別。

位元組陣列的encoding型別3種,encoding有8位元、16位元、40位三種長度,context的長度也是變化的:

encoding長度 encoding格式 content格式
8bit 高兩位固定00,後6位表示位元組陣列的長度 長度小於等於63(2^6-1)位元組的位元組陣列
16bit 高兩位固定01,後14位元表示位元組陣列的長度。 長度小於等於16383(2^14-1)位元組的位元組陣列
40bit 高兩位固定10,後38位元表示位元組陣列的長度。 長度小於等於4294967295(2^32-1)位元組的位元組陣列

整數值的encoding型別6種,固定長度8位元,高兩位固定11,表示整數,因此需要後兩位來表示不同的整數型別。整數型別的content的長度雖然也是可變的,但固定範圍內的整數長度一樣,也就是說content長度只有固定的幾種。

encoding長度 encoding格式 content格式
1bit 1111xxxx,後四位用來表示content。 4bit長的無符號整數,即介於0至12之間,沒有content欄位,在encoding中儲存。
11111110 8bit,有符號整數。
11000000 16bit,有符號整數。
11110000 24bit,有符號整數。
11010000 32bit,有符號整數。
11100000 64bit,有符號整數。

3 Redis quicklist

Redis 的list在3.2版本之前在元素較少時實際上是採用ziplist結構,當連結串列entry資料超過512、或單個value 長度超過64,底層就會轉化成linkedlist編碼,而Redis3.2及其之後則採用quicklist結構代替ziplist和linkedlist。

ziplist儲存在一段連續的記憶體上,所以儲存和查詢效率很高,順序IO存取。但是,它不利於修改操作,插入和刪除操作需要頻繁的申請和釋放記憶體。特別是當ziplist長度很長的時候,一次realloc可能會導致大批次的資料拷貝,適用於儲存整數和短字串。

雙向連結串列linkedlist便於在表的兩端進行push和pop操作,在插入節點上覆雜度很低,但是它的記憶體開銷比較大。首先,它在每個節點上除了要儲存資料之外,還要額外儲存兩個prev 和 next指標(64 位元運算系統佔用 8 個位元組);其次,雙向連結串列的各個節點是單獨的記憶體塊,地址不連續,隨機IO存取,節點多了容易產生記憶體碎片,影響記憶體管理效率。

quickList將 linkedList 按段切分,每一段使用 zipList 來緊湊儲存,多個 zipList 之間使用雙向指標串接起來。

首先quickList就是一個標準的雙向連結串列的設定,有head 和tail節點,每個節點是一個quicklistNode節點,包含prev和next指標,內部還包含一個ziplist,使用ziplist來儲存資料,而ziplist實際上含有多個entry節點,儲存著資料。相當與一個quicklistNode節點儲存的是一片資料,而不再是一個資料。

quickList將二者的優點結合起來,在宏觀上是一個雙向連結串列結構,插入、刪除quicklistNode節點的成本很低,不需要移動其他節點的位置,而在微觀上,每一個quicklistNode節點又是一個個的ziplist,內部包含多個資料,ziplist記憶體連續,減少了記憶體碎片,同時由於每一個ziplist不是很大(大小可以設定),因此插入和刪除操作不會進行大量的資料移動。

相關文章:

https://redis.io/topics/data-types

https://redis.io/topics/data-types-intro

到此這篇關於Redis的底層資料結構之dict、ziplist、quicklist詳解的文章就介紹到這了,更多相關Redis底層資料結構內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com!


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