Zset 是 Redis 里最让我觉得“设计得很聪明”的数据结构没有之一。很多人用 Zset 做排行榜、延迟队列用得飞起但真要问一句“Zset 底层到底怎么存的为什么 ZRANGE 能那么快为什么它一边能 O(1) 查 score一边还能 O(logN) 做范围查询”——能讲清楚的人立刻少一大半。这篇就从底层实现讲起把 Zset 的两套存储结构、跳表的核心机制、复杂度推导、以及我在线上实际踩过的坑一次说透。后端开发、中间件维护者、准备面试的朋友都适合看尤其是想真正理解 Redis 而不只是背八股的人。1. Zset 到底是干嘛的为什么要单独设计它1.1 一个结构同时要两种能力先回到最基础的问题Zset有序集合和普通的 Set、List、Hash 到底差在哪Set 能去重但无序List 能有序但没法按“权重”排序Hash 能存字段但字段之间没有先后关系。Zset 的核心诉求是每个元素关联一个 double 类型的 score并且集合内部永远按 score 维护好顺序你随时可以按 score 的范围取出一段元素也可以按排名取出元素。这种需求在业务里太常见了游戏排行榜玩家 ID 是元素积分是 score要“查第 1 名到第 50 名”延迟队列任务 ID 是元素执行时间戳是 score要“取出当前时间之前的所有到期任务”滑动窗口限流请求 ID 是元素时间戳是 score要“删除窗口外的记录统计窗口内的数量”问题在于这些操作对数据结构提出了两种互相矛盾的要求。按元素查 score 需要哈希表的速度按 score 排序和范围扫描又需要有序结构的能力。如果只用一个有序数组插入删除的代价是 O(N)如果只用一个哈希表范围查询就废了。Redis 的解法很直接Zset 底层同时维护两个结构一个 dict 负责精确查找一个 skiplist 负责有序操作。查“某个元素当前的 score 是多少”走 dictO(1)查“排名 100 到 200 之间的元素”走 skiplistO(logN)。1.2 用图书馆的类比理解双结构设计打个比方你就明白了。一家图书馆有两套索引一套是“书名到书架位置的卡片目录”按书名首字母快速定位——这就是 dict。另一套是“按出版日期排列的书目清单”每本书都记录了它前后是哪本书——这就是 skiplist。你要找某本书在哪走卡片目录一翻就到。你要查“最近三个月出版的书”走时间清单顺着链表从前往后扫就行。各有各的用武之地谁也替代不了谁。Zset 就是把这两个索引放在同一份数据上通过指针让同一条记录在两个结构里都能被访问到。这也解释了为什么 Zset 的内存开销比普通的 Set 大它要为每个元素同时维护哈希表条目和跳表节点。后面讲内存优化的时候这个结论会反复用到。2. 编码方式的演进从紧凑存储到跳表2.1 Zset 的两种底层编码很多人以为 Zset 底层就是跳表这其实是个常见的误区。Redis 的 Zset 根据元素个数和元素大小会选择两种完全不同的编码方式OBJ_ENCODING_LISTPACK老版本是 ZIPLIST把所有元素按 score 升序排好紧凑地存在一块连续内存里成员和 score 交替排列。OBJ_ENCODING_SKIPLIST这才是我们常说的“跳表 dict”的完整结构。当一个 Zset 的元素数量很少、每个元素的字符串长度也很短时Redis 会优先用紧凑编码把数据打包成一块连续内存。这种做法的好处是内存占用极小而且局部性好遍历起来 cache 友好。但紧凑编码的代价也很明显插入和删除时要移动后续所有数据复杂度是 O(N)。所以它只适合小规模数据。一旦元素数量或单个元素大小超过阈值Redis 就会把它转换成 skiplist 编码并且这个转换是不可逆的。触发转换的条件有两个对应两个配置项zset-max-listpack-entries默认 128元素数量超过这个值就转zset-max-listpack-value默认 64 字节单个成员长度超过这个值就转想调大还是调小取决于你的业务。如果你明确知道 Zset 里的数据量会很小可以适当调大阈值让更多 Zset 停留在紧凑编码下省内存如果你知道会写入大字符串就保持默认甚至调小避免出现零散的紧凑编码 Zset 频繁触发转换的尴尬。2.2 为什么新版本用 listpack 替换 ziplist如果你看过老版本的 Redis 源码会发现紧凑编码以前叫 ziplist7.0 之后才替换成 listpack。这个替换背后有一个经典的连锁更新问题。ziplist 的每个节点会记录前一个节点的长度而这个长度字段的大小取决于前一个节点的大小。如果前一个节点长度超过 254 字节字段就得用 5 字节来存否则只用 1 字节。问题来了当你插入一个超大节点后它后面的节点为了记录“前一个节点长度”可能需要扩容扩容又可能导致再后面的节点也面临同样的问题——像多米诺骨牌一样连锁触发内存搬移最坏情况下插入一个节点导致后面所有节点都要重新分配内存复杂度退化到 O(N²)。listpack 的设计彻底绕开了这个问题每个节点只记录自己的长度不记录前一个节点的长度从根上消除了连锁更新的存在。所以新版本的紧凑编码在大字符串场景下更稳健。这也是我在实际工作中强烈建议使用 Redis 7.0 的原因之一如果你还在用老版本线上如果出现过 Zset 写入突然变慢的情况这就是一个值得排查的方向。2.3 什么时候该关心编码转换转换条件默认是 128 个元素、64 字节。这里有个容易被忽视的点score 是 double 类型不参与“value 长度”的统计但成员的字符串长度参与。也就是说如果成员是 20 个字符的用户 ID那 64 字节的阈值很难触发但如果成员是 URL、JSON 串、或者带时间戳的复合字符串很容易超过 64 字节。我在线上见过一个典型案例某业务用 Zset 做用户行为时间线成员存的是“用户ID:行为ID:时间戳”拼接的字符串平均长度超过 60 字节一旦某些极端用户的行为串很长直接触发编码转换。转换本身不是问题问题是转换发生时 Redis 需要把原有紧凑编码的所有数据遍历一遍重新构建跳表和 dict这个过程的耗时跟元素数量成正比。如果一个 Zset 恰好卡在阈值附近线上会出现偶发的毫秒级延迟尖峰。所以我的建议是如果你能预估成员的字节长度最好在测试环境压一把观察 Zset 什么时候发生转换、转换耗时多少。别等到线上出了慢查询才来查。3. 跳表原理深度拆解结构、查找、插入3.1 跳表节点的数据结构长什么样跳表skiplist的本质是在有序链表上增加多层索引。Redis 的实现里节点定义大致是这样的typedef struct zskiplistNode { sds ele; // 成员字符串 double score; // 分值 struct zskiplistNode *backward; // 后退指针 struct zskiplistLevel { struct zskiplistNode *forward; // 前进指针 unsigned long span; // 跨度到下一个节点的距离 } level[]; } zskiplistNode; typedef struct zskiplist { struct zskiplistNode *header, *tail; unsigned long length; // 节点总数 int level; // 当前最大层数 } zskiplist;每个节点除了存 datascore ele还有一个 flexible array member也就是 level[] 数组。这个数组的每个元素代表一层的“前进指针”和“跨度”。一个节点在多少层上出现是插入时随机决定的。跟教科书里最简单的跳表相比Redis 的跳表多了两个设计细节务必注意。第一个是 backward 后退指针。普通跳表只有前进指针但 Redis 的 Zset 需要支持 ZREVRANGE、ZREVRANK 这样的逆序操作没有后退指针就得从 head 重新遍历代价很大。有了 backward逆序操作可以直接从 tail 往前走配合跨度可以快速定位。第二个是 span 跨度。每层的 forward 指针不只指向下一个节点还记录了“从当前节点到目标节点之间跳过了多少个元素”。这个跨度是 ZRANGE 和 ZRANK 能快速算出排名的关键。没有 span你想知道某个元素的排名就得老老实实从头数一遍有了 span从高层向下累加就能算出来。3.2 查找过程从高层往低层走跳表的查找逻辑其实一句话就能概括从最高层开始如果“下一个节点的 score 小于目标”就往右走否则往下走直到最底层仍然找不到目标就说明不存在。我画过很多次这个流程给你描述一下。假设跳表有 4 层目标 score 是 17。指针从 header 的最高层出发发现第一个节点的 score 是 5比 17 小于是向右移到 score5 的节点继续在同一层往后看发现下一个是 20比 17 大说明这一层走过头了于是下沉到第 3 层。在第 3 层score5 的节点的 forward 指向 score11 的节点11 小于 17继续向右然后发现下一跳是 22又过头了再下沉。重复这个过程直到最低层最终定位到 score17 或者确认它不存在。这个过程的复杂度是 O(logN)前提是层高分布合理。为什么能接近二分查找的效率因为每一层相当于对下层做了一次“隔一个取一个”的抽样从最高层开始每次跳过大约 2^k 个元素指数级地逼近目标。实际使用中我不建议大家死记“平均 O(logN)”这个结论而是要理解它为什么是 logN层数越高跨度越大查找时能跳过更多的元素层数越低越接近线性扫描用来做精确定位。高层的“大步跳”加上底层的“细步走”组合起来就是效率的来源。3.3 插入操作随机层高与逐层缝合插入一个节点比查找多两步随机决定层高、逐层更新指针和跨度。Redis 里随机层高的算法是初始层高为 1每次有 1/4 的概率增加一层直到最大层数 64Redis 7.0 之前是 32。这个 1/4 的概率是我认为 Redis 设计里很精妙的一个选择。如果概率是 1/2跳表会变得很“高”每层节点太多查询确实更快但内存浪费严重因为高层节点重复存储指针的代价很高。如果概率是 1/8层高太低跳表的“跳跃”效果变差查找退化。1/4 是时间和空间权衡下来比较理想的点。按这个概率平均每个节点层高约 1/(1-1/4) 1.33 层内存开销可控。插入的缝合过程是从 header 开始逐层查找插入位置记录每一层的前驱节点update[]和从头到该前驱节点的步数rank[]然后从底层向上依次调整指针。关键点在于 span 的更新公式新节点的跨度 原前驱到下一个节点的跨度 - (总排名 - 前驱排名)前驱的跨度 总排名 - 前驱排名 1。这个公式你要是记不住也没关系核心思想是插入后前驱跨向“下一个节点”的跨度要拆分成“前驱到新节点”和“新节点到下一个节点”两段。这也是 span 让排名计算变快的原因——每次插入都把这个距离信息维护好了。3.4 更新 score为什么是“先删后插”Zset 支持的 ZADD 可以覆盖更新 scoreZINCRBY 可以在原有 score 上增量。很多人以为更新 score 只需要找到节点改一下数值就行但底层实现并不是这样。Redis 更新 score 的逻辑是先通过 dict 找到节点删除它再用新的 score 插入跳表。为什么不能原地改因为跳表的有序性依赖于 score 作为比较键你改了 score节点在跳表中的位置可能完全不正确了。虽然可以按照“改 score 后前后移动若干步”的思路去维护但实现复杂得多而且极端情况下移动的距离可能很大。先删后插虽然常数略高但逻辑清晰正确性有保证。顺便说一句这也是为什么 ZINCRBY 频繁调用时涉及两个 O(logN) 操作删除 插入但常数很小实际性能依然优秀。我在压测里见过单实例每秒几十万次 ZINCRBY问题不大。4. 为什么是跳表而不是红黑树或 B 树4.1 平衡树的麻烦如果你看过其它有序数据结构一定会问为什么跳表而不是红黑树红黑树也是 O(logN) 的平衡树在很多语言的标准库里都有现成实现。我的理解是跳表的核心优势不在渐进复杂度而在工程实现和并发友好的程度上。红黑树实现一个范围查询给出 score 范围返回所有元素麻烦在于你必须先找到起点然后中序遍历找后继节点——中序遍历本身不是问题问题在于红黑树的节点没有“同层链表”结构找后继可能要回溯多层父节点。跳表就简单得多底层本来就是一个完整的有序链表从起点开始一路 forward 扫过去就行。范围查询是所有 Zset 业务的基础操作这一点直接让跳表胜出。另外一个在 Redis 的历史版本中曾被考虑过的点是并发性。虽然 Redis 本身是单线程的但跳表作为数据结构在并发环境下做无锁读、锁粒度拆分的难度远低于平衡树。这虽然不是 Redis 选择跳表的决定性理由但至少不添乱。4.2 为什么不用 B 树B 树是数据库索引的常客为什么 Redis 不用它做 ZsetB 树的核心优势在于磁盘 IO每个节点能存大量 key树的高度矮一次磁盘读取能带出很多数据。但 Redis 是内存数据库数据都在内存里B 树的“扇出大”就没什么意义了。相反B 树的节点分裂、合并逻辑极其复杂实现成本高而且在内存里维护这种结构未必比跳表快。再加上跳表可以通过调整层高生成概率来灵活控制内存和时间的平衡这在业务调优时非常实用。B 树做不到这种“按概率调节”的灵活性。所以对这个场景而言跳表是更务实的选型。4.3 跳表有什么缺点说实话跳表不是完美的。最明显的缺点是内存比紧凑编码大、比平衡树也略大。每个节点的 level[] 数组要为每一层存一个指针和一个 span指针 8 字节span 8 字节unsigned long平均 1.33 层的话每节点额外增加大约 20 字节左右。百万元素的 Zset这部分开销就是几十 MB。这在内存型数据库里不算小数目。跳表的缓存局部性也不如紧凑编码和数组。跳表节点是分散分配的遍历时可能频繁跳内存地址cache miss 较多。Redis 的解决办法是当数据量小时用 listpack 编码、数据量大时反正也要遍历很多节点cache miss 的影响相对有限——但你要知道这个 trade-off 是真实存在的。5. 核心操作的时间复杂度与真实场景推演5.1 ZADD、ZSCORE、ZRANGE 的底层路径把 Zset 的操作和底层结构对应起来是最容易理解全貌的方式。我用一张表总结命令时间复杂度底层路径ZADD key score memberO(logN)先走 dict 查找是否存在再走跳表插入/更新ZSCORE key memberO(1)走 dict 直接取分值ZINCRBY key increment memberO(logN)dict 找到后跳表先删后插ZRANGE key start stopO(logN M)跳表定位起点沿底层链表扫描 M 个元素ZREVRANGE key start stopO(logN M)利用 backward 从 tail 开始反向扫ZRANGEBYSCORE key min maxO(logN M)跳表按 score 定位起点再扫ZRANK key memberO(logN)跳表查找时累加 span算排名ZREVRANK key memberO(logN) O(1)总长减正序排名ZREMRANGEBYSCOREO(logN M)定位起点后逐节点删除更新前驱跨度看起来都是 logN但真实场景里差别很大。这个表格我建议你直接截图存着面试和排查问题都用得上。5.2 排行榜系统里每个命令发生了什么我用一个实际场景推演。假设你在做某游戏平台的全服积分榜Zset 的 key 是leaderboard:game_1里面有几百万玩家。玩家打完一局积分变了客户端调用 ZADDRedis 在 dict 里查这个玩家 ID 是否存在如果不存在O(1) 确认他是新玩家记录在案。如果存在拿到旧 score接着走跳表删除旧节点再插入新节点。删除时先沿高层定位沿途累加 span 获得排名然后缝合前后指针。插入时随机生成层高创建新节点重新调整受影响的前驱节点的 forward 和 span。整个过程是两次 O(logN) 跳表操作加一次 O(1) dict 操作。几百万节点的跳表层高通常在十几层到二十几层每一层做的都是指针比较常数很小。实测下来单条 ZADD 的耗时在微秒级别。查询“当前第 1 名到第 50 名”时使用 ZREVRANGE。Redis 会从 tail 节点的 backward 指针出发因为它本身就是按 score 升序排列的tail 对应最大 score。从 tail 往前走 50 步取出元素和 score再反转顺序返回。这里的耗时主要取决于 M50跟总量 N 无关。排行榜的前几页为什么快因为这个特性。查询“我排第几名”使用 ZREVRANK。跳表从 header 最高层出发查找该玩家每经过一个节点就把它的 span 加总得到正序排名再用总长度减去正序排名加一得到逆序排名。这里没有遍历整个链表全靠插入时维护好的 span 信息。5.3 延迟队列与滑动窗口的时间特性延迟队列是 Zset 的经典用法。score 存的是任务应执行的时间戳消费者用一个死循环执行 ZRANGEBYSCORE key -inf now LIMIT 0 100把到期任务取出来。这里的关键是复杂度 O(logN M)其中 M 是每个批次取出的任务数。即使队列里有千万级别的未到期任务只要到期任务不多扫描的成本就很低。滑动窗口限流的逻辑类似每个请求的 score 是当前时间戳每次请求前用 ZREMRANGEBYSCORE key -inf (now-window) 清掉过期记录再 ZADD 新请求最后 ZCARD 统计窗口内总数。这个场景里插入和删除都是 O(logN)清空过期窗口的删除复杂度取决于过期请求数。有个容易忽略的问题延迟队列和滑动窗口里的 Zset 会无限增长吗不会因为 score 是时间戳老任务会被 ZREMRANGEBYSCORE 清掉。但如果消费者挂了Zset 会持续堆积直到内存报警。所以这种场景必须配监控Zset 的 cardinality 超过阈值就要告警。我见过不止一次因为消费者故障导致 Zset 撑爆内存的事故教训就是排行榜和队列类 key 都要设置独立的监控项。6. 线上调优与常见问题排查6.1 调整编码转换阈值前面说过listpack 编码在内存上有压倒性优势。如果业务里大量 Zset 的规模都小于 128 个元素可以适当调大 zset-max-listpack-entries让更多小 Zset 留在紧凑编码。但别调得过于激进。一旦数据超过阈值触发转换是老数据全量重排耗时跟老数据量成正比线上会出现一次明显的延迟尖峰。我见过有人把阈值调到 10000结果一个 Zset 从 9999 涨到 10001 时Redis 卡了将近 200 毫秒。这个尖峰足以让依赖方超时。我的建议是默认 128 在大多数场景已经够用如果确实要调结合预热测试来确定合理值。不要拍脑袋调大。6.2 大 key 的检测与治理大 key 是所有 Redis 使用者的噩梦。Zset 的大 key 不只是“元素多”还包括“单个元素大”。我用 redis-cli --bigkeys 扫过很多次线上实例经常揪出几百万元素的排行榜。这类 key 的问题不是单条命令慢而是持久化的时候很慢——RDB 要序列化整个跳表AOF 重写也要遍历全量数据大 key 直接拖垮主从同步的延迟。治理方案无非几种拆 key比如把全服榜拆成“前 100 名榜 剩余普通榜”清零历史数据定期删除过期榜单或者对超大 Zset 用 scan 分批删除。删除 Zset 里的元素用 ZREMRANGEBYRANK 一次删一批比逐条 ZREM 快得多因为少了很多次跳表定位的开销。6.3 慢查询排查思路如果线上 Zset 相关的命令突然变慢我会按这个顺序排查第一确认编码。执行 OBJECT ENCODING key看是不是 LISTPACK。如果是再看元素数量和转换阈值的关系有没有可能刚触发过转换。第二确认大 key。执行 DEBUG OBJECT key看序列化长度和元素数量。第三确认慢命令类型。ZADD 慢可能是节点太多、层高过高ZRANGE 慢可能是返回太多数据网络传输占大头。第四如果以上都正常看是不是 Redis 本身的问题内存碎片、swap、或者同一实例上有其它大 key 干扰。排查慢查询不能只盯着数据结构Redis 是单线程的一个慢操作会拖累整个实例。6.4 跳表层高真的稳定吗跳表的随机性意味着极端情况下可能出现层高分布不均。虽然概率极低但理论上百万级节点全部集中在低层、导致查找近似 O(N) 的情况并非不可能。Redis 的层高生成上限是 64随机算法已经很成熟实际中我从未见过因随机性引发的性能灾难。但如果你在压测中发现查找速度异常可以用 ZSCAN 配合代码分析层高分布不过这个属于极少数情况大多数时候不用操心。7. 我的一些实践体会最后说点实际的。我带团队维护过不少 Redis 集群Zset 用的最多的地方就是排行榜和延迟队列。这两类场景的运维差异很明显。排行榜的 Zset 是典型的“读多写少”而且读取热点极其集中在前几页。虽然跳表对范围查询很友好但热 key 问题才是真正的挑战——几百万的访问量打到同一个 Zset 上单实例扛不住。我的做法是把排行榜做成两级全量榜放在主 Redis前 100 名单独缓存一份每次查询直接读缓存写操作异步更新全量榜并同步刷新前 100 名缓存。这比单纯调 Redis 参数有效得多。延迟队列的 Zset 则是“写多读少”而且容易堆积。我的经验是给每个业务配独立的 key 前缀方便排查和清理同时用 Lua 脚本把“取出到期任务 删除”合并成原子操作避免并发消费者重复处理。Zset 的 score 用毫秒时间戳不同业务之间错开 key不要混在一个 Zset 里否则一个消费者堵住整个队列都卡死。还有一个小技巧如果 Zset 里成员很长、重复前缀很多可以考虑在业务层做压缩存短 ID 而不是长字符串然后另建映射关系。这能显著降低跳表节点的内存占用同时避免触发 listpack 转 skiplist 的阈值。内存是 Redis 最贵的资源省一点是一点。Zset 的底层实现说到底就是两个结构各司其职、协同工作。dict 是索引跳表是顺序span 是排名的捷径backward 是逆序的后门。理解了这些你不仅能在面试里聊得深更能在线上出问题时知道从哪里下手。