数据类型-List
概述
Redis 中的 List 对象在版本 3.2 之前，列表底层的编码是 ziplist 和 linkedlist 实现的， 但是在版本 3.2 之后，重新引入了一个 quicklist 的数据结构，列表的底层都由 quicklist 实现。
在早期的设计中， 当列表对象中元素的长度比较小或者数量比较少的时候，采用 ziplist 来存储，当列表对象中元素的长度比较大或者数量比较多的时候，则会转而使用双向列表 linkedlist 来存储。这两种存储方式都各有优缺点：
ziplist存储在一段连续的内存上，所以存储效率很高。但是，它不利于修改操作，插入和删除操作需要频繁的申请和释放内存。特别是当ziplist长度很长的时候，一次realloc可能会导致大批量的数据拷贝。双向链表
linkedlist便于在表的两端进行push和pop操作，在插入节点上复杂度很低，但是它的内存开销比较大。首先，它在每个节点上除了要保存数据之外，还要额外保存两个指针；其次，双向链表的各个节点是单独的内存块，地址不连续，节点多了容易产生内存碎片。并且临界条件变化时，会触发
ziplist和linkedlist间的转换，会浪费性能。
那么 quicklist 是一种什么样的格式呢？简单的说，我们仍旧可以将其看作一个双向链表，但是列表的每个节点都是一个 ziplist，其实就是 linkedlist 和 ziplist 的结合。quicklist 中的每个节点 ziplist 都能够存储多个数据元素。
quicklist实现
接下去我们看下 quicklist 的具体实现。
quicklist 的定义如下：
typedef struct quicklist {
quicklistNode *head; // quicklist的头部
quicklistNode *tail; // quicklist的尾部
unsigned long count; // 列表中所有数据项的个数总和
unsigned int len; // quicklist节点的个数，即ziplist的个数
int fill : QL_FILL_BITS; // 16位，每个ziplist里的最大容量
unsigned int compress : QL_COMP_BITS; // 16位，quicklist的压缩深度
unsigned int bookmark_count: QL_BM_BITS;
quicklistBookmark bookmarks[];
} quicklist;这个结构占 40B 的空间，其中 int fill : 16 表示不用整个 int 存储 fill，而是只用了其中的 16 位来存储，和其他字段共用空间。
bookmarks 是一个可选字段，quicklist 重新分配内存空间时使用，不使用时不占用空间
quicklist 的节点 node 的定义如下：
typedef struct quicklistNode {
struct quicklistNode *prev; // 指向上一个ziplist节点
struct quicklistNode *next; // 指向下一个ziplist节点
unsigned char *zl; // 数据指针，如果没有被压缩，就指向ziplist结构，反之指向quicklistLZF结构
unsigned int sz; // 表示指向ziplist结构的总长度(内存占用长度)
unsigned int count : 16; // 表示ziplist中的数据项个数
unsigned int encoding : 2; // 编码方式，1--ziplist，2--quicklistLZF
unsigned int container : 2; // 预留字段，存放数据的方式，1--NONE，2--ziplist
unsigned int recompress : 1; // 解压标记，当查看一个被压缩的数据时，需要暂时解压，标记此参数为1，之后再重新进行压缩
unsigned int attempted_compress : 1; // 测试相关
unsigned int extra : 10; // 扩展字段，暂时没用
} quicklistNode;redis 为了节省内存空间，会将 quicklist 的节点用 LZF 压缩后存储，但这里不是全部压缩，可以配置 compress 的值。
为什么不全部节点都压缩，而是流出
compress这个可配置的口子呢？其实从统计来看，list两端的数据变更最为频繁，像lpush, rpush, lpop, rpop等命令都是在两端操作，如果频繁压缩或解压缩会代码不必要的性能损耗。因此一般两端不压缩，方便进出元素。中间压缩，节省体积。
压缩后的结构为：
typedef struct quicklistLZF {
unsigned int sz; /* LZF size in bytes*/
char compressed[];
} quicklistLZF;
插入的时候，需要判断下插入 ziplist 的长度。如果 ziplist 能够放入新元素，即大小没有超过 list-max-ziplist-size，那么直接插入。如果 ziplist 不能放入新元素，则新建一个 quicklist 节点，即新的 ziplist ，新的数据项会被插入到新的 ziplist ，新的节点插入到原有的 quicklist 上。
参考
Last updated