【Redis】基础数据结构-quicklist

Redis List

在Redis3.2版之前，Redis使用压缩列表和双向链表作为List的底层实现。当元素个数比较少并且元素长度比较小时，Redis使用压缩列表实现，否则Redis使用双向链表实现。

ziplist存在问题

1. 不能保存过多的元素，否则查找复杂度高，性能降低。

2. 由于每个节点保存了前一个节点的长度，不同长度使用的字节数不一样，所以在更新节点的时候有可能引起长度的变化导致连锁更新问题。

为了解决上面两个问题，在Redis3.2版之后，引入了quicklist。

quicklist

quicklist可以理解为是ziplist和链表的结合体，一个quicklist是一个双向链表，链表中的每一个节点是一个ziplist。

quicklist结构定义

typedef struct quicklist {
    // 头指针
    quicklistNode *head;
    // 尾指针
    quicklistNode *tail;
    unsigned long count;        /* 列表中的元素总个数，也就是所有ziplist中包含的元素数量之和 */
    unsigned long len;          /* 链表中节点的个数 */
    int fill : QL_FILL_BITS;              /* 表示ziplist的大小 */
    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;
1
2
3
4
5
6
7
8
9
10
11
12

• head：指向头结点的指针

• tail：指向尾节点的指针

• count：列表中的元素总个数，等于所有节点的ziplist中包含的元素数量之和

• len：quicklist中quicklistNode节点的个数

• fill：用来限制quicklistNode中ziplist的大小，为正数时代表ziplist中最多能包含的元素个数，为负数时有以下几种情况：

  数值	含义
  -1	表示ziplist的字节数不能超过4KB
  -2	表示ziplist的字节数不能超过8KB
  -3	表示ziplist的字节数不能超过16KB
  -4	表示ziplist的字节数不能超过32KB
  -5	表示ziplist的字节数不能超过64KB

​除此之外，也可以通过list-max-ziplist-size参数配置最大的字节数。

quicklistNode结构定义

typedef struct quicklistNode {
    // 前一个节点
    struct quicklistNode *prev;
    // 下一个节点
    struct quicklistNode *next;
    // 指向ziplist压缩列表的指针
    unsigned char *zl;
    unsigned int sz;             /* ziplist压缩列表的字节数 */
    unsigned int count : 16;     /* ziplist压缩列表的元素个数 */
    unsigned int encoding : 2;   /* 编码格式：RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* 是否被压缩 */
    unsigned int attempted_compress : 1; /* 是否可以被压缩 */
    unsigned int extra : 10; /* 预留bit位*/
} quicklistNode;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

quicklist创建

quicklist *quicklistCreate(void) {
    struct quicklist *quicklist;
    // 分配空间
    quicklist = zmalloc(sizeof(*quicklist));
    // 初始化头尾节点
    quicklist->head = quicklist->tail = NULL;
    quicklist->len = 0;
    quicklist->count = 0;
    quicklist->compress = 0;
    // 默认为-2，表示ziplist的字节数最大不能超过8KB
    quicklist->fill = -2;
    quicklist->bookmark_count = 0;
    return quicklist;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

添加元素

添加元素的时候可以在链表的头部或者尾部进行添加，以头部添加为例：

1. 首先调用_quicklistNodeAllowInsert方法判断是否允许添加元素到ziplist，如果允许，调用ziplistPush方法进行添加
2. 如果_quicklistNodeAllowInsert不允许添加元素，则需要新创建一个quicklistNode，然后将元素添加到新创建的quicklistNode的压缩列表中

// 从头部添加元素
int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
    quicklistNode *orig_head = quicklist->head;
    // 判断是否允许添加
    if (likely(
            _quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {
        // 将元素添加到ziplit
        quicklist->head->zl =
            ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD);
        quicklistNodeUpdateSz(quicklist->head);
    } else {
        // 新创建quicklistNode节点
        quicklistNode *node = quicklistCreateNode();
        // 添加元素
        node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);

        quicklistNodeUpdateSz(node);
        _quicklistInsertNodeBefore(quicklist, quicklist->head, node);
    }
    // 更新数量
    quicklist->count++;
    quicklist->head->count++;
    return (orig_head != quicklist->head);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

_quicklistNodeAllowInsert

_quicklistNodeAllowInsert方法用于判断是否允许在某个quicklistNode指向的压缩列表中添加元素。

在quicklist的结构体定义中，fill指定了ziplist中能包含的最大元素个数或者ziplist最大的字节数，_quicklistNodeAllowInsert方法就是判断ziplist中的元素个数或者ziplist的字节数是否超过了限制：

// node：当前的quicklistNode节点
// fill：ziplist中能包含的最大元素个数或者ziplist最大的字节数
// sz：要添加元素的大小
REDIS_STATIC int _quicklistNodeAllowInsert(const quicklistNode *node,
                                           const int fill, const size_t sz) {
    if (unlikely(!node))
        return 0;

    int ziplist_overhead;
    /* 判断要添加元素的大小是否小于254 */
    if (sz < 254)
        ziplist_overhead = 1;
    else
        ziplist_overhead = 5;

    /* 判断要添加元素的大小是否小于64 */
    if (sz < 64)
        ziplist_overhead += 1;
    else if (likely(sz < 16384))
        ziplist_overhead += 2;
    else
        ziplist_overhead += 5;

    /* 计算添加元素后的当前的quicklistNode的大小 + 新加入元素的大小 + 插入元素后ziplit的prevlen占用大小 */
    unsigned int new_sz = node->sz + sz + ziplist_overhead;
    // 判断添加元素后的ziplist的字节数是否超过了fill中设置的大小
    if (likely(_quicklistNodeSizeMeetsOptimizationRequirement(new_sz, fill)))
        return 1;
    else if (!sizeMeetsSafetyLimit(new_sz))
        return 0;
    else if ((int)node->count < fill) // 判断ziplist的元素个数是否超过了fill设置的大小
        return 1;
    else
        return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

总结

1. 在Redis3.2版之前，Redis使用压缩列表和双向链表作为List的底层实现。当元素个数比较少并且元素长度比较小时，Redis使用压缩列表实现，否则Redis使用双向链表实现。

2. 为了解决压缩列表在节点多的时候查找效率低的问题以及连锁更新问题，在Redis3.2版之后引入了quicklist，quicklist是一个双向链表，链表中的每一个节点是一个ziplist。

3. quicklist中限定了ziplist的大小，如果超过了限制的大小，新加入元素的时候会生成一个新的quicklistNode节点。

4. quicklist通过限定ziplist的大小来保证一个ziplist中的元素个数不会太多，如果需要连锁更新，也只在某个quicklistNode节点指向的ziplist中更新，不会引发整个链表的更新，以此来解决压缩列表存在的问题。

参考

陈雷《Redis5设计与源码分析》

极客时间 - Redis源码剖析与实战(蒋德钧)

Redis版本：redis-6.2.5