Redis底层数据结构之quicklist

redis底层数据结构已完结👏👏👏：

• ☑️redis底层数据结构之SDS
• ☑️redis底层数据结构之ziplist
• ☑️redis底层数据结构之quicklist
• ☑️redis底层数据结构之Dict
• ☑️redis底层数据结构之IntSet
• ☑️redis底层数据结构之ZSkipList

一、概述

QuickList是由多个 ziplist 组成的双向链表，每个 ziplist 存储一定数量的元素。优点:结合了 ziplist 和双向链表的优点，既节省空间，又提升了修改操作的性能。使用场景: 在列表键元素较多或包含较大元素时使用。

ziplist补充(ziplist缺点-链式扩容&级联更新)
当一个entry被插入的时候，我们需要设置下一个entry中的prevlen字段为新插入entry的长度。会发生如下的情况：新插入entry的长度超过了254[>=254]，那么下一个entry的prelen需要5个字节记录该长度，但是呢，此时下一个entry的prevlen字段此时只有一个字节，所以需要对下一个entry进行grown[扩容]，更糟糕的是，下个entry因为扩容导致长度超过254，还会引起下下个entry的扩容…，这种现象呢就是级联更新，简单点来说就是，因为一个entry的插入导致之后的entry都需要重新扩容和记录前一个entry的prevlen现象称之为“级联更新”。

从 Redis 6.2 版本开始，quicklist 的底层实现由原来的 ziplist 改为了 listpack。Listpack 是 ziplist 的升级版本，主要是为了解决ziplist中存在的一些问题，比如，ziplist中扩展元素长度时可能需要进行昂贵的重新分配操作。listpack 提供了更好的性能和内存使用效率，在保持与 ziplist 类似的密集存储方式的同时，允许更大的单个元素大小，并且有更强的扩展性。listpack和ziplist对象结构的不同是，listpack将prevlen替换为了curlen，从而有效避免级联更新。并将且将culen字段放在entry结构的最后面。这样做是为了，能够通过total-bytes定位到最后一个element的末尾位置然后获取到curlen从而找到前一个element的位置，从而实现从后往前遍历。

补充说明listpack和ziplist
参考博客 ziplist和listpack

• ziplist包括三大部分，<头部，entry，尾部>。头部包含"zlbytes,zltail,zllen"；尾部包含"zlend标记ziplist的结尾"；entry包括"prevlen,encoding,entry_data"。由于prevlen记录方式存在级联更新的问题，小于254字节需要1字节内存，大于等于254字节需要5字节内存。
• listpack包括三大部分，<头部，entry，尾部>。头部包含"zlbytes,zllen"相比与ziplist少了zltail；entry包括"encoding,entry_data,curlen"；尾部包含"zlend标记listpack的结尾"。由于entry中的prevlen由curlen取代，所以不再有级联更新的问题。
• 不论是"ziplist"还是"listpack"获取len的方式都是一样的：
  先判断头部中zllen字段存储的数值与UNIT16_MAX的关系
  小于UNIT16_MAX，直接返回zllen
  大于等于UNIT16_MAX需要从头到尾遍历获取元素总数
  如果新得到的元素总数小于UINT16_MAX，重新设置zllen的数值

二、quicklist结构

(直达源码–>src/quicklist.h)

基于listpack(V6.2)

/* quicklist is a 40 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: 0 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.
* 'bookmarks are an optional feature that is used by realloc this struct,
*      so that they don't consume memory when not used. */
typedef struct quicklist {
   quicklistNode *head;
   quicklistNode *tail;
   unsigned long count;        /* total count of all entries in all listpacks */
   unsigned long len;          /* number of quicklistNodes */
   signed 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;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

基于ziplist

typedef struct quicklist {
   // quicklist头结点
   quicklistNode *head;
   // quicklist 尾节点
   quicklistNode *tail;
   // 所有的ziplist中的entry总数量
   unsigned long count; /* total count of all entries in all ziplists */
   // ziplist节点数量
   unsigned long len;   /* number of quicklistNodes */
   // ziplist中entry的上限，默认为-2，和redis中配置的 list-max-ziplist-size 一致
   int fill : QL_FILL_BITS;  /* fill factor for individual nodes */
   // 首尾节点不压缩的个数，若设置为1，则首尾节点各有一节点不压缩；设置为0，则代表所有节点不压缩
   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
13
14
15
16
17
18

三、quicklistNode结构

基于listpack(V6.2)

/* quicklistNode is a 32 byte struct describing a listpack for a quicklist.
* We use bit fields keep the quicklistNode at 32 bytes.
* count: 16 bits, max 65536 (max lp bytes is 65k, so max count actually < 32k).
* encoding: 2 bits, RAW=1, LZF=2.
* container: 2 bits, PLAIN=1 (a single item as char array), PACKED=2 (listpack with multiple items).
* recompress: 1 bit, bool, true if node is temporary decompressed for usage.
* attempted_compress: 1 bit, boolean, used for verifying during testing.
* dont_compress: 1 bit, boolean, used for preventing compression of entry.
* extra: 9 bits, free for future use; pads out the remainder of 32 bits */
typedef struct quicklistNode {
   struct quicklistNode *prev;
   struct quicklistNode *next;
   unsigned char *entry;
   size_t sz;             /* entry size in bytes */
   unsigned int count : 16;     /* count of items in listpack */
   unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
   unsigned int container : 2;  /* PLAIN==1 or PACKED==2 */
   unsigned int recompress : 1; /* was this node previous compressed? */
   unsigned int attempted_compress : 1; /* node can't compress; too small */
   unsigned int dont_compress : 1; /* prevent compression of entry that will be used later */
   unsigned int extra : 9; /* more bits to steal for future usage */
} quicklistNode;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

基于ziplist

typedef struct quicklistNode {
   // 前一个节点（ziplist）指针
   struct quicklistNode *prev;
   // 后一个节点（ziplist）指针
   struct quicklistNode *next;
   // 当前节点ziplist指针
   unsigned char *zl;
   // 当前节点ziplist的字节大小，即zlbytes
   unsigned int sz;             /* ziplist size in bytes */
   // 当前节点ziplist中entry的数量
   unsigned int count : 16;     /* count of items in ziplist */
   // 编码方式:1-ziplist; 2-lzf压缩模式
   unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
   // 数据容器类型：1-其他（预留扩展类型）；2-ziplist
   unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
   // 是否被压缩：1-说明被解压，将来要重新压缩。
   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;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

四、优缺点

优点：

• 快表的节点大小固定，可以有效地避免内存碎片的发生。
• 快表支持动态增加和删除节点，可以随着数据的增长而自动扩容或缩容，不需要预先分配空间。
• 快表的节点采用ziplist的紧凑存储方式，使得节点访问和遍历的效率较高。同时，快表支持从头和尾部两个方向同时遍历节点。

缺点：

• 快表的节点大小固定，如果节点中的元素数量较少，会造成一定的空间浪费。
• 快表中的元素只能是整数或字节数组，不支持其他数据类型的存储。
• 快表的插入和删除操作的效率较低，因为在插入或删除元素时，需要移动后面的元素，可能会导致大量的内存复制操作。如果需要频繁进行插入和删除操作，建议使用其他数据结构，例如链表。
• 当快表中的元素数量较大时，遍历整个快表的效率也可能较低，因为快表是由多个节点组成的链表，需要依次遍历每个节点才能访问所有元素。