redis使用兩種數(shù)據(jù)結構保存鏈表，分別是ziplist與linkedlist料滥，內存占用及常用操作效率各不相同。
本文嘗試簡要說明他們之間的區(qū)別讳推。

眾所周知顶籽，redis中的list有兩種編碼結構，ziplist和linkedlist银觅。兩種編碼結構的切換由下面的配置信息決定：

redis 127.0.0.1:6379> config get list*
1) "list-max-ziplist-entries"
2) "512"
3) "list-max-ziplist-value"
4) "64"

以上兩個配置是默認的配置礼饱。

針對以上的配置，當列表對象保存的所有字符串元素的長度都小于64字節(jié)究驴，并且列表對象保存的元素數(shù)量小于512時镊绪，list使用ziplist編碼；不能滿足這兩種情況就是用linkedlist編碼纳胧。

ziplist的特點是節(jié)省內存镰吆，linkedlist是一個雙向列表帘撰，特點就是插入速度快跑慕，但是占內存。

測試

正式開始我今天主要想發(fā)表的東西摧找，雖不是什么了不起的東西核行，但是是我認認真真測試出來的結果，留個紀念吧蹬耘。

測試方式：
a. 一個key芝雪，分別對其進行rpush、lrange综苔、ltrim三種操作惩系；
b. rpush數(shù)據(jù)為80W個整型，每插入10W條記錄記錄一次此時的平均插入速率如筛；
c. 每隔10W條記錄進行一次lrange堡牡，查看占用時間；
d. 全部數(shù)據(jù)更新成功后杨刨，開始測試ltrim晤柄；
e. 分兩種編碼結構進行測試，作對比妖胀；

以下是測試結果：

Paste_Image.png

關于ziplist和linkedlist的內存占用芥颈，80W的數(shù)據(jù)，ziplist占用內存不到5M赚抡，而linked占用內存為37M+爬坑，內存占用相差7倍多。但是執(zhí)行速度方面涂臣，linkedlist有明顯的優(yōu)勢妇垢，在80w級別的數(shù)據(jù)相差63左右。

通過上面的測試，我們已經知道ziplist在空間利用上有優(yōu)勢闯估，linkedlist在執(zhí)行效率上有優(yōu)勢灼舍，具體選擇什么類型，需結合使用場景而定涨薪。

數(shù)據(jù)結構

鏈表

每個鏈表節(jié)點使用一個 adlist.h/listNode 結構來表示：

typedef struct listNode {

    // 前置節(jié)點
    struct listNode *prev;

    // 后置節(jié)點
    struct listNode *next;

    // 節(jié)點的值
    void *value;

} listNode;

多個 listNode 可以通過 prev 和 next 指針組成雙端鏈表骑素，如圖 3-1 所示。

Paste_Image.png

雖然僅僅使用多個 listNode 結構就可以組成鏈表刚夺， 但使用 adlist.h/list 來持有鏈表的話献丑， 操作起來會更方便：

typedef struct list {

    // 表頭節(jié)點
    listNode *head;

    // 表尾節(jié)點
    listNode *tail;

    // 鏈表所包含的節(jié)點數(shù)量
    unsigned long len;

    // 節(jié)點值復制函數(shù)
    void *(*dup)(void *ptr);

    // 節(jié)點值釋放函數(shù)
    void (*free)(void *ptr);

    // 節(jié)點值對比函數(shù)
    int (*match)(void *ptr, void *key);

} list;

list 結構為鏈表提供了表頭指針 head 、表尾指針 tail 侠姑， 以及鏈表長度計數(shù)器 len 创橄， 而 dup 、 free 和 match 成員則是用于實現(xiàn)多態(tài)鏈表所需的類型特定函數(shù)：

• dup 函數(shù)用于復制鏈表節(jié)點所保存的值莽红；
• free 函數(shù)用于釋放鏈表節(jié)點所保存的值妥畏；
• match 函數(shù)則用于對比鏈表節(jié)點所保存的值和另一個輸入值是否相等。

圖 3-2 是由一個 list 結構和三個 listNode 結構組成的鏈表：

Paste_Image.png

Redis 的鏈表實現(xiàn)的特性可以總結如下：

• 雙端： 鏈表節(jié)點帶有 prev 和 next 指針安吁， 獲取某個節(jié)點的前置節(jié)點和后置節(jié)點的復雜度都是 O(1) 醉蚁。
• 無環(huán)： 表頭節(jié)點的 prev 指針和表尾節(jié)點的 next 指針都指向 NULL ， 對鏈表的訪問以 NULL 為終點鬼店。
• 帶表頭指針和表尾指針： 通過 list 結構的 head 指針和 tail 指針网棍， 程序獲取鏈表的表頭節(jié)點和表尾節(jié)點的復雜度為 O(1) 。
• 帶鏈表長度計數(shù)器： 程序使用 list 結構的 len 屬性來對 list 持有的鏈表節(jié)點進行計數(shù)妇智， 程序獲取鏈表中節(jié)點數(shù)量的復雜度為 O(1) 滥玷。
• 多態(tài)： 鏈表節(jié)點使用 void* 指針來保存節(jié)點值， 并且可以通過 list 結構的 dup 巍棱、 free 惑畴、 match 三個屬性為節(jié)點值設置類型特定函數(shù)， 所以鏈表可以用于保存各種不同類型的值拉盾。

壓縮列表

壓縮列表（ziplist）是列表鍵和哈希鍵的底層實現(xiàn)之一桨菜。

當一個列表鍵只包含少量列表項， 并且每個列表項要么就是小整數(shù)值捉偏， 要么就是長度比較短的字符串倒得， 那么 Redis 就會使用壓縮列表來做列表鍵的底層實現(xiàn)。

比如說夭禽， 執(zhí)行以下命令將創(chuàng)建一個壓縮列表實現(xiàn)的列表鍵：

redis> RPUSH lst 1 3 5 10086 "hello" "world"
(integer) 6

redis> OBJECT ENCODING lst
"ziplist"

壓縮列表的構成

壓縮列表是 Redis 為了節(jié)約內存而開發(fā)的霞掺， 由一系列特殊編碼的連續(xù)內存塊組成的順序型（sequential）數(shù)據(jù)結構。

一個壓縮列表可以包含任意多個節(jié)點（entry）讹躯， 每個節(jié)點可以保存一個字節(jié)數(shù)組或者一個整數(shù)值菩彬。

圖 7-1 展示了壓縮列表的各個組成部分缠劝， 表 7-1 則記錄了各個組成部分的類型、長度骗灶、以及用途惨恭。

Paste_Image.png

圖 7-2 展示了一個壓縮列表示例：

• 列表 zlbytes 屬性的值為 0x50 （十進制 80）， 表示壓縮列表的總長為 80 字節(jié)舷暮。
• 列表 zltail 屬性的值為 0x3c （十進制 60）态罪， 這表示如果我們有一個指向壓縮列表起始地址的指針 p 噩茄， 那么只要用指針 p 加上偏移量 60 下面， 就可以計算出表尾節(jié)點 entry3 的地址。
• 列表 zllen 屬性的值為 0x3 （十進制 3）绩聘， 表示壓縮列表包含三個節(jié)點沥割。

Paste_Image.png

圖 7-3 展示了另一個壓縮列表示例：

• 列表 zlbytes 屬性的值為 0xd2 （十進制 210）， 表示壓縮列表的總長為 210 字節(jié)凿菩。
• 列表 zltail 屬性的值為 0xb3 （十進制 179）机杜， 這表示如果我們有一個指向壓縮列表起始地址的指針 p ， 那么只要用指針 p 加上偏移量 179 衅谷， 就可以計算出表尾節(jié)點 entry5 的地址椒拗。
• 列表 zllen 屬性的值為 0x5 （十進制 5）， 表示壓縮列表包含五個節(jié)點获黔。

Paste_Image.png

壓縮列表節(jié)點的構成

每個壓縮列表節(jié)點可以保存一個字節(jié)數(shù)組或者一個整數(shù)值蚀苛， 其中， 字節(jié)數(shù)組可以是以下三種長度的其中一種：

1. 長度小于等于 63 （2^{6}-1）字節(jié)的字節(jié)數(shù)組玷氏；

2. 長度小于等于 16383 （2^{14}-1） 字節(jié)的字節(jié)數(shù)組堵未；

3. 長度小于等于 4294967295 （2^{32}-1）字節(jié)的字節(jié)數(shù)組；
   而整數(shù)值則可以是以下六種長度的其中一種：

4. 4 位長盏触，介于 0 至 12 之間的無符號整數(shù)渗蟹；

5. 1 字節(jié)長的有符號整數(shù)块饺；

6. 3 字節(jié)長的有符號整數(shù)；

7. int16_t 類型整數(shù)雌芽；

8. int32_t 類型整數(shù)授艰；

9. int64_t 類型整數(shù)。
   每個壓縮列表節(jié)點都由 previous_entry_length 世落、 encoding 想诅、 content 三個部分組成， 如圖 7-4 所示岛心。

Paste_Image.png

接下來的內容將分別介紹這三個組成部分来破。

previous_entry_length

節(jié)點的 previous_entry_length 屬性以字節(jié)為單位， 記錄了壓縮列表中前一個節(jié)點的長度忘古。

previous_entry_length 屬性的長度可以是 1 字節(jié)或者 5 字節(jié)：

• 如果前一節(jié)點的長度小于 254 字節(jié)徘禁， 那么 previous_entry_length 屬性的長度為 1 字節(jié)： 前一節(jié)點的長度就保存在這一個字節(jié)里面。
• 如果前一節(jié)點的長度大于等于 254 字節(jié)髓堪， 那么 previous_entry_length 屬性的長度為 5 字節(jié)： 其中屬性的第一字節(jié)會被設置為 0xFE （十進制值 254）送朱， 而之后的四個字節(jié)則用于保存前一節(jié)點的長度。

圖 7-5 展示了一個包含一字節(jié)長 previous_entry_length 屬性的壓縮列表節(jié)點干旁， 屬性的值為 0x05 驶沼， 表示前一節(jié)點的長度為 5 字節(jié)。

Paste_Image.png

圖 7-6 展示了一個包含五字節(jié)長 previous_entry_length 屬性的壓縮節(jié)點争群， 屬性的值為 0xFE00002766 回怜， 其中值的最高位字節(jié) 0xFE 表示這是一個五字節(jié)長的 previous_entry_length 屬性， 而之后的四字節(jié) 0x00002766 （十進制值 10086 ）才是前一節(jié)點的實際長度换薄。

Paste_Image.png

因為節(jié)點的 previous_entry_length 屬性記錄了前一個節(jié)點的長度玉雾， 所以程序可以通過指針運算， 根據(jù)當前節(jié)點的起始地址來計算出前一個節(jié)點的起始地址轻要。

舉個例子复旬， 如果我們有一個指向當前節(jié)點起始地址的指針 c ， 那么我們只要用指針 c 減去當前節(jié)點 previous_entry_length 屬性的值冲泥， 就可以得出一個指向前一個節(jié)點起始地址的指針 p 驹碍， 如圖 7-7 所示。

Paste_Image.png

壓縮列表的從表尾向表頭遍歷操作就是使用這一原理實現(xiàn)的： 只要我們擁有了一個指向某個節(jié)點起始地址的指針凡恍， 那么通過這個指針以及這個節(jié)點的 previous_entry_length 屬性志秃， 程序就可以一直向前一個節(jié)點回溯， 最終到達壓縮列表的表頭節(jié)點咳焚。

圖 7-8 展示了一個從表尾節(jié)點向表頭節(jié)點進行遍歷的完整過程：

• 首先洽损，我們擁有指向壓縮列表表尾節(jié)點 entry4 起始地址的指針 p1 （指向表尾節(jié)點的指針可以通過指向壓縮列表起始地址的指針加上 zltail 屬性的值得出）；
• 通過用 p1 減去 entry4 節(jié)點 previous_entry_length 屬性的值革半， 我們得到一個指向 entry4 前一節(jié)點 entry3 起始地址的指針 p2 ；
• 通過用 p2 減去 entry3 節(jié)點 previous_entry_length 屬性的值， 我們得到一個指向 entry3 前一節(jié)點 entry2 起始地址的指針 p3 行施；
• 通過用 p3 減去 entry2 節(jié)點 previous_entry_length 屬性的值， 我們得到一個指向 entry2 前一節(jié)點 entry1 起始地址的指針 p4 漫试， entry1 為壓縮列表的表頭節(jié)點；
• 最終碘赖， 我們從表尾節(jié)點向表頭節(jié)點遍歷了整個列表驾荣。

Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png

encoding

節(jié)點的 encoding 屬性記錄了節(jié)點的 content 屬性所保存數(shù)據(jù)的類型以及長度：

• 一字節(jié)、兩字節(jié)或者五字節(jié)長普泡， 值的最高位為 00 播掷、 01 或者 10 的是字節(jié)數(shù)組編碼： 這種編碼表示節(jié)點的 content 屬性保存著字節(jié)數(shù)組， 數(shù)組的長度由編碼除去最高兩位之后的其他位記錄撼班；
• 一字節(jié)長歧匈， 值的最高位以 11 開頭的是整數(shù)編碼： 這種編碼表示節(jié)點的 content 屬性保存著整數(shù)值， 整數(shù)值的類型和長度由編碼除去最高兩位之后的其他位記錄砰嘁；

表 7-2 記錄了所有可用的字節(jié)數(shù)組編碼件炉， 而表 7-3 則記錄了所有可用的整數(shù)編碼。 表格中的下劃線 _ 表示留空矮湘， 而 b 斟冕、 x 等變量則代表實際的二進制數(shù)據(jù)， 為了方便閱讀缅阳， 多個字節(jié)之間用空格隔開磕蛇。

表 7-2 字節(jié)數(shù)組編碼

表 7-3 整數(shù)編碼

content

節(jié)點的 content 屬性負責保存節(jié)點的值， 節(jié)點值可以是一個字節(jié)數(shù)組或者整數(shù)候引， 值的類型和長度由節(jié)點的 encoding 屬性決定侯养。

圖 7-9 展示了一個保存字節(jié)數(shù)組的節(jié)點示例：

• 編碼的最高兩位 00 表示節(jié)點保存的是一個字節(jié)數(shù)組；
• 編碼的后六位 001011 記錄了字節(jié)數(shù)組的長度 11 澄干；
• content 屬性保存著節(jié)點的值 "hello world" 逛揩。

Paste_Image.png

圖 7-10 展示了一個保存整數(shù)值的節(jié)點示例：

• 編碼 11000000 表示節(jié)點保存的是一個 int16_t 類型的整數(shù)值柠傍；
• content 屬性保存著節(jié)點的值 10086 。

Paste_Image.png

參考

Redis 設計與實現(xiàn)
Redis 命令參考