为什么要有 ziplist

普通链表的内存浪费问题

指针开销大于实际数据
缓存不友好的内存访问模式

ziplist的设计哲学

核心设计思想

在数据量小的情况下，它比普通链表更高效

空间换时间：紧凑内存布局提升遍历速度
计算换内存：偏移量计算替代指针存储

与普通链表的对比

内存占用对比示例（“hello"存储案例）

// 普通链表节点
typedef struct listNode {
    struct listNode *prev;    // 8字节指针
    struct listNode *next;    // 8字节指针  
    void *value;              // 8字节指针
} listNode;

// 假设存储字符串 "hello" (5字节)
// 实际内存占用：8+8+8+5 = 29字节
// 其中指针占用：24字节，数据只占：5字节

// ziplist 中存储 "hello" 的方式，没有指针，只有偏移量信息

// 节点结构：<prevlen> <encoding> <data>
// 例如：[02] [00 05] [68 65 6c 6c 6f]
// 其中：
// 02 = 前一个节点长度(2字节)
// 00 05 = 编码类型(字符串) + 长度(5)
// 68 65 6c 6c 6f = "hello" 的ASCII码

// 总内存占用：1+2+5 = 8字节
// 比普通链表节省：29-8 = 21字节！

访问模式差异

// 普通链表遍历：用指针直接访问
listNode *current = list->head;
while (current != NULL) {
    // 直接通过指针访问下一个节点
    current = current->next;  // 直接跳转
}

// Ziplist：用偏移量计算访问
// ziplist 遍历 - 通过计算偏移量找到下一个节点
unsigned char *ziplistNext(unsigned char *zl, unsigned char *p) {
    // 关键：通过计算当前节点的长度来找到下一个节点
    p += zipRawEntryLength(p);  // 计算偏移量，而不是直接跳转
    
    if (p[0] == ZIP_END) {
        return NULL;
    }
    return p;
}

// 向后遍历 - 通过 prevlen 字段计算前一个节点位置
unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p) {
    unsigned int prevlensize, prevlen = 0;
    
    // 关键：解码 prevlen 字段，计算前一个节点的偏移量
    ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
    
    // 通过偏移量计算前一个节点位置
    p -= prevlen;  // 计算偏移量，而不是直接跳转
    return p;
}

不存储指针：ziplist 中每个节点不存储 next 和 prev 指针
存储偏移量：只存储前一个节点的长度（prevlen）
运行时计算：访问下一个节点时，通过当前节点长度 + 当前节点位置计算
访问前一个节点：通过当前节点位置 - prevlen 计算

“计算换内存"的本质：用 CPU 的 加/减 法运算，代替内存中的指针存储

ziplist 是一个特殊编码的紧凑型双向链表，特殊之处在于：没有维护双向指针，prev、next，而是存储了上一个 entry 的长度和当前 entry 的长度，通过长度推算下一个元素

本质上就是一个字节数组
为节约内存而设计的一种线性结构
可以包含多个元素，每个元素可以是一个字节数组或一个整数

通过宏定义操作字段

ziplist允许在列表的两端进行O(1)时间的push和pop操作，但由于每次操作都需要重新分配内存，实际复杂度与ziplist使用的内存量相关

应用

早期

List类型：当列表元素较少时使用ziplist编码
Hash类型：当哈希表元素较少时使用ziplist编码
ZSet类型：当有序集合元素较少时使用ziplist编码

现在

向后兼容性：支持旧版本 RDB 文件
数据迁移：从 ziplist 到 listpack 的转换
测试代码：保持测试覆盖

结构

整体

<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

┌─────────────────────────────────────────────────────────────────────────────────┐
│                        Ziplist 完整结构                                         │
│                                                                                 │
│  ┌─────────────┬─────────────┬─────────────┬─────────────────┬───────────────┐  │
│  │   zlbytes   │   zltail    │   zllen     │     entries     │    zlend      │  │
│  │   (4字节)   │   (4字节)   │   (2字节)   │     (变长)      │   (1字节)     │  │
│  │             │             │             │                 │               │  │
│  │             │             │             │                 │               │  │
│  │ 总字节数    │ 尾部偏移量  │  条目数量   │ 实际的entry数据 │  结束标记     │  │
│  └─────────────┴─────────────┴─────────────┴─────────────────┴───────────────┘  │ 
│      ↑              ↑             ↑                               ↑         │
│  ZIPLIST_BYTES ZIPLIST_TAIL_OFFSET ZIPLIST_LENGTH               ZIP_END         │
│                                                                                 │
│              头部信息(10字节)                数据区域(变长)   结束标记(1字节)   │ 
└─────────────────────────────────────────────────────────────────────────────────┘

zlbytes

整个 ziplist 占用的字节数，包括 zlbytes 字段本身的4字节
zltail

最后一个条目的偏移量，用于O(1) 快速定位尾部
zllen

entry的数量。当超过2^16-2个entry时，此值设为2^16-1，需要遍历整个列表才能知道实际数量
entry

实际的条目数据
zlend

特殊entry，表示ziplist的结束，值为255 (0xFF)，确保不会与正常entry编码冲突

字段	大小	偏移量	宏定义
zlbytes	4字节	0	ZIPLIST_BYTES(zl)	(((uint32_t)(zl)))
zltail	4字节	4	ZIPLIST_TAIL_OFFSET(zl)	(((uint32_t)((zl)+sizeof(uint32_t))))
zllen	2字节	8	ZIPLIST_LENGTH(zl)	(((uint16_t)((zl)+sizeof(uint32_t)*2)))
entries	变长	10
zlend	1字节	最后1字节	ZIP_END

条目结构

每个entry都包含以下元数据：

<prevlen> <encoding> <entry-data>
 1/5字节  1/2/5字节  变长

prevlen编码机制

// 如果前一个entry长度 < 254字节：使用1字节存储
// 如果前一个entry长度 >= 254字节：使用5字节存储 (1字节标记 + 4字节长度)
#define ZIP_BIG_PREVLEN 254

encoding字段编码

字符串编码

|00pppppp| (1字节): 长度≤63字节的字符串，6位表示长度
|01pppppp|qqqqqqqq| (2字节): 长度≤16383字节的字符串，14位表示长度（大端序）
|10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| (5字节): 长度≥16384字节的字符串，32位表示长度（大端序

整数编码

|11000000| (3字节): int16_t整数
|11010000| (5字节): int32_t整数
|11100000| (9字节): int64_t整数
|11110000| (4字节): 24位有符号整数
|11111110| (2字节): 8位有符号整数
|1111xxxx| (1字节): 4位立即整数，值范围0-12（实际编码值1-13）

┌─────────────────────────────────────────────────────────────────┐
│                    Ziplist 整体布局                             │
│  <zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend> │
│                                                                 │
│  ┌────────────────────────────────────────────────────────────┐ │
│  │                实际 Entry 编码                             │ │
│  │  <prevlen> <encoding> <entry-data>                         │ │
│  │                                                            │ │
│  │  ┌───────────────────────────────────────────────────────┐ │ │
│  │  │              Zlentry 结构体                           │ │ │
│  │  │  (解析后的元数据)                                     │ │ │
│  │  │  prevrawlensize, prevrawlen, lensize, len,            │ │ │
│  │  │  headersize, encoding, p                              │ │ │
│  │  └───────────────────────────────────────────────────────┘ │ │
│  │                                                            │ │
│  │  ┌───────────────────────────────────────────────────────┐ │ │
│  │  │              ZiplistEntry 结构体                      │ │ │
│  │  │  (用户友好的接口)                                     │ │ │
│  │  │  sval, slen, lval                                     │ │ │
│  │  └───────────────────────────────────────────────────────┘ │ │
│  └────────────────────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────────────────┘

Zlentry 结构体

typedef struct zlentry {
    unsigned int prevrawlensize; /* prevlen字段的字节数 */
    unsigned int prevrawlen;     /* 前一个entry的长度 */
    unsigned int lensize;        /* encoding字段的字节数 */
    unsigned int len;            /* 实际数据的长度 */
    unsigned int headersize;     /* 头部总长度 */
    unsigned char encoding;      /* 编码类型 */
    unsigned char *p;            /* 指向entry起始位置的指针 */
} zlentry;

ZiplistEntry 结构体

typedef struct {
    unsigned char *sval;  /* 字符串值指针 */
    unsigned int slen;    /* 字符串长度 */
    long long lval;       /* 整数值 */
} ziplistEntry;

转换关系图

┌──────────────────┐   解析     ┌─────────────────┐   转换     ┌─────────────────┐
│  实际 Entry 编码 │ ────────→ │   Zlentry       │ ────────→ │  ZiplistEntry   │
│  (二进制格式)    │            │  (元数据)       │            │  (用户接口)     │
└──────────────────┘            └─────────────────┘            └─────────────────┘
         │                            │                            │
         │ 内存存储                   │ 程序内部使用               │ 用户层面使用
         │ 紧凑高效                   │ 解析结果                   │ 类型统一
         │ 变长编码                   │ 结构化信息                 │ 友好接口

创建Ziplist并插入数据

创建空的Ziplist

unsigned char *ziplistNew(void) {
    unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;  // 10 + 1 = 11字节
    unsigned char *zl = zmalloc(bytes);
    ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);                    // 设置总字节数
    ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE); // 设置尾部偏移
    ZIPLIST_LENGTH(zl) = 0;                                     // 设置条目数量为0
    zl[bytes-1] = ZIP_END;                                      // 设置结束标记
    return zl;
}

详细步骤

1. 计算总字节数

ZIPLIST_HEADER_SIZE = sizeof(uint32_t)*2 + sizeof(uint16_t) = 4+4+2 = 10字节
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
- 第一个 uint32_t：zlbytes - 整个 ziplist 的总字节数
- 第二个 uint32_t：zltail - 最后一个 entry 的偏移量
- 一个 uint16_t：zllen - entry 的数量
ZIPLIST_END_SIZE = sizeof(uint8_t) = 1字节
bytes = 10 + 1 = 11字节

2. 分配内存

使用 zmalloc(bytes) 分配11字节的内存

3. 初始化头部字段

ZIPLIST_BYTES(zl) = 11：设置总字节数为11
ZIPLIST_TAIL_OFFSET(zl) = 10：设置尾部偏移为10（指向zlend）
ZIPLIST_LENGTH(zl) = 0：设置条目数量为0

4. 设置结束标记

zl[10] = ZIP_END：在最后一个字节设置0xFF

初始内存布局：

┌─────────────┬─────────────┬─────────────┬─────────────┐
│   zlbytes   │   zltail    │   zllen     │    zlend    │
│   (4字节)   │   (4字节)   │   (2字节)   │   (1字节)   │
│             │             │             │             │
│ 0x0000000B  │ 0x0000000A  │ 0x0000      │    0xFF     │
└─────────────┴─────────────┴─────────────┴─────────────┘

插入数据到Ziplist

// 用户调用
unsigned char *zl = ziplistNew();
zl = ziplistPush(zl, (unsigned char*)"hello", 5, ZIPLIST_TAIL);

// ziplistPush 函数
unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where) {
    unsigned char *p;
    p = (where == ZIPLIST_HEAD) ? ZIPLIST_ENTRY_HEAD(zl) : ZIPLIST_ENTRY_END(zl);
    return __ziplistInsert(zl,p,s,slen);
}

zl: ziplist 指针
s: 要插入的字符串
slen: 字符串长度
where: 插入位置（ZIPLIST_HEAD 或 ZIPLIST_TAIL）

插入位置确定

p = (where == ZIPLIST_HEAD) ? ZIPLIST_ENTRY_HEAD(zl) : ZIPLIST_ENTRY_END(zl);

为后续的 __ziplistInsert 函数提供正确的插入点

头部插入 (ZIPLIST_HEAD)

┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                    头部插入示例                                                             │
├─────────────┬─────────────┬─────────────┬─────────────────────────────────────────────────────┬─────────────┤
│   HEADER    │             │             │              entries                                │    zlend    │
│   (10字节)  │             │             │              (变长)                                 │   (1字节)   │
│             │             │             │                                                     │             │
│             │             │             │ [NEW][entry1][entry2][entry3]                       │    0xFF     │
│             │             │             │  ↑                                                 │             │
│             │             │             │   └── ZIPLIST_ENTRY_HEAD 指向的位置                 │             │
└─────────────┴─────────────┴─────────────┴─────────────────────────────────────────────────────┴─────────────┘

#define ZIPLIST_ENTRY_HEAD(zl)  ((zl)+ZIPLIST_HEADER_SIZE)

含义：返回第一个 entry 的位置
计算：zl + 10（跳过头部10字节）
位置：ziplist 中第一个实际数据的位置

确定插入位置

// where = ZIPLIST_HEAD (值为0)
// 条件判断：where == ZIPLIST_HEAD (0) 为直
// 所以选择：ZIPLIST_ENTRY_HEAD(zl)

// 插入到第一个位置
p = ZIPLIST_ENTRY_HEAD(zl);	// zl + 10
// 结果：新元素成为第一个元素

尾部插入 (ZIPLIST_TAIL)

┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                    尾部插入示例                                                             │
├─────────────┬─────────────┬─────────────┬─────────────────────────────────────────────────────┬─────────────┤
│   HEADER    │             │             │              entries                                │    zlend    │
│   (10字节)  │             │             │              (变长)                                 │   (1字节)   │
│             │             │             │                                                     │             │
│             │             │             │ [entry1][entry2][entry3][NEW]                       │    0xFF     │
│             │             │             │                           ↑                        │             │
│             │             │             │                            └── ZIPLIST_ENTRY_END 指向的位置       │             
└─────────────┴─────────────┴─────────────┴─────────────────────────────────────────────────────┴─────────────┘

#define ZIPLIST_ENTRY_END(zl)   ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-ZIPLIST_END_SIZE)

含义：返回最后一个 entry 之后的位置（即 zlend 之前）
计算：zl + 总字节数 - 1
位置：ziplist 的末尾，zlend 标记之前

确定插入位置

// where = ZIPLIST_TAIL (值为1)
// 条件判断：where == ZIPLIST_HEAD (0) 为假
// 所以选择：ZIPLIST_ENTRY_END(zl)
p = ZIPLIST_ENTRY_END(zl);

计算具体位置

// 假设 zl 的总字节数是 11（空 ziplist）
// ZIPLIST_BYTES(zl) = 11
// ZIPLIST_END_SIZE = 1
// p = zl + 11 - 1 = zl + 10

// 结果：新元素成为最后一个元素

__ziplistInsert()

unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
    size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen, newlen;
    unsigned int prevlensize, prevlen = 0;
    size_t offset;
    int nextdiff = 0;
    unsigned char encoding = 0;
    long long value = 123456789;
    zlentry tail;

    /* 步骤1: 确定前一个entry的长度 */
    if (p[0] != ZIP_END) {
        ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
    } else {
        unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
        if (ptail[0] != ZIP_END) {
            prevlen = zipRawEntryLengthSafe(zl, curlen, ptail);
        }
    }

    /* 步骤2: 尝试编码为整数 */
    if (zipTryEncoding(s,slen,&value,&encoding)) {
        reqlen = zipIntSize(encoding);
    } else {
        reqlen = slen;
    }

    /* 步骤3: 计算需要的总字节数 */
    reqlen += zipStorePrevEntryLength(NULL,prevlen);
    reqlen += zipStoreEntryEncoding(NULL,encoding,slen);

    /* 步骤4: 检查是否需要调整下一个entry的prevlen字段 */
    int forcelarge = 0;
    nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
    if (nextdiff == -4 && reqlen < 4) {
        nextdiff = 0;
        forcelarge = 1;
    }

    /* 步骤5: 重新分配内存 */
    offset = p-zl;
    newlen = curlen+reqlen+nextdiff;
    zl = ziplistResize(zl,newlen);
    p = zl+offset;

    /* 步骤6: 移动现有数据 */
    if (p[0] != ZIP_END) {
        memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);
        
        /* 更新下一个entry的prevlen字段 */
        if (forcelarge)
            zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
        else
            zipStorePrevEntryLength(p+reqlen,reqlen);

        /* 更新尾部偏移 */
        ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);
    } else {
        /* 这是新的尾部entry */
        ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
    }

    /* 步骤7: 级联更新（如果需要） */
    if (nextdiff != 0) {
        offset = p-zl;
        zl = __ziplistCascadeUpdate(zl,p+reqlen);
        p = zl+offset;
    }

    /* 步骤8: 写入新entry */
    p += zipStorePrevEntryLength(p,prevlen);
    p += zipStoreEntryEncoding(p,encoding,slen);
    if (ZIP_IS_STR(encoding)) {
        memcpy(p,s,slen);
    } else {
        zipSaveInteger(p,value,encoding);
    }
    
    /* 步骤9: 更新条目数量 */
    ZIPLIST_INCR_LENGTH(zl,1);
    return zl;
}

步骤1：确定前一个entry的长度

if (p[0] != ZIP_END) {
    ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
} else {
    unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
    if (ptail[0] != ZIP_END) {
        prevlen = zipRawEntryLengthSafe(zl, curlen, ptail);
    }
}

插入位置的统一处理

中间插入：直接解析当前位置的prevlen
末尾插入：找到真正的最后一个entry并计算其长度

第一个分支：p[0] != ZIP_END

如果当前位置p不是ziplist的末尾（ZIP_END = 255）
说明在ziplist中间插入，可以直接从当前位置解码前一个entry的长度
ZIP_DECODE_PREVLEN(p, prevlensize, prevlen)会解析p指向的entry的prevlen字段

第二个分支：p[0] == ZIP_END

如果当前位置是ziplist末尾，说明要在ziplist末尾插入新entry
需要找到真正的最后一个entry作为新entry的前一个entry

边界条件的处理

unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
if (ptail[0] != ZIP_END) {
    prevlen = zipRawEntryLengthSafe(zl, curlen, ptail);
}

ZIPLIST_ENTRY_TAIL(zl)获取ziplist的最后一个entry
但还要检查ptail[0] != ZIP_END，这是为了处理空ziplist的情况
如果ziplist为空，ZIPLIST_ENTRY_TAIL(zl)会指向ZIP_END字节，此时prevlen保持为0

安全的长度计算

prevlen = zipRawEntryLengthSafe(zl, curlen, ptail);

使用zipRawEntryLengthSafe而不是zipRawEntryLength：

Safe版本会进行边界检查，防止访问越界
传入zl、curlen、ptail参数进行安全验证
这在处理可能损坏的ziplist时非常重要

步骤2：尝试编码为整数

if (zipTryEncoding(s,slen,&value,&encoding)) {
    reqlen = zipIntSize(encoding);
} else {
    reqlen = slen;
}

尝试将字符串编码为整数（如果可能）
对于"hello”，无法编码为整数，所以 reqlen = 5

步骤3：计算需要的总字节数

reqlen += zipStorePrevEntryLength(NULL,prevlen);
reqlen += zipStoreEntryEncoding(NULL,encoding,slen);

prevlen = 0（第一个entry），所以 zipStorePrevEntryLength(NULL,0) = 1
encoding = 0（字符串），slen = 5，所以 zipStoreEntryEncoding(NULL,0,5) = 1
reqlen = 5 + 1 + 1 = 7字节

步骤4：检查nextdiff

nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;

由于是第一个entry，p[0] == ZIP_END，所以 nextdiff = 0

步骤5：重新分配内存

offset = p-zl;
newlen = curlen+reqlen+nextdiff;  // 11 + 7 + 0 = 18
zl = ziplistResize(zl,newlen);
p = zl+offset;

原长度：11字节
新长度：18字节
重新分配内存并更新指针

步骤6：移动数据并写入新entry

/* 写入prevlen字段 */
p += zipStorePrevEntryLength(p,0);  // 写入0，1字节

/* 写入encoding字段 */
p += zipStoreEntryEncoding(p,0,5);  // 写入字符串编码，1字节

/* 写入数据 */
memcpy(p,"hello",5);  // 写入"hello"，5字节

步骤7：更新头部信息

ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);  // 更新尾部偏移
ZIPLIST_INCR_LENGTH(zl,1);                     // 增加条目数量

插入"hello"后的内存布局

┌─────────────┬─────────────┬─────────────┬────────────────────────────┬─────────────┐
│   zlbytes   │   zltail    │   zllen     │         entry              │    zlend    │
│   (4字节)   │   (4字节)   │   (2字节)   │         (7字节)            │   (1字节)   │
│             │             │             │                            │             │
│ 0x00000012  │ 0x0000000A  │ 0x0001      │       [00][05]hello        │    0xFF     │
│             │             │             │                            │             │
│ 总字节数18  │ 尾部偏移10  │ 条目数量1   │ prevlen=0,enc=05,data=hello│  结束标记   │
└─────────────┴─────────────┴─────────────┴────────────────────────────┴─────────────┘

Ziplist的Cascade Update

问题根源

Ziplist 中每个节点都存储了前一个节点的长度（prevlen），这个字段有两种编码方式：

如果前一个节点长度 < 254 字节，prevlen 占用 1 字节
如果前一个节点长度 ≥ 254 字节，prevlen 占用 5 字节（1字节标记 + 4字节长度）

连锁更新场景

当插入或删除节点导致某个节点的长度从 < 254 字节变为 ≥ 254 字节时，该节点的 prevlen 字段需要从 1 字节扩展到 5 字节。这会导致：

内存重新分配：整个 ziplist 需要重新分配内存
数据移动：后续所有节点的数据都需要向后移动 4 字节
连锁效应：如果后续节点的 prevlen 字段也接近 254 字节边界，可能触发更多节点的 prevlen 字段扩展

性能影响

需要调用 ziplistResize() 重新分配内存
需要调用 memmove() 移动大量数据
时间复杂度从 O(1) 退化到 O(n)

早期著名的连锁更新bug

核心问题是在ziplist插入操作中，当遇到特定的prevlen编码情况时，内存分配和编码逻辑不一致，导致数据损坏

Cascade Update的核心算法

unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) {
    // 1. 计算需要多少额外字节
    while (p[0] != ZIP_END) {
        if (cur.prevrawlen == prevlen) break;  // 没有变化，停止
        if (cur.prevrawlensize >= prevlensize) break;  // 空间足够，停止
        
        // 需要更多空间，继续计算
        extra += delta;  // delta = 4 (5-1)
        cnt++;
    }
    
    // 2. 重新分配内存并移动数据
    zl = ziplistResize(zl, curlen + extra);
    
    // 3. 从后往前更新每个entry的prevlen
    while (cnt) {
        // 更新prevlen字段
        zipStorePrevEntryLength(p, new_prevlen);
        cnt--;
    }
}

Listpack 的改进

Listpack 采用了一种更智能的内存管理策略：

统一的内存偏移量

当修改节点时，所有后续节点的内存地址都移动相同的偏移量
避免重新分配

不需要像 ziplist 那样重新分配整个数据结构的内存
批量内存操作

使用 memmove() 一次性移动所有数据，而不是逐个处理

从 lpInsert() 函数可以看到：

/* Setup the listpack relocating the elements to make the exact room
 * we need to store the new one. */
if (where == LP_BEFORE) {
    memmove(dst+enclen+backlen_size,dst,old_listpack_bytes-poff);
} else { /* LP_REPLACE. */
    memmove(dst+enclen+backlen_size,
            dst+replaced_len,
            old_listpack_bytes-poff-replaced_len);
}

性能提升原因：

内存连续性

所有后续节点移动相同的偏移量，保持了内存的连续性
减少内存分配

避免了频繁的内存重新分配操作
批量操作

一次 memmove() 操作完成所有数据移动，比多次小规模移动效率更高

总结

虽然 ziplist 和 listpack 在修改节点时都会影响后续节点，但 listpack 通过以下方式实现了性能提升：

ziplist

连锁更新导致内存重新分配 + 逐个节点处理，性能较差
listpack

统一偏移量移动 + 批量内存操作，性能更优

这就是为什么 listpack 在内存操作方面比 ziplist 性能略高的根本原因

redis ziplist

为什么要有 ziplist

ziplist的设计哲学

核心设计思想

与普通链表的对比

内存占用对比示例（“hello"存储案例）

访问模式差异

应用

早期

现在

结构

整体

条目结构

prevlen编码机制

encoding字段编码

字符串编码

整数编码

Zlentry 结构体

ZiplistEntry 结构体

转换关系图

创建Ziplist并插入数据

创建空的Ziplist

详细步骤

1. 计算总字节数

2. 分配内存

3. 初始化头部字段

4. 设置结束标记

插入数据到Ziplist

插入位置确定

头部插入 (ZIPLIST_HEAD)

确定插入位置

尾部插入 (ZIPLIST_TAIL)

确定插入位置

计算具体位置

__ziplistInsert()

步骤1：确定前一个entry的长度

插入位置的统一处理

边界条件的处理

安全的长度计算

步骤2：尝试编码为整数

步骤3：计算需要的总字节数

步骤4：检查nextdiff

步骤5：重新分配内存

步骤6：移动数据并写入新entry

步骤7：更新头部信息

插入"hello"后的内存布局

Ziplist的Cascade Update

问题根源

连锁更新场景

性能影响

早期著名的连锁更新bug

Cascade Update的核心算法

Listpack 的改进

总结