Redis ziplist 壓縮列表的原始碼解析

2022-06-30 18:01:28

前言

相信對使用過 Redis 的人來說，資料型別 List 是不會陌生的吧。大多數人需要實現一個佇列時候，首選的就是 List 了。但是其實 Redis 的 List 型別有多種實現方式。這篇文章就是介紹其中一種實現 ziplist - 壓縮列表。

原始碼解讀

一如既往，關於 ziplist 的定義和實現還是放在一對檔案中，分別是 ziplist.h 和 ziplist.c。在 ziplist.c 檔案的頭部有著這麼一段註釋介紹什麼是 ziplist。

ziplist 是一個經過特殊編碼的雙向連結串列，旨在提高記憶體效率。它儲存字串和整數值，其中整數被編碼為實際整數而不是一系列字元。它允許在 O(1) 時間內在列表的任一側進行推播和彈出操作。但是，由於每個操作都需要重新分配 ziplist 使用的記憶體，因此實際複雜性與 ziplist 使用的記憶體量有關。

從這段話得到：對於不同的資料型別有著不同的編碼方式，理解為會對資料進行壓縮，從而達到減少記憶體使用的目的。但是隨著儲存的 value 資料級增加，使用 ziplist 所付出的代價也隨之增加。

ziplist 佈局

ziplist 是一個特殊雙向連結串列，不像普通的連結串列使用前後指標關聯在一起，它是儲存在連續記憶體上的。整體的結構佈局如下圖：

zlbytes: 32 位無符號整型，記錄 ziplist 整個結構體的佔用空間大小。當然了也包括 zlbytes 本身。這個結構有個很大的用處，就是當需要修改 ziplist 時候不需要遍歷即可知道其本身的大小。這個 SDS 中記錄字串的長度有相似之處，這些好的設計往往在平時的開發中可以採納一下。
zltail: 32 位無符號整型, 記錄整個 ziplist 中最後一個 entry 的偏移量。所以在尾部進行 POP 操作時候不需要先遍歷一次。
zllen: 16 位無符號整型, 記錄 entry 的數量，所以只能表示 2^16。但是 Redis 作了特殊的處理：當實體數超過 2^16 ,該值被固定為 2^16 - 1。所以這種時候要知道所有實體的數量就必須要遍歷整個結構了。
entry: 真正存資料的結構。
zlend: 8 位無符號整型, 固定為 255 。為 ziplist 的結束標識。

entry 節點

每個 entry 都包含兩條資訊的後設資料為字首。第一後設資料用來儲存前一個 entry 的長度，以便能夠從後向前遍歷列表。第二後設資料是表示 entry 的編碼形式。用來表示 entry 型別，整數或字串，在字串的情況下，它還表示字串有效的長度。

所以一個完整的 ziplist 是這樣儲存的：

prelen

記錄前一個 entry 的長度。若前一個 entry 的長度小於 254 , 則使用 1 個位元組的 8 位無符號整數來表示。

若前一個 entry 長度大於等於 254，則使用 5 個位元組來表示。第 1 個位元組固定為 254 (FE) 作為標識，剩餘 4 位元組則用來表示前一個 entry 的實際大小。

所以兩種情況下的 entry 結構如下所示：

1. 前一個 entry 大小不超過 253。
<prevlen from 0 to 253> <encoding> <entry>
2. 前一個 entry 大小超過 253。
0xFE <4 bytes unsigned little endian prevlen> <encoding> <entry>

encoding 編碼

entry 的編碼欄位取決於具體值的內容，分為字串、數位兩種型別單獨處理。

一、當 entry 是字串時，有 3 種編碼方式。編碼第 1 個位元組的前 2 位將儲存用於儲存字串長度的編碼型別，後面是字串的實際長度。

1. 長度小於或等於 63 位元組（6 位）的字串值。 「pppppp」表示無符號的 6 位資料長度。
|00pppppp| - 1 byte
2. 長度小於或等於 16383 位元組（14 位）的字串值。14 位的資料採用  big endian 儲存。
big endian 是一種位元組序方式，有Little-Endian、Big-Endian兩種。
|01pppppp|qqqqqqqq| - 2 bytes
3. 長度大於或等於 16384 位元組的字串值。
採用 big endian 儲存且可表示的字串長度最大2^32-1，所以第一個位元組沒有用到，所以低6位沒有用，所以都是0。
|10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 bytes

二、當 entry 是整數時，有 6 種編碼方式。前 2 位都固定為 1，接下來的 2 位用於指定將在此檔頭後儲存哪種型別的整數。

與 ziplist 檔頭一樣，所有整數都以 Little-Endian 序表示，即使此程式碼是在 Big-Endian 系統中編譯的。

1. 整數編碼為 int16_t（2 位元組）。
|11000000| - 3 bytes
2. 整數編碼為int32_t（4個位元組）。
|11010000| - 5 bytes
3. 整數編碼為 int64_t（8 位元組）。
|11100000| - 9 bytes
4. 整數編碼為24位元帶符號（3個位元組）。
|11110000| - 4 bytes
5. 整數編碼為 8 位有符號（1 位元組）。
|11111110| - 2 bytes
6. 0到12的無符號整數。編碼後的值實際上是1到13，因為0000和1111不能用，所以要從編碼後的4位元值中減去1才能得到正確的值。
|1111xxxx| - (with xxxx between 0001 and 1101) immediate 4 bit integer

三、結尾編碼標識

1. 表示 ziplist 結尾的標識。
|11111111|

總結

ziplist 為了節省記憶體，採用了緊湊的連續儲存。所以在修改操作下並不能像一般的連結串列那麼容易，需要從新分配新的記憶體，然後複製到新的空間。
ziplist 是一個雙向連結串列，可以在時間複雜度為O(1)從下頭部、尾部進行pop或push。
可能會出現連鎖更新現象。

其實使用中並沒有直接操作這種資料結構，但是可以設定何種情況下使用它。可以在 Redis 的組態檔中進行設定。

如有以下可選設定項：

hash-max-ziplist-entries：hash 型別元素數量超過指定資料後時候。使用 hash 儲存，否則使用壓縮表。
hash-max-ziplist-value： hash 型別元素長度超過指定資料後時候。使用 hash 儲存，否則使用壓縮連結串列。
zset-max-ziplist-entries：zset 型別壓縮列表 ziplist 最大限制元素數。超過指定值將會使用跳錶 skiplist + dict 來儲存。
zset-max-ziplist-value：set 型別壓縮列表 ziplist 最大限制大小。超過指定將會使用跳錶 skiplist+dict 來儲存。

到此這篇關於Redis ziplist 壓縮列表的原始碼解析的文章就介紹到這了,更多相關Redis ziplist 壓縮列表內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！