Go back

ZipList连锁更新到listpack——Redis压缩列表的演进

ZipList → listpack：Redis 如何根除连锁更新

一句话结论（30s）

ZipList 连锁更新的根因在于「当前 entry 的 prevlen 字段编码的是前驱长度」——因为前驱从 <254B 变到 ≥254B 时 prevlen 会由 1 字节膨胀到 5 字节，导致自身变大，进而可能触发后继 entry 的 prevlen 再次膨胀，形成 O(N) 的级联传播。关键设计：listpack 把 prevlen 改为末尾的 backlen（记录自身长度），写入时即确定、不随前驱变化。权衡：listpack 彻底消除连锁更新，反向遍历改为从尾部读 backlen 回跳，内存紧凑度与 ziplist 相同。

核心原理（2min）

ZipList 是连续内存块（zlbytes/zltail/zllen/entry…/zlend），每个 entry 为 ，用 prevlen 支持反向遍历。当某 entry 从 253B 变 254B 时，后继 entry 的 prevlen 从 1B 扩为 5B，引发「读旧数据→扩内存→写回」的连锁重分配，最坏一次修改触发上百次内存复制造成 CPU 尖刺。listpack 的 entry 改为 ，backlen 存自身长度，反向遍历时读 backlen 跳过当前 entry 回跳前驱，长度不依赖前驱，故级联更新被根除。Redis 7.0 起 listpack 全面替代 ziplist。

底层深入（5-10min）

ZipList 的设计与问题

ZipList 是 Redis 用于小数据 Hash/ZSet 的紧凑编码——连续内存块，没有指针开销：

<zlbytes><zltail><zllen><entry1><entry2>...<zlend>

每个 entry:
<prevlen><encoding><entry-data>

prevlen 存储前一个 entry 的长度——用于反向遍历。关键设计缺陷就藏在这段真实源码里：

#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 字节占 5 字节（sizeof(uint32_t)+1）。因为「当前 entry 的头」由「前驱的内容」决定，前驱一旦跨过 254 这个阈值，当前 entry 的头部就要膨胀 4 字节。

思考：为什么 prevlen 编码「前驱长度」就会引发连锁？追因果链——当前 entry 的头依赖前驱内容，前驱从 <254B 变成 ≥254B 时，prevlen 从 1 字节膨胀到 5 字节；而当前 entry 变大了 4 字节，又可能让它的后继 entry 的 prevlen 也跨过阈值、跟着膨胀……一步牵一步。根源不是「变长编码」本身，而是「当前 entry 的大小写在了别人（后继）头上」，于是任何一处变大都会向后传染。

连锁更新的多米诺效应

初始: [entry A (253 bytes)] [entry B (253 bytes)] [entry C (253 bytes)]
每个 entry 的 prevlen = 1 字节

插入一个 254 字节的 entry X 在 A 和 B 之间:
→ B 的 prevlen 从 1 字节扩为 5 字节（记录 X 的 254 字节）
→ B 大小从 253 → 257 字节
→ C 的 prevlen 从 1 字节扩为 5 字节（记录 B 的新大小 257）
→ C 大小从 253 → 257 字节
→ 继续向后传播...

这正是 ziplist.c 里 __ziplistCascadeUpdate 要处理的场景。它从发生变化的 entry 出发，先向后扫描统计需要追加多少字节，再一次性 realloc + memmove 腾出空间并反向回写：

unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) {
    zlentry cur;
    size_t prevlen, prevlensize, prevoffset; /* Info of the last changed entry. */
    size_t firstentrylen; /* Used to handle insert at head. */
    size_t rawlen, curlen = intrev32ifbe(ZIPLIST_BYTES(zl));
    size_t extra = 0, cnt = 0, offset;
    size_t delta = 4; /* Extra bytes needed to update a entry's prevlen (5-1). */
    unsigned char *tail = zl + intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl));

    /* Empty ziplist */
    if (p[0] == ZIP_END) return zl;

    zipEntry(p, &cur); /* no need for "safe" variant since the input pointer was validated by the function that returned it. */
    firstentrylen = prevlen = cur.headersize + cur.len;
    prevlensize = zipStorePrevEntryLength(NULL, prevlen);
    prevoffset = p - zl;
    p += prevlen;

    /* Iterate ziplist to find out how many extra bytes do we need to update it. */
    while (p[0] != ZIP_END) {
        assert(zipEntrySafe(zl, curlen, p, &cur, 0));

        /* Abort when "prevlen" has not changed. */
        if (cur.prevrawlen == prevlen) break;

        /* Abort when entry's "prevlensize" is big enough. */
        if (cur.prevrawlensize >= prevlensize) {
            if (cur.prevrawlensize == prevlensize) {
                zipStorePrevEntryLength(p, prevlen);
            } else {
                /* This would result in shrinking, which we want to avoid.
                 * So, set "prevlen" in the available bytes. */
                zipStorePrevEntryLengthLarge(p, prevlen);
            }
            break;
        }

        /* cur.prevrawlen means cur is the former head entry. */
        assert(cur.prevrawlen == 0 || cur.prevrawlen + delta == prevlen);

        /* Update prev entry's info and advance the cursor. */
        rawlen = cur.headersize + cur.len;
        prevlen = rawlen + delta;
        prevlensize = zipStorePrevEntryLength(NULL, prevlen);
        prevoffset = p - zl;
        p += rawlen;
        extra += delta;
        cnt++;
    }

    /* Extra bytes is zero all update has been done(or no need to update). */
    if (extra == 0) return zl;

    /* Update tail offset after loop. */
    if (tail == zl + prevoffset) {
        /* When the last entry we need to update is also the tail, update tail offset
         * unless this is the only entry that was updated (so the tail offset didn't change). */
        if (extra - delta != 0) {
            ZIPLIST_TAIL_OFFSET(zl) =
                intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra-delta);
        }
    } else {
        /* Update the tail offset in cases where the last entry we updated is not the tail. */
        ZIPLIST_TAIL_OFFSET(zl) =
            intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra);
    }

    /* Now "p" points at the first unchanged byte in original ziplist,
     * move data after that to new ziplist. */
    offset = p - zl;
    zl = ziplistResize(zl, curlen + extra);
    p = zl + offset;
    memmove(p + extra, p, curlen - offset - 1);
    p += extra;

    /* Iterate all entries that need to be updated tail to head. */
    while (cnt) {
        zipEntry(zl + prevoffset, &cur);
        rawlen = cur.headersize + cur.len;
        /* Move entry to tail and reset prevlen. */
        memmove(p - (rawlen - cur.prevrawlensize),
                zl + prevoffset + cur.prevrawlensize,
                rawlen - cur.prevrawlensize);
        p -= (rawlen + delta);
        if (cur.prevrawlen == 0) {
            zipStorePrevEntryLength(p, firstentrylen);
        } else {
            /* An entry's prevlen can only increment 4 bytes. */
            zipStorePrevEntryLength(p, cur.prevrawlen+delta);
        }
        prevoffset -= cur.prevrawlen;
        cnt--;
    }
    return zl;
}

delta = 4 是理解这段代码的钥匙：每个 entry 的 prevlen 从 1 字节扩到 5 字节净增 4 字节，extra 累加所有受影响 entry 需要腾出的空间，cnt 记录受影响 entry 的个数。一次插入触发连锁的 prevlen 扩展——每个受影响的后续 entry 都经历”读取旧数据→扩展内存→写回新位置”。 如果 ZipList 有 100 个 entry 全在边界附近，一次修改触发 100 次内存重写——严重 CPU 尖刺。

思考：为什么 delta = 4 是理解级联的钥匙？因为每个受影响 entry 的 prevlen 都从 1 字节扩到 5 字节，净增正好 4 字节；extra 累加所有受影响 entry 需要腾出的总空间，cnt 记录受影响的个数。最坏情况下每个后继 entry 都要经历「读旧数据→扩展内存→写回新位置」，100 个 entry 就是 100 次重写，这就是 O(N) CPU 尖刺的来源。看清「单点 +4、级联 N 次」就看清了连锁更新的代价。

listpack：根除连锁更新

listpack entry:
<encoding><data><backlen>

backlen：存储当前 entry 的长度（不是前一个 entry 的长度！）

真实的 backlen 编码就在 listpack.c 里，它用 7-bit 分组 + 最高位作延续位，把长度反向写在 entry 末尾：

/* 把长度 l 反向编码成变长字段写入 buf，返回占用的字节数（1~5） */
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;
    }
}

彻底去掉了 prevlen。 backlen 存的是”我自己有多长”，用于反向遍历时跳过当前 entry 到达前一个 entry。注意 lpEncodeBacklen 的入参只有一个长度值 l——它只依赖当前 entry 自身，写入那一刻就确定了，不会因为前一个 entry 变化而需要更新。连锁更新的根源（级联 prevlen 变化）被彻底消除。

思考：backlen 为什么能彻底根除，而不是仅仅缓解？因为它把「依赖前驱」换成了「依赖自己」——backlen 记录自身长度，写入那一刻就确定，前驱怎么变都不影响它；反向遍历时从尾部读 backlen 回跳即可，不再需要知道前驱多长。于是「一处变大→向后传染」的链条被从结构上掐断：因为后继 entry 的头部里根本没有「前驱长度」这个会变的东西了。

Redis 7.0 用 listpack 全面替代 ziplist。

embstr 44 字节阈值计算

Redis 的 embstr 编码将 RedisObject + SDS 分配在同一块内存中。阈值 44 来自精确的 jemalloc 对齐：

RedisObject: 16B
sdshdr8:     3B (len + alloc + flags)
'\0':        1B
内容:        ?B

16 + 3 + 1 + ? = jemalloc 最小分配单元 64B
→ 内容 = 64 - 20 = 44B

超过 44 字节的内容 → Redis 用 raw 编码（两次分配：RedisObject + 独立 SDS），多一次 jemalloc 开销。

总结

ZipListlistpack
反向遍历prevlen（前一个的长度）backlen（自己的长度）
连锁更新有（prevlen 变长级联传播）无（backlen 写入时确定不变）
内存效率高（紧凑布局）同
引入版本Redis 早期Redis 7.0 替代 ZipList

章末提问

Q1：ZipList 连锁更新的根因是什么？为什么 prevlen 会触发级联传播？

回答思路：结论——根因是 prevlen 记录的是前驱长度，当前 entry 的头部依赖前驱内容，前驱跨过 254 字节阈值时 prevlen 从 1B 膨胀到 5B。因为：当前 entry 因此变大会让后继 entry 的 prevlen 也跨阈值膨胀，级联传播；这不是变长编码的错，而是「当前 entry 的大小写在了别人（后继）头上」，任何一处变大都会向后传染。

Q2：listpack 是怎么根除连锁更新的？backlen 和 prevlen 的本质区别是什么？

回答思路：结论——listpack 把 prevlen 换成末尾的 backlen，记录自身长度、写入即定，反向遍历从尾部读 backlen 回跳。因为：backlen 只依赖自身、不随前驱变化，后继 entry 头部不再存「会变的前驱长度」，级联更新的根源被从结构上根除；且内存紧凑度与 ziplist 相同。本质区别就是「依赖别人」vs「只依赖自己」。

Q3：连锁更新的最坏复杂度是多少？quicklist 和 listpack 分别怎么限制/解决它？

回答思路：结论——连锁更新最坏 O(N)（整个 ziplist 的元素数），一次修改触发上百次内存重写、造成 CPU 尖刺。因为：prevlen 每跨阈值净增 4 字节会向后传染；quicklist 把元素分散到多个节点、让连锁更新被隔离在单个节点内（最坏降到 O(节点内 entry 数)），listpack 则通过 backlen 从结构上彻底根除。

Share this post on:
Share this post via WhatsAppShare this post on FacebookShare this post on XShare this post via TelegramShare this post on PinterestShare this post via email
Previous Post
布隆过滤器 vs 布谷鸟过滤器——为什么布隆过滤器不支持删除？
Next Post
Redis渐进式rehash