Redis Zset底层结构解析：ziplist与跳跃表的设计与切换

聊到 Redis 的 Zset很多同学第一反应就是背诵八股文有序集合嘛底层是 ziplist 和跳跃表skiplist。但真被问到为什么是这两个结构什么条件下切换跳跃表凭什么取代平衡树的时候又容易卡壳。这篇不打算展开 Redis 客户端怎么调用就聚焦 Zset 底层的数据结构设计把 ziplist 和跳跃表这两个核心存储方案从源码层面拆清楚顺带聊聊我实际排查过的几个坑。Zset 解决的是既要集合去重、又要按分数排序的问题Hashtable 和 Sorted Set 的需求叠加起来Redis 给出的方案是一套组合拳小数据量用压缩列表压缩内存大数据量换成跳跃表加哈希表的复合结构这套设计在内存占用和查询效率之间做了很务实的取舍。文章会涵盖结构设计、参数选择、转换逻辑、踩坑实录适合准备面试的开发者也给正在用 Zset 做排行榜或时间窗口的工程同学做参考。1. 内容整体设计与思路拆解1.1 为什么 Zset 不直接只用一个数据结构先回到一个朴素的问题为什么 Zset 不老老实实只用一个结构存到底很多人把Zset 底层是 ziplist 和跳跃表当成结论背却忽略了 Redis 选择这种组合的底层逻辑。任何数据结构都存在权衡要么牺牲内存换时间要么牺牲时间换内存。Zset 面对的场景很具体存储一组带分数的成员支持按分数排序、范围查询、排名计算成员的个数和单个成员的大小不确定可能只有几个也可能是几百万个。如果只用跳跃表实现每个节点要维护多层指针加上成员对象和分数内存开销相当可观。一个空的跳表节点在 64 位系统下光指针就可能占几十字节遇到成员值是长字符串时内存成本会被进一步放大。但跳跃表的优势在于插入、删除、查找复杂度都是 O(logN)范围查询和排名计算也非常顺手。反过来如果只用 ziplist内存确实省到了极致但插入和删除都要移动后面的元素数据量一上来就是灾难性的 O(N) 复杂度。所以 Redis 的思路不是选一个最好的而是选一个当前阶段最合适的。数据量小的时候内存敏感操作效率的劣势不明显ziplist 是最优解。数据量大了以后操作效率变成瓶颈跳跃表的 O(logN) 代价就值得付。这种动态切换的思路在 Redis 源码里随处可见比如哈希表的 small hash 也用了压缩列表只是 Zset 的切换逻辑更典型。1.2 组合结构哈希表加跳跃表Zset 真正的大数据量结构并不是跳跃表单独作战而是跳跃表加哈希表的复合体。这个点特别容易被忽略。源码层面Zset 对应的结构体是zset里面有两个成员typedef struct zset { dict *dict; zskiplist *zsl; } zset;dict保存 member 到 score 的映射用来快速根据成员查分数复杂度 O(1)。zskiplist保存按 score 排序的完整成员列表用来支持范围查询和排名。这两个结构共享同一批 member 和 score 数据不会真把元素复制两份指针层面的复用。这样设计的原因很好理解仅仅有跳跃表按成员名查分数就变成了 O(logN) 的查找但哈希表能做到 O(1)。仅仅有哈希表范围查询和排序就没法高效实现因为哈希表天然无序。两者搭配成员查询走 dict排序和范围走 zskiplist各司其职。我曾经见过有面试者把 Zset 的底层回答成哈希表加双向链表这基本是混淆了 Redis 的快速列表和有序集合的实现。Zset 用的确实是跳跃表不是普通链表。跳跃表在范围查找上的表现比链表好得多这个差异在数据量大的时候非常显著。1.3 Zset 的语义约束score 相同怎么办聊底层结构之前还必须先搞清楚 Zset 的排序规则因为它直接影响数据结构的设计。Zset 里每个 member 对应一个 double 类型的 score排序时先按 score 升序排score 相同的情况下按 member 的字典序排。这个score 相等时按成员字典序的规则不只是业务约束而是写死在排序结构里的。跳跃表节点里存的不是裸的字符串指针而是一个sds字符串和一个 double score。插入和查找时比较的先后顺序是先比 scorescore 相等再比 member 的字典序。ziplist 里也遵循同样的比较逻辑只是把比较的逻辑写在了 ziplist 遍历的代码分支里。这个一致性是 Redis 设计比较严格的地方保证不管数据量小还是大排序结果都是一样的。这也解释了为什么在 Zset 里写入两个相同 member 时分数会被覆盖而不是报错因为 member 本身就是唯一键dict 部分直接做覆盖跳跃表部分则删除旧节点插入新节点。2. 核心细节解析ziplist 的布局与操作逻辑2.1 ziplist 的内存布局ziplist 的本质是一块连续内存上排列的多个 entry每个 entry 存储一个 member 或者一个 score。Zset 使用 ziplist 时成员和分数是交替存储的也就是说第一个 entry 是 member1第二个 entry 是 score1第三个是 member2第四个是 score2依次类推。这种排列方式让 member 和 score 的配对关系直接在布局上就固定下来不需要额外存索引。每个 entry 的结构包含三个部分prevlen前一个 entry 的长度用于从后往前遍历时快速定位前一个节点。这个字段可能占 1 字节或 5 字节取决于前一个节点的长度是否超过 254。encoding编码类型标识当前 entry 存储的是整数还是字符串以及具体的长度信息。data实际存储的数据。prevlen这个字段就是所谓的连锁更新问题的根源。当某个 entry 的长度发生变化导致后一个 entry 的prevlen需要从 1 字节扩展成 5 字节时这个扩展又可能导致再后面一个 entry 的prevlen跟着变像多米诺骨牌一样往后连锁。虽然触发条件比较苛刻但确实存在这也是 ziplist 在写多场景下不够稳的原因之一。2.2 Zset 在 ziplist 编码下的读写路径当 Zset 的编码类型是OBJ_ENCODING_ZIPLIST时所有的查找都是线性遍历。比如要查询某个 member 的 scoreRedis 会从 ziplist 头开始逐个 entry 比较 member 字符串找到之后再读取相邻的 score entry。插入一个元素时先遍历找到合适的位置然后把后续的数据整体后移再写入新的 member 和 score。听起来很原始但注意这是在小数据量前提下跑的实测下来几千个 entry 级别的查找和插入都是微秒或者几十微秒级别完全够用。ziplist 真正的优势是内存密度高得吓人。一个只存整数 score 和短 member 的 Zset用 ziplist 存储时每个 entry 的额外开销可能只有几个字节比起跳跃表动辄几十字节的指针开销内存占用可能相差一个数量级。我实际测过一组数据往一个空的 Zset 里连续写入 10000 个结构相同的 member每个 member 是 8 字节左右的短字符串score 是 1 到 10000 的整数。此时还没有触发升级条件的话用 ziplist 编码的 Zset 占用内存大概在几十 KB 级别如果手动强制用跳跃表编码内存占用会翻好几倍。这个差距在生产环境如果体现在大规模实例上就是几个 GB 和几十 GB 的差距。2.3 什么时候 ziplist 撑不住ziplist 撑不住的本质原因有两个一是写入时的内存移动成本随 entry 数量线性增长二是连锁更新会把最坏情况的时间复杂度放大到 O(N²)。当 Zset 的 member 数量变大之后每次插入都可能触发大块内存的 memmove这个操作的时间开销会直接体现在命令延迟上。而且 ziplist 的查找是 O(N)当 entry 数量到了几万级别时一次 ZSCORE 也可能消耗几十微秒这和哈希表的 O(1) 相比差距就出来了。触发从 ziplist 转到跳跃表的条件Redis 有两个参数控制参数默认值含义zset-max-ziplist-entries128Zset 元素个数超过该值则转换zset-max-ziplist-value64单个 member 的长度超过该字节数则转换只要元素个数超过 128或者任意一个 member 的字符串长度超过 64 字节整个 Zset 就会被转换成OBJ_ENCODING_SKIPLIST。这个转换是“不可逆”的Redis 不会在元素删除到少于 128 个之后自动转回 ziplist。值得注意的一个细节是当 Zset 还处于 ziplist 编码时如果新插入一个长 member即使此时元素个数很少也会触发转换。因为转换条件的判断是插入前先检查待插入的 member 长度超过 64 字节直接进入转换流程。我在实际业务中遇到过类似场景一个 Zset 正常存了 80 多个短 ID某次不小心插入了一个几百字节的 JSON 字符串结果整个 Zset 就被升级成跳跃表了内存瞬间上涨。这个问题在写代码的时候容易被忽略。3. 跳跃表的核心结构层、指针和跨度3.1 为什么选跳跃表而不是红黑树跳跃表能成为 Zset 大数据量下的核心结构原因可以从几个维度看。红黑树在内存数据库里也常见比如 MemDB 和实际数据库引擎都会用它的查找、插入、删除复杂度同样是 O(logN)而且最坏情况可控。但跳跃表有一个红黑树很难比的优势实现简单且更容易支持范围查询和排名。跳表是链表加多层索引的产物。每层都是一个有序链表底层链表包含所有节点上层链表是下层节点的抽样索引。查找时从最高层开始遇到比目标大的节点就下沉一层继续找最终到底层完成精确查找整个过程类似二分查找。代码层面遍历和插入逻辑很直白不需要像红黑树那样做左旋右旋、染色这些复杂的平衡操作。范围查询方面红黑树虽然也能做中序遍历但要找到范围内的起始节点然后一路 next代码写起来比较复杂。跳跃表要查某个分数区间就非常简单先找到区间左端点然后顺着底层链表往右遍历即可。Zset 的ZRANGEBYSCORE就是这么实现的效率非常高。排名计算也是同理只要在节点里维护好跨度span就能在查找过程中累加算出来。3.2 跳表节点的核心字段拆解Redis 的跳跃表实现有自己的一套细节和教科书里的标准跳表略有不同。先看节点结构typedef struct zskiplistNode { sds ele; double score; struct zskiplistNode *backward; struct zskiplistLevel { struct zskiplistNode *forward; unsigned long span; } level[]; } zskiplistNode;逐字段拆解ele成员字符串的指针持有 sds 对象。scoredouble 类型的分数。backward指向前一个节点的指针仅在底层链表存在用于 ZREVRANGE 这种反向遍历。level[]柔性数组每个节点有一个 level 数组数组的每一项包含forward指针和span。forward指向当前层下一个节点span表示当前节点到下一个节点之间跨过的底层节点数量。span是 Redis 跳表实现里非常关键的一个字段也是我之前忽略的地方。没有 span 的话要计算一个节点的排名就只能从链表头开始数复杂度 O(N)。有 span 之后查找节点沿途累加 span就能在 O(logN) 时间内得到排名ZRANK命令的性能就是这样保证的。每个节点的层数不是固定的而是在插入时按概率随机生成。Redis 的层数生成逻辑是每层有 25% 的概率继续向上加层最高限制为 64 层。这意味着平均每个节点大概有 1.33 层绝大多数节点只有一层少数节点有多层。正是这种随机性让跳表在期望意义上达到 O(logN) 的查找复杂度并且不需要像平衡树那样做严格的结构调整。3.3 跳表头节点与查询过程跳表本身有一个zskiplist结构体typedef struct zskiplist { struct zskiplistNode *header, *tail; unsigned long length; int level; } zskiplist;header头节点不存储实际数据但 level 数组有 64 层各层的 forward 指针初始化为 NULL。tail指向最后一个节点。length节点的个数。level当前跳表的最大层数。查找一个 score 的过程可以概括为从 header 的最高层开始如果当前层的 forward 节点不为空且它的 score 小于目标 score或者 score 相等但 member 字典序小于目标 member就向前移动到该节点并累加 span如果 forward 节点为空或者已经大于目标就下沉一层继续。重复这个动作直到最底层最终定位到目标节点或者确定它不存在。这个过程在代码里表现为一个双层循环外层循环控制层数从高到低内层循环控制在同一层的跳跃移动。整个过程的比较次数期望值是 O(logN)优于 ziplist 的 O(N)。4. 切换机制与相关配置的实操细节4.1 切换触发点和不可逆性Zset 编码从 ziplist 切换到 skiplist 的过程源码逻辑在t_zset.c的zsetConvert函数里。触发点并不是在每次写入指令后都判断一次而是在插入新元素的流程里插入完成后确认 ziplist 的 entry 数量或者某个 member 的长度是否超过阈值。一旦超过Redis 会新建一个 zset 结构把原有 ziplist 里的数据逐个取出插入到新建的跳表和哈希表中然后释放原有 ziplist。具体转换过程有三种情况Zset 创建时就是空的可能直接用 skiplist 编码比如通过ZADD插入第一个元素时就决定了后续编码类型。Zset 从 ziplist 转换到 skiplist这是最常见的路径发生在插入操作期间。从其他编码转换成 skiplist比如 RDB 加载或者 AOF 重放时如果配置参数不同也可能强制转换。转换是单向的这一点非常重要。Redis 官方文档里没有说数据删少之后会转回 ziplist源码里也看不到反向转换逻辑。所以一旦 Zset 经历过大数据量阶段即使后来数据删得很少它的内存占用也不会回落。要真正回收内存只能删除这个 key 或者把数据重写到另一个新 key 里。4.2 如何正确配置 zset-max-ziplist-entries 和 zset-max-ziplist-value这两个配置的值直接影响内存和性能的平衡。默认值是 128 和 64但很多人不知道的是Redis 在 7.0 之后引入了 listpack 来替代 ziplist新版本的配置名变为zset-max-listpack-entries和zset-max-listpack-value。虽然概念类似但底层实现不同listpack 解决了 ziplist 的连锁更新问题。在生产环境调整这两个参数时我的经验是按业务实际数据特征来不盲目按默认值。如果 Zset 的成员数量稳定在几千个以内而且每个 member 都是短字符串可以把zset-max-ziplist-entries调大到 1024 甚至 2048这样可以继续享受 ziplist 的内存优势。但要注意ziplist 的写入复杂度是 O(N)如果这个 Zset 是写频繁的热点 key调大 entries 阈值可能带来明显的延迟抖动。如果 member 长度不可控比如用户输入或者接口返回的字符串建议保持默认或者把 value 阈值调小。因为一个长 member 一旦出现整个 Zset 就会升级之前的 ziplist 内存优化全部白费。与其这样不如在业务层面直接限制 member 长度或者给长内容做哈希映射后再存入 Zset。我还见过一种比较极端的用法纯粹用 Zset 做时间窗口member 是事件 IDscore 是时间戳同时开启淘汰策略定期清理过期成员。这种场景下 Zset 的成员数量会长期保持高位ziplist 编码基本没有机会使用直接走 skiplist 编码所以配置 ziplist 阈值意义不大核心优化方向应该是控制 Zset 的容量和清理频率。4.3 从 RDB 和 AOF 加载时如何选择编码Redis 从 RDB 文件加载或从 AOF 文件重放指令时走的是另外一套逻辑直接把数据重建到内存此时对 Zset 编码选择的判断同样会依据当前实例的配置参数。如果 RDB 文件里存的是一个使用 ziplist 编码的 Zset而当前实例的zset-max-ziplist-entries配置比保存时小加载时就有可能直接转换成 skiplist 编码。这个行为带来的实际影响是备份恢复之后同样一个 Zset 的内存占用可能和备份之前完全不同。我曾在一次演练中把 RDB 从测试环境恢复到生产环境因为两边配置不一致恢复后内存凭空多了几个 GB查了很久才发现是 Zset 编码不一致导致的。所以线上环境建议统一配置管理 Redis 参数确保主从、备份恢复后行为一致。5. 实操中的几类典型问题与排查方法5.1 为什么 Zset 内存比预估的大很多遇到 Zset 内存暴增第一步应该用DEBUG OBJECT key查看内部编码和内存占用。如果编码已经变成 skiplist但业务预期数据量很小大概率是曾经插入过超长 member或者曾经元素数量超过阈值导致不可逆转换。还有一种隐蔽情况Zset 的 member 是数字字符串时Redis 可能用整数编码存储内存占用比较低如果 member 是随机字符串或者 UUID每个 member 都是一长串字符skiplist 节点里要保存完整的 sds 字符串内存增长会变得很明显。这种情况下可以考虑把长字符串映射成数字 ID再用 Zset 维护 ID 的有序关系原字符串单独存到哈希里。DEBUG OBJECT的输出里能看到encoding字段这是判断编码类型的直接依据。我排查问题时一般先看这个字段再结合业务写入量判断是否发生过升级。5.2 连锁更新是否要在意ziplist 的连锁更新是一个老生常谈的问题实际触发的概率其实不高。连锁更新的前提是连续多个 entry 的长度都在 250 字节到 253 字节之间任何一个 entry 长度变化超过阈值就会引发后续 entry 的 prevlen 从 1 字节变 5 字节。在 Zset 场景下如果一个 Zset 大量存储长度接近的字符串且处于 ziplist 编码确实有这个风险。但因为默认 64 字节的 value 阈值本身限制了 member 的长度字符串 entry 长度超过 64 字节就会触发编码升级因此 Zset 在 ziplist 编码下出现 chain reaction 的概率比 list 场景更低。更需要注意的是 hash 编码的哈希表不过不在这次讨论范围里。如果真担心这个问题换用 Redis 7.0 以上的 listpack 实现是最直接的方案listpack 从设计上避免了对前一个节点长度的依赖不会出现连锁更新。5.3 跳跃表层数过高或者过低的影响跳表层数由随机算法决定Redis 通过ZSKIPLIST_MAXLEVEL宏限制最大层数为 64。虽然随机算法会让每个节点的层数独立分布但极端情况下可能出现层数特别高或者整体层数偏高的情况。如果插入的数据量非常大高层节点偏多会导致内存微增但时间复杂度仍然维持在期望的 O(logN)不会有严重退化。真正需要注意的是 score 出现 NaN 或者特别大的数值。Redis 的 Zset 对 score 为 NaN 的处理是直接拒绝的但极端大的 score 和负 score 会导致排序行为比较抽象业务上容易踩坑。比如存储时间戳时如果某个成员的时间戳设置成了 0 或者负数它会排在 ZSET 的最前面如果业务逻辑默认第一个成员是最新的就会读错数据。5.4 排查命令和观察手段汇总处理 Zset 问题时我用得比较多的排查命令有这么几个命令用途ZSCAN key遍历 Zset 成员观察成员长度分布ZCARD key获取成员数量判断是否超过阈值DEBUG OBJECT key查看编码类型和内存占用MEMORY USAGE key查看 key 整体内存占用ZRANGE key 0 -1 WITHSCORES快速人工检查排序是否异常我曾经排查过一个Zset 查询越来越慢的线上问题。客户端反映ZRANGEBYSCORE的耗时从原本的不到 1 毫秒涨到几十毫秒结果发现这个 Zset 的成员数量已经到了百万级别而且底层是 skiplist 编码。按理说 skiplist 的 O(logN) 查找不应该这么慢但问题是业务方在ZRANGEBYSCORE时没有加 LIMIT一次性把符合条件的几万条数据全返回了网络传输和数据序列化成了真正的瓶颈。这个案例提醒我很多时候底层结构设计得再好命令用法不当也会把性能吃回去。另一个常见问题是 Zset 存储大 member 的场景。有个业务把整个日志行作为 member 存入 Zset每条日志好几 KB导致 value 阈值轻松触发编码升级再加上ZREVRANGE每次读取大数据量Redis 的内存和带宽双双告警。后来改成只存日志 ID把完整日志放到对象存储问题立刻缓解。这类问题通常不是 Redis 本身不行而是数据建模时没有考虑底层结构的特点。6. 个人实践中的几点体会最后聊几个我自己的操作习惯不一定适合所有团队但至少能帮你少走弯路。第一个习惯是初始化时就明确 Zset 的规模预期。如果业务明确知道这个 Zset 会超过 128 个元素那就不要依赖默认的 ziplist 阶段直接用ZADD时指定的合理参数或者干脆在代码层面设计好数据淘汰策略避免 Zset 无限膨胀。第二个习惯是监控 Zset 的编码类型变化。可以用定时任务扫描生产环境的DEBUG OBJECT把编码类型和内存占用变化记录到监控系统里。一旦发现某个 key 从 ziplist 变成 skiplist就要关注对应的业务代码是不是写入了异常的大 value这个信号往往比内存告警来得更早。第三个习惯是在涉及排名的场景尽量把 score 设计成整数或者定点数。虽然 Redis 的 score 是 double但浮点比较的精度问题在长时间运行后可能带来排序错乱。我在做排行榜业务时用了时间戳加计数组合编码成一个大整数作为 score既保证排序稳定又避免了浮点精度问题。最后一个看似小但很实用的技巧清除 Zset 大 key 时不要直接用DEL在 Redis 4.0 以上版本虽然有 UNLINK 异步删除但如果是集群环境最好还是先ZREMRANGEBYRANK key 0 -1分批清理或者直接 rename 之后异步删除避免主线程卡顿。这个操作看起来简单但在大数据量 Zset 上实测过能明显降低对线上服务的影响。Zset 底层的双结构设计本质上是一种小数据量追求极致内存、大数据量追求稳定性能的工程折中。理解这套机制不只是为了应付面试更是在实际业务里做出正确建模选择的前提。希望这篇能帮你在遇到 Zset 性能或者内存问题时多一个排查思路。