[TOC] ## 概述 Redis中的List是一个有序（按加入的时序排序）的数据结构，一般有序我们会采用数组或者是双向链表，其中双向链表由于有前后指针实际上会很浪费内存, 3.2版本之前采用两种数据结构作为底层实现： * 压缩列表ziplist： `ziplist`存储在一段连续的内存上，所以存储效率很高。但是，它不利于修改操作，插入和删除操作需要频繁的申请和释放内存。特别是当`ziplist`长度很长的时候，一次`realloc`可能会导致大批量的数据拷贝。 * 双向链表linkedlist：双向链表`linkedlist`便于在表的两端进行`push`和`pop`操作，在插入节点上复杂度很低，但是它的内存开销比较大。首先，它在每个节点上除了要保存数据之外，还要额外保存两个指针；其次，双向链表的各个节点是单独的内存块，地址不连续，节点多了容易产生内存碎片。 3.2版本之后升级为quicklist。`ziplist`会引入频繁的内存申请和释放，而linkedlist由于指针也会造成内存的浪费，而且每个节点是单独存在的，会造成很多内存碎片，所以结合两个结构的特点，设计了quickList。 `quickList` 是一个 `ziplist` 组成的双向链表。每个节点使用 `ziplist` 来保存数据。本质上来说，`quicklist` 里面保存着一个一个小的 `ziplist`。  ## quicklist数据结构 ``` 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; 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; ``` `quicklistNode`结构为节点类型： * prev：指向前驱节点 * next：指向后继节点 * zl：指向对应的压缩列表 * sz：压缩列表的大小 * encoding：采用的编码方式，1为原生，2代表使用LZF进行压缩 * container：为节点指向的容器类型，1代表none，2代表ziplist存储数据 * recompress：代表这个节点是否是压缩节点，如果是，则使用压缩节点前先进行解压缩，使用后重新压缩 * attempted_compress：测试时使用 `quicklist`结构为双向链表类型： * head：指向头节点 * tail：指向尾节点 * count：quicklist中压缩列表的entry总数 * len：节点个数 * fill：每个节点的ziplist长度，可以通过参数`list-max-ziplist-size`配置节点所占内存大小 * compress：该值表示两端各有compress个节点不压缩 ## 参数配置 ### list-max-ziplist-size ``` list-max-ziplist-size -2 ``` * 当取正值的时候，表示按照数据项个数来限定每个quicklist节点上的ziplist长度。比如，当这个参数配置成5的时候，表示每个quicklist节点的ziplist最多包含5个数据项。 * 当取负值的时候，表示按照占用字节数来限定每个quicklist节点上的ziplist长度。这时，它只能取-1到-5这五个值，每个值含义如下： * \-5: 每个quicklist节点上的ziplist大小不能超过64 Kb。（注：1kb => 1024 bytes） * \-4: 每个quicklist节点上的ziplist大小不能超过32 Kb。 * \-3: 每个quicklist节点上的ziplist大小不能超过16 Kb。 * \-2: 每个quicklist节点上的ziplist大小不能超过8 Kb。（-2是Redis给出的默认值） * \-1: 每个quicklist节点上的ziplist大小不能超过4 Kb。 ### list-compress-depth ``` list-compress-depth 0 ``` **这个参数表示一个quicklist两端不被压缩的节点个数**。注：这里的节点个数是指quicklist双向链表的节点个数，而不是指ziplist里面的数据项个数。实际上，一个quicklist节点上的ziplist，如果被压缩，就是整体被压缩的。 * 0: 是个特殊值，表示都不压缩。这是Redis的默认值。 * 1: 表示quicklist两端各有1个节点不压缩，中间的节点压缩。 * 2: 表示quicklist两端各有2个节点不压缩，中间的节点压缩。 * 3: 表示quicklist两端各有3个节点不压缩，中间的节点压缩。 * 依此类推… 由于0是个特殊值，很容易看出quicklist的头节点和尾节点总是不被压缩的，以便于在表的两端进行快速存取。Redis对于quicklist内部节点的压缩算法，采用的[LZF](http://oldhome.schmorp.de/marc/liblzf.html)——一种无损压缩算法。 ## 优点 结合了list和ziplist的优点。quicklist表示的是一个链表节点里存放的是一个ziplist。 ## 应用场景 redis3.2版本后的list数据结构底层用的是quicklist