Redis 系列（四）：底层实现（二）——List、Set、ZSet 与 Stream 的数据结构

QAZ600888

485人浏览 · 2026-08-10 07:23:59

QAZ600888 · 2026-08-10 07:23:59 发布

核心目标：理解 quicklist、intset、skiplist、listpack、rax 的原理与取舍；用 MEMORY USAGE 实测回答"为什么相同元素数，ZSet 比 List 贵 10 倍"；理解集合编码的升级路径与阻塞命令（BLPOP）的等待机制。

前置知识：完成 Part 3（redisObject、SDS、dict），理解"编码 = 当前实现"与每键固定开销。

验证环境：Redis 8.10.0（cygwin 移植版，127.0.0.1:6379）、redis-py 8.1.0、Python 3.11.6、Windows 11；源码依据官方 Redis 7.4.2（_refsrc/redis-7.4.2）。最后复核日期：2026-08-07。

0. 本篇问题场景：相同 1000 个元素，内存差 10 倍

实测同一实例、同一批 1000 个元素分别装进三种结构：

List 1000 元素 → 5,921  字节
Set  1000 元素 → 30,162 字节
ZSet 1000 元素 → 67,914 字节

同样的数据量，ZSet 是 List 的 11 倍。为什么？答案在三种结构的底层设计里：List 用"链表 + 紧凑包"省内存，Set 用"整数压缩"或哈希表，ZSet 为了支持排序付出了"跳表节点 + 哈希表"的双份结构。本篇逐一打开这些实现，并回答三个问题：

List 的"快"与"省"是怎么同时成立的？
Set 的 intset 何时失效？
ZSet 的 skiplist 为什么贵，贵得值不值？

1. List：quicklist = 双向链表 + listpack 节点

1.1 结构

Redis 的 List 既不是简单的双向链表，也不是单个 listpack，而是 quicklist：一个双向链表，每个节点（quicklistNode）内部是一个 listpack（紧凑列表）。源码 quicklist.h：

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *entry;        // 指向本节点内的 listpack
    size_t sz;                   // listpack 字节数
    unsigned int count : 16;     // 本节点内元素数
    unsigned int encoding : 2;   // RAW==1 或 LZF==2（压缩）
    ...
} quicklistNode;

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;         // 全部元素总数
    unsigned long len;           // 节点个数
    signed int fill : QL_FILL_BITS;    // 每节点填充策略
    unsigned int compress : QL_COMP_BITS; // 两端保留不压缩的深度
    ...
} quicklist;

小 List（元素 ≤ list-max-listpack-size 对应阈值）甚至不需要节点链，直接以单个 listpack 形式存在——这就是实测 10 元素 → encoding=listpack 的原因；数据变大后拆成多个 listpack 节点组成 quicklist（2000 元素 → encoding=quicklist）。

1.2 为什么"快"与"省"兼得

需求	解决结构	代价
头尾 O(1) 插入删除	quicklist 的头/尾节点	链表指针（每节点 16+ 字节，摊到多元素上）
省内存	每个节点内是紧凑 listpack（无每元素指针）	中间插入/删除需要移动节点内数据，O(N)
大值省内存	`list-compress-depth` 压缩中间节点（LZF）	访问被压缩节点要先解压

list-max-listpack-size 默认 -2（每个 listpack 约 8 KB），list-compress-depth 0（默认不压缩）。设计哲学：内存与随机访问性能的平衡——头尾操作永远是 O(1)，中间操作按需付出拷贝代价。

1.3 阻塞命令的等待机制

BLPOP/BRPOP 在空队列时不返回而是挂起，这是轻量任务队列的核心能力。实测：

$ redis-cli BLPOP nonexistent:list 1
（等待 1 秒后返回 nil）

本机实测挂起 1.06 秒后返回 None（timeout=1）。机制：客户端被挂到该 key 的等待队列（server.db 的阻塞键表），当其他客户端 LPUSH/RPUSH 该 key 时，事件循环把数据直接推给等待者并唤醒——这就是"生产者-消费者"零轮询的实现基础。阻塞期间客户端连接保持，服务端不受影响（单线程只是"等待"，不是"忙等"）。

2. Set：intset 的"整数快车道"

2.1 intset 结构

当 Set 的所有成员都是整数且数量不多时，使用 intset（整数集合，intset.h）：

typedef struct intset {
    uint32_t encoding;   // 元素位宽：16/32/64 位
    uint32_t length;     // 元素个数
    int8_t contents[];   // 有序、无重复的整数数组
} intset;

contents 是有序数组，因此查找用二分查找 O(log N)，且天然去重。8 字节一个整数，几乎没有每元素开销——这是所有编码里最省内存的集合形态。

2.2 升级路径：三条路

实测的编码决策（全部真实输出）：

SADD 100 个整数     → intset     （整数、有序、去重）
SADD 512 个整数     → intset     （未超阈值）
SADD 513 个整数     → hashtable  （超 set-max-intset-entries=512）
SADD 整数 + "abc"   → listpack   （出现非整数，转紧凑列表）
SADD 100 个字符串   → listpack   （非整数，小集合）

升级条件（任一触发即离开 intset）：

元素个数 > set-max-intset-entries（默认 512）→ hashtable；
加入非整数元素 → 若元素数仍小则 listpack，否则 hashtable。

注意第二条：混合后 4 个元素的集合是 listpack 而不是 hashtable——intset 的替代品在小规模时是 listpack（更紧凑），数据规模大了才上 hashtable。"intset 升级 = 变 hashtable"是旧版本的印象，7.2+ 的正确路径是 intset → listpack（小）或 hashtable（大）。

2.3 对选型的意义

纯整数集合（如"在线用户 ID 集合"）在 512 以内享受二分查找 + 极低内存；
一旦混入字符串或增长，编码升级，但命令语义不变——这正是"type 与 encoding 两层"设计的好处：业务代码永远不用关心底层。

3. ZSet：skiplist + dict 的组合

3.1 结构：一份数据，两套索引

ZSet 的每个成员同时出现在两个结构中（server.h:1341）：

typedef struct zskiplistNode {
    sds ele;                       // 成员（字符串）
    double score;                  // 分数
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;  // 前向指针
        unsigned long span;             // 跨越的节点数
    } level[];                     // 多层（随机高度）
} zskiplistNode;

typedef struct zset {
    dict *dict;        // 成员 → score 的哈希索引（O(1) 查分）
    zskiplist *zsl;    // 按 score 排序的跳表（O(log N) 范围查询）
} zset;

为什么是"dict + skiplist"两份：没有哪个单一结构能同时满足两个需求——

ZSCORE member（按成员查分数）要 O(1) → dict；
ZRANGEBYSCORE（按分数范围遍历）、ZRANK（查名次）要有序遍历 → skiplist。

3.2 skiplist 为什么贵

跳表是"多级索引的链表"：每个节点随机一个层高，level[] 数组里每层存 forward 指针与 span。查找时从最高层往下跳，期望 O(log N)。代价是每个节点多层指针（平均 ~1.33 层额外指针 × 8 字节）+ 每节点一个 dictEntry（24 字节）+ 两个结构的元数据。

这就是 §0 实测"ZSet 1000 元素 = 67,914 字节，是 List 的 11 倍"的构成：排序能力是用内存换来的。设计取舍：

替代方案	为什么不用
平衡树（红黑树）	实现复杂、范围遍历不如链表结构直观、需要节点旋转
数组 + 二分	插入/删除 O(N) 移动
仅 dict	无法按 score 排序遍历
仅 skiplist	`ZSCORE` 退化为 O(log N) 且无法 O(1) 精确查分

skiplist 在期望 O(log N) 下实现简单、范围遍历自然，是"够用且简单"的工程选择。

3.3 listpack 编码的小 ZSet

小 ZSet（zset-max-listpack-entries 默认 128、zset-max-listpack-value 默认 64）先以 listpack 存储（成员与 score 交替压缩），超限后整体转 skiplist：

ZADD 100 成员 → listpack
ZADD 1000 成员 → skiplist

与 Hash/Set 同理：编码只升不降，删除部分成员后不会自动回到 listpack。

4. Stream：rax 基数树

Stream 的消息按 ID（毫秒时间戳-序号）存储。若用普通哈希表，前缀相同的 ID 会浪费大量空间；Redis 用 rax（基数树/压缩前缀树） 存储消息索引，rax.h：

typedef struct raxNode {
    uint32_t iskey:1;     // 本节点是否是一个 key（有值）
    uint32_t isnull:1;
    uint32_t iscompr:1;   // 是否压缩路径
    uint32_t size:29;     // 子节点数，或压缩路径长度
    ...
} raxNode;

rax 把公共前缀合并成一个节点（iscompr=1 表示"这一段路径被压缩成单节点"）。Stream 的消息 ID 共享 时间戳- 前缀，rax 能把数百万条消息的索引压缩到极小；同时保持字典序，让"从某 ID 之后读"（XRANGE）成为天然的前缀遍历。

OBJECT ENCODING 对 Stream 返回：

stream type: stream encoding: stream

（Stream 没有多种编码，stream 就是它的实现名。）

5. 内存分析实战：为什么"我的 Redis 内存涨得比数据大"

5.1 MEMORY USAGE 对比

§0 的三组数据，拆解其构成：

结构	1000 元素内存	每元素开销	主要构成
List	5,921 B	~6 B	listpack 紧凑存储，无每元素指针
Set	30,162 B	~30 B	hashtable 的 dictEntry（24 B/个）+ 桶
ZSet	67,914 B	~68 B	dictEntry + skiplist 节点（多层指针）+ span

结论：

需要"只按顺序存取"用 List——最省；
需要"去重/集合运算"用 Set——每个元素一个 dictEntry；
需要"排序+范围"用 ZSet——最贵但功能最强；
能用 List/Set 解决的场景别用 ZSet，反之亦然。

5.2 单键内存观察命令

$ redis-cli MEMORY USAGE z:mem     # 只算 value 对象
$ redis-cli MEMORY USAGE z:mem 0   # 0 表示把 key 名也算上
$ redis-cli MEMORY DOCTOR          # 内存健康体检（碎片、峰值等）
$ redis-cli --bigkeys              # 扫描最大的 key（Part 6 详讲）

MEMORY USAGE 的"含 key"选项很有用：它直接给出"如果删掉这个 key 能省多少内存"——Part 6 治理大 key 时的第一工具。

6. 版本与环境差异

差异点	官方 7.4	本机 8.10.0（cygwin 移植版）	影响
`hash-max-listpack-entries` 默认	512	512（`CONFIG GET` 实测）	升级阈值以 `CONFIG GET` 实测为准
`set-max-intset-entries`	512	512	一致
`zset-max-listpack-entries`	128	128	一致
intset 升级目标	listpack（小）/hashtable（大）	listpack	7.2+ 行为，与旧资料"必转 hashtable"不同
`list-max-listpack-size`	-2（~8KB）	-2	一致
quicklist / skiplist / rax	结构稳定	一致	源码引用 7.4.2