1、Redis List 是什么

作為 Java 開發(fā)者的你，看到這個(gè)詞并不陌生。在 Java 開發(fā)中幾乎每天都會(huì)使用這個(gè)數(shù)據(jù)結(jié)構(gòu)。

Redis 的 List 與 Java 中的 LinkedList 類似，是一種線性的有序結(jié)構(gòu)，可以按照元素被推入列表中的順序來存儲(chǔ)元素，能滿足先進(jìn)先出的需求，這些元素既可以是文字?jǐn)?shù)據(jù)，又可以是二進(jìn)制數(shù)據(jù)。

你可以把他當(dāng)做隊(duì)列、棧來使用。

2、修煉心法

我叫 Redis，在 C 語言中，并沒有現(xiàn)成的鏈表結(jié)構(gòu)，所以 antirez 為我專門設(shè)計(jì)了一套實(shí)現(xiàn)方式。

關(guān)于 List 類型的底層數(shù)據(jù)結(jié)構(gòu)，可謂英雄輩出，antirez 大佬一直在優(yōu)化，創(chuàng)造了多種數(shù)據(jù)結(jié)構(gòu)來保存。

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

MySQL：“為何弄了這么多數(shù)據(jù)結(jié)構(gòu)呀？”

antirez 所做的這一切都是為了在內(nèi)存空間開銷與訪問性能之間做取舍和平衡，跟著我去吃透每個(gè)類型的設(shè)計(jì)思想和不足，你就明白了。

linkedlist（雙端列表）

在 Redis 3.2 版本之前，List 的底層數(shù)據(jù)結(jié)構(gòu)由 linkedlist 或者 ziplist 實(shí)現(xiàn)，優(yōu)先使用 ziplist 存儲(chǔ)。

當(dāng)列表對象滿足以下兩個(gè)條件的時(shí)候，List 將使用 ziplist 存儲(chǔ)，否則使用 linkedlist。

• List 的每個(gè)元素的占用的字節(jié)小于 64 字節(jié)。
• List 的元素?cái)?shù)量小于 512 個(gè)。

鏈表的節(jié)點(diǎn)使用 adlist.h/listNode結(jié)構(gòu)來表示。

typedef struct listNode {
    // 前驅(qū)節(jié)點(diǎn)
    struct listNode *prev;
    // 后驅(qū)節(jié)點(diǎn)
    struct listNode *next;
    // 指向節(jié)點(diǎn)的值
    void *value;
} listNode;

listNode 之間通過 prev 和 next 指針組成雙端鏈表。除此之外，我還提供了 adlist.h/list 結(jié)構(gòu)提供了頭指針 head、尾指針 tail 以及一些實(shí)現(xiàn)多態(tài)的特定函數(shù)。

typedef struct list {
    // 頭指針
    listNode *head;
    // 尾指針
    listNode *tail;
    // 節(jié)點(diǎn)值的復(fù)制函數(shù)
    void *(*dup)(void *ptr);
    // 節(jié)點(diǎn)值釋放函數(shù)
    void (*free)(void *ptr);
    // 節(jié)點(diǎn)值比對是否相等
    int (*match)(void *ptr, void *key);
    // 鏈表的節(jié)點(diǎn)數(shù)量
    unsigned long len;
} list;

linkedlist 的結(jié)構(gòu)如圖 2-5 所示。

Redis 的鏈表實(shí)現(xiàn)的特性總結(jié)如下。

• 雙端：鏈表節(jié)點(diǎn)帶有 prev 和 next 指針，獲取某個(gè)節(jié)點(diǎn)的前置節(jié)點(diǎn)和后繼節(jié)點(diǎn)的復(fù)雜度都是 O(1)。
• 無環(huán)：表頭節(jié)點(diǎn)的 prev 指針和尾節(jié)點(diǎn)的 next 指針都指向 NULL，對鏈表的訪問以 NULL 為結(jié)束。
• 帶表頭指針和表尾指針：通過 list 結(jié)構(gòu)的 head 指針和 tail 指針，程序獲取鏈表的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)的復(fù)雜度為 O(1)。
• 使用 list 結(jié)構(gòu)的 len 屬性來對記錄節(jié)點(diǎn)數(shù)量，獲取鏈表中節(jié)點(diǎn)數(shù)量的復(fù)雜度為 O(1)。

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

你知道的，我在追求快和節(jié)省內(nèi)存的方向上無所不及，有兩個(gè)原因?qū)е铝?ziplist 的誕生。

• 普通的 linkedlist 有 prev、next 兩個(gè)指針，當(dāng)存儲(chǔ)數(shù)據(jù)很小的情況下，指針占用的空間會(huì)超過數(shù)據(jù)占用的空間，這就離譜了，是可忍孰不可忍。
• linkedlist 是鏈表結(jié)構(gòu)，在內(nèi)存中不是連續(xù)的，遍歷的效率低下。

ziplist（壓縮列表）

為了解決上面兩個(gè)問題，antirez 創(chuàng)造了 ziplist 壓縮列表，是一種內(nèi)存緊湊的數(shù)據(jù)結(jié)構(gòu)，占用一塊連續(xù)的內(nèi)存空間，提升內(nèi)存使用率。

當(dāng)一個(gè)列表只有少量數(shù)據(jù)的時(shí)候，并且每個(gè)列表項(xiàng)要么是小整數(shù)值，要么就是長度比較短的字符串，那么我就會(huì)使用 ziplist 來做 List 的底層實(shí)現(xiàn)。

ziplist 中可以包含多個(gè) entry 節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)可以存放整數(shù)或者字符串，結(jié)構(gòu)如圖 2-6 所示。

• zlbytes，占用 4 個(gè)字節(jié)，記錄了整個(gè) ziplist 占用的總字節(jié)數(shù)。
• zltail，占用 4 個(gè)字節(jié)，指向最后一個(gè) entry 偏移量，用于快速定位最后一個(gè) entry。
• zllen，占用 2 字節(jié)，記錄 entry 總數(shù)。
• entry，列表元素。
• zlend，ziplist 結(jié)束標(biāo)志，占用 1 字節(jié)，值等于 255。

因?yàn)?ziplist 頭尾元數(shù)據(jù)的大小是固定的，并且在 ziplist 頭部 zllen 記錄了最后一個(gè)元素的位置，所以，當(dāng)在 ziplist 中查找第一個(gè)或最后一個(gè)元素的時(shí)候，能以 O(1) 時(shí)間復(fù)雜度找到。

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

接下來看真正存儲(chǔ)數(shù)據(jù)的 entry 結(jié)構(gòu)長啥樣。

正常來說有三部分構(gòu)成 <prevlen> <encoding> <entry-data>。

prevlen

記錄前一個(gè) entry 占用字節(jié)數(shù)，能實(shí)現(xiàn)逆序遍歷就是靠這個(gè)字段確定往前移動(dòng)多少字節(jié)拿到上一個(gè) entry 首地址。

這部分會(huì)根據(jù)上一個(gè) entry 的長度進(jìn)行變長編碼（為了節(jié)省內(nèi)存操碎了心），變長方式如下。

• 前一個(gè) entry 的字節(jié)大小小于 254（255 用于 zlend），prevlen 長度為 1 字節(jié)，值等于上一個(gè) entry 的長度。
• 前一個(gè) entry 的字節(jié)大小大于等于 254，prevlen 占用 5 字節(jié)，第一個(gè)字節(jié)設(shè)置為 254 作為一個(gè)標(biāo)識(shí)，后面四字節(jié)組成一個(gè) 32 位的 int 值，用于存放上一個(gè) entry 的字節(jié)長度。

encoding

簡言之用于表示當(dāng)前 entry 的類型和長度，當(dāng)前 entry 的長度和值是根據(jù)保存的是 int 還是 string 以及數(shù)據(jù)的長度共同來決定。

前兩位用于表示類型，當(dāng)前兩位值為 “11” 則表示 entry 存放的是 int 類型數(shù)據(jù)，其他表示存儲(chǔ)的是 string。

entry-data

實(shí)際存放數(shù)據(jù)的區(qū)域，需要注意的是，如果 entry 中存儲(chǔ)的是 int 類型，encoding 和 entry-data 會(huì)合并到 encoding 中，沒有 entry-data 字段。

此刻結(jié)構(gòu)就變成了 <prevlen> <encoding>。

MySQL：“為什么說 ziplist 省內(nèi)存？”

1. 與 linkedlist 相比，少了 prev、next 指針。
2. 通過 encoding 字段針對不同編碼來細(xì)化存儲(chǔ)，盡可能做到按需分配，當(dāng) entry 存儲(chǔ)的是 int 類型時(shí)，encoding 和 entry-data 會(huì)合并到 encoding ，省掉了 entry-data 字段。
3. 每個(gè) entry-data 占據(jù)內(nèi)存大小不一樣，為了解決遍歷問題，增加了 prevlen 記錄上一個(gè) entry 長度。遍歷數(shù)據(jù)時(shí)間復(fù)雜度是 O(1)，但是數(shù)據(jù)量很小的情況下影響不大。

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

既要又要還要的需求是很難實(shí)現(xiàn)的，ziplist 節(jié)省了內(nèi)存，但是也有不足。

• 不能保存過多的元素，否則查詢性能會(huì)大大降低，O(N) 時(shí)間復(fù)雜度。
• ziplist 存儲(chǔ)空間是連續(xù)的，當(dāng)插入新的 entry 時(shí)，內(nèi)存空間不足就需要重新分配一塊連續(xù)的內(nèi)存空間，引發(fā)連鎖更新的問題。

連鎖更新

每個(gè) entry 都用 prevlen 記錄了上一個(gè) entry 的長度，從當(dāng)前 entry B 前面插入一個(gè)新的 entry A 時(shí)，會(huì)導(dǎo)致 B 的 prevlen 改變，也會(huì)導(dǎo)致 entry B 大小發(fā)生變化。entry B 后一個(gè) entry C 的 prevlen 也需要改變。以此類推，就可能造成了連鎖更新。

連鎖更新會(huì)導(dǎo)致 ziplist 的內(nèi)存空間需要多次重新分配，直接影響 ziplist 的查詢性能。于是乎在 Redis 3.2 版本引入了 quicklist。

quicklist

quicklist 是綜合考慮了時(shí)間效率與空間效率引入的新型數(shù)據(jù)結(jié)構(gòu)。結(jié)合了原先 linkedlist 與 ziplist 各自的優(yōu)勢，本質(zhì)還是一個(gè)鏈表，只不過鏈表的每個(gè)節(jié)點(diǎn)是一個(gè) ziplist。

數(shù)據(jù)結(jié)構(gòu)定義在 quicklist.h? 文件中，鏈表由 quicklist? 結(jié)構(gòu)體定義，每個(gè)節(jié)點(diǎn)由 quicklistNode 結(jié)構(gòu)體定義（源碼版本為 6.2，7.0 版本使用 listpack 取代了 ziplist）。

quicklist 是一個(gè)雙向鏈表，所以每個(gè) quicklistNode 都有前序指針（*prev?）、后序指針（*next?）。每個(gè)節(jié)點(diǎn)是 ziplist，所以還有一個(gè)指向 ziplist 的指針 *zl。

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

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

typedef struct quicklist {
    // 鏈表頭指針
    quicklistNode *head;
    // 鏈表尾指針
    quicklistNode *tail;
    // 所有 ziplist 的總 entry 個(gè)數(shù)
    unsigned long count;
    // quicklistNode 個(gè)數(shù)
    unsigned long len;
    int fill : QL_FILL_BITS;
    unsigned int compress : QL_COMP_BITS;
    unsigned int bookmark_count: QL_BM_BITS;
    // 柔性數(shù)組，給節(jié)點(diǎn)添加標(biāo)簽，通過名稱定位節(jié)點(diǎn)，實(shí)現(xiàn)隨機(jī)訪問的效果
    quicklistBookmark bookmarks[];
} quicklist;

結(jié)合 quicklist 和 quicklistNode定義，quicklist 鏈表結(jié)構(gòu)如下圖所示。

從結(jié)構(gòu)上看，quicklist 就是 ziplist 的升級(jí)版，優(yōu)化的關(guān)鍵點(diǎn)在于控制好每個(gè) ziplist 的大小或者元素個(gè)數(shù)。

• quicklistNode 的 ziplist 越小，可能會(huì)造成更多的內(nèi)存碎片，極端情況下是每個(gè) ziplist 只有一個(gè) entry，退化成了 linkedlist。
• quicklistNode 的 ziplist 過大，極端情況下一個(gè) quicklist 只有一個(gè) ziplist，退化成了 ziplist。連鎖更新的性能問題就會(huì)暴露無遺。

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

當(dāng) list-max-ziplist-size 為負(fù)數(shù)時(shí)表示限制每個(gè) quicklistNode 的 ziplist 的內(nèi)存大小，超過這個(gè)大小就會(huì)使用 linkedlist 存儲(chǔ)數(shù)據(jù)，每個(gè)值有以下含義：

• -5：每個(gè) quicklist 節(jié)點(diǎn)上的 ziplist 大小最大 64 kb <--- 正常環(huán)境不推薦
• -4：每個(gè) quicklist 節(jié)點(diǎn)上的 ziplist 大小最大 32 kb <--- 不推薦
• -3：每個(gè) quicklist 節(jié)點(diǎn)上的 ziplist 大小最大 16 kb <--- 可能不推薦
• -2：每個(gè) quicklist 節(jié)點(diǎn)上的 ziplist 大小最大 8 kb <--- 不錯(cuò)
• -1：每個(gè) quicklist 節(jié)點(diǎn)上的 ziplist 大小最大 4kb <--- 不錯(cuò)

默認(rèn)值為 -2，也是官方最推薦的值，當(dāng)然你可以根據(jù)自己的實(shí)際情況進(jìn)行修改。

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

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

ziplist 是緊湊型數(shù)據(jù)結(jié)構(gòu)，可以有效利用內(nèi)存。但是每個(gè) entry 都用 prevlen 保留了上一個(gè) entry 的長度，所以在插入或者更新時(shí)可能會(huì)出現(xiàn)連鎖更新影響效率。

于是 antirez 又設(shè)計(jì)出了“鏈表 + ziplist” 組成的 quicklist 來避免單個(gè) ziplist 過大，降低連鎖更新的影響范圍。

可畢竟還是使用了 ziplist，本質(zhì)上無法避免連鎖更新的問題，于是乎在 5.0 版本設(shè)計(jì)出另一個(gè)內(nèi)存緊湊型數(shù)據(jù)結(jié)構(gòu) listpack，于 7.0 版本替換掉 ziplist。

listpack

出現(xiàn) listpack 的原因是因?yàn)橛脩羯蠄?bào)了一個(gè) Redis 崩潰的問題，但是 antirez 并沒有找到崩潰的明確原因，猜測可能是 ziplist 結(jié)構(gòu)導(dǎo)致的連鎖更新導(dǎo)致的，于是就想設(shè)計(jì)一種簡單、高效的數(shù)據(jù)結(jié)構(gòu)來替換 ziplist 這個(gè)數(shù)據(jù)結(jié)構(gòu)。

MySQL：“l(fā)istpack 是啥？”

?listpack 也是一種緊湊型數(shù)據(jù)結(jié)構(gòu)，用一塊連續(xù)的內(nèi)存空間來保存數(shù)據(jù)，并且使用多種編碼方式來表示不同長度的數(shù)據(jù)來節(jié)省內(nèi)存空間。

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

先看 listpack 的整體結(jié)構(gòu)。

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

• tot-bytes，也就是 total bytes，占用 4 字節(jié)，記錄 listpack 占用的總字節(jié)數(shù)。
• num-elements，占用 2 字節(jié)，記錄 listpack elements 元素個(gè)數(shù)。
• elements，listpack 元素，保存數(shù)據(jù)的部分。
• listpack-end-byte，結(jié)束標(biāo)志，占用 1 字節(jié)，值固定為 255。

MySQL：“好家伙，這跟 ziplist 有啥區(qū)別？別以為換了個(gè)名字，換個(gè)馬甲我就不認(rèn)識(shí)了”

聽我說完！確實(shí)有點(diǎn)像，listpack 也是由元數(shù)據(jù)和數(shù)據(jù)自身組成。最大的區(qū)別是 elements 部分，為了解決 ziplist 連鎖更新的問題，element 不再像 ziplist 的 entry 保存前一項(xiàng)的長度。

• encoding-type，元素的編碼類型，會(huì)不同長度的整數(shù)和字符串編碼。
• element-data，實(shí)際存放的數(shù)據(jù)。
• element-tot-len，encoding-type + element-data 的總長度，不包含自己的長度。

?每個(gè) element 只記錄自己的長度，不像 ziplist 的 entry，記錄上一項(xiàng)的長度。當(dāng)修改或者新增元素的時(shí)候，不會(huì)影響后續(xù) element 的長度變化，解決了連鎖更新的問題。

從 linkedlist、 ziplist 到“鏈表 + ziplist” 構(gòu)成的 quicklist，再到 listpack 結(jié)構(gòu)。可以看到，設(shè)計(jì)的初衷都是能夠高效的使用內(nèi)存，同時(shí)避免性能下降。

本文轉(zhuǎn)載自微信公眾號(hào)「碼哥字節(jié)」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系碼哥字節(jié)公眾號(hào)。