淺析 Redis 資料結構 List 及其底層編碼方式

list 基本指令和介紹

Redis中的 List 類型與 Java中的 LinkedList類似，可以看做是一個雙向連結清單結構。既可以支援正向檢索也可以支援反向檢索。特征也與LinkedList類似：

• 有序
• 元素可以重複
• 插入和删除快
• 查詢速度一般

我們可以用 List 存儲一個有序資料，例如：朋友圈點贊清單，評論清單等。

List的常見指令有：

• LPUSH key element ... ：向清單左側插入一個或多個元素
• LPOP key：移除并傳回清單左側的第一個元素，沒有則傳回nil
• RPUSH key element ... ：向清單右側插入一個或多個元素
• RPOP key：移除并傳回清單右側的第一個元素
• LRANGE key star end：傳回一段角标範圍内的所有元素
• BLPOP和BRPOP：與LPOP和RPOP類似，隻不過在沒有元素時等待指定時間，而不是直接傳回nil

List 的底層編碼方式

為了實作可以從首、尾操作清單中的元素，并且保證查詢效率和降低記憶體占用，在 3.2 版本之前，Redis 采用 ZipList 和 LinkedList 來實作 List，當元素數量小于 512 并且元素大小小于 64 位元組時采用 ZipList 編碼，超過則采用 LinkedList 編碼。在 3.2 版本之後，Redis統一采用 QuickList 來實作 List。

下面我們來看看 ZipList 和 QuickList 的結構分别是怎樣的。

ZipList

ZipList 的結構

ZipList 是一種特殊的“雙端連結清單” ，由一系列特殊編碼的連續記憶體塊組成（類似于連結清單） 。可以在任意一端進行壓入/彈出操作, 并且該操作的時間複雜度為 O(1)。其結構如下圖所示，

各個成員變量如下：

• zlbytes，記錄整個壓縮清單占用記憶體位元組數；
• zltail，記錄壓縮清單「尾部」節點距離起始位址有多少位元組，也就是清單尾的偏移量；
• zllen，記錄壓縮清單包含的節點數量；
• entry , 壓縮清單包含的各個節點，節點的長度由節點儲存的内容決定。
• zlend，标記壓縮清單的結束點，固定值 0xFF（十進制255）。

在壓縮清單中，如果我們要查找定位第一個元素和最後一個元素，可以通過 zltail 直接定位，複雜度是 O(1)。而查找其他元素時，就沒有這麼高效了，隻能逐個查找，此時的複雜度就是 O(N) 了，是以壓縮清單不适合儲存過多的元素。

ZipListEntry

• ZipList 中的 Entry 并不像普通連結清單那樣記錄前後節點的指針，因為記錄兩個指針要占用16個位元組，浪費記憶體。而是采用下面的結構

• previous_entry_length：前一節點的長度，占1個或5個位元組。
• 如果前一節點的長度小于 254 位元組，則采用1個位元組來儲存這個長度值
• 如果前一節點的長度大于 254 位元組，則采用5個位元組來儲存這個長度值，第一個位元組為 0xf，後四個位元組才是真實長度資料
• encoding：編碼屬性，記錄 content 的資料類型（字元串還是整數）以及長度，占用1個、2個或5個位元組，詳見下一個 part -- Encoding 編碼
• contents：負責儲存節點的資料，可以是字元串或整數

Encoding 編碼

• ZipListEntry 中的 encoding 編碼分為字元串和整數兩種

字元串

• 如果encoding:是以“00”、“"01”或者“10”開頭，則證明 content 是字元串，根據字元串的長度大小，encoding 會使用 1 位元組/2位元組/5位元組的空間進行編碼，encoding 編碼的前兩個 bit 表示資料的類型，後續的其他 bit 辨別字元串資料的實際長度，即 data 的長度。

編碼	編碼長度	字元串大小
00pppppp
01pppppp	qqqqqqqq
10000000	qqqqqqqq

例如，我們要儲存字元串：“ab”和 “bc”

整數

• 如果 encoding 是以“11”開始，則證明 content 是整數，且 encoding 固定隻占用1個位元組。通過 encoding 确認了整數類型，就可以确認整數資料的實際大小了，比如如果 encoding 編碼确認了資料是 int16 整數，那麼 data 的長度就是 int16 的大小。

編碼	編碼長度	整數類型
11000000	1	int16_t（2 bytes）
11010000	1	int32_t（4 bytes）
11100000	1	int64_t（8 bytes）
11110000	1	24位有符整數(3 bytes)
11111110	1	8位有符整數(1 bytes)
1111xxxx	1	直接在xxxx位置儲存數值，範圍從0001~1101，減1後結果為實際值

例如，一個ZipList中包含兩個整數值：“2”和“5”

可以看到，ZipList 使用 previous_entry_length 來進行向前周遊的操作，而向後周遊使用 encoding的長度 + contents 的長度就可以實作，這導緻 ZipList 對非首尾節點的查詢操作時間複雜度達到 O(n)

ZipList 的連鎖更新問題

連鎖更新

壓縮清單除了查找複雜度高的問題，還有一個問題。

壓縮清單新增某個元素或修改某個元素時，如果空間不不夠，壓縮清單占用的記憶體空間就需要重新配置設定。而當新插入的元素較大時，可能會導緻後續元素的 prevlen 占用空間都發生變化，進而引起「連鎖更新」問題，導緻每個元素的空間都要重新配置設定，造成通路壓縮清單性能的下降。

前面提到，壓縮清單節點的 prevlen 屬性會根據前一個節點的長度進行不同的空間大小配置設定：

• 如果前一個節點的長度小于 254 位元組，那麼 prevlen 屬性需要用 1 位元組的空間來儲存這個長度值；
• 如果前一個節點的長度大于等于 254 位元組，那麼 prevlen 屬性需要用 5 位元組的空間來儲存這個長度值；

現在假設一個壓縮清單中有多個連續的、長度在 250～253 之間的節點，如下圖：

因為這些節點長度值小于 254 位元組，是以 prevlen 屬性需要用 1 位元組的空間來儲存這個長度值。

這時，如果将一個長度大于等于 254 位元組的新節點加入到壓縮清單的表頭節點，即新節點将成為 e1 的前置節點，如下圖：

因為 e1 節點的 prevlen 屬性隻有 1 個位元組大小，無法儲存新節點的長度，此時就需要對壓縮清單的空間重配置設定操作，并将 e1 節點的 prevlen 屬性從原來的 1 位元組大小擴充為 5 位元組大小。

多米諾牌的效應就此開始。

e1 原本的長度在 250～253 之間，因為剛才的擴充空間，此時 e1 的長度就大于等于 254 了，是以原本 e2 儲存 e1 的 prevlen 屬性也必須從 1 位元組擴充至 5 位元組大小。

正如擴充 e1 引發了對 e2 擴充一樣，擴充 e2 也會引發對 e3 的擴充，而擴充 e3 又會引發對 e4 的擴充.... 一直持續到結尾。

這種在特殊情況下産生的連續多次空間擴充操作就叫做「連鎖更新」，就像多米諾牌的效應一樣，第一張牌倒下了，推動了第二張牌倒下；第二張牌倒下，又推動了第三張牌倒下....，

壓縮清單的缺陷

空間擴充操作也就是重新配置設定記憶體，是以連鎖更新一旦發生，就會導緻壓縮清單占用的記憶體空間要多次重新配置設定，這就會直接影響到壓縮清單的通路性能。

是以說，雖然壓縮清單緊湊型的記憶體布局能節省記憶體開銷，但是如果儲存的元素數量增加了，或是元素變大了，會導緻記憶體重新配置設定，最糟糕的是會有「連鎖更新」的問題。

是以，壓縮清單隻會用于儲存的節點數量不多的場景，隻要節點數量足夠小，即使發生連鎖更新，也是能接受的。

雖說如此，Redis 針對壓縮清單在設計上的不足，在後來的版本中，新增設計了兩種資料結構：quicklist 和 listpack（這個資料結構會單獨開一篇文章）。這兩種資料結構的設計目标，就是盡可能地保持壓縮清單節省記憶體的優勢，同時解決壓縮清單的「連鎖更新」的問題。

QuickList

為什麼需要 QuickList

在 Redis 3.0 之前，List 對象的底層資料結構是雙向連結清單或者壓縮清單。然後在 Redis 3.2 的時候，List 對象的底層改由 quicklist 資料結構實作。

其實 Quicklist 就是「雙向連結清單 + 壓縮清單」組合，因為一個 quicklist 就是一個連結清單，而連結清單中的每個元素又是一個 ZipList。

在上文中中，我們提到壓縮清單存在一些不足之處，雖然壓縮清單是通過緊湊型的記憶體布局節省了記憶體開銷，但是因為它的結構設計，如果儲存的元素數量增加，或者元素變大了，壓縮清單會有「連鎖更新」的風險，一旦發生，會造成性能下降。而且， ZipList 對非首尾節點的查詢操作時間複雜度是 O(n) ，這在元素數量過多的情況下，同樣不可接受。

Quicklist 解決辦法，通過控制每個連結清單節點中的壓縮清單的大小或者元素個數，來規避連鎖更新的問題。因為壓縮清單元素越少或越小，連鎖更新帶來的影響就越小，對其進行周遊操作所需要的時間代價也變得可以接受，進而提供了更好的通路性能。

是以，QuickList 要做的事情就是

• 限制 ZipList 的長度和 entry 大小
• 通過連結清單的結構來管理每一個 ZipList 節點

QuickList 的結構是什麼樣的

從本質上來說，QuickList 是一個雙端清單，特殊之處在于，它的每一個節點是一個 ZipList。

在向 quicklist 添加一個元素的時候，不會像普通的連結清單那樣，直接建立一個連結清單節點。而是會檢查插入位置的壓縮清單是否能容納該元素，如果能容納就直接儲存到 quicklistNode 結構裡的壓縮清單，如果不能容納，才會建立一個新的 quicklistNode 結構。

QuickList

QuickList 的結構源碼如下：

c複制代碼typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned long len;          /* number of quicklistNodes */
    int fill : QL_FILL_BITS;              /* fill factor for individual nodes */
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;
           

這裡介紹一下幾個重要的變量的含義

• *quicklistNode head ：頭結點指針
• *quicklistNode tail ：尾節點指針
• unsigned long count ：節點中所有 entry 的數量之和
• unsigned long len ：節點數量
• int fill : QL_FILL_BITS ：ZipList 中的 entry 數量上限
• 為了避免 QuickList 中的每個 ZipList 中 entry 過多，Redis提供了一個配置項：list-max-ziplist-size 來限制，也即 QL_FILL_BITS 的值。
• 如果值為正，則代表 ZipList 的允許的 entry 個數的最大值
• 如果值為負，則代表ZipList的最大記憶體大小，分5種情況：（其預設值為 -2）
• -1：每個ZipList的記憶體占用不能超過4kb
• -2：每個ZipList的記憶體占用不能超過8kb
• -3：每個ZipList的記憶體占用不能超過16kb
• -4：每個ZipList的記憶體占用不能超過32kb
• -5：每個ZipList的記憶體占用不能超過64kb
• unsigned int compress : QL_COMP_BITS：首尾不壓縮的節點數量

QuickListNode

c複制代碼typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;
           

• *struct quicklistNode prev ：前一個節點指針
• *struct quicklistNode next ：後一個節點指針
• *unsigned char zl ：目前節點的 ZipList 指針
• unsigned int sz ：目前節點的 ZipList 大小
• unsigned int count : 16 ：目前節點的 ZipList entry 個數
• unsigned int encoding : 2 ：編碼方式 1：ZipList ；2：lzf 壓縮模式
• unsigned int container : 2 ：資料類型容器（預留）
• unsigned int recompress : 1 ：是否被解壓縮 1：被解壓了，需要重新壓縮

整體結構圖

原文連結：https://juejin.cn/post/7239923199609094202