3. List

3.1 ziplist

​ ziplist是由一块连续的内存构成，列表中的节点没有类似链表节点中的next或prev指针，而是在每个节点中记录自身的字节长度以及其前驱节点的字节长度，从而进行指针移动。

一个ziplist可以包含多个节点（entry），每个节点可以保存一个长度有限的字符数组或者整数。其结构如下：

<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

• zlbytes：32bits，表示该ziplist占用的字节总数（也包括zlbytes本身占用的4个字节）。

• zltail：32bits，表示ziplist中最后一项（entry）在ziplist中的偏移字节数。zltail的存在可以让我们无需遍历整个ziplist就能很快地找到最后一项，从而进行rpush或rpop操作。

• zllen：16bits，表示ziplist中数据项（entry）的个数，注意上面两个都是字节数，而这个是个数。zllen字段最大可表示2^16-1 （65535）个。这里需要特别注意的是，如果ziplist中数据项个数超过了16bits能表达的最大值是不是zllen就作废了呢？细心的同学就能发现了，上面提到16bits最大可表示2^16-1（65535）个，那65536用来干什么？这里做了这样的规定：如果ziplist的entry个数小于65536那么zllen就表示真实的个数；如果大于等于65536的话，zllen就会定格成65536，这时候如果想知道ziplist中entry的个数，就必须对ziplist从头到位遍历各个数据项才能计算出来。

  tips：我们用redis的目的就是为了快，如果数据长度需要遍历，也就是O(n)的时间复杂度的话，redis作为一个单work线程的应用性能会大打折扣，所以在配置文件中 list-max-ziplist-value（默认是64）最好不要超过zllen能表示的最大值

• entry：表示真正存放数据的数据项，长度不定。这个内部结构比较复杂，我们单独在下面对这个部分进行解读。

• zlend：8bits，是个结束标记，恒等于255。

现在我们来展开entry相关构成，首先看一下zlentry结构体：

/* 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 {
    unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/
    unsigned int prevrawlen;     /* Previous entry 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. */
    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;            /* Pointer to the very start of the entry, that
                                    is, this points to prev-entry-len field. */
} zlentry;

• prevrawlensize：prevrawlen所需的字节数。
• prevrawlen：前一节点长度，通过该值可从当前节点位置跳转到上一个节点。
• lensize：len所需的字节数。
• len：当前节点所记录数据的长度。
• headersize：prevrawlensize + lensize
• encoding：4 bits，具体编码规则我们放到下面来解读。
• *p：指向节点入口处的指针，即 prev-entry-len 字段。

以上源码第一行备注就说了，这个结构体不是数据实际的编码方式，那实际的编码方式是什么呢？下面我们来看看实际的编码方式：

<prevlen> <encoding> <entry-data>

可以看出这个格式和上面的结构体还是很相似的。

prevlen：表示前一个数据项占用的总字节数。这个字段的用处是为了让ziplist能够从后向前遍历（从后一项的位置，只需向前偏移prevrawlen个字节，就找到了前一项）。这个字段采用变长编码。

encoding：表示当前数据项的数据长度（即entry-data部分的长度）。也采用变长编码。

那么这两者是如何进行变长编码的呢？这也是ziplist最繁琐的地方了。

先说prevlen，它有两种可能，要么是1个字节，要么是5个字节：

• 如果前一个数据项占用字节数小于254，那么prevlen就只用一个字节来表示，这个字节的值就是前一个数据项的占用字节数（最大值为253）。为什么这里是小于254而不是255呢？因为255已经被定义为ziplist的结束标记zlend的值了。
• 如果前一个数据项占用字节数大于254，那么prevlen就用5个字节来表示，其中第一个字节的值为254，以此作为标记，后面的4个字节组成一个整型值来存储这个数据项真正占用的字节数。

再来看看复杂的encoding：

1. 00xxxxxx 是最大长度位数为2^6 -1（63）的短字符串。
2. 01xxxxxx xxxxxxxx 是中等长度的字符串，最大可表示2^14 - 1个字符。
3. 10000000 xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx 是超长字符串，前两位是10，剩余6位不使用， 后面4个字节来表示字符串真实的长度，最大可表示2^32 - 1个字符（ziplist的上限就是这个值），这种超长字符串一般不会使用ziplist来存储，本身ziplist就是来存储小数据的。
4. 11000000 表示 int16，后面跟2个字节表示整数。
5. 11010000 表示 int32，后面跟4个字节表示整数。
6. 11100000 表示 int64，后面跟8个字节表示整数。
7. 11110000 表示 int24，后面跟3个字节表示整数。
8. 11111110 表示int8，后面跟1个字节表示整数。
9. 11111111 表示ziplist结束，即zlend。
10. 1111xxxx 表示极小整数，xxxx的范围只能是 0001~1101，也就是 1~13，因为0000、1110、1111都被占用了。这里的xxxx表示的是真正的数据，并不是数据长度了，也就是说上面的entry的结构中entry-data不存在了。这里是以小端序来记录，所以数据需要从0开始，因此这13个值分别表示0到12，即xxxx的值减去1才是它所要表示的那个整数数据的值。

总结一下：这里第 1~3 种encoding后面跟的是字符串，4~8表示整数，9表示ziplist的结束，10是一种特殊情况，表示0到12这13个数字。

✨ 插入或删除的级联更新需要重点讲一下

3.2 linkedlist

​ redis3.2版本之前的list是使用ziplist或者linkedlist（目前已经没用了）来实现的。也就是说当元素少的时候用ziplist，当元素多的时候就用linkedlist（具体看配置list-max-ziplist-value和list-max-ziplist-entries）。linkedlist其实就是一个双向链表，由于prev和next指针占用空间大，以及每个内存节点都需要单独分配会导致内存碎片化，后来就用quicklist代替了ziplist和linkedlist。

3.3 quicklist

​ 为了克服linkedlist前后指针占用空间大及容易产生内存碎片的问题，redis使用了quicklist来作为list的底层数据结构，quicklist可以简单的看成ziplist和linkedlist的结合体，也就是说本来linkedlist每个节点是一个元素，现在把这个元素换成了ziplist。这样的实现方式是在时间效率和空间效率之间做了折中，相比linkedlist更省空间，相比ziplist更加高效。

/* quicklist is a 40 byte struct (on 64-bit systems) describing a quicklist.
 * 'count' is the number of total entries.
 * 'len' is the number of quicklist nodes.
 * 'compress' is: -1 if compression disabled, otherwise it's the number
 *                of quicklistNodes to leave uncompressed at ends of quicklist.
 * 'fill' is the user-requested (or default) fill factor.
 * 'bookmakrs are an optional feature that is used by realloc this struct,
 *      so that they don't consume memory when not used. */

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;

该数据结构总共占40个字节

• head：指向头节点（左侧第一个节点）的指针
• tail：指向尾节点（右侧第一个节点）的指针
• count：所有的entry数量，这个参数也就是当我们查看列表个数的时候返回的值
• len：quicklistNode 个数
• fill：看上面一串叽叽歪歪的英文解释，其实就是配置文件里的list-max-ziplist-size值
• compress：首尾两端不被压缩的节点个数

/* quicklistNode is a 32 byte struct describing a ziplist for a quicklist.
 * We use bit fields keep the quicklistNode at 32 bytes.
 * count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually < 32k).
 * encoding: 2 bits, RAW=1, LZF=2.
 * container: 2 bits, NONE=1, ZIPLIST=2.
 * recompress: 1 bit, bool, true if node is temporarry decompressed for usage.
 * attempted_compress: 1 bit, boolean, used for verifying during testing.
 * extra: 10 bits, free for future use; pads out the remainder of 32 bits */

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    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;

该数据结构总共占32个字节

• prev：向前指针
• next：向后指针
• zl：ziplist或者是被压缩之后的ziplist(quicklistLZF)
• sz：ziplist的字节长度，不受压缩影响
• count：ziplist中包含的元素个数
• encoding：ziplist编码标示,1为原始数据,2为被压缩后数据
• container：数据存储方式(目前只有ziplist)
• recompress：需要再次被压缩标记，压缩节点被解压缩读取后会置为1
• attempted_compress：测试用例使用
• extra：额外字段，给未来使用

看了上面两个结构体，我们能对quicklist有个清晰的认识，不过提到了两个东西是比较模糊的，一个是list-max-ziplist-size，另一个是quicklistLZF（list-compress-depth），这两个都是redis配置文件“ADVANCED CONFIG”中的配置项。

list-max-ziplist-size：

• 正数时，表示ziplist所包含的最大entry个数
• 负数则有以下意义
  • -1 ziplist大小不超过4kb
  • -2 ziplist大小不超过8kb
  • -3 ziplist大小不超过16kb
  • -4 ziplist大小不超过32kb
  • -5 ziplist大小不超过64kb

list-compress-depth：

看这个配置名我们可以知道这是压缩深度，因为列表的常见的应用场景大多是访问两边的节点(例如:lpush, lpop, rpush, rpop等)，为了进一步的节省空间，快速列表提供了选项可以使用LZF压缩算法对中间的节点中的ziplist进行压缩，节点压缩后原本指向ziplist的sz指针元素指向quicklistLZF结构体。 快速列表两边分别有几个节点不被压缩有配置项 list-compress-depth 决定，存储在qulicklist的compress元素中，默认为0(不进行节点压缩)。

问题：

如果list-max-ziplist-size设置成-2，那么万一有一个key大于8KB怎么办？

测试结果显示 -> 只会存储8KB，多的部分直接删掉，也就是说list-max-ziplist-size限制了每个节点的大小不能超过它，如果有大的数据要存储的话，这里不注意很容易引起数据丢失哦~

最后还是回到RedisObject中，我们看见list其实包含了三种encoding，分别是：OBJ_ENCODING_LINKEDLIST（新版已经不用了）、OBJ_ENCODING_ZIPLIST（新版不用这个来单独存储list结构了）、OBJ_ENCODING_QUICKLIST

3.4 listpack

用于替代ziplist的数据结构，比较新，还有些时日才能成熟。