redis的List为什么用ziplist和quicklist

redis的List为什么用ziplist和quicklist

压缩列表（ziplist） 是一种节省内存的数据结构，最早是 Redis 中为了减少内存开销而引入的一种顺序存储结构。它不是标准库里的内容，而是某些底层系统（比如 Redis）在特定场景下的手动实现。

你可以把它理解为一个连续内存块中，紧凑地存储多个数据项（字符串或整数）的结构。

压缩列表的应用场景（以 Redis 为例）

在 Redis 中，压缩列表常被用于：

• 存储 小的 list 类型（如 list、hash、set 的底层实现）。

• 当使用 lpush、rpush 插入少量数据时，Redis 会自动用压缩列表来表示这些数据。

• 例如：

  lpush mylist a b c
  

  如果 mylist 很小，Redis 可能会用 ziplist 来存储它，而不是链表

适合的场景：

• 元素数量少（比如不到 512 个）。
• 每个元素的值比较小（比如小于 64 字节）。

为什么要有压缩列表？

• 普通的链表结构虽然插入删除方便，但每个节点要额外的内存（如指针、元数据等）。
• 压缩列表用一个连续内存块来存储多个数据节点，没有额外指针，节省内存

压缩列表是一个连续内存块，由以下几个部分组成：

+--------------+--------------+--------------+----+--------+
| zlbytes(4B)  | zltail(4B)   | zllen(2B)    | e1 |  ...   |
+--------------+--------------+--------------+----+--------+

• zlbytes：整个压缩列表占用的字节数。
• zltail：最后一个节点的偏移量，方便从尾部快速访问。
• zllen：压缩列表中的节点个数（最大 65535 个）。
• entry1, entry2, ..., entryN：每个元素（entry），包括了：
  • 前一个 entry 的长度（用于反向遍历）。
  • 当前元素的数据长度。
  • 当前数据本身（字符串或整数）。
• 0xFF：结束标志，表示列表结束。

压缩列表的特点

压缩列表 vs 可变数组：核心区别

1. 【内存效率】——压缩列表完胜

Java 的 ArrayList 或 C++ 的 vector 是为“通用场景”设计的：

• 每个元素在 ArrayList 中都是一个对象引用（Java 里是 String、Integer 等包装类）。
• 存 10000 个 "a" 字符串，实际上是 10000 个指针 + 10000 个 String 对象，严重浪费内存。

而压缩列表：

• 是二进制内存块，直接连续存储数据内容（无指针、无对象）。
• Redis 中 ziplist 存的字符串 "a" 可能只用 1-2 个字节。
• 节省内存效果非常明显，尤其对大量小数据。

2. 【数据结构灵活性】——ziplist 更自由

压缩列表允许每个元素长度不同，不像数组那样必须等长或类型一致。

举个例子：

["a", "abc", 12345678, "x"]

• 压缩列表每个 entry 都有自己的长度描述（灵活、压缩）。
• 数组只能是统一类型（Java 中要么全是 String，要么全是 int）。

3. 【操作性能】——ArrayList 更方便，但不节省

可变数组是通用型的，优点在于：

• 插入、删除逻辑简单。
• 开发者操作方便（get(i)、set(i) 快）。

但压缩列表为了压缩内存，不惜：

• 每次插入可能要整体 memmove。
• 删除时要更新前一个长度字段。
• 某些情况还需要“链式更新”（如 prevlen 变化导致后续 entry 移位）。

所以压缩列表牺牲了操作性能，换取空间节省。

为什么 ziplist 不适合大数据或频繁增删？

1. 插入删除效率差（因为是连续内存）

压缩列表是连续的内存块，如果在中间插入一个新元素，会导致：

• 整体 memmove
• 后续所有 entry 的 prevlen 都要更新（可能出现“连锁更新效应”）

这在大数据场景下非常不划算。

2. 每个 entry 编码复杂

每个节点结构是变长的，读取/写入开销比链表大，处理大数据不划算。

3. 空间不够时需要重新分配

连续内存意味着一旦空间不够，需要 realloc 整个块，效率也不如链表的逐块扩展。

quicklist

quicklist 是 Redis 在 3.2 版本之后引入的一种 list 底层结构，它是：

一个由多个 ziplist 组成的 双向链表

简要表示为：

quicklist = ziplist1 <-> ziplist2 <-> ziplist3 <-> ...

每个节点是一个 ziplist，多个 ziplist 组成链表。

于是 Redis 设计了 quicklist，想达到：

既能节省内存，又支持高效的插入/删除

每个 quicklist 节点（quicklistNode）结构如下：

+--------------+-------------+--------------+
| prev pointer | ziplist ptr | next pointer |
+--------------+-------------+--------------+

• quicklist 是整个链表的头部结构，指向若干 quicklistNode
• 每个 quicklistNode 内部包含一个压缩列表（ziplist）
• 双向链表结构，支持正向和反向遍历
• 节点数目不会太多（通过配置项控制 ziplist 的长度或总大小）

quicklist优点

• quicklist 把 ziplist 拆分为多个小块，避免大块连续内存的性能问题
• 通过链表连接这些 ziplist，提高插入/删除的灵活性
• 又保留 ziplist 的压缩特性，节省内存

ListPack

• listpack是 Redis 自研的 紧凑型二进制编码结构，用来存储一组 字符串或整数，被广泛用于 Redis 的内部实现，比如：

• Stream（流）里的一些内部结构

• quicklist 的节点（quicklist 是 list 的底层结构）

• Hash、Zset 在元素少时的压缩编码

也就是说，listpack 是“容器的容器” —— 用来承载多个数据项（entry），以一种压缩的方式存起来。

listpack 的结构长什么样？

listpack 的整体结构是个二进制数组，格式大致是这样：

| total_bytes | num_elements | entry1 | entry2 | ... | entryN | end_byte |

分别解释：

• total_bytes（4字节）

  listpack 的总字节长度，方便 Redis 直接跳到末尾，不用每次都遍历。

• num_elements（2字节）

  当前 listpack 里有多少个 entry，方便遍历时不重复计算。

• entry1 ~ entryN

  这是重点，每个 entry 都是变长的，内部有：

  • 长度信息（包括类型、是否是整数）
  • 内容（字符串或整数值）
  • 后跟一段表示本 entry 的总长度（方便向后、向前遍历）

• end_byte（1字节，固定是 0xFF）

  表示 listpack 的结尾。

和普通数据结构比，它有这些优点：