Redis List 底層三種數據結構原理剖析

1. Redis List 是什麼

作爲 Java 開發者的你，看到這個詞並不陌生。在 Java 開發中幾乎每天都會使用這個數據結構。

Redis 的 List 與 Java 中的 LinkedList 類似，是一種線性的有序結構，可以按照元素被推入列表中的順序來存儲元素，能滿足先進先出的需求，這些元素既可以是文字數據，又可以是二進制數據。

你可以把他當做隊列、棧來使用。

2. 修煉心法

我叫 Redis，在 C 語言中，並沒有現成的鏈表結構，所以 antirez 爲我專門設計了一套實現方式。

關於 List 類型的底層數據結構，可謂英雄輩出，antirez 大佬一直在優化，創造了多種數據結構來保存。

從一開始早期版本使用 **linkedlist（雙端列表）**和 **ziplist（壓縮列表）**作爲 List 的底層實現，到 Redis 3.2 引入了由 linkedlist + ziplist 組成的 quicklist，再到 7.0 版本的時候使用 listpack 取代 ziplist。

MySQL：“爲何弄了這麼多數據結構呀？”

antirez 所做的這一切都是爲了在內存空間開銷與訪問性能之間做取捨和平衡，跟着我去喫透每個類型的設計思想和不足，你就明白了。

linkedlist（雙端列表）

在 Redis 3.2 版本之前，List 的底層數據結構由 linkedlist 或者 ziplist 實現，優先使用 ziplist 存儲。

當列表對象滿足以下兩個條件的時候，List 將使用 ziplist 存儲，否則使用 linkedlist。

• List 的每個元素的佔用的字節小於 64 字節。

• List 的元素數量小於 512 個。

鏈表的節點使用 adlist.h/listNode結構來表示。

typedef struct listNode {
    // 前驅節點
    struct listNode *prev;
    // 後驅節點
    struct listNode *next;
    // 指向節點的值
    void *value;
} listNode;

listNode 之間通過 prev 和 next 指針組成雙端鏈表。除此之外，我還提供了 adlist.h/list 結構提供了頭指針 head、尾指針 tail 以及一些實現多態的特定函數。

typedef struct list {
    // 頭指針
    listNode *head;
    // 尾指針
    listNode *tail;
    // 節點值的複製函數
    void *(*dup)(void *ptr);
    // 節點值釋放函數
    void (*free)(void *ptr);
    // 節點值比對是否相等
    int (*match)(void *ptr, void *key);
    // 鏈表的節點數量
    unsigned long len;
} list;

linkedlist 的結構如圖 2-5 所示。

圖 2-5

Redis 的鏈表實現的特性總結如下。

• 雙端：鏈表節點帶有 prev 和 next 指針，獲取某個節點的前置節點和後繼節點的複雜度都是 O(1)。

• 無環：表頭節點的 prev 指針和尾節點的 next 指針都指向 NULL，對鏈表的訪問以 NULL 爲結束。

• 帶表頭指針和表尾指針：通過 list 結構的 head 指針和 tail 指針，程序獲取鏈表的頭節點和尾節點的複雜度爲 O(1)。

• 使用 list 結構的 len 屬性來對記錄節點數量，獲取鏈表中節點數量的複雜度爲 O(1)。

MySQL：“看起來沒啥問題呀，爲啥還要 ziplist 呢？”

你知道的，我在追求快和節省內存的方向上無所不及，有兩個原因導致了 ziplist 的誕生。

• 普通的 linkedlist 有 prev、next 兩個指針，當存儲數據很小的情況下，指針佔用的空間會超過數據佔用的空間，這就離譜了，是可忍孰不可忍。

• linkedlist 是鏈表結構，在內存中不是連續的，遍歷的效率低下。

ziplist（壓縮列表）

爲了解決上面兩個問題，antirez 創造了 ziplist 壓縮列表，是一種內存緊湊的數據結構，佔用一塊連續的內存空間，提升內存使用率。

當一個列表只有少量數據的時候，並且每個列表項要麼是小整數值，要麼就是長度比較短的字符串，那麼我就會使用 ziplist 來做 List 的底層實現。

ziplist 中可以包含多個 entry 節點，每個節點可以存放整數或者字符串，結構如圖 2-6 所示。

圖 2-6

• zlbytes，佔用 4 個字節，記錄了整個 ziplist 佔用的總字節數。

• zltail，佔用 4 個字節，指向最後一個 entry 偏移量，用於快速定位最後一個 entry。

• zllen，佔用 2 字節，記錄 entry 總數。

• entry，列表元素。

• zlend，ziplist 結束標誌，佔用 1 字節，值等於 255。

因爲 ziplist 頭尾元數據的大小是固定的，並且在 ziplist 頭部 zllen 記錄了最後一個元素的位置，所以，當在 ziplist 中查找第一個或最後一個元素的時候，能以 O(1) 時間複雜度找到。

而查找中間元素時，只能從列表頭或者列表尾遍歷，時間複雜度就是 O(N)。

接下來看真正存儲數據的 entry 結構長啥樣。

圖 2-7

正常來說有三部分構成 <prevlen> <encoding> <entry-data>。

prevlen

記錄前一個 entry 佔用字節數，能實現逆序遍歷就是靠這個字段確定往前移動多少字節拿到上一個 entry 首地址。

這部分會根據上一個 entry 的長度進行變長編碼（爲了節省內存操碎了心），變長方式如下。

• 前一個 entry 的字節大小小於 254（255 用於 zlend），prevlen 長度爲 1 字節，值等於上一個 entry 的長度。

• 前一個 entry 的字節大小大於等於 254，prevlen 佔用 5 字節，第一個字節設置爲 254 作爲一個標識，後面四字節組成一個 32 位的 int 值，用於存放上一個 entry 的字節長度。

encoding

簡言之用於表示當前 entry 的類型和長度，當前 entry 的長度和值是根據保存的是 int 還是 string 以及數據的長度共同來決定。

前兩位用於表示類型，當前兩位值爲 “11” 則表示 entry 存放的是 int 類型數據，其他表示存儲的是 string。

entry-data

實際存放數據的區域，需要注意的是，如果 entry 中存儲的是 int 類型，encoding 和 entry-data 會合併到 encoding 中，沒有 entry-data 字段。

此刻結構就變成了 <prevlen> <encoding>。

MySQL：“爲什麼說 ziplist 省內存？”

1. 與 linkedlist 相比，少了 prev、next 指針。

2. 通過 encoding 字段針對不同編碼來細化存儲，儘可能做到按需分配，當 entry 存儲的是 int 類型時，encoding 和 entry-data 會合併到 encoding ，省掉了 entry-data 字段。

3. 每個 entry-data 佔據內存大小不一樣，爲了解決遍歷問題，增加了 prevlen 記錄上一個 entry 長度。遍歷數據時間複雜度是 O(1)，但是數據量很小的情況下影響不大。

MySQL：“聽起來很完美，爲啥還搞什麼 quicklist”

既要又要還要的需求是很難實現的，ziplist 節省了內存，但是也有不足。

• 不能保存過多的元素，否則查詢性能會大大降低，O(N) 時間複雜度。

• ziplist 存儲空間是連續的，當插入新的 entry 時，內存空間不足就需要重新分配一塊連續的內存空間，引發連鎖更新的問題。

連鎖更新

每個 entry 都用 prevlen 記錄了上一個 entry 的長度，從當前 entry B 前面插入一個新的 entry A 時，會導致 B 的 prevlen 改變，也會導致 entry B 大小發生變化。entry B 後一個 entry C 的 prevlen 也需要改變。以此類推，就可能造成了連鎖更新。

圖 2-8

連鎖更新會導致 ziplist 的內存空間需要多次重新分配，直接影響 ziplist 的查詢性能。於是乎在 Redis 3.2 版本引入了 quicklist。

quicklist

quicklist 是綜合考慮了時間效率與空間效率引入的新型數據結構。結合了原先 linkedlist 與 ziplist 各自的優勢，本質還是一個鏈表，只不過鏈表的每個節點是一個 ziplist。

數據結構定義在 quicklist.h 文件中，鏈表由 quicklist 結構體定義，每個節點由 quicklistNode 結構體定義（源碼版本爲 6.2，7.0 版本使用 listpack 取代了 ziplist）。

quicklist 是一個雙向鏈表，所以每個 quicklistNode 都有前序指針（*prev）、後序指針（*next）。每個節點是 ziplist，所以還有一個指向 ziplist 的指針 *zl。

typedef struct quicklistNode {
    // 前序節點指針
    struct quicklistNode *prev;
    // 後序節點指針
    struct quicklistNode *next;
    // 指向 ziplist 的指針
    unsigned char *zl;
    // ziplist 字節大小
    unsigned int sz;
    // ziplst 元素個數
    unsigned int count : 16;
    // 編碼格式，1 = RAW 代表未壓縮原生ziplist，2=LZF 壓縮存儲
    unsigned int encoding : 2;
    // 節點持有的數據類型，默認值 = 2 表示是 ziplist
    unsigned int container : 2;
    // 節點持有的 ziplist 是否經過解壓， 1 表示已經解壓過，下一次操作需要重新壓縮。
    unsigned int recompress : 1;
    // ziplist 數據是否可壓縮，太小數據不需要壓縮
    unsigned int attempted_compress : 1;
    // 預留字段
    unsigned int extra : 10;
} quicklistNode;

quicklist 作爲鏈表，定義了 頭、尾指針，用於快速定位表表頭和鏈表尾。

typedef struct quicklist {
    // 鏈表頭指針
    quicklistNode *head;
    // 鏈表尾指針
    quicklistNode *tail;
    // 所有 ziplist 的總 entry 個數
    unsigned long count;
    // quicklistNode 個數
    unsigned long len;
    int fill : QL_FILL_BITS;
    unsigned int compress : QL_COMP_BITS;
    unsigned int bookmark_count: QL_BM_BITS;
    // 柔性數組，給節點添加標籤，通過名稱定位節點，實現隨機訪問的效果
    quicklistBookmark bookmarks[];
} quicklist;

結合 quicklist 和 quicklistNode定義，quicklist 鏈表結構如下圖所示。

圖 2-9

從結構上看，quicklist 就是 ziplist 的升級版，優化的關鍵點在於控制好每個 ziplist 的大小或者元素個數。

• quicklistNode 的 ziplist 越小，可能會造成更多的內存碎片，極端情況下是每個 ziplist 只有一個 entry，退化成了 linkedlist。

• quicklistNode 的 ziplist 過大，極端情況下一個 quicklist 只有一個 ziplist，退化成了 ziplist。連鎖更新的性能問題就會暴露無遺。

合理配置很重要，Redis 提供了 list-max-ziplist-size -2，

當 list-max-ziplist-size 爲負數時表示限制每個 quicklistNode 的 ziplist 的內存大小，超過這個大小就會使用 linkedlist 存儲數據，每個值有以下含義：

• -5：每個 quicklist 節點上的 ziplist 大小最大 64 kb <--- 正常環境不推薦

• -4：每個 quicklist 節點上的 ziplist 大小最大 32 kb <--- 不推薦

• -3：每個 quicklist 節點上的 ziplist 大小最大 16 kb <--- 可能不推薦

• -2：每個 quicklist 節點上的 ziplist 大小最大 8 kb <--- 不錯

• -1：每個 quicklist 節點上的 ziplist 大小最大 4kb <--- 不錯

默認值爲 -2，也是官方最推薦的值，當然你可以根據自己的實際情況進行修改。

MySQL：“搞了半天還是沒能解決連鎖更新的問題嘛”

別急，飯要一口口喫，路要一步步走，步子邁大了容易扯着蛋。

ziplist 是緊湊型數據結構，可以有效利用內存。但是每個 entry 都用 prevlen 保留了上一個 entry 的長度，所以在插入或者更新時可能會出現連鎖更新影響效率。

於是 antirez 又設計出了 “鏈表 + ziplist” 組成的 quicklist 來避免單個 ziplist 過大，降低連鎖更新的影響範圍。

可畢竟還是使用了 ziplist，本質上無法避免連鎖更新的問題，於是乎在 5.0 版本設計出另一個內存緊湊型數據結構 listpack，於 7.0 版本替換掉 ziplist。

listpack

出現 listpack 的原因是因爲用戶上報了一個 Redis 崩潰的問題，但是 antirez 並沒有找到崩潰的明確原因，猜測可能是 ziplist 結構導致的連鎖更新導致的，於是就想設計一種簡單、高效的數據結構來替換 ziplist 這個數據結構。

MySQL：“listpack 是啥？”

listpack 也是一種緊湊型數據結構，用一塊連續的內存空間來保存數據，並且使用多種編碼方式來表示不同長度的數據來節省內存空間。

源碼文件 listpack.h對 listpack 的解釋：A lists of strings serialization format，意思是一種字符串列表的序列化格式，可以把字符串列表進行序列化存儲，可以存儲字符串或者整形數字。

先看 listpack 的整體結構。

圖 2-10

一共四部分組成，tot-bytes、num-elements、elements、listpack-end-byte。

• tot-bytes，也就是 total bytes，佔用 4 字節，記錄 listpack 佔用的總字節數。

• num-elements，佔用 2 字節，記錄 listpack elements 元素個數。

• elements，listpack 元素，保存數據的部分。

• listpack-end-byte，結束標誌，佔用 1 字節，值固定爲 255。

MySQL：“好傢伙，這跟 ziplist 有啥區別？別以爲換了個名字，換個馬甲我就不認識了”

聽我說完！確實有點像，listpack 也是由元數據和數據自身組成。最大的區別是 elements 部分，爲了解決 ziplist 連鎖更新的問題，element 不再像 ziplist 的 entry 保存前一項的長度。

圖 2-11

• encoding-type，元素的編碼類型，會不同長度的整數和字符串編碼。

• element-data，實際存放的數據。

• element-tot-len，encoding-type + element-data 的總長度，不包含自己的長度。

每個 element 只記錄自己的長度，不像 ziplist 的 entry，記錄上一項的長度。當修改或者新增元素的時候，不會影響後續 element 的長度變化，解決了連鎖更新的問題。

從 linkedlist、 ziplist 到 “鏈表 + ziplist” 構成的 quicklist，再到 listpack 結構。可以看到，設計的初衷都是能夠高效的使用內存，同時避免性能下降。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/By7Ahh0pyW_RfYom4ZWndQ