linkedlist

linkedlist 是一個(gè)雙向列表，每個(gè)節(jié)點(diǎn)都會(huì)存儲(chǔ)指向上一個(gè)節(jié)點(diǎn)和指向下一個(gè)節(jié)點(diǎn)的指針。linkedlist 因?yàn)槊總€(gè)節(jié)點(diǎn)之間的空間是不連續(xù)的，所以可能會(huì)造成過(guò)多的內(nèi)存空間碎片。

linkedlist存儲(chǔ)結(jié)構(gòu)

鏈表中每一個(gè)節(jié)點(diǎn)都是一個(gè) listNode 對(duì)象（源碼 adlist.h 內(nèi)），不過(guò)需要注意的是，列表中的 value 其實(shí)也是一個(gè)字符串對(duì)象，其他幾種數(shù)據(jù)類(lèi)型其內(nèi)部最終也是會(huì)嵌套字符串對(duì)象，字符串對(duì)象也是唯一一種會(huì)被其他對(duì)象引用的基本類(lèi)型：

typedef struct listNode {
  struct listNode *prev;//前一個(gè)節(jié)點(diǎn)
  struct listNode *next;//后一個(gè)節(jié)點(diǎn)
  void *value;//值(字符串對(duì)象)
} listNode;

然后會(huì)將其再進(jìn)行封裝成為一個(gè) list 對(duì)象（源碼 adlist.h 內(nèi)）：

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

Redis 中對(duì) linkedlist 的訪問(wèn)是以 NULL 值為終點(diǎn)的，因?yàn)?head 節(jié)點(diǎn)的 prev 節(jié)點(diǎn)為 NULL，tail 節(jié)點(diǎn)的 next 節(jié)點(diǎn)也為 NULL，所以從頭節(jié)點(diǎn)開(kāi)始遍歷，當(dāng)發(fā)現(xiàn) tail 為 NULL 時(shí)，則可以認(rèn)為已經(jīng)到了列表末尾。

當(dāng)我們?cè)O(shè)置一個(gè)列表對(duì)象時(shí)，在 Redis 3.2 版本之前我們可以得到如下存儲(chǔ)示意圖：

ziplist

壓縮列表在前面已經(jīng)介紹過(guò)，想要詳細(xì)了解的可以點(diǎn)擊這里。

linkedlist 和 ziplist 的選擇

在 Redis3.2 之前，linkedlist 和 ziplist 兩種編碼可以進(jìn)選擇切換，如果需要列表使用 ziplist 編碼進(jìn)行存儲(chǔ)，則必須滿(mǎn)足以下兩個(gè)條件：

列表對(duì)象保存的所有字符串元素的長(zhǎng)度都小于 64 字節(jié)。列表對(duì)象保存的元素?cái)?shù)量小于 512 個(gè)。

一旦不滿(mǎn)足這兩個(gè)條件的任意一個(gè)，則會(huì)使用 linkedlist 編碼進(jìn)行存儲(chǔ)。

PS：這兩個(gè)條件可以通過(guò)參數(shù) list-max-ziplist-value 和 list-max-ziplist-entries 進(jìn)行修改。

這兩種列表能在特定的場(chǎng)景下發(fā)揮各自的作用，應(yīng)該來(lái)說(shuō)已經(jīng)能滿(mǎn)足大部分需求了，然后 Redis 并不滿(mǎn)足于此，于是一場(chǎng)改革引發(fā)了，quicklist 橫空出世。

quicklist

在 Redis 3.2 版本之后，為了進(jìn)一步提升 Redis 的性能，列表對(duì)象統(tǒng)一采用 quicklist 來(lái)存儲(chǔ)列表對(duì)象。quicklist存儲(chǔ)了一個(gè)雙向列表，每個(gè)列表的節(jié)點(diǎn)是一個(gè) ziplist，所以實(shí)際上 quicklist 并不是一個(gè)新的數(shù)據(jù)結(jié)構(gòu)，它就是linkedlist 和 ziplist 的結(jié)合，然后被命名為快速列表。

quicklist 內(nèi)部存儲(chǔ)結(jié)構(gòu)

quicklist 中每一個(gè)節(jié)點(diǎn)都是一個(gè) quicklistNode 對(duì)象，其數(shù)據(jù)結(jié)構(gòu)定義如下：

typedef struct quicklistNode {
  struct quicklistNode *prev;//前一個(gè)節(jié)點(diǎn)
  struct quicklistNode *next;//后一個(gè)節(jié)點(diǎn)
  unsigned char *zl;//當(dāng)前指向的ziplist或者quicklistLZF
  unsigned int sz;//當(dāng)前ziplist占用字節(jié)
  unsigned int count : 16;//ziplist中存儲(chǔ)的元素個(gè)數(shù)，16字節(jié)(最大65535個(gè))
  unsigned int encoding : 2; //是否采用了LZF壓縮算法壓縮節(jié)點(diǎn) 1：RAW 2:LZF
  unsigned int container : 2; //存儲(chǔ)結(jié)構(gòu)，NONE=1, ZIPLIST=2
  unsigned int recompress : 1; //當(dāng)前ziplist是否需要再次壓縮(如果前面被解壓過(guò)則為true，表示需要再次被壓縮)
  unsigned int attempted_compress : 1;//測(cè)試用 
  unsigned int extra : 10; //后期留用
} quicklistNode;

然后各個(gè) quicklistNode 就構(gòu)成了一個(gè)快速列表 quicklist：

typedef struct quicklist {
  quicklistNode *head;//列表頭節(jié)點(diǎn)
  quicklistNode *tail;//列表尾節(jié)點(diǎn)
  unsigned long count;//ziplist中一共存儲(chǔ)了多少元素，即:每一個(gè)quicklistNode內(nèi)的count相加
  unsigned long len; //雙向鏈表的長(zhǎng)度，即quicklistNode的數(shù)量
  int fill : 16;//填充因子
  unsigned int compress : 16;//壓縮深度 0-不壓縮
} quicklist;

根據(jù)這兩個(gè)結(jié)構(gòu)，我們可以得到 Redis 3.2 版本之后的列表對(duì)象的一個(gè)存儲(chǔ)結(jié)構(gòu)示意圖：

quicklist 的 compress 屬性

compress 是用來(lái)表示壓縮深度，ziplist 除了內(nèi)存空間是連續(xù)之外，還可以采用特定的 LZF 壓縮算法來(lái)將節(jié)點(diǎn)進(jìn)行壓縮存儲(chǔ)，從而更進(jìn)一步的節(jié)省空間，壓縮深度可以通過(guò)參數(shù) list-compress-depth 控制：

0：不壓縮(默認(rèn)值)
1：首尾第1個(gè)元素不壓縮
2：首位前2個(gè)元素不壓縮
3：首尾前3個(gè)元素不壓縮以此類(lèi)推

注意：之所以采取這種壓縮兩端節(jié)點(diǎn)的方式是因?yàn)楹芏鄨?chǎng)景都是兩端的元素訪問(wèn)率最高的，而中間元素訪問(wèn)率相對(duì)較低，所以在實(shí)際使用時(shí)，我們可以根據(jù)自己的實(shí)際情況選擇是否進(jìn)行壓縮，以及具體的壓縮深度。

quicklistNode 的 zl 指針

zl 指針默認(rèn)指向了 ziplist，上面提到 quicklistNode 中有一個(gè) sz 屬性記錄了當(dāng)前 ziplist 占用的字節(jié)，不過(guò)這僅僅限于當(dāng)前節(jié)點(diǎn)沒(méi)有被壓縮（通過(guò)LZF 壓縮算法）的情況，如果當(dāng)前節(jié)點(diǎn)被壓縮了，那么被壓縮節(jié)點(diǎn)的 zl 指針會(huì)指向另一個(gè)對(duì)象 quicklistLZF，而不會(huì)直接指向 ziplist。quicklistLZF 是一個(gè) 4+N 字節(jié)的結(jié)構(gòu)：

typedef struct quicklistLZF {
  unsigned int sz;// LZF大小，占用4字節(jié)
  char compressed[];//被壓縮的內(nèi)容，占用N字節(jié)
} quicklistLZF;

quicklist 對(duì)比原始兩種編碼的改進(jìn)

quicklist 同樣采用了 linkedlist 的雙端列表特性，然后 quicklist 中的每個(gè)節(jié)點(diǎn)又是一個(gè) ziplist，所以quicklist 就是綜合平衡考慮了 linkedlist 容易產(chǎn)生空間碎片的問(wèn)題和 ziplist 的讀寫(xiě)性能兩個(gè)維度而設(shè)計(jì)出來(lái)的一種數(shù)據(jù)結(jié)構(gòu)。使用 quicklist 需要注意以下 2 點(diǎn)：

如果 ziplist 中的 entry 個(gè)數(shù)過(guò)少，最極端情況就是只有 1 個(gè) entry 的壓縮列表，那么此時(shí) quicklist 就相當(dāng)于退化成了一個(gè)普通的 linkedlist。如果 ziplist 中的 entry 過(guò)多，那么也會(huì)導(dǎo)致一次性需要申請(qǐng)的內(nèi)存空間過(guò)大（ziplist 空間是連續(xù)的），而且因?yàn)?ziplist 本身的就是以時(shí)間換空間，所以會(huì)過(guò)多 entry 也會(huì)影響到列表對(duì)象的讀寫(xiě)性能。

ziplist 中的 entry 個(gè)數(shù)可以通過(guò)參數(shù) list-max-ziplist-size 來(lái)控制：

list-max-ziplist-size 1

注意：這個(gè)參數(shù)可以配置正數(shù)也可以配置負(fù)數(shù)。正數(shù)表示限制每個(gè)節(jié)點(diǎn)中的 entry 數(shù)量，如果是負(fù)數(shù)則只能為 -1~-5，其代表的含義如下：

-1：每個(gè) ziplist 最多只能為 4KB

-2：每個(gè) ziplist 最多只能為 8KB

-3：每個(gè) ziplist 最多只能為 16KB

-4：每個(gè) ziplist 最多只能為 32KB

-5：每個(gè) ziplist 最多只能為 64KB

列表對(duì)象常用操作命令

lpush key value1 value2：將一個(gè)或者多個(gè) value 插入到列表 key 的頭部，key 不存在則創(chuàng)建 key（value2 在value1 之后）。

• lpushx key value1 value2：將一個(gè)或者多個(gè) value 插入到列表 key 的頭部，key 不存在則不做任何處理（value2 在value1 之后）。
• lpop key：移除并返回 key 值的列表頭元素。
• rpush key value1 value2：將一個(gè)或者多個(gè) value 插入到列表 key 的尾部，key 不存在則創(chuàng)建 key（value2 在value1 之后）。
• rpushx key value1 vaue2：將一個(gè)或者多個(gè) value 插入到列表 key 的尾部，key 不存在則不做任何處理（value2 在value1 之后）。
• rpop key：移除并返回列表 key 的尾元素。
• llen key：返回列表 key 的長(zhǎng)度。
• lindex key index：返回列表 key 中下標(biāo)為 index 的元素。index 為正數(shù)（從 0 開(kāi)始）表示從隊(duì)頭開(kāi)始算，index 為負(fù)數(shù)（從-1開(kāi)始）則表示從隊(duì)尾開(kāi)始算。
• lrange key start stop：返回列表 key 中下標(biāo) [start,end] 之間的元素。
• lset key index value：將 value 設(shè)置到列表 key 中指定 index 位置，key 不存在或者 index 超出范圍則會(huì)報(bào)錯(cuò)。 ltrim key start end：截取列表中 [start,end] 之間的元素，并替換原列表保存。

了解了操作列表對(duì)象的常用命令，我們就可以來(lái)驗(yàn)證下前面提到的列表對(duì)象的類(lèi)型和編碼了，在測(cè)試之前為了防止其他 key 值的干擾，我們先執(zhí)行 flushall 命令清空 Redis 數(shù)據(jù)庫(kù)。

接下來(lái)依次輸入命令：

lpush name zhangsan type name object encoding name

可以看到，通過(guò) type 命令輸出的是 list，說(shuō)明當(dāng)前 name 存的是一個(gè)列表對(duì)象，并且編碼是 quicklist（示例中用的是 5.0.5 版本）。

總結(jié)

本文主要介紹了 Redis 中 5 種常用數(shù)據(jù)類(lèi)型中的 列表對(duì)象，并介紹了底層的存儲(chǔ)結(jié)構(gòu) quicklist，并分別對(duì)舊版本的兩種底層數(shù)據(jù) linkedlist 和 ziplist 進(jìn)行了分析對(duì)比得出了為什么 Redis 最終要采用 quicklist 來(lái)存儲(chǔ)列表對(duì)象。

到此這篇關(guān)于Redis都做了哪些加快速度的設(shè)計(jì)的文章就介紹到這了,更多相關(guān)Redis 加快速度的設(shè)計(jì)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！