quicklist 源码分析(List 底层)

quicklist 是 List 类型的底层结构:一个双向链表,但每个节点装的不是单个元素,而是一段 listpack(紧凑连续内存,塞多个元素)。
它解决的是两难:纯双向链表每个元素背 prev/next 两个指针,内存开销大、碎片多;单个大 listpack 中间插删要整块 memmove,元素一多成本失控。
quicklist 把两者拼起来——链表负责 O(1) 两端增删,listpack 负责省内存,中段冷数据还能 LZF 压缩。

先看三个核心结构。quicklistNode 用位域死死压在 32 字节,一个字段都不多给:

代码块C · 35 行收起展开

// 基于本地 Redis 仓 (unstable), src/quicklist.h
typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *entry;        // 指向 listpack；被压缩时指向 quicklistLZF
    size_t sz;             /* entry size in bytes */    // 永远记「未压缩」的字节数，解压时靠它分配缓冲
    unsigned int count : 16;     /* count of items in listpack */   // listpack 上限 64KB，元素数撑不爆 16 位
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* PLAIN==1 or PACKED==2 */    // PLAIN=大元素独占节点，entry 是裸字节数组不是 listpack
    unsigned int recompress : 1; /* was this node previous compressed? */   // 被临时解压给人用，用完要压回去的标记
    unsigned int attempted_compress : 1; /* node can't compress; too small */   // 仅 REDIS_TEST 下的验证标记，生产路径不读它
    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;

// ...

typedef struct quicklistLZF {
    size_t sz; /* LZF size in bytes*/   // 压缩后的长度；解压后的长度在 node->sz 里
    char compressed[];                  // 柔性数组：头 + 压缩数据一次 zmalloc，少一层指针
} quicklistLZF;

// ...

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all listpacks */  // LLEN O(1) 靠它，不用遍历
    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 */   // list-max-listpack-size：正=限元素个数，负=限字节数
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */    // list-compress-depth：两端各留几个节点不压
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];  // 柔性数组：不用 bookmark 时零开销
} quicklist;

写入路径的全部智慧集中在「一个节点还能不能再塞」这一个判断上。fill 为负时查表限字节数(-1 到 -5 对应 4KB 到 64KB,quicklistCreate 的初始值是 -2 即 8KB),为正时限元素个数但仍有 8KB 兜底:

代码块C · 81 行收起展开

// 基于本地 Redis 仓 (unstable), src/quicklist.c
static const size_t optimization_level[] = {4096, 8192, 16384, 32768, 65536};  // fill=-1..-5 对应的单节点字节上限

// ...

#define SIZE_SAFETY_LIMIT 8192      // 按个数限制时的兜底：listpack 再怎么也不许超 8KB

// ...

#define SIZE_ESTIMATE_OVERHEAD 8    // 预估一条 listpack entry 的头部开销，故意高估

// ...

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);    // 负 fill 查 optimization_level 表
    }
}

// ...

static int isLargeElement(size_t sz, int fill) {    // 「大元素」的标准跟着 fill 走，不是写死的 8KB
    if (unlikely(packed_threshold != 0)) return sz >= packed_threshold;     // 仅测试套件用的开关
    if (fill >= 0)
        return !sizeMeetsSafetyLimit(sz);
    else
        return sz > quicklistNodeNegFillLimit(fill);
}

REDIS_STATIC int _quicklistNodeAllowInsert(const quicklistNode *node,
                                           const int fill, const size_t sz) {
    if (unlikely(!node))
        return 0;

    if (unlikely(QL_NODE_IS_PLAIN(node) || isLargeElement(sz, fill)))
        return 0;   // PLAIN 节点只容一个大元素，谁都不能再挤进去

    // ...
    size_t new_sz = node->sz + sz + SIZE_ESTIMATE_OVERHEAD;     // 不真插一次再量，用高估的增量预判，省一次 realloc+memmove
    if (unlikely(quicklistNodeExceedsLimit(fill, new_sz, node->count + 1)))
        return 0;
    return 1;
}

// ...

/* Add new entry to head node of quicklist.
 *
 * Returns 0 if used existing head.
 * Returns 1 if new head created. */
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);   // 大元素不进 listpack，独占一个 PLAIN 节点
        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);  // 头节点没满：直接进它的 listpack
        quicklistNodeUpdateSz(quicklist->head);
        quicklistUpdateAllocSize(quicklist, quicklist->head->sz, oldsize);
    } else {
        quicklistNode *node = quicklistCreateNode(quicklist);
        node->entry = lpPrepend(lpNew(0), value, sz);   // 满了：新建节点装单元素 listpack，挂到链表头
        quicklistNodeUpdateSz(node);
        quicklistUpdateAllocSize(quicklist, node->sz, 0);
        _quicklistInsertNodeBefore(quicklist, quicklist->head, node);
    }
    quicklist->count++;
    quicklist->head->count++;
    return (orig_head != quicklist->head);
}

中段压缩是 quicklist 独有的第二层省内存手段。压缩以节点为单位、尽力而为,压不动就保持 RAW:

代码块C · 105 行收起展开

// 基于本地 Redis 仓 (unstable), src/quicklist.c
#define MIN_COMPRESS_BYTES 48   // 不到 48 字节不压：连 LZF 的头部开销都赚不回来

// ...

#define MIN_COMPRESS_IMPROVE 8  // 至少省 8 字节才保留压缩结果，防「越压越大」

// ...

REDIS_STATIC int __quicklistCompressNode(quicklist *quicklist, quicklistNode *node) {
    // ...
    if (node->dont_compress) return 0;

    /* validate that the node is neither
     * tail nor head (it has prev and next)*/
    assert(node->prev && node->next);   // head/tail 永远不压：两端是 push/pop 热点，压了每次操作都要先解压

    node->recompress = 0;
    /* Don't bother compressing small values */
    if (node->sz < MIN_COMPRESS_BYTES)
        return 0;

    quicklistLZF *lzf = zmalloc(sizeof(*lzf) + node->sz);

    /* Cancel if compression fails or doesn't compress small enough */
    if (((lzf->sz = lzf_compress(node->entry, node->sz, lzf->compressed,
                                 node->sz)) == 0) ||
        lzf->sz + MIN_COMPRESS_IMPROVE >= node->sz) {
        /* lzf_compress aborts/rejects compression if value not compressible. */
        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;
    quicklistUpdateAllocSize(quicklist, sizeof(*lzf) + lzf->sz, node->sz);
    return 1;
}

// ...

/* Force node to not be immediately re-compressible */
#define quicklistDecompressNodeForUse(_ql, _node)                              \
    do {                                                                       \
        if ((_node) && (_node)->encoding == QUICKLIST_NODE_ENCODING_LZF) {     \
            __quicklistDecompressNode((_ql), (_node));                         \
            (_node)->recompress = 1;                                           \
        }                                                                      \
    } while (0)     // 中段节点被读写前先走这里解压，recompress=1 记下「用完压回去」

// ...

#define quicklistCompress(_ql, _node)                                          \
    do {                                                                       \
        if ((_node)->recompress)                                               \
            quicklistCompressNode((_ql), (_node));                             \
        else                                                                   \
            __quicklistCompress((_ql), (_node));                               \
    } while (0)     // 压缩总入口：带 recompress 标记走快路径直接压回，否则做一次深度扫描

// ...

REDIS_STATIC void __quicklistCompress(quicklist *quicklist,
                                      quicklistNode *node) {
    if (quicklist->len == 0) return;

    /* The head and tail should never be compressed (we should not attempt to recompress them) */
    assert(quicklist->head->recompress == 0 && quicklist->tail->recompress == 0);

    /* If length is less than our compress depth (from both sides),
     * we can't compress anything. */
    if (!quicklistAllowsCompression(quicklist) ||
        quicklist->len < (unsigned int)(quicklist->compress * 2))
        return;

    // ...

    quicklistNode *forward = quicklist->head;
    quicklistNode *reverse = quicklist->tail;
    int depth = 0;
    int in_depth = 0;
    while (depth++ < quicklist->compress) {     // 双指针从两端向内各走 compress 步，路过的节点全部解压
        quicklistDecompressNode(quicklist, forward);
        quicklistDecompressNode(quicklist, reverse);

        if (forward == node || reverse == node)
            in_depth = 1;

        /* We passed into compress depth of opposite side of the quicklist
         * so there's no need to compress anything and we can exit. */
        if (forward == reverse || forward->next == reverse)
            return;

        forward = forward->next;
        reverse = reverse->prev;
    }

    if (!in_depth)
        quicklistCompressNode(quicklist, node);     // 刚动过的节点落在深度之外，把它压掉

    /* At this point, forward and reverse are one node beyond depth */
    quicklistCompressNode(quicklist, forward);
    quicklistCompressNode(quicklist, reverse);
}

原理串讲

以一条 LPUSH key value 走完整链路。命令层最终调到 quicklistPushHead,第一件事不是找位置,而是 isLargeElement:元素超过当前 fill 对应的字节上限(默认 -2 即 8KB)就直接 __quicklistInsertPlainNode,新建一个 container=PLAIN 的节点独占它,根本不碰 listpack。
为什么大元素要隔离?因为 listpack 的一切操作都是整块 realloc + memmove,一个 5MB 的元素混进去,之后这个节点的每次插删都要搬这 5MB,而且它也会把「按字节数限容」的判断彻底打穿——干脆让它自成一个节点,链表指针天然隔离了搬移成本。

普通元素走 _quicklistNodeAllowInsert 判断头节点还装不装得下。
这里有个容易忽略的细节:它不真的插入再检查,而是用 node->sz + sz + SIZE_ESTIMATE_OVERHEAD 预估插入后的大小。

代码块JAVA · 2 行收起展开

为什么用估算而且故意高估?因为 listpack 每条 entry 有 1~11 字节不等的头部,精确值只有真插进去才知道,而「插进去发现超限再拆出来」等于白付一次 realloc + memmove;高估 8 字节最多让节点比 4KB 下限小几个字节,代价几乎为零,换来的是判断和执行一次完成。
装得下就 `lpPrepend` 进头节点的 listpack 并 `quicklistNodeUpdateSz` 刷新缓存的 sz;装不下则 `quicklistCreateNode` + `lpNew` 造一个单元素新节点,`_quicklistInsertNodeBefore` 挂到链表头。

挂接最终落到 __quicklistInsertNode,它做完指针缝合、len++ 之后调 quicklistCompress,这是压缩机制的总入口:若节点带着 recompress 标记就地压回去,否则走 __quicklistCompress——双指针从 head 和 tail 同时向内走 compress 步,沿途节点全部解压(保证两端深度内永远是 RAW),走完后把深度边界外的第一个节点压掉。
为什么每次插入节点都要跑这个扫描?因为插入会把原来处于「深度边界」的节点向内挤一格,它的压缩状态必须跟着变;而深度通常配 1 或 2,这个循环实际只走一两步,代价是常数级的。
也因此 quicklistPush 入口处直接 assert head/tail 一定未压缩——两端是 List 的访问热点(LPUSH/RPOP 的工作面),永远保持可直接读写。

反方向的 RPOP 走 quicklistPop → quicklistPopCustom:lpSeek(node->entry, -1) 定位尾元素,lpGetValue 取值(字符串走 saver 回调拷贝,整数直接由 sval 带出),然后 quicklistDelIndex 删除。
节点里最后一个元素被删掉时 __quicklistDelNode 摘掉整个节点,并再次调 __quicklistCompress(quicklist, NULL)——摘节点让两端深度内「多出」一个被压缩的节点,得把它解压回来,压缩不变量在增删两个方向都要维护。

中间插入(LINSERT)在 _quicklistInsert 里,是各种边界的集大成:

目标节点没满直接 lpInsertString;
满了但插入点恰好在节点边缘、邻居有空位,就把元素塞进邻居(lpPrepend 进 next 或 lpAppend 进 prev);
邻居也满就新建节点;
最糟的情况——满节点的正中间——只能 _quicklistSplitNode 把 listpack 一分为二,插完再 _quicklistMergeNodes 尝试把碎节点合并回去,避免链表被切得越来越碎。

设计取舍

fill 一个字段两种语义:正数限个数(给用户直觉),负数查表限字节(给内存控制),正数时还有 8KB 安全上限兜底——防止「个数没超但单节点巨大」。
压缩全程尽力而为:小于 48 字节不压、省不到 8 字节不存,任何失败都静默保持 RAW,encoding 位保证读路径永远能分辨。
count/sz/alloc_size 全是冗余缓存,换 LLEN、MEMORY USAGE 的 O(1);代价是每次增删都要同步维护,源码里大量 quicklistNodeUpdateSz/quicklistUpdateAllocSize 就是在还这笔债。
Redis 7.0 起 listpack 全面接替 ziplist:ziplist 每条 entry 记「前一条的长度」,一次插入可能引发连锁扩容(级联更新);listpack 只记自身长度,从结构上消灭了这个问题。
版本注意:7.x 的小 List 编码直接是单个 listpack(OBJ_ENCODING_LISTPACK),超过 list-max-listpack-size 或出现大元素才升级为 quicklist,quicklist 是「大 List」的形态。

quicklist 源码分析(List 底层)

原理串讲

设计取舍

延伸阅读