redis学习笔记-list原理

list 基本功能

图表来自：https://www.cnblogs.com/amyzhu/p/13466311.html

单链表

在学习 redis 的 list 实现之前，我们先来看一下单链表 list 怎么实现：

每一个节点都有一个向后的指针（引用）指向下一个节点，最后一个节点指向NULL表示结束，有一个Head（头）指针指向第一个节点表示开始。

类似于这样，新建和删除虽然只需要 O(1)，但是查找需要 O(n) 的时间；无法反向查找，一旦错过需要从头开始。

增加一个节点：

删除一个节点：

双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

特点：

1. 每次在插入或删除某个节点时, 需要处理四个节点的引用, 而不是两个. 实现起来要困难一些

2. 相对于单向链表, 必然占用内存空间更大一些.

3. 既可以从头遍历到尾, 又可以从尾遍历到头

这好像就解决 redis 可以实现前后都可以遍历的问题了。

那么我们来看看 redis 的链表 怎么处理的：

再来看一下它的结构体定义源码

ListNode：

typedef struct listNode
{
    // 前驱节点
    struct listNode *prev;
    // 后继节点
    struct listNode *next;
    // 节点的值
    void *value;
} listNode;

List：

typedef struct listNode
{
    // 表头节点
    listNode *head;
    // 表尾节点
    listNode *tail;
    // 链表所包含的节点数量
    unsigned long len;
    // 节点值复制函数
    void *(*dup)(void *ptr);
    // 节点值释放函数
    void *(*free)(void *ptr);
    // 节点值对比函数
    int (*match)(void *ptr,void *key)
} list;

redis 链表的特性：

• 双向无环：链表节点带有前驱、后继指针获取某个节点的前驱、后继节点的时间复杂度为O(1)，表头节点的前驱指针和表尾节点的后继指针都指向NULL，对链表的访问以NULL为终点。

• 长度计数器：通过List结构的len属性获取节点数量的时间复杂度为O(1)。

由于 list 还存在一个内存分配不连续，并引发的内存碎片的问题，是否有办法让他们的内存优化一下？

redis 压缩列表

ZipList不是基础数据结构，是Redis自己设计的一种数据存储结构。它有点类似数组，通过一片连续的内存空间来存储数据。

与数组不同的是，它允许所存储的列表元素所占据的内存空间不同。说到压缩这两个字，大家第一时间可能想到的就是节省内存。之所以说这种存储结构节省内存，是相对数组而言的。

我们都知道，数组要求每个元素存储空间的大小相同，如果我们要存储不同长度的字符串，就要以最大长度的字符串所占的存储空间作为字符串数组每个元素存储空间的大小（假如是50字节）。

因此在字符数数值中存储小于50字节长度的字符串时就会浪费一部分存储空间。

数组 的优势就是占用一片连续的空间，可以很好地利用CPU缓存快速访问数据。

如果既想保留数组的这种优势又想节省存储空间，那么我们可以对数组进行压缩：

不过，有一个问题，在遍历压缩列表的时候我们并不知道每个元素占用的内存大小是多少，因此无法计算出下一个元素的具体起始位置。

但是转念一想，如果每个元素访问之前我们能有它的长度，那么不就可以解决这个问题了嘛。

接下来我们看看Redis是如何通过实现ZipList使之结合既保留了数组的优点又节省了内存。

• zlbytes：压缩列表的字节长度，是uint32_t类型，占4字节，因此压缩列表最多有232-1字节，可以通过该值计算zlend的位置，也可以在内存重新分配的时候使用。

• zltail：压缩列表尾元素相对于压缩列表起始地址的偏移量，是uint32_t类型，占4字节，可以通过该值快速定位到列表尾元素的位置。

• zllen：压缩列表元素的个数，是uint16_t类型，占2字节，表示最多存储的元素个数为216-1=65 535，如果需要计算总数量，则需要遍历整个压缩列表。

• entryx：压缩列表存储的元素，既可以是字节数组，也可以是整数，长度不限。

• zlend：压缩列表的结尾，是uint8_t类型，占1字节，恒为0xFF。

• previous_entry_length：表示前一个元素的字节长度，占1字节或者5字节，当前元素的长度小于254时用1字节，大于等于254时用5字节，previous_entry_length 字段的第一个字节固定是0xFE，后面的4字节才是真正的前一个元素的长度。

• encoding：表示元素当前的编码，有整数或者字节数。为了节省内存，encoding字段长度可变。

• content：表示当前元素的内容。

ZipList变量的读取和赋值都是通过宏来实现的，代码片段如下：

//返回整个压缩列表的总字节
#define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))

//返回压缩列表的tail_offset变量，方便获取最后一个节点的位置
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))

//返回压缩列表的节点数量
#define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))

//返回压缩列表的表头的字节数
//（内存字节数zlbytes，最后一个节点地址ztail_offset,节点总数量zllength）
#define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))

//返回压缩列表最后结尾的字节数
#define ZIPLIST_END_SIZE        (sizeof(uint8_t))

//返回压缩列表首节点地址
#define ZIPLIST_ENTRY_HEAD(zl)  ((zl)+ZIPLIST_HEADER_SIZE)

//返回压缩列表尾节点地址
#define ZIPLIST_ENTRY_TAIL(zl)  ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))

//返回压缩列表最后结尾的地址
#define ZIPLIST_ENTRY_END(zl)   ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)

对此，可以通过定义的结构体和对应的操作定义知道大概 redis 设计 压缩list 的思路；

这种方式虽然节约了空间，但是会存在每次插入和创建存在内存重新分配的问题。

quicklist

quicklist是Redis 3.2中新引入的数据结构，能够在时间效率和空间效率间实现较好的折中。Redis中对quciklist的注释为A doubly linked list of ziplists。顾名思义，quicklist是一个双向链表，链表中的每个节点是一个ziplist结构。quicklist可以看成是用双向链表将若干小型的ziplist连接到一起组成的一种数据结构。

当ziplist节点个数过多，quicklist退化为双向链表，一个极端的情况就是每个ziplist节点只包含一个entry，即只有一个元素。当ziplist元素个数过少时，quicklist可退化为ziplist，一种极端的情况就是quicklist中只有一个ziplist节点。

quicklist 结构定义:

typedef struct quicklist {
    // 指向quicklist的首节点
    quicklistNode *head;
    // 指向quicklist的尾节点
    quicklistNode *tail;
    // quicklist中元素总数
    unsigned long count;        /* total count of all entries in all ziplists */
    // quicklistNode节点个数
    unsigned long len;          /* number of quicklistNodes */
    // ziplist大小设置，存放list-max-ziplist-size参数的值
    int fill : 16;              /* fill factor for individual nodes */
    // 节点压缩深度设置，存放list-compress-depth参数的值
    unsigned int compress : 16; /* depth of end nodes not to compress;0=off */
    unsigned int bookmark_count: 4;
    quicklistBookmark bookmarks[];
} quicklist;

typedef struct quicklistBookmark {
    quicklistNode *node;
    char *name;
} quicklistBookmark;

quicklistNode定义如下:

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;

redis为了节省内存空间，会将quicklist的节点用LZF压缩后存储，但这里不是全部压缩，可以配置compress的值，compress为0表示所有节点都不压缩，否则就表示从两端开始有多少个节点不压缩；compress如果是1，表示从两端开始，有1个节点不做LZF压缩。compress默认是0(不压缩)，具体可以根据你们业务实际使用场景去配置。

redis 的配置文件可以配置该参数

list-compress-depth 0

还有个fill字段，它的含义是每个quicknode的节点最大容量，不同的数值有不同的含义，默认是-2，当然也可以配置为其他数值；

list-max-ziplist-size -2

• 当值为正数时，表示quicklistNode节点上的ziplist的长度。比如当这个值为5时，每个quicklistNode节点的ziplist最多包含5个数据项

• 当值为负数时，表示按照字节数来限制quicklistNode节点上的ziplist的的长度，可选值为 -1 到 -5。

为什么会有配置提供出来呢？

• ziplist越短，内存碎片增多，影响存储效率。当一个ziplist只存一个元素时，quicklist又退化成双向链表了

• ziplist越长，为ziplist分配大的连续的内存空间难度也就越大，会造成很多小块的内存空间被浪费，当quicklist只有一个节点，元素都存在一个ziplist上时，quicklist又退化成ziplist了

结束语

虽然没有完全去理解它的源码，但我们也可以通过这篇文章来熟悉 redis 的一个设计思路。并知道它是怎么一步一步优化过来的。让我们有一个大概的性能认知。