QuickList详解

[toc]

ZipList虽然节省空间，但它申请的内存必须是连续的，如果内存占用过多，就会导致申请内存的效率很低。

  • 所以必须限制ZipList的长度和Entry大小

假设我们要存储大量数据该怎么办？

  • 创建多个ZipList分片存储数据

分片后，数据变得分散，不方便管理和查找怎么办？

  • 引入QuickList，它是一个双端列表，它的每个节点都是一个ZipList（Redis6.2之前），如下图所示
    • Redis6.2之后ZipList被更换为listpack，以下叙述基于Redis6.2之前，即底层是ZipList

image-20240921115903842

为了限制ZipList节点的大小，Redis提供了参数list-max-ziiplist-size进行限制

  • 如果size > 0，则代表了允许存放的entry个数的最大值
  • 如果size < 0 ，代表Ziplist的最大内存大小为$2^{1-size}kb（-1<=size <= -5）$，例如size=-1时，最大内存大小为2^2=4kb
    • 默认值为-2

除此之外，QuickList还提供了list-compress-depth控制节点压缩，depth = N代表QuickList的首尾各有N个节点不压缩，中间剩余节点压缩

  • 默认值为0

以下是list-compress-depth = 1的QuickList示意

image-20240921122602982

QuickList特点总结
  • 是一个双端列表，节点为ZipList，6.2之后换为listpack
  • 节点采用ZipList，节省空间
  • 控制分片大小，解决了连续空间申请的问题
  • 中间结点可以进行压缩，进一步节省空间
QuickList源码分析(基于ZipList)

Redis-6.0.19

1
2
3
4
5
6
7
8
9
10
11
typedef struct quicklist {
    quicklistNode *head;					// 头指针
    quicklistNode *tail;					// 尾指针
    unsigned long count;        			// 总Entry数量
    unsigned long len;          			// 总节点ZipList数量
    int fill : QL_FILL_BITS;              	// 控制ZipList的上限
    unsigned int compress : QL_COMP_BITS; 	// 控制QuickList压缩
    unsigned int bookmark_count: QL_BM_BITS;	// 内存重分配时使用的书签数量和数组
    quicklistBookmark bookmarks[];
} quicklist;

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct quicklistNode {
    struct quicklistNode *prev;			// 前指针
    struct quicklistNode *next;			// 后指针
    unsigned char *zl;					// 当前节点的ZipList指针
    unsigned int sz;             		// 当前Ziplist大小，按字节计
    unsigned int count : 16;     		// 当前Ziplist的Entry数
    unsigned int encoding : 2;   		// 编码方式：1，ZipList ; 2，LZF压缩模式
    unsigned int container : 2;  		// 容器类型：1，预留 ; 2，ZipList
    unsigned int recompress : 1; 		// 是否被解压缩：1，解压状态，可能需要重新压缩
    unsigned int attempted_compress : 1;
    unsigned int extra : 10; 			// 预留字段
} quicklistNode;