做后端这些年Redis的Zset有序集合用得是真不少排行榜、延迟队列、关注列表随手就是一个场景。但说实话很长一段时间我对Zset的理解也就停在“底层有个跳跃表”的程度直到有一次接口压测发现一个几万成员的Zset插入耗时突然涨了一个量级才逼着我去把底层结构彻底翻了一遍。翻完才发现Zset底层的设计远比我以为的讲究——它用的是ziplist和跳跃表两套结构小数据量时走压缩列表省内存数据规模上来之后切到跳跃表保效率。这篇文章就把我梳理出来的东西完整讲一遍包括两套结构各自的设计逻辑、切换阈值、源码层面的实现细节以及我在排查性能问题时踩过的坑。1. 为什么Zset要同时持有两套方案1.1 Zset对外暴露的能力决定了它没法只用一种结构先把Zset的对外能力捋一下。一条ZADD命令要支持按分数排序一条ZSCORE要能直接拿到某个成员的分数一条ZRANGE要做范围遍历而且这些操作面对的数据量可能是几十条、也可能是上千万条。这意味着底层结构得同时满足四个需求按成员精确查询分数要快按分数区间遍历成员要快插入时自动维持有序要快存储时要尽可能省内存。如果用数组实现范围查询倒是简单但中间插入一个元素就要搬动后面一堆数据O(N)的成本在大数据量下直接崩掉。如果用普通链表插入虽然方便但按分数查找要一个一个遍历同样扛不住。用红黑树能做到平衡但实现复杂度摆在那而且范围遍历还要做中序遍历、代码写起来烦。用哈希表按成员查分数是O(1)可哈希表本身不维护顺序想按分数排序还得再排一遍。所以Zset的核心矛盾是单靠任何一种基础数据结构都没法同时把这四件事做好。Redis最终的做法不是选一种而是准备了两种编码让它们在不同规模下各管一段。这也是Redis一贯的思路——能用紧凑结构省内存的地方绝对不追求花哨。1.2 两套方案的分工小集合用ziplist大集合用skiplistZset的底层编码有两种编码类型使用条件核心优势ziplist元素数量少、元素长度小内存紧凑、缓存友好skiplist元素数量多或元素长度大插入、查询、范围操作O(logN)ziplist的本质是一块连续内存所有成员按分数从小到大紧密排列没有指针也没有额外节点开销几十个元素的场景下查询直接遍历这块内存内存访问是顺序的、CPU缓存命中率极高实测下来反而比跳到表还快。skiplist则是跳表加哈希表的组合用跳表维持有序性、支持范围遍历用哈希表提供按成员查分数的O(1)能力。我见过不少人在面试里只知道“Zset是跳表”实际上Redis 3.2之前底层只有ziplist和skiplist两套Redis 7.0之后把ziplist换成了listpack但设计哲学一脉相承。对这个演变过程心里有数之后再看Zset的性能问题就不会只盯着命令本身了。2. ziplist编码内存抠到极致的小集合方案2.1 先把ziplist的内存结构拆开ziplist这个名字翻译成“压缩列表”说白了就是一块连续的字节数组但它内部不是一棵树也不是链表而是通过特殊的编码格式把一系列entry串起来。整体布局是zlbytes zltail zllen entry1 entry2 ... entryN zlend四个字段各司其职zlbytes记录整个ziplist占用的字节数zltail记录最后一个entry的偏移量zllen记录entry数量zlend是结束标记。这套设计让ziplist可以在O(1)时间内定位到头尾节点做双向遍历时依靠每个entry里的prevlen字段往回跳。每个entry本身又分成三个部分prevlen记录前一个entry的长度用于反向遍历encoding标注当前entry存储的是整数还是字符串以及占了多长data实际的数据内容。这里有个很妙的点prevlen不是固定字节数。如果前一个entry长度小于254字节prevlen用1字节就够如果前一个entry超过254字节prevlen就要扩展成5字节其中第一个字节是固定标记0xFE后面4字节才是真实长度。这个设计是为了省内存但后面会引出一个让人头疼的级联更新问题。2.2 ziplist省内存与慢改写的取舍ziplist为什么省内存因为它把多个元素一个挨一个地塞进同一块连续内存没有指针、没有节点头和尾的冗余信息每个元素的额外开销压缩到极致。对比一下普通链表每个节点至少要存一个next指针64位系统下是8字节还要存prev指针加上节点对齐一个元素几十字节的内存就没了。而ziplist里一个整数元素总共可能只占3到5字节差距非常明显。但省内存是有代价的。ziplist的插入和删除操作本质是在连续内存上做memmove把目标位置之后的元素整体搬移。举个例子往中间插入一个元素最坏情况下后面所有元素都要往后挪时间复杂度是O(N)。数据量小的时候N可能就几十一次搬移几十个字节这点成本完全可以忽略可一旦元素量涨到几百上千每次插入都伴随着大块内存搬移性能就开始难看了。这也就是为什么Redis给ziplist设置了使用上限元素数默认不超过128个每个元素长度默认不超过64字节。在这个规模内ziplist的遍历和搬移成本都可控而且因为内存紧凑、cache完全命中它的实测性能甚至好过跳跃表。我在本机对比过100个元素的Zset里做ZRANK和ZSCOREziplist编码的耗时确实比skiplist编码稳定低一截这就是缓存命中的威力。2.3 需要时刻提防的级联更新级联更新cascade update是ziplist最经典的坑。前面说了prevlen可能是1字节也可能是5字节。当一个entry的长度发生变化比如从250字节变成260字节它后面那个entry的prevlen字段就可能要从1字节扩展成5字节。而prevlen扩展意味着后面那个entry本身也变长了于是再后面那个entry的prevlen又要跟着变一层层传导下去最坏情况下整个ziplist所有entry都要重写。这个问题的根源在于“记录前一个entry长度”这个设计本身。虽然绝大多数情况下一个entry变长不会触发连锁反应因为prevlen从1字节变5字节的阈值是254字节一个元素长度从原本的小于254变成大于254才有可能爆一次但一旦触发最坏情况就是O(N)的重写操作。生产环境里一批大量的小字符串不小心更新成超长字符串就可能引发一次预料之外的CPU毛刺。3. skiplist编码有序能力的真正支撑3.1 跳跃表的基本结构当Zset元素量超过128个或者某个成员的长度超过64字节编码就切换成skiplist。很多文章把这一步写成“变成跳跃表”严格来说不对实际是变成了跳跃表 哈希表的组合。先从跳跃表本身说起。跳跃表本质上是在链表上加了多层索引每个节点不止有forward指针还有一个level数组数组里每一层都保存一个指向下一个节点的指针以及一个span字段记录这一层跨越了多少个节点。查找时从最高层开始如果下一层的目标节点分数比当前大就往当前层的下一个节点走否则降低一层继续走。这个“先跳大步再缩小步长”的过程把查找复杂度压到了O(logN)。Redis的跳跃表节点结构大致长这样typedef struct zskiplistNode { sds ele; // 成员对象 double score; // 分数 struct zskiplistNode *backward; // 后退指针 struct zskiplistLevel { struct zskiplistNode *forward; // 前进指针 unsigned long span; // 跨度 } level[]; } zskiplistNode;你注意看这个结构里只存了ele和score没有存字典。而zskiplist结构本身则维护着header、tail、length和当前最大层数。真正的member到score的映射关系是靠旁边那个哈希表dict来维护的。3.2 查找、插入、删除的时间复杂度跳跃表的查找、插入、删除平均时间复杂度都是O(logN)。原因在于每一层索引都近似地把数据量减半从最高层一路下来每一层都只访问常数个节点整个过程遍历的节点总数被控制在O(logN)级别。插入的时候跳跃表会从header开始在每一层找到最后一个分数小于目标值的节点记录下“插入路径”然后随机生成一个层高再按路径更新每一层的forward指针和span值。Redis采用的随机策略是每往上提升一层的概率是25%这种分布会让绝大多数节点只停留在第1层少数节点会被抽到更高的层从而保证索引分布的均匀性。删除是插入的逆过程先定位到目标节点然后从每一层把对应的指针摘掉。这里值得提的是跳跃表里的节点已按分数成员字典序排好所以删除操作能精确命中不需要额外比较字符串内容。整个过程对Zset的命令表现来看插入、删除、按分数查找的耗时都非常稳定数据量从1万涨到100万单次操作从几十微秒涨到几百微秒完全可控。3.3 为什么是跳跃表而不是红黑树这个问题我自己也想过很久后来看了一些源码和论文整理出来几个关键理由实现简单。红黑树的插入删除要处理左旋、右旋、变色各种边界条件很容易写错。跳跃表就是随机化加多层链表逻辑直接调试起来也方便。范围查询友好。Zset的核心命令是ZRANGE、ZRANGEBYSCORE红黑树虽说也能做中序遍历得到有序序列但从指定位置开始截取一段区间的成本跳跃表在结构上更自然。内存可控。红黑树每个节点有两个指针跳跃表平均层数约1.33因为25%概率递增节点指针数比红黑树多不了多少再加上Redis做了内存池和对象复用差距在可接受范围。调参灵活。跳跃表的层高上限、每层提升概率都可以配置方便针对读写比例做微调。红黑树的平衡策略是写死的想动都动不了。顺便提一句Redis的跳跃表用的是概率平衡而不是绝对平衡也就是说极端情况下某棵高层索引可能偏斜但实际概率极低工程上完全够用。这一点和红黑树的严格平衡形成了鲜明对比。3.4 为什么旁边还要配一个哈希表如果你只用跳跃表存member到score的映射那ZSCORE命令就得从跳表根节点一路查找虽然也是O(logN)但代价不小而且跳表查找还要逐层比较分数和成员字符串。Redis的做法是额外维护一个dictkey是membervalue是score这样ZSCORE就能做到O(1)。这个组合在源码里看得很清楚。当编码是skiplist时zset结构是这样typedef struct zset { dict *dict; zskiplist *zsl; } zset;dict负责member到score的快速映射zsl负责维持有序性和范围操作。两套结构共享同一份member对象的引用代价就是每次修改分数时两个结构都要同步更新。这也是为什么ZADD更新已存在成员的分数时不光是跳表里挪个位置字典的value也得跟着改。理解了这层组合你再看Zset在数据量大时的内存开销就明白了每个成员要同时存在跳表节点和哈希表节点里索引开销自然比ziplist大。这也是Redis换掉ziplist时不止换成skiplist、还要搭一个dict的原因——单纯用跳表ZSCORE这种高频命令就没法保持O(1)了。4. 切换阈值、转换过程与Redis 7.0之后的升级4.1 默认阈值与配置项Zset从ziplist切到skiplist的开关是两个配置项zset-max-ziplist-entries默认128控制ziplist最多容纳多少个元素zset-max-ziplist-value默认64控制单个元素的最大长度字节。只要“元素数量超过128”或者“任一元素长度超过64字节”两者满足其一这个key就整段切到skiplist编码。注意这两个条件是“或”而不是“且”很多人背的时候容易记混其实源码里就是一条if (zsetLength server.zset_max_ziplist_entries || ziplistLength(...) server.zset_max_ziplist_value)。Redis 7.0之后ziplist退出历史舞台换成listpack配置项也改成了zset-max-listpack-entries和zset-max-listpack-value默认值还是128和64。如果你在Redis 7.0上执行CONFIG GET *zset*看到的会是listpack开头的配置项而不是ziplist。4.2 从ziplist到skiplist的转换到底发生了什么一旦触发阈值Redis会在zaddGenericCommand的执行路径上做一次编码转换。这个转换是原子的先申请并构建一个新的zset结构包含dict和skiplist把原ziplist里的元素逐个读出、插入新结构然后释放原ziplist最后让key指向新结构。转换过程的时间复杂度是O(N)N是当前Zset的元素个数。如果哪个key恰好卡在阈值附近比如130个元素转换就只牵扯130次插入几乎无感但如果你手贱把阈值调得极大比如调成100万然后硬生生往里塞到超过阈值那一次转换就要重建上百万个节点瞬间的CPU开销会相当可观。这里有个非常容易被忽略的细节转换是单向的不可逆。一个key一旦从ziplist转成skiplist哪怕你随后把元素删到只剩几个它也会永远维持skiplist编码不会自动“缩回去”。这跟Redis对字符串类型的embstr转raw的逻辑完全不同——字符串类型再写回短值时还能转回embstr但Zset没有设计“反向降级”的路径。原因也简单反向转换一样要O(N)重建而且频繁来回切换会造成更差的内存抖动干脆不做。4.3 Redis 7.0为什么把ziplist换成listpackziplist的级联更新问题在特定场景下会引发性能毛刺Redis社区其实很早就在找替代方案。listpack就是那个替代品它的思路是不再记录前一个entry的长度而是用一套更精巧的编码在每个entry自身尾部带上长度信息。这样一来修改某个entry只需要更新它自己的长度字段完全不会影响后面的元素级联更新这个顽疾从根上就被消除了。对比一下两种结构维度ziplistlistpack反向遍历依据前一个entry的prevlen当前entry的backlen级联更新存在最坏O(N)不存在内存开销较省略高一点但差距极小Redis 7.0之后仅用于兼容旧数据Zset、Hash、List新写入默认我个人的理解是listpack牺牲了极小的内存密度换来了稳定的最坏时间复杂度。对现代CPU来说那一点内存增量几乎无感但操作耗时抖动没了这才是生产环境最看重的。5. 用OBJECT与DEBUG命令看真实编码5.1 实战查看编码类型理论讲再多不如直接上手看一次。连接一个Redis实例执行127.0.0.1:6379 ZADD test 1 a 2 b 3 c (integer) 3 127.0.0.1:6379 OBJECT ENCODING test ziplist三个短成员编码是ziplist。继续往里加把元素数量顶到128个以上127.0.0.1:6379 EVAL for i1,200 do redis.call(zadd, KEYS[1], i, member_..i) end return redis.call(zcard, KEYS[1]) 1 bigset (integer) 200 127.0.0.1:6379 OBJECT ENCODING bigset skiplist也可以换个角度用一个大字符串当作member单个元素长度超过64字节就会触发转换127.0.0.1:6379 ZADD longmember 1 [string repeat x 100] (integer) 1 127.0.0.1:6379 OBJECT ENCODING longmember skiplist这个命令在生产环境也能用只是如果key很大OBJECT ENCODING本身耗时极低可以放心执行。5.2 实测两种编码的真实内存差异空说没意义我拿本机Redis 6.2做了个对比测试。构造一个正好100个成员的Zset成员是8字节长的数字字符串对比它在ziplist编码和强制切到skiplist编码时的内存占用。先正常插入100个短成员编码是ziplist用MEMORY USAGE看占用127.0.0.1:6379 ZADD z1 1 m1 2 m2 3 m3 ... 127.0.0.1:6379 MEMORY USAGE z1 (integer) 1144然后强制插入一个长度为200字节的长成员触发转为skiplist再去掉这个长成员编码不会降级再看内存127.0.0.1:6379 MEMORY USAGE z1 (integer) 4536同一个Zset同样的100个短成员内存从1.1KB涨到4.5KB整整多了接近4倍。这就是skiplist编码要额外维护跳表索引和哈希表的代价。别小看这个差距如果Redis里堆了成千上万个百人左右的部门排行榜、小组排行榜每个key多出几KB累积起来就是几百MB的额外内存。5.3 从命令表现反推底层结构其实不用OBJECT ENCODING光看命令耗时也能反推编码类型。在member数量小于100的情况下ziplist编码ZRANGEBYSCORE底层是顺序遍历连续内存耗时和返回值长度基本线性没有额外索引开销skiplist编码ZRANGEBYSCORE会走跳表索引小范围取值的耗时甚至可能比ziplist略高一点点因为指针分散、CPU缓存命中率低。我自己压过一个小数据量的查询ziplist编码的ZSCORE耗时大约是skiplist编码的60%左右这不是Redis算得慢而是连续内存的缓存优势太明显。反过来SKIPLIST在百万级数据上的ZRANGEBYSCORE耗时几乎是常量级别的稳定而ziplist在这种规模下根本不可能出现——它早就在128个元素时被强制转换了。6. 生产环境调优与踩坑经验6.1 阈值设多少才合理绝大多数场景都不需要动zset-max-ziplist-entries和zset-max-ziplist-value的默认值。128和64是Redis团队压了大量真实负载调出来的平衡点超过这个区间后ziplist的写操作成本会明显抬头省下的内存可能不够补偿CPU毛刺。但在一种场景下我会考虑调大阈值key数量极多、每个Zset很小、且几乎只读不写。比如商品维度的标签分数集合每个key就几十个元素写入只发生在上架阶段后续全是读。这时候把zset-max-ziplist-entries调到512甚至1024能让更多key停留在ziplist编码省下的内存非常可观而写入阶段多出来的那点O(N)成本反正在批量导入时才发生可以接受。反过来如果你的写入QPS很高而且元素长度参差不齐我建议保持默认值甚至稍微调小避免元素一多就在临界区反复触发转换。6.2 大key与范围操作的性能教训开头说我压测时遇到插入耗时突然涨了一个量级的case根因就是某个排行榜key的成员数长期在几十万规模用的skiplist编码没毛病但当时是Redis 5.0Zset底层有一层ziplist转skiplist的临界点而我的写入模式恰好让这个key经常在128个元素附近震荡每次震荡都触发一次O(N)重建。定位方法很简单开启SLOWLOG看到大量耗时超过50ms的ZADD都指向同一个key再DEBUG OBJECT看编码变化次数和空转时长就锁定问题了。后来我把批量写入改成先删key再一次性ZADD导入让Zset直接落在skiplist编码不再反复横跳问题立刻消失。这里要专门提醒一句别拿大key直接执行DEL。一个几百万成员的ZsetDEL本身要遍历所有节点释放内存会阻塞Redis主线程我就是因为这个吃过亏。正确做法是先用UNLINK异步删除Redis会把释放内存的动作丢给后台线程处理。6.3 几个容易被忽略的细节ZINCRBY这类命令虽然在语义上是“原地增量”但底层如果发生编码转换同样要重建结构耗时可能比想象中高很多高并发下要留意。skiplist编码下dict里存的是score的double值不是指针。如果有大量成员频繁修改分数哈希表value在不断覆盖内存分配和释放也会成为隐形开销。Redis 7.0之后老的ziplist数据在第一次写入时会被转换为listpack所以升级后注意观察INFO memory里的碎片率和瞬时CPU转换动作集中在升级后的首次访问上最好提前在低峰期roll。监控上我习惯加一条OBJECT ENCODING从ziplist变成skiplist的key数量变化曲线。如果大量小key在同一时间点集体转换说明要么是业务成员数突然涨了要么是有超长字符串被写进去了这两件事都值得立刻跟。6.4 如果你在做Redis 7.0的容量规划最后给个新版本的补充。Redis 7.0的listpack和之前的ziplist在Zset上表现得几乎一样但listpack单个entry的最大长度限制更大编码切换阈值语义上略有变化。做容量规划时不要拿老版本的MEMORY USAGE数据直接套新版本至少要有一次线上对比采样的过程。我自己在新版本上观察到的经验是listpack编码的内存通常比同规模的ziplist高2%到4%换来的是彻底告别级联更新这个买卖划算。还有一点如果你用了Redis 7.0的CONFIG SET动态调整listpack阈值要注意当前已有的大key不会被重新转换配置只对新建的Zset和后续写入触发转换时生效。想验证调整效果就造一批新key实测别盯着老key看。