二.Redis中那些你不知道的秘密-五大基本结构List的实现原理

前言

Redis中的List也是一种非常常用的存储结构，它和Java中的List结构类似，通常用来存储一个列表或者作为队列实现，在Redis 3.2之前，list采用了两种数据结构作为底层实现：压缩列表ziplist以及双向链表adlist，在3.2之后，使用quicklist替代，本篇文章将带你了解Redis底层的三种存储结构。

双向链表adlist

C 语言没有内置这种数据结构的实现，Redis构建了自己的链表结构,一个元素结构如下：(点我查看源码地址)

/* Node, List, and Iterator are the only data structures used currently. */
typedef struct listNode {
   
   
    struct listNode *prev;    //上一元素
    struct listNode *next;    //下一元素
    void *value;    //元素值
} listNode;

多个listNode组成了一个双向链表结构，以及提供了相关的链表操作的函数，如下：

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;

图例：

Redis的链表是一个双端链表结构，它有如下特点：

• 无环的结构(尾的next没有指向头，头的prev没有指向尾)
• 在list中维护了len很方便的可以取到链表的长度，复杂度是o(1)
• 使用void* 指针保存元素的值可以保存各种类型的值
• 对链表的表头和表尾进行插入的复杂度都为 o(1)

但是链表的缺点也是比较明显的，就是链表的附加空间比较高，在数据较小的时候会造成空间的浪费，prev和next就需要占用16个字节(64bit的系统，指针8字节)，每个元素的内存是独立分配的，不要求连续性，会增加内存的碎片化，影响内存管理效率。所以它不适合存储少量或者小数据。所以Redis在列表对象中小数据量的时候使用压缩列表ziplist作为底层实现。

压缩列表ziplist

ziplist本质上就是一个字节数组，是Redis为了解决内存而设计的一种线性数据结构，Redis中的有序集合，散列，列表都直接或者间接使用到了压缩列表。在Redis源码中有这么一段注释对ziplist做了解释：ziplist源码

The ziplist is a specially encoded dually linked list that is designed to be very memory efficient. It stores both strings and integer values, where integers are encoded as actual integers instead of a series of characters. It allows push and pop operations on either side of the list in O(1) time. However, because every operation requires a > reallocation of the memory used by the ziplist, the actual complexity is related to the amount of memory used by the ziplist.

大致意思是：ziplist是一个特殊编码的双向链表，它非常节省内存，一个压缩列表可以包含任意多个元素（entry），每个元素可以保存一个字节数组或者一个整数值，它允许在列表的任意一侧进行push 和pop 操作，时间复杂度是o(1)。

注意：搞清楚一个概念，压缩列表并不是按照某种算法对数据进行压缩，而是通过一定的规则把数据编码在一段连续的内存空间，来达到节约内存的目的。

ziplist的结构

那么这个压缩列表到底长成什么样子呢？这里我从Redis源码的注释中找到了答案,ziplist的总体布局如下:

The general layout of the ziplist is as follows:

• <zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
  NOTE: all fields are stored in little endian, if not specified otherwise.
• is an unsigned integer to hold the number of bytes that
  the ziplist occupies, including the four bytes of the zlbytes field itself.
  This value needs to be stored to be able to resize the entire structure
  without the need to traverse it first.
  是一个无符号整数，用于保存ziplist数据，zlbytes字段本身的四个字节
• is the offset to the last entry in the list. This allows
  a pop operation on the far side of the list without the need for full
  traversal.
  是到列表中最后一个条目的偏移量。这允许在列表的远端进行的弹出操作，不需要完全遍历
• is the number of entries. When there are more than
  2^16-2 entries, this value is set to 2^16-1 and we need to traverse the
  entire list to know how many items it holds.
  是条目数。当有超过 2^16-2个条目，此值设置为2^16-1，我们需要遍历完整的列表来知道它包含多少项
• is a special entry representing the end of the ziplist.
  Is encoded as a single byte equal to 255. No other normal entry starts
  with a byte set to the value of 255.
  是表示ziplist结尾的特殊条目

图例：

解释：

• zlbytes: 压缩列表的字节长度，占4个字节
• zltail:压缩列表尾元素相对于压缩列表起始地址的偏移量，占4字节
• zllen: 压缩列表的元素个数，占用2个字节
• entry:压缩列表存储的元素，可以是字节数组或者整数
• zlend:压缩列表的结尾，占用1字节

ziplist元素结构

根据压缩列表的结构，我们可以很容易的获取到列表的长度，元素个数。那么压缩列表是如何遍历的呢？在此之前我们来了解一下压缩列表元素的编码结构,下面是Redis源码中对元素的描述：

ZIPLIST ENTRIES 压缩列表的元素条目
Every entry in the ziplist is prefixed by metadata that contains two pieces of information. First, the length of the previous entry is stored to be able to traverse the list from back to front. Second, the entry encoding is provided. It represents the entry type, integer or string, and in the case of strings it also represents the length of the string payload. So a complete entry is stored like this:
<prevlen> <encoding> <entry-data>
ziplist中的每个元素都以包含两部分的元数据为前缀信息，首先，将前一个元素的长度存储为
previous entry lenth ，能够实现从后到前遍历列表。其次，条目编码endoding是表示条目类型，整数或字符串，在case中它还表示字符串负载的长度。所以一个完整的条目是这样存储的<prevlen> <encoding> <entry-data>

解释：

• previous_entry_length

  表示的是前一个元素的字节长度，如果前一元素的长度小于254 字节，用1字节长的空间来保存这个长度值。如果前一元素的长度大于等于254 字节，用5 字节长的空间来保存这个长度值。

  根据该长度可以计算出前一个元素的地址，当前元素的地址减去上一个元素的长度previous_entry_length即得到上一个元素的起始地址(思考一下如何向后遍历呢？)，所以该值可以用来实现表为向表头遍历。这种设计非常节约内存，不需要额外的空间维护prev和next指向。

• encoding:表示当前元素的编码，即conent字段存储的数据类型和长度，整数或者字节数组
• content:数据的内容存储在content中，值的类型和长度由元素的encoding属性决定。

所以你应该明白了为什么说ziplist 是一个特殊的双向链表，它没有维护双向指针:prev nex，依然可以实现如同双向链表一样向前或者向后的遍历效果，就是因为previous_entry_length的设计。

这里需要注意一下，对于压缩列表的元素而言，获取前一个元素长度，判断存储类型，获取数据内容都是需要进行解码运算的，因此Redis定义了zlentry 来缓存解码后的结构体,看一下他的源码：

/*
我们使用此功能来接收有关ziplist条目的信息。请注意，这并不是实际编码数据的方式，这只是我们
由函数填充以便更轻松地操作。
 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 {
   
   
    //prevrawlensize是previous_entry_length字段的长度，有1字节和5字节两种
    unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/
    //上一个元素的长度
    unsigned int prevrawlen;     /* Previous entry len. */
    //encoding字段的长度
    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. */
    //当前元素的首部元素大小 prevrawlensize + lensize
    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;

解释：

• prevrawlen ： 是指前一个元素的长度
• prevrawlensize ： 编码前元素prevrawlen所需要的字节大小
• lensize ：当前元素值长度len所需要的字节数，
• len ：当前元素长度，
• headersize ：当前元素header大小（lensize+prevrawlensize），
• encoding 为当前元素的编码格式，
• *p 只想当前元素的指针

ziplist连锁更新

什么是连锁更新？之前说到 previous_entry_length：表示的是前一个元素的字节长度，如果前一元素的长度小于254 字节，用1字节长的空间来保存这个长度值。如果前一元素的长度大于等于254 字节，用5 字节长的空间来保存这个长度值。

那如果我们将大于254的新元素设置为表头，会出现什么情况？由于previous entry length大小不够用(1b不够要扩充5b)，那么后面所有的元素都需要重新分配内存来保证连续性，这会导致效率很低，这种情况我们叫做连锁更新，当然我们大可不必考虑这种性能问题，因为实际上这种情况发生的几率很低，即使发生了，如果元素个数不多也没有太多的性能影响，所以Redis本身也没有去处理 这种情况，放心的用即可。

需要注意的是：虽然ziplist是一种节约内存的设计，但是只是适合存储少量数据，以及短字符串内容，因为它的ziplist空间是连续的，如果元素多伴随着增加，删除操作需要重新分配存储空间，这会给Redis的执行效率带来很大的影响，故而一般采用双向链表结构。

quicklist 快排列表

quicklist是redis 3.2之后出现的，在3.2之前采用的是 ziplist 压缩列表和adlist 双向链表。当元素个数比较少且元素长度比较小的时候，Redis采用ziplist来存储可以有效的节省内存空，但是由于ziplist内存空间的连续性导致在修改元素时需要重新分配存储空间，会造成一定的性能影响，所以当上面两个条件任意一个不满足Redis就会采用adlist作为存储结构，adlist是一种双向链表结构不要求空间的连续性，而在redis 3.2之后，为了综合考虑时间效率与空间效率引入了quicklist。

quicklist的结构

quicklist是由list链表和ziplist结合而成的，或者可以看做是quicklist由若干个ziplist组成的双向链表结构，它在时间和空间的性能上得到了平衡，先来看看它的结构

下面是quicklist的源码

/* quicklist is a 32 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. */
typedef struct quicklist {
   
   
    //指向链表的头
    quicklistNode *head;
    //指向链表的尾
    quicklistNode *tail;
    //quicklist中的元素总数
    unsigned long count;        /* total count of all entries in all ziplists */
    //len : quicklist的节点数
    unsigned int len;           /* number of quicklistNodes */
    int fill : 16;              /* fill factor for individual nodes */
    unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
} quicklist;

解释：

• head : 指向链表的头
• tail : 指向链表的尾
• count: quicklist中的元素总数
• len : quicklist的节点数
• compress: 节点压缩，16bit，通过修改参数list-compress-depth进行配置。
• fill : 16bit,用来表示ziplist大小，如果为正数表示每个ziplist最多含有的数据项，如果该值为负数则：

我们可以通过Redis修改参数list-max-ziplist-size配置节点所占内存大小，quicklist结构图例：

quicklistNode

quicklistNode是quicklist 的节点类型，结构如下：

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;
/* quicklistLZF is a 4+N byte struct holding 'sz' followed by 'compressed'.
 * 'sz' is byte length of 'compressed' field.
 * 'compressed' is LZF data with total (compressed) length 'sz'
 * NOTE: uncompressed length is stored in quicklistNode->sz.
 * When quicklistNode->zl is compressed, node->zl points to a quicklistLZF 
 注意：未压缩的长度存储在quicklistNode->sz中 ， 
 压缩quicklistNode->zl时，node->zl指向quicklistLZF */

解释：

• prev: 指向前一个节点的指针。
• next: 指向后一个节点的指针。
• zl: 数据指针，如果当前节点没有压缩那么它指向一个ziplist结构，否则它指向一个quicklistLZF结构。
• sz: 表示整个ziplist的总大小，如果ziplist被压缩了这个sz的值保存的是压缩前的ziplist大小。
• count: 表示ziplist里面包含的元素个数，16bit
• encoding: 表示ziplist采用的编码方式，2表示使用了LZF压缩，1表示没有压缩。
• container: 为quicklistNode节点zl指向的容器类型：1代表none,2代表使用ziplist存储数据
• recompress: 1代表是压缩节点，在使用压缩节点时会先进行解压缩，使用后重新压缩
• attempted_compress: 自动化测试时使用
• -extra: 预留字段，目前Redis的实现里也没用上

quicklistLZF

quicklistLZF结构表示一个被压缩过的ziplist,结构如下

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

解释：

• sz：压缩后的quicklist大小
• compressed[] : 存放压缩后的ziplist字节数组

总结

本章节介绍了Redis中的list存储结构的底层实现，在Redis3.2之前使用到了 双向链表(adlist)和压缩列表(ziplist) , 当存储的数据小且数据个数少时，为了节省内存空间，Redis选择ziplist压缩列表来存储。

ziplist是由一系列特殊编码的连续内存块组成的顺序型数据结构，它的每个节点存储了上一个节点的长度，从而可以实现如同链表一样的向前，或向后遍历。但是它的缺点就是修改了数据后，为了保证内存空间的连续性需要重新分配内存空间，非常耗时，所以如果当数据量多或者数据大的时候Redis选择使用adlist(linkedlist)双向链表结构来存储。

由于链表结构的内存是独立分配的，会加剧内存的碎片化，影响内存管理的效率，且链表的附加空间相对较高prev 和 next 就要占去 16 个字节。所以在Redis 3.2之后使用了quicklist代替 adlist（linkedlist）链表和ziplist压缩列表。

quicklist是 双向链表 和 压缩列表 的结合体，或者可以看做是quicklist由若干个ziplist组成的双向链表结构，quicklist综合考虑了时间效率与空间效。

文章结束，希望对你有所帮助