1.2 list - 图1

list	ziplist (压缩列表）
	quicklist （快速列表）

在低版本的Redis 中，链表和压缩列表是 Redis list对象的底层实现方式，但是考虑到链表的附加空间相对很高，prev和next指针就要占去16个字节（64bit系统的指针是8bytes）, 另外每个节点的内存都是单独分配，会加剧内存的碎片化，影响内存管理效率。因此Redis 3.2 版本开始对列表数据结构进行了改造，使用 quicklist 代替了 ziplist 和 linkedlist.

在Redis3.2版本以前列表类型的内部编码有两种。

ziplist（压缩列表）：当列表的元素个数小于list-max-ziplist-entries配置（默认512个），同时列表中每个元素的值都小于list-max-ziplist-value配置时（默认64字节），Redis会选用ziplist来作为列表的内部实现来减少内存的使用。
linkedlist（链表）：当列表类型无法满足ziplist的条件时，Redis会使用linkedlist作为列表的内部实现。

在Redis3.2版本开始对列表数据结构进行了改造，使用 quicklist 代替了 ziplist 和 linkedlist.

1.内部结构

1.1 双向链表（adlist.h/adlist.c)

双向链表

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;
typedef struct listIter {
    listNode *next;
    int direction;
} listIter;
typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;

1.2 list - 图2
1.2 list - 图3

Redis链表结构其主要特性如下:

双向：链表节点带有前驱、后继指针获取某个节点的前驱、后继节点的时间复杂度为0(1)。
无环: 链表为非循环链表表头节点的前驱指针和表尾节点的后继指针都指向NULL，对链表的访问以NULL为终点。
带表头指针和表尾指针：通过list结构中的head和tail指针，获取表头和表尾节点的时间复杂度都为O(1)。
带链表长度计数器:通过list结构的len属性获取节点数量的时间复杂度为O(1)。
多态：链表节点使用void*指针保存节点的值，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用来保存各种不同类型的值。

1.2 压缩列表(ziplist.c/ziplist.h)

1.2.1 何为压缩

听到“压缩”两个字，直观的反应就是节省内存。之所以说这种存储结构节省内存,是相较于数组的存储思路而言的。我们知道,数组要求每个元素的大小相同,如果我们要存储不同长度的字符串,那我们就需要用最大长度的字符串大小作为元素的大小(假设是20个字节)。存储小于 20 个字节长度的字符串的时候，便会浪费部分存储空间。

1.2 list - 图4

数组的优势占用一片连续的空间可以很好的利用CPU缓存访问数据。如果我们想要保留这种优势，又想节省存储空间我们可以对数组进行压缩。

1.2 list - 图5

但是这样有一个问题，我们在遍历它的时候由于不知道每个元素的大小是多少，因此也就无法计算出下一个节点的具体位置。这个时候我们可以给每个节点增加一个lenght的属性。

1.2 list - 图6
如此。我们在遍历节点的之后就知道每个节点的长度(占用内存的大小)，就可以很容易计算出下一个节点再内存中的位置。这种结构就像一个简单的压缩列表了。

1.2.2 Redis的压缩列表实现

当一个列表只包含少量列表项,并且每个列表项要么就是小整数值,要么就是长度比较短的字符串,那么Redis就会使用压缩列表来做列表的底层实现；

/* Return total bytes a ziplist is composed of. */
#define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl))) 
/* Return the offset of the last item inside the ziplist. */
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
/* Return the length of a ziplist, or UINT16_MAX if the length cannot be
 * determined without scanning the whole ziplist. */
#define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
/* The size of a ziplist header: two 32 bit integers for the total
 * bytes count and last item offset. One 16 bit integer for the number
 * of items field. */
#define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))
/* Size of the "end of ziplist" entry. Just one byte. */
#define ZIPLIST_END_SIZE        (sizeof(uint8_t))
/* Return the pointer to the first entry of a ziplist. */
#define ZIPLIST_ENTRY_HEAD(zl)  ((zl)+ZIPLIST_HEADER_SIZE)
/* Return the pointer to the last entry of a ziplist, using the
 * last entry offset inside the ziplist header. */
#define ZIPLIST_ENTRY_TAIL(zl)  ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))
/* Return the pointer to the last byte of a ziplist, which is, the
 * end of ziplist FF entry. */
#define ZIPLIST_ENTRY_END(zl)   ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)
/* Increment the number of items field in the ziplist header. Note that this
 * macro should never overflow the unsigned 16 bit integer, since entries are
 * always pushed one at a time. When UINT16_MAX is reached we want the count
 * to stay there to signal that a full scan is needed to get the number of
 * items inside the ziplist. */
#define ZIPLIST_INCR_LENGTH(zl,incr) { \
    if (ZIPLIST_LENGTH(zl) < UINT16_MAX) \
        ZIPLIST_LENGTH(zl) = intrev16ifbe(intrev16ifbe(ZIPLIST_LENGTH(zl))+incr); \
}
/* We use this function to receive information about a ziplist entry.
 * Note that this is not how the data is actually encoded, is just what we
 * get filled by a function in order to operate more easily. */
typedef struct zlentry {
    //prevrawlen 前驱节点的长度
    //prevrawlensize 编码前驱节点的长度prevrawlen所需要的字节大小
    unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/
    unsigned int prevrawlen;     /* Previous entry len. */
    //len 当前节点值长度
    //lensize 编码当前节点长度len所需的字节数
    unsigned int lensize;        /* Bytes used to encode this entry type/len.
                                    For example strings have a 1, 2 or 5 bytes
                                    header. Integers always use a single byte.*/
    unsigned int len;            /* Bytes used to represent the actual entry.
                                    For strings this is just the string length
                                    while for integers it is 1, 2, 3, 4, 8 or
                                    0 (for 4 bit immediate) depending on the
                                    number range. */
    //当前节点header的大小 = lensize + prevrawlensize
    unsigned int headersize;     /* prevrawlensize + lensize. */
    //当前节点的编码格式
    unsigned char encoding;      /* Set to ZIP_STR_* or ZIP_INT_* depending on
                                    the entry encoding. However for 4 bits
                                    immediate integers this can assume a range
                                    of values and must be range-checked. */
    unsigned char *p;//指向 开始的entry指针            /* Pointer to the very start of the entry, that
                                    is, this points to prev-entry-len field. */
} zlentry;

压缩列表是Redis为了节约内存而开发的,是由一系列特殊编码的连续内存块组成的顺序型(sequential)数据结枃。一个压缩列表可以包含任意多个节点(entry),每个节点可以保存一个字节数组或者一个整数值，如下图。

1.2 list - 图7

1.2 list - 图8

虽然定义了这个zlentry结构体，但是根本就没有使用zlentry结构来作为压缩列表中用来存储数据节点中的结构，但是。因为，这个结构存小整数或短字符串实在是太浪费空间了。这个结构总共在32位机占用了28个字节(32位机)，在64位机占用了32个字节。这不符合压缩列表的设计目的：提高内存的利用率。因此，在redis中，并没有定义结构体来进行操作，也是定义了一些宏，压缩列表的节点真正的结构如下图所示：
1.2 list - 图9

prev_entry_len：记录前驱节点的长度。
encoding：记录当前节点的value成员的数据类型以及长度。
value：根据encoding来保存字节数组或整数。
1.2.2.1 previous_entry_length

previousentrylength成员实际上就是zlentry结构中prevrawlensize,和prevrawlen**这两个成员的压缩版**
用于存储上一个节点的长度，因此压缩列表可以从尾部向头部遍历，即当前节点位置减去上一个节点的长度即得到上一个节点的起始位置。

节点的 previous_entry_length属性以字节为单位,记录了压缩列表中前一个节点的长度。 previous_entry_length属性的长度可以是1字节或者5字节。

如果前一节点的长度小于254,那么 previous_entry_length属性的长度为1字节（8bits , 2^8=256），前一节点的长度就保存在这一个字节里面。
如果前一节点的长度大于等于254,那么 previous_entry_length属性的长度为5字节:其中属性的第一字节会被设置为0xFE(十进制值254),后四个字节才是真正保存前驱节点的长度值。
为啥要这么搞呢？
因为，对于访问的指针都是char 类型，它能访问的范围1个字节，如果这个字节的大小等于0xFE，那么就会继续访问四个字节来获取前驱节点的长度，如果该字节的大小小于0xFE，那么该字节就是要获取的前驱节点的长度。因此这样就使prev_entry_len同时具有了prevrawlen和prevrawlensize的功能，而且更加节约内存。

举例说明下逻辑：（转载：http://redisbook.com/preview/ziplist/node.html#previous-entry-length）

图 7-5 展示了一个包含一字节长 previous_entry_length 属性的压缩列表节点，属性的值为 0x05 ，表示前一节点的长度为 5 字节。
1.2 list - 图10

图 7-6 展示了一个包含五字节长 previous_entry_length 属性的压缩节点，属性的值为 0xFE00002766 ，其中值的最高位字节 0xFE 表示这是一个五字节长的 previous_entry_length 属性，而之后的四字节 0x00002766 （十进制值 10086 ）才是前一节点的实际长度。

1.2 list - 图11
**

1.2.2.2 encoding

节点的 encoding 属性记录了节点的 content 属性所保存数据的类型以及长度：

一字节、两字节或者五字节长，值的最高位为 00 、 01 或者 10 的是字节数组编码：这种编码表示节点的 content 属性保存着字节数组，数组的长度由编码除去最高两位之后的其他位记录；
一字节长，值的最高位以 11 开头的是整数编码：这种编码表示节点的 content 属性保存着整数值，整数值的类型和长度由编码除去最高两位之后的其他位记录；

表 7-2 记录了所有可用的字节数组编码，而表 7-3 则记录了所有可用的整数编码。表格中的下划线 _ 表示留空，而 b 、 x 等变量则代表实际的二进制数据，为了方便阅读，多个字节之间用空格隔开。

表 7-2 字节数组编码

编码	编码长度	`content` 属性保存的值
`00bbbbbb（2^6-1=63）`	`1` 字节	长度小于等于 `63` 字节的字节数组。
`01bbbbbb xxxxxxxx（2^14-1=16383）`	`2` 字节	长度小于等于 `16383` 字节的字节数组。
`10______ aaaaaaaa bbbbbbbb cccccccc dddddddd`	`5` 字节	长度小于等于 `4294967295` 的字节数组。

表 7-3 整数编码

编码	编码长度	`content` 属性保存的值
`11000000`	`1` 字节	`int16_t` 类型的整数。
`11010000`	`1` 字节	`int32_t` 类型的整数。
`11100000`	`1` 字节	`int64_t` 类型的整数。
`11110000`	`1` 字节	`24` 位有符号整数。
`11111110`	`1` 字节	`8` 位有符号整数。
`1111xxxx`	`1` 字节	使用这一编码的节点没有相应的 `content` 属性，因为编码本身的 `xxxx` 四个位已经保存了一个介于 `0` 和 `12` 之间的值，所以它无须 `content` 属性。

1.2.2.3 value

节点的 content 属性负责保存节点的值，节点值可以是一个字节数组或者整数，值的类型和长度由节点的 encoding 属性决定。
图 7-9 展示了一个保存字节数组的节点示例：

编码的最高两位 00 表示节点保存的是一个字节数组；
编码的后六位 001011 记录了字节数组的长度 11 ；
content 属性保存着节点的值 "hello world" 。

1.2 list - 图12
图 7-10 展示了一个保存整数值的节点示例：

编码 11000000 表示节点保存的是一个 int16_t 类型的整数值；
content 属性保存着节点的值 10086 。
1.2.3 连锁更新

http://redisbook.com/preview/ziplist/cascade_update.html

1.3 快速列表(quicklist.c/quicklist.h)

1.2 list - 图14

1.3.1 组成结构

1.3.1.1 quicklistNode

typedef struct quicklistNode {
    struct quicklistNode *prev; //上一个node节点
    struct quicklistNode *next; //下一个node
    unsigned char *zl;            //保存的数据 压缩前ziplist 压缩后压缩的数据
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

prev: 指向链表前一个节点的指针。
next: 指向链表后一个节点的指针。
zl: 数据指针。如果当前节点的数据没有压缩，那么它指向一个ziplist结构；否则，它指向一个quicklistLZF结构。
sz: 表示zl指向的ziplist的总大小（包括zlbytes, zltail, zllen, zlend和各个数据项）。需要注意的是：如果ziplist被压缩了，那么这个sz的值仍然是压缩前的ziplist大小。
count: 表示ziplist里面包含的数据项个数。这个字段只有16bit。稍后我们会一起计算一下这16bit是否够用。
encoding: 表示ziplist是否压缩了（以及用了哪个压缩算法）。目前只有两种取值：2表示被压缩了（而且用的是LZF压缩算法），1表示没有压缩。
container: 是一个预留字段。本来设计是用来表明一个quicklist节点下面是直接存数据，还是使用ziplist存数据，或者用其它的结构来存数据（用作一个数据容器，所以叫container）。但是，在目前的实现中，这个值是一个固定的值2，表示使用ziplist作为数据容器。
recompress: 当我们使用类似lindex这样的命令查看了某一项本来压缩的数据时，需要把数据暂时解压，这时就设置recompress=1做一个标记，等有机会再把数据重新压缩。
attempted_compress: 这个值只对Redis的自动化测试程序有用。我们不用管它。
extra: 其它扩展字段。目前Redis的实现里也没用上。

1.3.1.2 quciklistLZF

typedef struct quicklistLZF {
    unsigned int sz; /* LZF size in bytes*/
    char compressed[];
} quicklistLZF;

quicklistLZF结构表示一个被压缩过的ziplist。其中：

sz: 表示压缩后的ziplist大小。

compressed: 是个柔性数组（flexible array member），存放压缩后的ziplist字节数组

1.3.1.3 quicklist

typedef struct quicklist {
  quicklistNode *head;
  quicklistNode *tail;
  unsigned long count;        /* total count of all entries in all ziplists */
  unsigned long len;          /* number of quicklistNodes */
  int fill : QL_FILL_BITS;              /* fill factor for individual nodes */
  unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
  unsigned int bookmark_count: QL_BM_BITS;
  quicklistBookmark bookmarks[];
} quicklist;

head: 指向头节点（左侧第一个节点）的指针。
tail: 指向尾节点（右侧第一个节点）的指针。
count: 所有ziplist数据项的个数总和。
len: quicklist节点的个数。
fill: 16bit，ziplist大小设置，存放list-max-ziplist-size参数的值。(从而限制entry个数）
compress: 16bit，节点压缩深度设置，存放list-compress-depth参数的值。

2.常用命令

BLPOP key [key …] timeout	删除，并获得该列表中的第一元素，或阻塞，直到有一个可用	O(1)
BRPOP key [key …] timeout	删除，并获得该列表中的最后一个元素，或阻塞，直到有一个可用	O(1)
BRPOPLPUSH source destination timeout	弹出一个列表的值，将它推到另一个列表，并返回它;或阻塞，直到有一个可用	O(1)
LINDEX key index	获取一个元素，通过其索引列表	O(N)
LINSERT key BEFORE	AFTER pivot value在列表中的另一个元素之前或之后插入一个元素	O(N)
LLEN key	获得队列(List)的长度	O(1)
LPOP key	从队列的左边出队一个元素	O(1)
LPUSH key value [value …]	从队列的左边入队一个或多个元素	O(1)
LPUSHX key value	当队列存在时，从队到左边入队一个元素	O(1)
LRANGE key start stop	从列表中获取指定返回的元素	O(S+N)
LREM key count value	从列表中删除元素	O(N)
LSET key index value	设置队列里面一个元素的值	O(N)
LTRIM key start stop	修剪到指定范围内的清单	O(N)
RPOP key	从队列的右边出队一个元	O(1)
RPOPLPUSH source destination	删除列表中的最后一个元素，将其追加到另一个列表	O(1)
RPUSH key value [value …]	从队列的右边入队一个元素	O(1)
RPUSHX key value	从队列的右边入队一个元素，仅队列存在时有效	O(1)

3.使用场景

关于列表的使用场景可参考以下几个命令组合：

lpush+lpop=Stack（栈）
lpush+rpop=Queue（队列）
lpush+ltrim=Capped Collection（有限集合）
lpush+brpop=Message Queue（消息队列）
3.1 消息队列
列表类型可以使用 rpush 实现先进先出的功能，同时又可以使用 lpop 轻松的弹出（查询并删除）第一个元素，所以列表类型可以用来实现消息队列;
可以作为基础中间件使用；
3.2 文章(订单，商品等)列表
为了加快程序的响应速度，可以将订单及文章存到缓存中，前端列表展示，但是需要保证的是后台业务对该订单变动时，保证同步修改缓存，或者让缓存失效，重新从数据库查。

引用

https://www.cnblogs.com/hunternet/p/12671125.html
http://redisbook.com/preview/ziplist/node.html
https://zhuanlan.zhihu.com/p/71880195
https://blog.csdn.net/men_wen/article/details/70176753

1.2 list