核心目标理解 quicklist、intset、skiplist、listpack、rax 的原理与取舍用MEMORY USAGE实测回答为什么相同元素数ZSet 比 List 贵 10 倍理解集合编码的升级路径与阻塞命令BLPOP的等待机制。前置知识完成 Part 3redisObject、SDS、dict理解编码 当前实现与每键固定开销。验证环境Redis 8.10.0cygwin 移植版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. Listquicklist 双向链表 listpack 节点1.1 结构Redis 的 List 既不是简单的双向链表也不是单个 listpack而是quicklist一个双向链表每个节点quicklistNode内部是一个 listpack紧凑列表。源码quicklist.htypedefstructquicklistNode{structquicklistNode*prev;structquicklistNode*next;unsignedchar*entry;// 指向本节点内的 listpacksize_tsz;// listpack 字节数unsignedintcount:16;// 本节点内元素数unsignedintencoding:2;// RAW1 或 LZF2压缩...}quicklistNode;typedefstructquicklist{quicklistNode*head;quicklistNode*tail;unsignedlongcount;// 全部元素总数unsignedlonglen;// 节点个数signedintfill:QL_FILL_BITS;// 每节点填充策略unsignedintcompress:QL_COMP_BITS;// 两端保留不压缩的深度...}quicklist;小 List元素 ≤list-max-listpack-size对应阈值甚至不需要节点链直接以单个 listpack 形式存在——这就是实测10 元素 → encodinglistpack的原因数据变大后拆成多个 listpack 节点组成 quicklist2000 元素 → encodingquicklist。1.2 为什么快与省兼得需求解决结构代价头尾 O(1) 插入删除quicklist 的头/尾节点链表指针每节点 16 字节摊到多元素上省内存每个节点内是紧凑 listpack无每元素指针中间插入/删除需要移动节点内数据O(N)大值省内存list-compress-depth压缩中间节点LZF访问被压缩节点要先解压list-max-listpack-size默认-2每个 listpack 约 8 KBlist-compress-depth 0默认不压缩。设计哲学内存与随机访问性能的平衡——头尾操作永远是 O(1)中间操作按需付出拷贝代价。1.3 阻塞命令的等待机制BLPOP/BRPOP在空队列时不返回而是挂起这是轻量任务队列的核心能力。实测$ redis-cli BLPOP nonexistent:list 1 等待 1 秒后返回 nil本机实测挂起 1.06 秒后返回Nonetimeout1。机制客户端被挂到该 key 的等待队列server.db的阻塞键表当其他客户端LPUSH/RPUSH该 key 时事件循环把数据直接推给等待者并唤醒——这就是生产者-消费者零轮询的实现基础。阻塞期间客户端连接保持服务端不受影响单线程只是等待不是忙等。2. Setintset 的整数快车道2.1 intset 结构当 Set 的所有成员都是整数且数量不多时使用intset整数集合intset.htypedefstructintset{uint32_tencoding;// 元素位宽16/32/64 位uint32_tlength;// 元素个数int8_tcontents[];// 有序、无重复的整数数组}intset;contents是有序数组因此查找用二分查找 O(log N)且天然去重。8 字节一个整数几乎没有每元素开销——这是所有编码里最省内存的集合形态。2.2 升级路径三条路实测的编码决策全部真实输出SADD 100 个整数 → intset 整数、有序、去重 SADD 512 个整数 → intset 未超阈值 SADD 513 个整数 → hashtable 超 set-max-intset-entries512 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. ZSetskiplist dict 的组合3.1 结构一份数据两套索引ZSet 的每个成员同时出现在两个结构中server.h:1341typedefstructzskiplistNode{sds ele;// 成员字符串doublescore;// 分数structzskiplistNode*backward;structzskiplistLevel{structzskiplistNode*forward;// 前向指针unsignedlongspan;// 跨越的节点数}level[];// 多层随机高度}zskiplistNode;typedefstructzset{dict*dict;// 成员 → score 的哈希索引O(1) 查分zskiplist*zsl;// 按 score 排序的跳表O(log N) 范围查询}zset;为什么是dict skiplist两份没有哪个单一结构能同时满足两个需求——ZSCORE member按成员查分数要 O(1) → dictZRANGEBYSCORE按分数范围遍历、ZRANK查名次要有序遍历 → skiplist。3.2 skiplist 为什么贵跳表是多级索引的链表每个节点随机一个层高level[]数组里每层存 forward 指针与 span。查找时从最高层往下跳期望 O(log N)。代价是每个节点多层指针平均 ~1.33 层额外指针 × 8 字节 每节点一个 dictEntry24 字节 两个结构的元数据。这就是 §0 实测ZSet 1000 元素 67,914 字节是 List 的 11 倍的构成排序能力是用内存换来的。设计取舍替代方案为什么不用平衡树红黑树实现复杂、范围遍历不如链表结构直观、需要节点旋转数组 二分插入/删除 O(N) 移动仅 dict无法按 score 排序遍历仅 skiplistZSCORE退化为 O(log N) 且无法 O(1) 精确查分skiplist 在期望 O(log N) 下实现简单、范围遍历自然是够用且简单的工程选择。3.3 listpack 编码的小 ZSet小 ZSetzset-max-listpack-entries默认 128、zset-max-listpack-value默认 64先以 listpack 存储成员与 score 交替压缩超限后整体转 skiplistZADD 100 成员 → listpack ZADD 1000 成员 → skiplist与 Hash/Set 同理编码只升不降删除部分成员后不会自动回到 listpack。4. Streamrax 基数树Stream 的消息按 ID毫秒时间戳-序号存储。若用普通哈希表前缀相同的 ID 会浪费大量空间Redis 用rax基数树/压缩前缀树存储消息索引rax.htypedefstructraxNode{uint32_tiskey:1;// 本节点是否是一个 key有值uint32_tisnull:1;uint32_tiscompr:1;// 是否压缩路径uint32_tsize:29;// 子节点数或压缩路径长度...}raxNode;rax 把公共前缀合并成一个节点iscompr1表示这一段路径被压缩成单节点。Stream 的消息 ID 共享时间戳-前缀rax 能把数百万条消息的索引压缩到极小同时保持字典序让从某 ID 之后读XRANGE成为天然的前缀遍历。OBJECT ENCODING对 Stream 返回stream type: stream encoding: streamStream 没有多种编码stream就是它的实现名。5. 内存分析实战为什么我的 Redis 内存涨得比数据大5.1 MEMORY USAGE 对比§0 的三组数据拆解其构成结构1000 元素内存每元素开销主要构成List5,921 B~6 Blistpack 紧凑存储无每元素指针Set30,162 B~30 Bhashtable 的 dictEntry24 B/个 桶ZSet67,914 B~68 BdictEntry 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 # 扫描最大的 keyPart 6 详讲MEMORY USAGE的含 key选项很有用它直接给出如果删掉这个 key 能省多少内存——Part 6 治理大 key 时的第一工具。6. 版本与环境差异差异点官方 7.4本机 8.10.0cygwin 移植版影响hash-max-listpack-entries默认512512CONFIG GET实测升级阈值以CONFIG GET实测为准set-max-intset-entries512512一致zset-max-listpack-entries128128一致intset 升级目标listpack小/hashtable大listpack7.2 行为与旧资料必转 hashtable不同list-max-listpack-size-2~8KB-2一致quicklist / skiplist / rax结构稳定一致源码引用 7.4.2本机与 7.4 在这些结构上行为一致写作时的关键教训是升级阈值要用CONFIG GET实测不要背文档里的数字。7. 测试与验收新增测试建议编码断言intset 512 边界、listpack→skiplist 升级、MEMORY USAGE量级对比List Set ZSet、BLPOP超时语义内存对比实验保留脚本数据规模、测量命令、环境。本篇验收清单能画出 quicklist 的结构双向链表 listpack 节点并解释头尾 O(1)/中间 O(N)能说出 intset 的三个升级触发条件超 512、非整数、规模与 7.2 的升级目标能解释 ZSetdict skiplist双结构的动机与 skiplist 的内存代价能解释 Stream 用 rax 存储消息 ID 的好处公共前缀压缩 字典序遍历能用MEMORY USAGE对比三种结构的实际内存并解释差异来源能说出BLPOP阻塞的机制挂起 写入唤醒并实测超时行为。8. 常见误区“List 是普通双向链表”——是 quicklist节点是 listpack小 List 直接就是一个 listpack§1。“intset 升级就一定变 hashtable”——7.2 小规模转 listpack§2.2旧资料过时。“ZSet 就是排序的 Set”——底层是 dict skiplist 两套结构内存接近 Set 的两倍排序能力有明确价格§3、§5。“skiplist 因为快所以用”——它比平衡树慢一点但简单很多、范围遍历自然Redis 的选择是够用 简单。“BLPOP 超时期间会占用 CPU”——不会客户端挂起等待唤醒不是忙等§1.3。“编码升级后删数据会降回来”——只升不降§3.3紧凑编码需要重建键。9. 本篇小结回到开篇同样 1000 个元素List 5.9KB、Set 30KB、ZSet 68KB——差异不是 bug是三种能力顺序存取 / 集合运算 / 排序范围各自的定价List 用链表 listpack买到了 O(1) 头尾 紧凑存储Set 用 intset 的整数快车道 hashtable 兜底ZSet 用 dict skiplist 双结构换排序能力代价是最高内存。至此五种核心结构 四种扩展结构的内存模型全部建立。下一篇 Part 5持久化回答内存里的一切如何落盘、如何恢复RDB 的 forkCOW、AOF 的 fsync 策略与混合持久化并用隔离实例做真实的断电丢数据实验。10. 官方资料Redis 7.4.2 源码https://github.com/redis/redis/tree/7.4.2/srcOBJECT/MEMORY USAGE/MEMORY DOCTORhttps://redis.io/docs/latest/commands/BLPOP阻塞语义https://redis.io/docs/latest/commands/blpop/Memory optimizationhttps://redis.io/docs/latest/operate/oss_and_stack/management/optimization/memory-optimization/ Redis 系列（四）：底层实现（二）——List、Set、ZSet 与 Stream 的数据结构
核心目标理解 quicklist、intset、skiplist、listpack、rax 的原理与取舍用MEMORY USAGE实测回答为什么相同元素数ZSet 比 List 贵 10 倍理解集合编码的升级路径与阻塞命令BLPOP的等待机制。前置知识完成 Part 3redisObject、SDS、dict理解编码 当前实现与每键固定开销。验证环境Redis 8.10.0cygwin 移植版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. Listquicklist 双向链表 listpack 节点1.1 结构Redis 的 List 既不是简单的双向链表也不是单个 listpack而是quicklist一个双向链表每个节点quicklistNode内部是一个 listpack紧凑列表。源码quicklist.htypedefstructquicklistNode{structquicklistNode*prev;structquicklistNode*next;unsignedchar*entry;// 指向本节点内的 listpacksize_tsz;// listpack 字节数unsignedintcount:16;// 本节点内元素数unsignedintencoding:2;// RAW1 或 LZF2压缩...}quicklistNode;typedefstructquicklist{quicklistNode*head;quicklistNode*tail;unsignedlongcount;// 全部元素总数unsignedlonglen;// 节点个数signedintfill:QL_FILL_BITS;// 每节点填充策略unsignedintcompress:QL_COMP_BITS;// 两端保留不压缩的深度...}quicklist;小 List元素 ≤list-max-listpack-size对应阈值甚至不需要节点链直接以单个 listpack 形式存在——这就是实测10 元素 → encodinglistpack的原因数据变大后拆成多个 listpack 节点组成 quicklist2000 元素 → encodingquicklist。1.2 为什么快与省兼得需求解决结构代价头尾 O(1) 插入删除quicklist 的头/尾节点链表指针每节点 16 字节摊到多元素上省内存每个节点内是紧凑 listpack无每元素指针中间插入/删除需要移动节点内数据O(N)大值省内存list-compress-depth压缩中间节点LZF访问被压缩节点要先解压list-max-listpack-size默认-2每个 listpack 约 8 KBlist-compress-depth 0默认不压缩。设计哲学内存与随机访问性能的平衡——头尾操作永远是 O(1)中间操作按需付出拷贝代价。1.3 阻塞命令的等待机制BLPOP/BRPOP在空队列时不返回而是挂起这是轻量任务队列的核心能力。实测$ redis-cli BLPOP nonexistent:list 1 等待 1 秒后返回 nil本机实测挂起 1.06 秒后返回Nonetimeout1。机制客户端被挂到该 key 的等待队列server.db的阻塞键表当其他客户端LPUSH/RPUSH该 key 时事件循环把数据直接推给等待者并唤醒——这就是生产者-消费者零轮询的实现基础。阻塞期间客户端连接保持服务端不受影响单线程只是等待不是忙等。2. Setintset 的整数快车道2.1 intset 结构当 Set 的所有成员都是整数且数量不多时使用intset整数集合intset.htypedefstructintset{uint32_tencoding;// 元素位宽16/32/64 位uint32_tlength;// 元素个数int8_tcontents[];// 有序、无重复的整数数组}intset;contents是有序数组因此查找用二分查找 O(log N)且天然去重。8 字节一个整数几乎没有每元素开销——这是所有编码里最省内存的集合形态。2.2 升级路径三条路实测的编码决策全部真实输出SADD 100 个整数 → intset 整数、有序、去重 SADD 512 个整数 → intset 未超阈值 SADD 513 个整数 → hashtable 超 set-max-intset-entries512 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. ZSetskiplist dict 的组合3.1 结构一份数据两套索引ZSet 的每个成员同时出现在两个结构中server.h:1341typedefstructzskiplistNode{sds ele;// 成员字符串doublescore;// 分数structzskiplistNode*backward;structzskiplistLevel{structzskiplistNode*forward;// 前向指针unsignedlongspan;// 跨越的节点数}level[];// 多层随机高度}zskiplistNode;typedefstructzset{dict*dict;// 成员 → score 的哈希索引O(1) 查分zskiplist*zsl;// 按 score 排序的跳表O(log N) 范围查询}zset;为什么是dict skiplist两份没有哪个单一结构能同时满足两个需求——ZSCORE member按成员查分数要 O(1) → dictZRANGEBYSCORE按分数范围遍历、ZRANK查名次要有序遍历 → skiplist。3.2 skiplist 为什么贵跳表是多级索引的链表每个节点随机一个层高level[]数组里每层存 forward 指针与 span。查找时从最高层往下跳期望 O(log N)。代价是每个节点多层指针平均 ~1.33 层额外指针 × 8 字节 每节点一个 dictEntry24 字节 两个结构的元数据。这就是 §0 实测ZSet 1000 元素 67,914 字节是 List 的 11 倍的构成排序能力是用内存换来的。设计取舍替代方案为什么不用平衡树红黑树实现复杂、范围遍历不如链表结构直观、需要节点旋转数组 二分插入/删除 O(N) 移动仅 dict无法按 score 排序遍历仅 skiplistZSCORE退化为 O(log N) 且无法 O(1) 精确查分skiplist 在期望 O(log N) 下实现简单、范围遍历自然是够用且简单的工程选择。3.3 listpack 编码的小 ZSet小 ZSetzset-max-listpack-entries默认 128、zset-max-listpack-value默认 64先以 listpack 存储成员与 score 交替压缩超限后整体转 skiplistZADD 100 成员 → listpack ZADD 1000 成员 → skiplist与 Hash/Set 同理编码只升不降删除部分成员后不会自动回到 listpack。4. Streamrax 基数树Stream 的消息按 ID毫秒时间戳-序号存储。若用普通哈希表前缀相同的 ID 会浪费大量空间Redis 用rax基数树/压缩前缀树存储消息索引rax.htypedefstructraxNode{uint32_tiskey:1;// 本节点是否是一个 key有值uint32_tisnull:1;uint32_tiscompr:1;// 是否压缩路径uint32_tsize:29;// 子节点数或压缩路径长度...}raxNode;rax 把公共前缀合并成一个节点iscompr1表示这一段路径被压缩成单节点。Stream 的消息 ID 共享时间戳-前缀rax 能把数百万条消息的索引压缩到极小同时保持字典序让从某 ID 之后读XRANGE成为天然的前缀遍历。OBJECT ENCODING对 Stream 返回stream type: stream encoding: streamStream 没有多种编码stream就是它的实现名。5. 内存分析实战为什么我的 Redis 内存涨得比数据大5.1 MEMORY USAGE 对比§0 的三组数据拆解其构成结构1000 元素内存每元素开销主要构成List5,921 B~6 Blistpack 紧凑存储无每元素指针Set30,162 B~30 Bhashtable 的 dictEntry24 B/个 桶ZSet67,914 B~68 BdictEntry 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 # 扫描最大的 keyPart 6 详讲MEMORY USAGE的含 key选项很有用它直接给出如果删掉这个 key 能省多少内存——Part 6 治理大 key 时的第一工具。6. 版本与环境差异差异点官方 7.4本机 8.10.0cygwin 移植版影响hash-max-listpack-entries默认512512CONFIG GET实测升级阈值以CONFIG GET实测为准set-max-intset-entries512512一致zset-max-listpack-entries128128一致intset 升级目标listpack小/hashtable大listpack7.2 行为与旧资料必转 hashtable不同list-max-listpack-size-2~8KB-2一致quicklist / skiplist / rax结构稳定一致源码引用 7.4.2本机与 7.4 在这些结构上行为一致写作时的关键教训是升级阈值要用CONFIG GET实测不要背文档里的数字。7. 测试与验收新增测试建议编码断言intset 512 边界、listpack→skiplist 升级、MEMORY USAGE量级对比List Set ZSet、BLPOP超时语义内存对比实验保留脚本数据规模、测量命令、环境。本篇验收清单能画出 quicklist 的结构双向链表 listpack 节点并解释头尾 O(1)/中间 O(N)能说出 intset 的三个升级触发条件超 512、非整数、规模与 7.2 的升级目标能解释 ZSetdict skiplist双结构的动机与 skiplist 的内存代价能解释 Stream 用 rax 存储消息 ID 的好处公共前缀压缩 字典序遍历能用MEMORY USAGE对比三种结构的实际内存并解释差异来源能说出BLPOP阻塞的机制挂起 写入唤醒并实测超时行为。8. 常见误区“List 是普通双向链表”——是 quicklist节点是 listpack小 List 直接就是一个 listpack§1。“intset 升级就一定变 hashtable”——7.2 小规模转 listpack§2.2旧资料过时。“ZSet 就是排序的 Set”——底层是 dict skiplist 两套结构内存接近 Set 的两倍排序能力有明确价格§3、§5。“skiplist 因为快所以用”——它比平衡树慢一点但简单很多、范围遍历自然Redis 的选择是够用 简单。“BLPOP 超时期间会占用 CPU”——不会客户端挂起等待唤醒不是忙等§1.3。“编码升级后删数据会降回来”——只升不降§3.3紧凑编码需要重建键。9. 本篇小结回到开篇同样 1000 个元素List 5.9KB、Set 30KB、ZSet 68KB——差异不是 bug是三种能力顺序存取 / 集合运算 / 排序范围各自的定价List 用链表 listpack买到了 O(1) 头尾 紧凑存储Set 用 intset 的整数快车道 hashtable 兜底ZSet 用 dict skiplist 双结构换排序能力代价是最高内存。至此五种核心结构 四种扩展结构的内存模型全部建立。下一篇 Part 5持久化回答内存里的一切如何落盘、如何恢复RDB 的 forkCOW、AOF 的 fsync 策略与混合持久化并用隔离实例做真实的断电丢数据实验。10. 官方资料Redis 7.4.2 源码https://github.com/redis/redis/tree/7.4.2/srcOBJECT/MEMORY USAGE/MEMORY DOCTORhttps://redis.io/docs/latest/commands/BLPOP阻塞语义https://redis.io/docs/latest/commands/blpop/Memory optimizationhttps://redis.io/docs/latest/operate/oss_and_stack/management/optimization/memory-optimization/