《閑扯Redis五》List數據類型底層之quicklist
一、前言
Redis 提供了5種數據類型：String（字元串）、Hash（哈希）、List（列表）、Set（集合）、Zset（有序集合），理解每種數據類型的特點對於redis的開發和運維非常重要。
Redis 中的 list 是我們經常使用到的一種數據類型，根據使用方式的不同，可以應用到很多場景中。
二、底層解析
1、上節回顧
上節《閑扯Redis四》List數據類型底層編碼轉換 說道，在 3.0 版本的 Redis 中，List 類型有兩種實現方式：
1、使用壓縮列表（ziplist）實現的列表對象。
2、使用雙端鏈表（linkedlist）實現的列表對象。
在 3.2 版本後新增了 quicklist 數據結構實現了 list，現在就來分析下 quicklist 的結構
2、官方描述
先來看看 Redis 官方對 quicklist 的描述：
A doubly linked list of ziplists
A generic doubly linked quicklist implementation
可見 quicklist 是一個雙向鏈表，並且是一個 ziplist 的雙向鏈表，也就是說 quicklist 的每個節點都是一個 ziplist。而通過前面的文章咱們可以知道，ziplist 本身也是一個能維持數據項先後順序的列表，而且數據項保存在一個連續的記憶體塊中。那是不是意味著 quicklist 結合了壓縮列表和雙端鏈表的特點呢！
3、結構分析
quicklist 結構定義
/*
* quicklist
*/
typedef struct quicklist {
//頭結點
quicklistNode *head;
//尾節點
quicklistNode *tail;
//所有ziplist中entry數量
unsigned long count;
//quicklistNodes節點數量
unsigned int len;
//ziplist中entry能保存的數量,由list-max-ziplist-size配置項控制
int fill : 16;
//壓縮深度,由list-compress-depth配置項控制
unsigned int compress : 16;
} quicklist;
quicklist 結構屬性注釋
注釋：
fill ：ziplist 中 entry 能保存的數量,由 list-max-ziplist-size 配置項控制
表示了單個節點(quicklistNode)的負載比例(fill factor)，負數限制 quicklistNode 中的 ziplist 的位元組長度,
正數限制 quicklistNode 中的 ziplist 的最大長度。
-5: 最大存儲空間: 64 Kb <-- 通常情況下不要設置這個值
-4: 最大存儲空間: 32 Kb <-- 非常不推薦
-3: 最大存儲空間: 16 Kb <-- 不推薦
-2: 最大存儲空間: 8 Kb <-- 推薦
-1: 最大存儲空間: 4 Kb <-- 推薦
對於正整數則表示最多能存儲到你設置的那個值, 當前的節點就裝滿了
通常在 -2 (8 Kb size) 或 -1 (4 Kb size) 時, 性能表現最好
compress ：壓縮深度,由 list-compress-depth 配置項控制
表示 quicklist 中的節點 quicklistNode, 除開最兩端的 compress 個節點之後, 中間的節點都會被壓縮（LZF壓縮演算法）。
quicklistNode 結構定義
typedef struct quicklistNode {
//前節點指針
struct quicklistNode *prev;
//後節點指針
struct quicklistNode *next;
//數據指針。當前節點的數據沒有壓縮，那麼它指向一個ziplist結構；否則，它指向一個quicklistLZF結構。
unsigned char *zl;
//zl指向的ziplist實際佔用記憶體大小。需要注意的是：如果ziplist被壓縮了，那麼這個sz的值仍然是壓縮前的ziplist大小
unsigned int sz;
//ziplist裡面包含的數據項個數
unsigned int count : 16;
//ziplist是否壓縮。取值：1--ziplist，2--quicklistLZF
unsigned int encoding : 2;
//存儲類型，目前使用固定值2 表示使用ziplist存儲
unsigned int container : 2;
//當我們使用類似lindex這樣的命令查看了某一項本來壓縮的數據時，需要把數據暫時解壓，這時就設置recompress=1做一個標記，等有機會再把數據重新壓縮
unsigned int recompress : 1;
unsigned int attempted_compress : 1; /* node can't compress; too small */
unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;
quicklistLZF 結構定義
typedef struct quicklistLZF {
unsigned int sz; //壓縮後的ziplist大小
char compressed[];//柔性數組，存放壓縮後的ziplist位元組數組
} quicklistLZF;
4、quicklist 結構圖
根據上述結構體定義，咱們可以繪製一下 quicklist 的結構：
三、要點總結
1、雙端鏈表
1.雙端鏈表便於在表的兩端進行 push 和 pop 操作，但是它的記憶體開銷比較大；
2.雙端鏈表每個節點上除了要保存數據之外，還要額外保存兩個指針；
3.雙端鏈表的各個節點是單獨的記憶體塊，地址不連續，節點多了容易產生記憶體碎片；
2、壓縮列表
1.ziplist 由於是一整塊連續記憶體，所以存儲效率很高；
2.ziplist 不利於修改操作，每次數據變動都會引發一次記憶體的 realloc；
3.當 ziplist 長度很長的時候，一次 realloc 可能會導致大批量的數據拷貝，進一步降低性能；
3、quicklist
1.空間效率和時間效率的折中；
2.結合了雙端鏈表和壓縮列表的優點；
