Redis quicklist 详解：双向链表 + listpack 的混合结构

一句话结论（30s）

quicklist 本质是「双向链表 + 压缩列表」的混合结构，外层链表保证 O(1) 头尾操作，内层 ziplist/listpack 把多个元素塞进一段连续内存以减少指针开销。关键设计：因为链表节点大小由 list-max-ziplist-size（默认 -2 即 8KB）控制，所以每个节点内的连锁更新被隔离在单节点内，最坏代价从全表 O(N) 降为单节点内 O(几百)。权衡：8KB 是社区经验平衡点——节点太小则数量过多、指针开销回归 linkedlist，太大则单次 memmove 代价过高。

核心原理（2min）

quicklist 外层是双向链表（head/tail/len/count），每个 quicklistNode 内嵌一个 ziplist（7.0 起 listpack）。插入时若头/尾节点还能装下就直接 push，否则新建节点；中间插入若目标节点已满则分裂成两个节点；删除到半满以下会合并相邻节点。list-max-ziplist-size 的负值表示「每个节点最大字节数」（-1=4KB … -5=64KB），正值表示「最多元素数」。Redis 7.0 用 listpack 替代 ziplist：listpack 把「前驱长度 prevlen」改为「末尾自描述 backlen」，从结构上消除了连锁更新。

底层深入（5-10min）

一、从 linkedlist + ziplist 到 quicklist

Redis 3.0 及之前

List 类型有两种底层实现：

linkedlist（双向链表）：每个节点存一个元素，prev/next 指针 + 值。内存碎片化严重，每个节点有指针开销（prev 8B + next 8B + value 指针 8B = 24B 额外开销）。
ziplist（压缩列表）：连续内存块，无指针开销。但对于长列表，插入/删除需要 memmove 大量数据。

选择逻辑：元素少或元素短 → ziplist，否则 → linkedlist。

Redis 3.2 引入 quicklist

quicklist 的灵感来自 “链表 + 数组” 的混合结构：外层是双向链表（快速头尾操作），每个链表节点内是一段 ziplist（减少指针开销）。本质上这是对 linkedlist 和 ziplist 的折衷：

quicklist 结构：
┌──────────┐    ┌──────────┐    ┌──────────┐
│ quicklist │───→│  Node 0   │←──→│  Node 1   │←──→│  Node 2   │
│  head     │    │  ziplist  │    │  ziplist  │    │  ziplist  │
│  tail     │    │ [a,b,c]   │    │ [d,e,f,g] │    │ [h]       │
│  len=3    │    └──────────┘    └──────────┘    └──────────┘
│  count=8  │
└──────────┘

思考：为什么 quicklist 要「链表 + 压缩列表」两层，而不是纯链表或纯 ziplist？反着想两个极端——纯 linkedlist 每个元素一个节点，prev/next/value 三个指针就是 24B 额外开销，100 万元素光指针就 24MB 还高度碎片化；纯 ziplist 无指针但插入删除要 memmove 整个列表，长列表单次操作 O(N)。quicklist 让外层链表管「定位到节点」（O(1) 头尾）、内层 listpack 管「节点内紧凑存元素」，两头好处都拿到、两头的坏处都被节点边界隔断。

二、核心数据结构

2.1 quicklist

quicklist 外层的「链表骨架」——只负责把节点串起来，真正的元素都塞在节点内的 listpack 里：

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all listpacks */
    unsigned long len;          /* number of quicklistNodes */
    size_t alloc_size;          /* total allocated memory (in bytes) */
    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;

head/tail 两个指针让头尾压入、弹出都是 O(1)，这是外层链表的职责；count 是所有 listpack 里 entry 的总数（跨节点累加），len 是 quicklistNode 的数量，两者语义分离——链表负责「定位到节点」，listpack 负责「节点内紧凑存元素」。alloc_size 缓存总分配内存，避免统计时反复遍历。

2.2 quicklistNode

真正承载数据的节点，内嵌一段 listpack（早期是 ziplist）：

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;

位域把整个节点压进 32 字节。entry 在 Redis 7.0+ 指向一段 listpack（更早版本指向 ziplist），container=PACKED(2) 表示 listpack、PLAIN(1) 表示超大元素单独存成裸字节数组；encoding 标记是否被 LZF 压缩，压缩只作用于中间节点，两端保留若干未压缩节点用于快速头尾访问。

三、插入策略与节点分裂

3.1 头插：能否塞进节点由 fill 决定

int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
    quicklistNode *orig_head = quicklist->head;

    if (unlikely(isLargeElement(sz, quicklist->fill))) {
        __quicklistInsertPlainNode(quicklist, quicklist->head, value, sz, 0);
        return 1;
    }

    if (likely(
            _quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {
        size_t oldsize = quicklist->head->sz;
        quicklist->head->entry = lpPrepend(quicklist->head->entry, value, sz);
        quicklistNodeUpdateSz(quicklist->head);
        quicklistUpdateAllocSize(quicklist, quicklist->head->sz, oldsize);
    } else {
        quicklistNode *node = quicklistCreateNode(quicklist);
        node->entry = lpPrepend(lpNew(0), value, sz);
        quicklistNodeUpdateSz(node);
        quicklistUpdateAllocSize(quicklist, node->sz, 0);
        _quicklistInsertNodeBefore(quicklist, quicklist->head, node);
    }
    quicklist->count++;
    quicklist->head->count++;
    return (orig_head != quicklist->head);
}

头插的完整逻辑一目了然：先看元素是不是「大元素」——若是则单独放进一个 PLAIN 节点（不压进 listpack）；否则用 _quicklistNodeAllowInsert 判断当前 head 节点的 listpack 是否还能装下，能装就 lpPrepend 原地前插，不能装就新建节点接到链表头部。这正体现了 quicklist 的折中：链表负责增删节点，listpack 负责节点内紧凑存元素，fill 决定两者的切换点。

3.2 中间插入的节点分裂

当在中间位置插入元素时，如果目标 ziplist 已满（根据 list-max-ziplist-size 配置），quicklist 会分裂节点：

分裂前：[Node A: ziplist[a,b,c,d,e]] (已满)
插入 'x' 在 'c' 之后
分裂后：[Node A: ziplist[a,b,c]] → [Node B: ziplist[x,d,e]]

分裂策略：插入位置作为分裂点，前一半元素留在原节点，后一半 + 新元素进入新节点。注意这里是 2 节点 分裂（不是 B+Tree 的 1→2 分裂 + 向上传播），因为 quicklist 没有层级索引。

3.3 删除时的节点合并

删除后，quicklist 会尝试把相邻节点合并，判断依据不是「少于半满」，而是「合并后的 listpack 是否还满足 fill 限制」：

REDIS_STATIC int _quicklistNodeAllowMerge(const quicklistNode *a,
                                          const quicklistNode *b,
                                          const int fill) {
    if (!a || !b)
        return 0;

    if (unlikely(QL_NODE_IS_PLAIN(a) || QL_NODE_IS_PLAIN(b)))
        return 0;

    /* approximate merged listpack size (- 7 to remove one listpack
     * header/trailer, see LP_HDR_SIZE and LP_EOF) */
    unsigned int merge_sz = a->sz + b->sz - 7;
    if (unlikely(quicklistNodeExceedsLimit(fill, merge_sz, a->count + b->count)))
        return 0;
    return 1;
}

合并时估算两个 listpack 合并后的字节数（减 7 是因为两个 listpack 共用一个 6 字节头 + 1 字节尾），只要不超过 fill 限制就执行 _quicklistListpackMerge 把右侧元素拼进左侧。这保证删除后节点不会「碎」成大量半空小节点，从而维持高填充率、避免指针开销回退到 linkedlist。

四、list-max-ziplist-size 配置

# redis.conf
list-max-ziplist-size -2

这个配置的负值含义常常被误解。实际语义：

值	含义
`-1`	每个 ziplist 节点 ≤ 4KB
`-2`	每个 ziplist 节点 ≤ 8KB（默认）
`-3`	每个 ziplist 节点 ≤ 16KB
`-4`	每个 ziplist 节点 ≤ 32KB
`-5`	每个 ziplist 节点 ≤ 64KB
正数 N	每个 ziplist 节点最多包含 N 个元素

为什么默认是 -2（8KB）？ 这是 Redis 社区长期实践的经验值：

ziplist 太小（如 1KB）→ 链表节点过多，prev/next 指针开销增加，接近 linkedlist
ziplist 太大（如 64KB）→ 插入/删除时 memmove 代价过大
8KB 是一个平衡点：节点数量适中，单次 memmove ≤ 8KB

思考：为什么节点大小默认 -2（8KB），而不是更大或更小？顺着权衡推——节点太小（如 1KB），节点数量暴增、prev/next 指针开销回归 linkedlist；节点太大（如 64KB），单次插入删除的 memmove 代价过高、还让连锁更新的爆炸半径变大。8KB 是「节点数量」与「单次 memmove 成本」之间的社区经验平衡点，单次 memmove 被控制在 ≤8KB 这个可接受的量级。

五、连锁更新的范围控制

ziplist 的经典问题——连锁更新——在 quicklist 中得到了范围控制。

5.1 ziplist 的连锁更新原罪

ziplist 中每个 entry 的前一个 entry 的长度被编码在 prevlen 字段中，阈值正是 254：

#define ZIP_END 255         /* Special "end of ziplist" entry. */
#define ZIP_BIG_PREVLEN 254 /* ZIP_BIG_PREVLEN - 1 是 prevlen 能用 1 字节表示的最大前驱长度 */

/* Encode the length of the previous entry and write it to "p". Return the
 * number of bytes needed to encode this length if "p" is NULL. */
unsigned int zipStorePrevEntryLength(unsigned char *p, unsigned int len) {
    if (p == NULL) {
        return (len < ZIP_BIG_PREVLEN) ? 1 : sizeof(uint32_t) + 1;
    } else {
        if (len < ZIP_BIG_PREVLEN) {
            p[0] = len;
            return 1;
        } else {
            return zipStorePrevEntryLengthLarge(p,len);
        }
    }
}

/* 从 prevlen 前缀读回「前一个 entry 的长度」和它占用的字节数 */
#define ZIP_DECODE_PREVLENSIZE(ptr, prevlensize) do {                          \
    if ((ptr)[0] < ZIP_BIG_PREVLEN) {                                          \
        (prevlensize) = 1;                                                     \
    } else {                                                                   \
        (prevlensize) = 5;                                                     \
    }                                                                          \
} while(0)

zipStorePrevEntryLength 揭示了问题的本质：prevlen 编码的是前驱的长度，前驱 < 254 字节时占 1 字节，≥ 254 字节时占 sizeof(uint32_t)+1 = 5 字节。因为「当前 entry 的头」依赖「前驱的内容」，前驱一旦跨越 254 这个阈值，当前 entry 的头部就要从 1 字节膨胀到 5 字节。

当某个 entry 从 253B 变为 254B 时，其后继 entry 的 prevlen 从 1B 膨胀到 5B，导致后继 entry 自身增大 4B → 可能触发再后继的 prevlen 膨胀 → 级联传播。

在纯 ziplist 场景下（Redis 3.0），list 的所有元素在一个 ziplist 中，连锁更新可能传播整个链表——O(N) 的最坏时间复杂度。

5.2 quicklist 如何限制范围

quicklist 将元素分散到多个 ziplist 节点中，每个节点独立维护自己的连锁更新域。一个 ziplist 节点内的连锁更新不会传播到相邻节点，因为 prevlen 只在 ziplist 内部有效。

quicklist 中：
[Node 0: ziplist] → [Node 1: ziplist] → [Node 2: ziplist]
                   ↑ 隔离边界
连锁更新最多影响 Node 1 的全部 entry，不会跨 Node 传播

这意味着最坏情况下，连锁更新的代价从 O(N) 降为 O(N_entries_in_one_ziplist)（通常 ≤ 几百个 entry）。

思考：quicklist 为什么能把连锁更新的代价从 O(N) 压到 O(单个节点内)？关键在「prevlen 只在 ziplist 内部有效」——每个节点是独立的一段连续内存，prevlen 记录的是「本 ziplist 内的前驱长度」，不会跨节点引用。所以连锁更新最多在单个节点内传播，被节点边界硬生生切断。这其实也解释了「为什么要切成多个小 ziplist」的另一个理由：不仅控制 memmove 成本，也顺带把连锁更新的爆炸半径框在一个节点里。

六、Redis 7.0 的 listpack 迁移

Redis 7.0 将 quicklist 节点的内部存储从 ziplist 迁移到 listpack。listpack 是 ziplist 的后继替代品，核心改进是 消除了连锁更新——把「前驱长度 prevlen」换成了「末尾自描述 backlen」，写入时即确定、不再随前驱变化：

/* 决定元素用整数还是字符串编码，并算出编码头 enclen 的字节数 */
static inline int lpEncodeGetType(unsigned char *ele, uint32_t size, unsigned char *intenc, uint64_t *enclen) {
    int64_t v;
    if (lpStringToInt64((const char*)ele, size, &v)) {
        lpEncodeIntegerGetType(v, intenc, enclen);
        return LP_ENCODING_INT;
    } else {
        if (size < 64) *enclen = 1+size;
        else if (size < 4096) *enclen = 2+size;
        else *enclen = 5+(uint64_t)size;
        return LP_ENCODING_STRING;
    }
}

/* 把字符串连同变长编码头写入 buf：<encoding+len><data> */
static inline void lpEncodeString(unsigned char *buf, unsigned char *s, uint32_t len) {
    if (len < 64) {
        buf[0] = len | LP_ENCODING_6BIT_STR;
        memcpy(buf+1,s,len);
    } else if (len < 4096) {
        buf[0] = (len >> 8) | LP_ENCODING_12BIT_STR;
        buf[1] = len & 0xff;
        memcpy(buf+2,s,len);
    } else {
        buf[0] = LP_ENCODING_32BIT_STR;
        buf[1] = len & 0xff;
        buf[2] = (len >> 8) & 0xff;
        buf[3] = (len >> 16) & 0xff;
        buf[4] = (len >> 24) & 0xff;
        memcpy(buf+5,s,len);
    }
}

/* 在 entry 末尾反向写回变长 backlen（记录的是自身的长度），返回占用字节数 */
static inline unsigned long lpEncodeBacklen(unsigned char *buf, uint64_t l) {
    if (l <= 127) {
        if (buf) buf[0] = l;
        return 1;
    } else if (l <= 16383) {
        if (buf) {
            buf[0] = l>>7;
            buf[1] = (l&127)|128;
        }
        return 2;
    } else if (l <= 2097151) {
        if (buf) {
            buf[0] = l>>14;
            buf[1] = ((l>>7)&127)|128;
            buf[2] = (l&127)|128;
        }
        return 3;
    } else if (l <= 268435455) {
        if (buf) {
            buf[0] = l>>21;
            buf[1] = ((l>>14)&127)|128;
            buf[2] = ((l>>7)&127)|128;
            buf[3] = (l&127)|128;
        }
        return 4;
    } else {
        if (buf) {
            buf[0] = l>>28;
            buf[1] = ((l>>21)&127)|128;
            buf[2] = ((l>>14)&127)|128;
            buf[3] = ((l>>7)&127)|128;
            buf[4] = (l&127)|128;
        }
        return 5;
    }
}

对比 ziplist 的 [prevlen][encoding][data]，listpack 的布局是 [encoding+len][data][backlen]：lpEncodeString 把长度编码在 entry 的头部（1/2/5 字节的变长 encoding），lpEncodeBacklen 把自身长度写在 entry 的末尾（1~5 字节的 7-bit 分组编码）。反向遍历时从尾部读 backlen 即可回跳到前一个 entry。因为 backlen 记录的是「自己有多长」，这个值在写入时就确定了，前驱再怎么变化都不会波及它——连锁更新的根源（级联 prevlen 膨胀）被从结构上根除。

思考：backlen 为什么能根除连锁更新，而 prevlen 不能？追到根因——prevlen 存「前驱长度」，当前 entry 的头部依赖前驱内容，前驱一变就要跟着改；backlen 存「自身长度」，写入那一刻就确定，前驱再怎么变都不影响它。一个「依赖别人」、一个「只依赖自己」，这就是级联更新被从结构上消除的本质区别——这也是理解 ziplist 和 listpack 差异的那把钥匙。

quicklistNode 的 container 取值也随之变化：

/* quicklist node container formats */
#define QUICKLIST_NODE_CONTAINER_PLAIN 1
#define QUICKLIST_NODE_CONTAINER_PACKED 2

升级兼容性：PACKED(2) 就是 listpack 节点，PLAIN(1) 是超大元素节点——这个版本的 quicklist 已彻底移除 ziplist 容器，listpack 全面取代 ziplist；旧版 RDB 里的 ziplist 编码 list 在载入时会被转换为 listpack。

章末提问

Q1：quicklist 为什么是「双向链表 + listpack」的混合结构，而不是纯链表或纯 ziplist？

回答思路：结论——外层链表保证 O(1) 头尾操作，内层 listpack 把多个元素塞进连续内存减少指针开销，是两者的折中。因为：纯链表每个元素一个节点、三个指针 24B 额外开销且高度碎片化；纯 ziplist 无指针但长列表插入删除要 memmove 整个列表、O(N)。混合后「定位」交给链表、「紧凑存储」交给 listpack，两种结构的缺点都被节点边界隔断。

Q2：list-max-ziplist-size 为什么默认 -2（8KB）？太大太小各有什么问题？

回答思路：结论——-2 表示每个节点 ≤8KB，是「节点数量」与「单次 memmove 成本」之间的平衡点。因为：节点太小则节点数量暴增、指针开销回归 linkedlist；太大则单次插入删除的 memmove 代价过高，连锁更新的爆炸半径也变大。另外负值是「按字节数上限」、正值是「按元素数上限」，默认 -2 是社区长期实践的经验值。

Q3：ziplist 的连锁更新是什么？quicklist 和 listpack 分别怎么解决/限制它？

回答思路：结论——连锁更新是 prevlen 记录前驱长度、前驱跨过 254 字节阈值导致 prevlen 从 1B 膨胀到 5B 的级联重写，最坏 O(N)。因为：当前 entry 头部依赖前驱内容，前驱一变就触发后继头部膨胀；quicklist 把元素分散到多节点、让连锁更新被隔离在单个节点内（最坏降到 O(节点内 entry 数)）；listpack 把 prevlen 换成末尾 backlen 记录自身长度、写入即定不随前驱变化，从结构上彻底根除。