redislist底层数据结构（zipList）

　　redis-list底层数据结构
　　前面学习解了redis的简单字符串sds的结构。这次来学习下List的底层数据结构 总概
　　Redis中list底层实现有三种 linkedList zipList quickList linkedList
　　与java中的linkedList类似。 // 定义链表节点的结构体  typedf struct listNode{     //前一个节点     struct listNode *prev;     //后一个节点     struct listNode *next;     //当前节点的值的指针     void *value; }listNode;  // 链表结构 typedf struct list{     // 头指针，即指向链表头部节点     listNode *head;     // 尾指针，指向尾部节点     listNode *tail;     // 节点拷贝函数     void *(*dup)(void *ptr);     // 释放节点函数     void *(*free)(void *ptr);     // 判断两个节点是否相等的函数     int (*match)(void *ptr,void *key);     // 链表长度     unsigned long len; }zipListzipList的数据结构typedf struct ziplist{     // 压缩列表占用字符数     int32 zlbytes;     // 最后一个元素距离起始位置的偏移量，用于快速定位最后一个节点     // 通过这个参数可以支持双向访问     int32 zltail_offset;     // 元素个数     int16 zllength;     // 元素内容     T[] entries;     // 结束位 0xFF     int8 zlend; }ziplist;  // entry typede struct entry{     // 前一个entry的长度     int prelen;     // 元素类型编码     int encoding;     // 元素内容     optional byte[] content; }entry;
　　entry解析：
　　prelen保存的是前一个entry节点的长度，这样在倒序遍历时就可以通过这个参数定位到上一个entry的位置。encoding保存了content的编码类型。content则是保存的元素内容，它是optional类型的，表示这个字段是可选的。当content是很小的整数时，它会内联到content字段的尾部。entry结构的示意图如下所示：
　　zipList遍历时，先根据zlbytes和zltail_offset定位到最后一个entry的位置，然后再根据最后一个entry里的prelen时确定前一个entry的位置。 zipList的连锁更新
　　entry中prelen字段，它的长度要么是1个字节，要么都是5个字节： 前一个节点的长度小于254个字节，则prelen长度为1字节； 前一个节点的长度大于254字节，则prelen长度为5字节；
　　假设现在有一组压缩列表，长度都在250~253字节之间，突然新增一个entry节点，这个entry节点长度大于等于254字节。由于新的entry节点大于等于254字节，这个entry节点的prelen为5个字节，随后会导致其余的所有entry节点的prelen增大为5字节。
　　同样地，删除操作也会导致出现 连锁更新 这种情况，假设在某一时刻，插入一个长度大于等于254个字节的entry节点，同时删除其后面的一个长度小于254个字节的entry节点，由于小于254的entry节点的删除，大于等于254个字节的entry节点将会与后面小于254个字节的entry节点相连，此时就与新增一个长度大于等于254个字节的entry节点时的情况一样，将会发生连续更新。发生连续更新时，Redis需要不断地对压缩列表进行 内存分配工作 ，直到结束。 linkedList和zipList对比zipList相比于linkedList，其少了pre和next两个指针。在Redis中，pre和next指针就要占用16个字节（64位系统的一个指针就是8个字节）。另外，linkedList的每个节点的内存都是单独分配，加剧内存的碎片化，影响内存的管理效率。与之相对的是，zipList是由连续的内存组成的，这样一来，由于内存是连续的，就减少了许多内存碎片和指针的内存占用，进而节约了内存。 linkedList便于在表的两端进行push和pop操作，在插入节点上复杂度很低，但是它的内存开销比较大。zipList存储在一块连续的内存上，所以存储效率很高。但是它不利于修改操作，插入和删除操作需要频繁地申请和释放内存。
　　因此当列表对象中元素的长度较小或者数量较少时，通常采用zipList来存储；当列表中元素的长度较大或者数量比较多的时候，则会转而使用双向链表linkedList来存储。 quickList
　　Redis3.2版本之后，list的底层实现方式又多了一种，quickList。qucikList是由zipList和双向链表linkedList组成的混合体。它将linkedList按段切分，每一段使用zipList来紧凑存储，多个zipList之间使用双向指针串接起来。示意图如下所示：
　　typedf struct quicklistNode{     //前一个节点     quicklistNode* prev;     //后一个节点     quicklistNode* next;     //压缩列表     ziplist* zl;         //ziplist大小     int32 size;          //ziplist 中元素数量     int16 count;     //编码形式 存储 ziplist 还是进行 LZF 压缩储存的zipList     int2 encoding;               ... }quickListNode;  typedf struct quicklist{     //指向头结点     quicklistNode* head;     //指向尾节点     quicklistNode* tail;     //元素总数     long count;     //quicklistNode节点的个数     int nodes;       //压缩算法深度     int compressDepth;           ... }quickList;quckList中zipList大小
　　打开redis.conf文件了。在DVANCED CONFIG下面有着清晰的记载。 # Lists are also encoded in a special way to save a lot of space. # The number of entries allowed per internal list node can be specified # as a fixed maximum size or a maximum number of elements. # For a fixed maximum size, use -5 through -1, meaning: # -5: max size: 64 Kb  <-- not recommended for normal workloads # -4: max size: 32 Kb  <-- not recommended # -3: max size: 16 Kb  <-- probably not recommended # -2: max size: 8 Kb   <-- good # -1: max size: 4 Kb   <-- good # Positive numbers mean store up to _exactly_ that number of elements # per list node. # The highest performing option is usually -2 (8 Kb size) or -1 (4 Kb size), # but if your use case is unique, adjust the settings as necessary. list-max-ziplist-size -2
　　quickList内部默认单个zipList长度为 8k 字节，即list-max-ziplist-size的值设置为 -2 ，超出了这个阈值，就会重新生成一个zipList来存储数据。根据注释可知，性能最好的时候就是就是list-max-ziplist-size为 -1 和 -2 ，即分别是 4kb和8kb 的时候，当然，这个值也可以被设置为正数，当list-max-ziplist-szie为 正数n 时，表示每个quickList节点上的zipList最多包含 n个 数据项。 压缩深度
　　quickList中可以使用压缩算法对zipList进行进一步的压缩，这个算法就是 LZF算法 ，这是一种无损压缩算法，具体可以参考这里。使用压缩算法对zipList进行压缩后，zipList的结构如下所示： typedf struct ziplist_compressed{     //元素个数     int32 size;     //元素内容     byte[] compressed_data }
　　在redis.conf文件中的DVANCED CONFIG下面也可以对压缩深度进行配置。 # Lists may also be compressed. # Compress depth is the number of quicklist ziplist nodes from *each* side of # the list to *exclude* from compression.  The head and tail of the list # are always uncompressed for fast push/pop operations.  Settings are: # 0: disable all list compression # 1: depth 1 means ＂don＂t start compressing until after 1 node into the list, #    going from either the head or tail＂ #    So: [head]->node->node->...->node->[tail] #    [head], [tail] will always be uncompressed; inner nodes will compress. # 2: [head]->[next]->node->node->...->node->[prev]->[tail] #    2 here means: don＂t compress head or head->next or tail->prev or tail, #    but compress all nodes between them. # 3: [head]->[next]->[next]->node->node->...->node->[prev]->[prev]->[tail] # etc. list-compress-depth 0
　　list-compress-depth这个参数表示 一个quickList两端不被压缩的节点个数。 需要注意的是，这里的节点个数是指quicklist双向链表的节点个数，而不是指ziplist里面的数据项个数。实际上，一个quicklist节点上的ziplist，如果被压缩，就是整体被压缩的。 quickList默认的压缩深度为 0 ，也就是不开启压缩 当list-compress-depth为1，表示quickList的两端各有1个节点不进行压缩，中间结点进行压缩； 当list-compress-depth为2，表示quickList的首尾2个节点不进行压缩，中间结点进行压缩； 以此类推 小结
　　封面图侵权删