Redis源码学习 -- 基本数据结构 -- Quicklist - -蓝蜗牛

1. 什么是 Quicklist？

Quicklist​​是Redis自主研发的一种双向表数据结构，是List的底层数据结构之一。设计的核心思想是在时间和空间之间取一个平衡点。

2. Quicklist vs 普通链表 vs Listpack

List系列命令的设计目标：两端操作O(1)，随机操作O(n)。

• 普通链表存在的问题？
  普通链表实现双向遍历需要保存两个指针，浪费内存空间。

• Listpack存在的问题？
  头部增删改操作是O(n)，只有元素少的时候才能看成O(1)。

为了解决上述问题，Quicklist的设计思想是将两者结合起来。将数据分割成多个Listpack，然后用普通链表将Listpack串起来。Quicklist基本结构如图：

如此一来，不仅节省大量空间，而且随机操作的速度比原来更快。
最好情况下是O(n^0.5)，如：1000000个元素均匀拆分成了1000个Listpack，访问最中间的元素需要遍历 500个Node + 500个元素。
最坏情况下是O(n)，每个Listpack只有1个元素退化成普通链表。

3. Quicklist 的优化方法

3.1 Listpack 分割策略

在Quicklist基本结构上，高效的核心是避免每个Listpack的元素过多或过少。
避免元素过多的方法：配置阈值，使得Listpack元素数量不能超过阈值或者Listpack占用的空间不能超过阈值。如果超过阈值则分割成两个Listpack。
避免元素过少的方法：在合适的时机进行Listpack合并。

typedef struct quicklist {quicklistNode *head;quicklistNode *tail;signed int fill : 16;/* ...... */
} quicklist;

Redis设计了fill字段来保存阈值：

• 如果 (fill > 0), 表示数量阈值为fill个元素。空间阈值为默认值 8 KB
• 如果 (-1 >= fill >= -5), 表示没有数量阈值，空间阈值为等级1~5，5个等级分别是{4KB, 8KB, 16KB, 32KB, 64KB}

fill转化为实际阈值的接口为quicklistNodeLimit()：

#define SIZE_SAFETY_LIMIT 8192
static const size_t optimization_level[] = {4096, 8192, 16384, 32768, 65536};/* Calculate the size limit of the quicklist node based on negative 'fill'. */
static size_t quicklistNodeNegFillLimit(int fill) {assert(fill < 0);size_t offset = (-fill) - 1;size_t max_level = sizeof(optimization_level) / sizeof(*optimization_level);if (offset >= max_level) offset = max_level - 1;return optimization_level[offset];
}/* Calculate the size limit or length limit of the quicklist node* based on 'fill', and is also used to limit list listpack. */
void quicklistNodeLimit(int fill, size_t *size, unsigned int *count) {*size = SIZE_MAX;*count = UINT_MAX;if (fill >= 0) {/* Ensure that one node have at least one entry */*count = (fill == 0) ? 1 : fill;} else {*size = quicklistNodeNegFillLimit(fill);}
}

增删改查操作如何触发分割和合并？

• 查询
  查询操作是读操作，只需要遍历元素，不会触发分割和合并。

• 修改
  修改有可能导致长度变大或变小，可以分别按增加和删除的情况处理。

• 删除
  删除操作显然不会触发分割。那么删除后元素变少是否需要合并？不需要！！！链表的使用场景是以两端操作为主，各个Listpack均匀删除的情况几乎不可能发生，删除后大概率是无法合并的。

• 增加
  增加元素后有可能会超过阈值。超过阈值后如果是两端新增，直接增加一个node，不会触发分割；如果是随机插入，原本的一个Listpack需要分割成2个或者3个，此时是唯一触发合并的时机，会尝试将相邻的5个node两两合并。合并代码如下：

/* Attempt to merge listpacks within two nodes on either side of 'center'.** We attempt to merge:*   - (center->prev->prev, center->prev)*   - (center->next, center->next->next)*   - (center->prev, center)*   - (center, center->next)* * Returns the new 'center' after merging.*/
REDIS_STATIC quicklistNode *_quicklistMergeNodes(quicklist *quicklist, quicklistNode *center) {int fill = quicklist->fill;quicklistNode *prev, *prev_prev, *next, *next_next, *target;prev = prev_prev = next = next_next = target = NULL;if (center->prev) {prev = center->prev;if (center->prev->prev)prev_prev = center->prev->prev;}if (center->next) {next = center->next;if (center->next->next)next_next = center->next->next;}/* Try to merge prev_prev and prev */if (_quicklistNodeAllowMerge(prev, prev_prev, fill)) {_quicklistListpackMerge(quicklist, prev_prev, prev);prev_prev = prev = NULL; /* they could have moved, invalidate them. */}/* Try to merge next and next_next */if (_quicklistNodeAllowMerge(next, next_next, fill)) {_quicklistListpackMerge(quicklist, next, next_next);next = next_next = NULL; /* they could have moved, invalidate them. */}/* Try to merge center node and previous node */if (_quicklistNodeAllowMerge(center, center->prev, fill)) {target = _quicklistListpackMerge(quicklist, center->prev, center);center = NULL; /* center could have been deleted, invalidate it. */} else {/* else, we didn't merge here, but target needs to be valid below. */target = center;}/* Use result of center merge (or original) to merge with next node. */if (_quicklistNodeAllowMerge(target, target->next, fill)) {target = _quicklistListpackMerge(quicklist, target, target->next);}return target;
}

在增加了分割策略后，有可能会出现一个元素大小比Listpack占用空间的阈值还要大。
对这种特殊情况，让该元素单独一个Node，并禁止该Node参与分割和合并。由于Node只有一个元素，Listpack无法进行压缩，直接保存二进制数据更节省空间。使用一个模式标志位container区分普通的Node，container = 1表示该Node只有一个大元素。container = 2表示数据是Listpack

typedef struct quicklistNode {struct quicklistNode *prev;struct quicklistNode *next;unsigned char *entry;  /* container = 1 指向二进制数组数据, container = 2 指向 listpack */size_t sz;             /* entry size in bytes */unsigned int count : 16;     /* count of items in listpack */unsigned int container : 2;  /* PLAIN==1 or PACKED==2 *//* ...... */
} quicklistNode;

3.2 Node 压缩策略

由于Listpack关注的是对长度字段进行压缩，实际的二进制数据并没有压缩。
为了进一步压缩空间，Quicklist结构增加了一个压缩Listpack的功能，该功能是可选的。
压缩算法采用LZF算法，在保持较高压缩速度的同时，提供合理的压缩率​​，尤其适合对时间和内存资源敏感的场景（如：实时数据处理）

但是，不是所有的Node都适合压缩！！！

1. 元素长度超过阈值不压缩（即: container = 1），元素太大时压缩和解压的时间将成为性能瓶颈。
2. 元素压缩后节省空间少时不压缩，元素太小（size <= 48字节）或者 (压缩空间 <= 8字节)

typedef struct quicklistLZF {size_t sz; /* LZF size in bytes*/char compressed[];
} quicklistLZF;REDIS_STATIC int __quicklistCompressNode(quicklistNode *node) {if (node->sz < MIN_COMPRESS_BYTES) // sz < 64 不压缩return 0;quicklistLZF *lzf = zmalloc(sizeof(*lzf) + node->sz); // 申请压缩后的空间, 按压缩前的大小申请if (((lzf->sz = lzf_compress(node->entry, node->sz, lzf->compressed, node->sz)) == 0) ||lzf->sz + MIN_COMPRESS_IMPROVE >= node->sz) { // 压缩收益小于8则不压缩zfree(lzf);return 0;}lzf = zrealloc(lzf, sizeof(*lzf) + lzf->sz); // 裁剪空间为压缩后的空间 zfree(node->entry);node->entry = (unsigned char *)lzf;node->encoding = QUICKLIST_NODE_ENCODING_LZF; // 标记为已压缩return 1;
}

3. 两端的Node不压缩，两端的Node是频繁操作的，压缩后每次操作都需要解压影响较大。同时允许配置压缩深度，允许两边的N个node不压缩。

完整的结构体定义如下：

typedef struct quicklistNode {struct quicklistNode *prev;struct quicklistNode *next;unsigned char *entry;        /* 指向实际的保存的元素结构 */size_t sz;                   /* entry 字段的字节数 */unsigned int count : 16;     /* listpack 元素总数 */unsigned int encoding : 2;   /* 1: 不压缩, 2: LZF压缩 (entry是listpack时有效) */unsigned int container : 2;  /* 1: entry直接存二进制(元素大小超阈值), 2: entry是listpack */unsigned int recompress : 1;unsigned int attempted_compress : 1;unsigned int dont_compress : 1;unsigned int extra : 9; /* 填充字段, 位域4字节对齐 */
} quicklistNode;typedef struct quicklist {quicklistNode *head;quicklistNode *tail;unsigned long count;        /* 所有 listpack 的元素总和 */unsigned long len;          /* Node 的总数 */signed int fill : QL_FILL_BITS;       /* listpack 分割阈值( >0 表示元素数量上限, <0 表示占用空间上限等级) */unsigned int compress : QL_COMP_BITS; /* 压缩深度, 两端的N个node不压缩. 0: 表示全部禁用压缩 */unsigned int bookmark_count: QL_BM_BITS;  /* 书签, 已废弃 */quicklistBookmark bookmarks[];            /* 书签, 已废弃 */
} quicklist;

quicklistNode有3个内部状态字段：

• recompress：Node临时解压标记。如插入数据时：先临时解压，再插入数据，然后压缩。临时解压将字段标记1，避免触发所有Node都需要检查是否压缩。
• attempted_compress：Redis运行测试用例时使用的标记字段，正常运行时永远为0。
• dont_compress：为了修复Replace操作的bug的规避字段，否则可能需要大改动才能修复。详见: https://github.com/redis/redis/pull/11242

quicklist的废弃功能bookmark：
bookmark是Redis 6版本用于优化ziplist批量迭代的产物，Redis 7版本优化了迭代器的实现，bookmark模块已经被废弃。

4. Redis 8 Quicklist 前瞻

1. 优化了LZF压缩算法的实现，压缩速度提升​​20%​，同时支持动态调整压缩深度list-compress-depth。
2. 允许对Quicklist的中间节点按需压缩。
3. 控制节点负载因子超过阈值时触发拆分 list-node-auto-split-threshold（默认 0.75）。
4. 支持通过LPUSH/RPUSH一次性插入多个元素时，自动合并到同一节点的Listpack中，减少内存碎片。
5. 新增quicklist-fragment-threshold 参数，允许自定义碎片触发回收的阈值。