【Redis / 缓存内核】ZSet 与 Stream：skiplist · rax · 消费组

紧凑编码 里，小 ZSet 用 listpack 存 (member, score) 对；一旦超过 zset-max-listpack-entries 或 member 过长，就升级为 跳表 + 哈希表 双结构。Stream（XADD / XREAD）则是另一套范式：按 时间 ID 追加的日志型结构，底层是 rax 树索引 listpack 节点，消费组在 rax 上再挂 PEL（pending entries list）。

本文只覆盖内核必要集：ZSet 为何双结构、跳表与 Pugh 原版的三个差异、Stream 写入/读取/消费组状态机；不展开 Kafka/RabbitMQ 级别的持久化、分区、事务消息全书。源码锚定 Redis OSS 7.4.2：src/t_zset.c、src/t_stream.c、src/stream.h、src/rax.h。

一、ZSet 的双结构：dict + skiplist

t_zset.c 文件头注释写清设计目标：

元素同时存在于 dict（member → score，O(1) 按 member 查分）与 skiplist（按 score 排序，O(log N) 范围/排名）。

// src/server.h
typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

共享 SDS：同一 member 的 SDS 指针在 dict 与 skiplist 节点间共享；释放只在 zslFreeNode() 进行，dict 不设 valDestructor——删除须 先 dict 后 skiplist（注释强调顺序）。

flowchart TB
  zobj["robj OBJ_ZSET"]
  lp["encoding=LISTPACK<br/>small"]
  zs["encoding=SKIPLIST"]
  zobj --> lp
  zobj --> zs
  zs --> dict["dict: member→score"]
  zs --> zsl["skiplist: score→member"]
  dict -.->|same SDS ptr| zsl

小编码：createZsetListpackObject()；zsetTypeCreate 在 size_hint <= zset-max-listpack-entries 且 val_len_hint <= zset-max-listpack-value 时选 listpack（默认 128 / 64 字节，config.c）。

升级：zsetAdd 在 listpack 路径上若新增后超条目或 sdslen(ele) 超限，调用 zsetConvert(zobj, OBJ_ENCODING_SKIPLIST)，预 dictExpand 后逐条迁入跳表（zsetConvertAndExpand）。

降级：仅当 skiplist 长度与最大 ele 长度重新低于阈值且操作允许时，zsetConvert 可回到 listpack（如 ZPOPMIN 删到足够小）——条件比升级严。

二、跳表工程参数与 Pugh 谱系

William Pugh 1990（Skip Lists: A Probabilistic Alternative to Balanced Trees, CACM）定义了随机层高、期望 \(O(\log n)\) 的排序链表。Redis 实现标注为 Pugh 算法的 C 移植，三处修改（t_zset.c 注释）：

1. 允许 重复 score（多 member 同分）；
2. 比较键是 (score, member) 二元组，非单一 key；
3. level 1 有 backward 指针，支持 ZREVRANGE 反向遍历。

层高由 zslRandomLevel 生成，\(P = 0.25\)（ZSKIPLIST_P），最大 32 层（ZSKIPLIST_MAXLEVEL，注释称足够 \(2^{64}\) 元素）：

// src/server.h
#define ZSKIPLIST_MAXLEVEL 32
#define ZSKIPLIST_P 0.25

插入时维护 span 以支持 ZRANK / ZREVRANK（按排名访问比纯 Pugh 论文多工程字段）。

zslInsert 典型路径：自顶向下找各层前驱 update[]，掷层后链接 forward 并修正 span；同 score 时按 member 字典序 决定相对位置，保证全序。zsetRank 在 skiplist 上累加 span 得排名；listpack 路径则线性扫描（条目少时更省）。

为何不用红黑树：Redis 作者与 Treap 与跳表 一文站在同一立场——跳表 实现短、无旋转 case、并发扩展友好（algorithms/74 并发跳表可对照，Redis 主路径仍单线程）。反对观点来自经典教材派：红黑树最坏 \(O(\log n)\) 确定性，跳表是期望界；在 \(n\) 极大且随机性不足时理论退化可能（工程上 Redis 用 random() 造层）。没有在相同 Redis workload 上的 peer-reviewed 红黑树 vs 跳表对照论文可引为定论——选型证据是代码与运维可维护性。

三、Stream 存储：rax 索引 listpack

stream 结构（stream.h）：

typedef struct stream {
    rax *rax;               /* key: 128-bit stream ID, val: listpack */
    uint64_t length;
    streamID last_id;
    streamID first_id;
    streamID max_deleted_entry_id;
    uint64_t entries_added;
    rax *cgroups;           /* consumer group name → streamCG */
} stream;

• ID：streamID { ms, seq }——毫秒时间 + 同毫秒内递增序号，保证字典序单调（时钟回拨有专门规则，t_stream.c）。
• rax：压缩字典树（rax.h 注释图解「单 child 链压缩成字符串」），按 ID 前缀组织；每个 rax 节点挂一个 listpack，存该 ID 段内的多条 XADD entry（master fields + 可选 tombstone 标志）。
• 对象编码：OBJ_ENCODING_STREAM，ptr 指向 stream*（createStreamObject）。

flowchart TB
  stream["stream"]
  rax["rax tree<br/>key=streamID prefix"]
  lp1["listpack chunk"]
  lp2["listpack chunk"]
  stream --> rax
  rax --> lp1
  rax --> lp2

这与 ZSet 的「全局排序跳表」不同：Stream 是 追加日志 + 按 ID 范围切片，listpack 让相邻消息字段局部紧凑；rax 让 ID 查找/范围迭代不必单块无限 listpack。

streamIterator（stream.h）把 rax + listpack 抽象成按 ID 顺序的 entry 流，供 XREAD 范围回复与 AOF rewrite 遍历——应用命令不必手写 rax 游标。单条 XADD 在 rax 中找到或创建对应 listpack 节点，lpAppend 写入 field-value 序列；max_deleted_entry_id 与 tombstone 标志支持 XDEL 后的迭代裁剪（细节见 t_stream.c，本篇不展开修剪策略）。

四、消费组：最小必要语义

消费组 不是 独立消息中间件，而是 Stream 上的 读指针 + 未确认表：

// src/stream.h
typedef struct streamCG {
    streamID last_id;       /* 已交付给组内读者的最大 ID（未必已 ACK） */
    long long entries_read;
    rax *pel;               /* 已投递未 ACK：ID → streamNACK */
    rax *consumers;         /* consumer name → streamConsumer */
} streamCG;

typedef struct streamConsumer {
    mstime_t seen_time, active_time;
    sds name;
    rax *pel;               /* 该消费者私有 PEL，值与组 PEL 共享 streamNACK */
} streamConsumer;

读者需要记住的四步：

1. XGROUP CREATE：streamCreateCG 在 s->cgroups rax 注册组，初始化 last_id（常用 $ 只消费新消息）。
2. XREADGROUP GROUP g c COUNT … STREAMS key >：从 last_id 之后拉新消息；消息进入 组 PEL 与 消费者 PEL，streamNACK 记录投递时间与次数。
3. XACK：从 PEL 删除，表示处理完成；否则消息一直 pending，可被 XPENDING / XCLAIM 看见。
4. NOACK 选项：跳过 PEL，适合允许丢语义的场景（注释写明传播 last_id 更复杂）。

与 MQ 书的边界：Redis Stream 提供 at-least-once 倾向（靠 PEL + ACK）、消费者组内竞争读、阻塞读（BLOCK）；不保证跨节点分区有序、不提供内置死信队列语义、不重写 Kafka 的 log segment 与 ISR。把它当「轻量日志 + 消费位点」才与实现同构。

开放争论（CIDR/工业博客级，非单一论文）：Stream 是否应替代专业 MQ——共识是 短链路、可容忍副本丢秒、已有 Redis 运维 时省事；长留存、超高吞吐、复杂路由应上专用系统（architecture/17 缓存模式不覆盖此决策）。

五、常见误解

六、三句话小结

1. 大 ZSet = dict（member→score）+ skiplist（score 序），共享 SDS；小 ZSet 用 listpack，阈值默认 128 条 / 64 字节。
2. 跳表来自 Pugh 1990，Redis 用 \(P=1/4\)、32 层、双向底层链支持逆序排名。
3. Stream = rax 索引的 listpack 日志 + cgroups；消费组用 PEL + last_id 实现至少一次投递语义，不是完整 MQ 替代品。

参考资料

A 级（源码 / 规范）

• Redis OSS 7.4.2：src/t_zset.c、src/t_zset.h（zsetAdd、zslCreate、zsetConvert）
• Redis OSS 7.4.2：src/t_stream.c、src/stream.h、src/rax.h、src/rax.c
• Redis 命令文档：Sorted Sets、Streams、XREADGROUP

B 级

• Pugh, W., Skip Lists: A Probabilistic Alternative to Balanced Trees, CACM 1990（跳表定义与期望复杂度）
• Redis 官方博客 / 发布说明中 Stream 与 consumer group 引入说明（5.0 时代设计上下文）

站内交叉

• Treap 与跳表：随机化的力量
• 紧凑编码 · TTL 与过期

返回 系列目录 ｜ 上一篇：紧凑编码 ｜ 下一篇：TTL 与过期