Redis ZSet 为什么选择跳表？排行榜背后的实现原理

ZSet 要同时满足两件事按 score 排序取范围和按 member 查 score。单靠一种结构做不到两件事都快。要按 score 排序得用有序结构要按 member O(1) 查得用哈希表。Redis 没有硬凑成一种而是两个都用一个跳表负责排序和范围一个dict负责 member 到 score 的映射。元素少的时候还有第三种形态一个 listpack 全搞定。所以 ZSet 也有两种编码listpack和skiplist。跳表跳表skip list是一摞链表叠起来。最底层是一条完整的有序链表往上一层是下一层的抽样每层节点数减半最上面几层只剩几个节点查找从最高层开始往右走。下一个节点的值比目标大或者到 NULL 了就下降一层继续往右比目标小就继续往右走。拿上面这个表找 5 走一遍L3: head 的 forward 是 77 5下降 L2: head 的 forward 是 44 5走到 4 4 的 forward 是 77 5下降 L1: 从 4 往右forward 是 5命中这个例子的节点太少看不出快在哪。节点一多差别就出来了最高层一步能跨过一大片节点每下降一层把范围缩小一截期望查找次数是 O(log n)和二分差不多。层高是随机的跳表每一层的节点是随机抽出来的。新插一个节点时它有几层是随机决定的先定 1 层然后每次有 1/4 的概率再加一层加到 32 层封顶。#defineZSKIPLIST_MAXLEVEL32// 最大层数#defineZSKIPLIST_P0.25// 升层的概率P 0.25表示每升一层的概率是四分之一平均下来的层数是1 / (1 - 0.25) 1.33也就是每个节点平均带 1.33 个前进指针内存开销不算大。为什么要随机不搞成严格二分因为严格二分需要维持结构平衡插入删除就得重新调整。随机层高让跳表在概率意义上保持平衡插入删除只要改几个指针不用做任何重新平衡的动作。这是跳表比平衡树简单的地方。节点的构成typedefstructzskiplistNode{sds ele;// member就是 ZADD 里的成员doublescore;// 分值structzskiplistNode*backward;// 后退指针只有一层structzskiplistLevel{structzskiplistNode*forward;// 每一层的前进指针unsignedlongspan;// 到下一个节点跨过了多少个底层节点}level[];}zskiplistNode;level是柔性数组长度就是随机出来的层数。每一层除了forward指针还带一个span。span是这一层从当前节点走到下一个节点沿途跨过了多少个最底层的节点。有了它在找路的时候顺手累加就能算出当前节点排第几。ZRANK就是靠span做到的。查一个 member 的排名时沿着跳表往下走每往右走一步就把那个节点的span加到计数里走到底就得到了排名全程 O(log n)不用遍历整个集合。span是为了让跳表除了能按分值找元素还能回答排第几。没有它ZRANK就只能从表头一个一个数过去变成 O(n)。哈希表配合跳表跳表按 score 排序但给定一个 member 去跳表里找它的 score得从头顺着跳ZSCORE会变成 O(log n)。所以 ZSet 同时挂了一个dicttypedefstructzset{dict*dict;// member → scoreO(1) 查zskiplist*zsl;// 按 score 排序}zset;两个结构里的 member 是同一份sds通过指针共享不复制内容只多花一个指针的存储。不同的命令走不同的结构命令走哪个复杂度ZSCORE、ZINCRBY的查找dictO(1)ZRANGE、ZREVRANGE、ZRANGEBYSCORE跳表O(log n M)M 是返回的元素数ZRANK、ZREVRANK跳表用 spanO(log n)ZADD、ZREM两个都改O(log n)写入类的命令要同时维护两个结构ZADD一个新 member得往dict里加一条映射同时往跳表里按 score 位置插一个节点ZREM要两边都删。所以这些是 O(log n)跳表那一侧是瓶颈。这里有个细节range 命令拿到的元素顺序是跳表的顺序但返回的真实数据member是跟dict共享的那份两边不会对不上。listpack 编码元素少的时候ZSet 不用跳表直接用一个 listpack127.0.0.1:6379ZADD rank90tom85jerry(integer)2127.0.0.1:6379OBJECT ENCODING ranklistpacklistpack 里元素按 score 从小到大排好member 和它对应的 score 相邻存大概长这样[ tom | 90 | jerry | 85 ]小集合上用 listpack 的理由和别的类型一样元素就几个从头线性扫一遍也不慢还省掉了跳表每个节点的指针、span、dict那一堆开销。切换条件是默认的老两组数元素数 zset-max-listpack-entries( 默认 128 ) 且 每个 member zset-max-listpack-value( 默认 64 字节 ) → listpack 否则 → skiplist注意listpack和skiplist之间是互斥的二选一不像 Hash 那样hashtable底下还藏着一个dict——ZSet 的skiplist编码本身就包含了跳表加dict两个结构。转换同样是单向的一旦成了skiplist就不会退回 listpack。和平衡树的取舍为什么不用平衡树红黑树、AVL是常见的问题。按能力对比两种结构其实打平维度跳表平衡树单点查找O(log n)O(log n)范围查询O(log n)O(log n)插入删除改指针改指针 旋转/变色实现复杂度低高概率性是期望值否确定性功能上跳表没有比平衡树强性能上也都是 O(log n)。Redis 选跳表理由是实现简单。平衡树的插入删除要维护平衡红黑树有一整套旋转和变色的规则代码长边界情况多出了问题不好查。跳表的插入删除就是顺着找路改几个指针层高随机生成不用任何重新平衡的逻辑代码短得多。antirez 在实现 ZSet 的时候明确说过跳表实现起来简单而且做范围查询ZRANGEBYSCORE这类比平衡树更直接。还有一个次要的优势是范围查询的缓存局部性。跳表最底层是一条链表按顺序遍历就是顺着forward走平衡树做一个范围查询要在树上中序遍历跳来跳去。不过这个理由在 Redis 里不占主要位置。内存上跳表不占便宜。每个节点平均 1.33 个前进指针加上span比平衡树每个节点两个子指针的开销还大一点。所以内存不是选它的原因简单才是。排行榜ZSet 最经典的用法就是排行榜因为 score 排序和 member 去重它天然都有。# 三个玩家分数 90 / 85 / 95ZADD rank90tom85jerry95spike# 取分数最高的 10 个带分数从高到低ZREVRANGE rank09WITHSCORES# spike 95# tom 90# jerry 85# 查某个人的排名从 0 开始ZREVRANK rank tom# 1# 给某人加分ZINCRBY rank5tom# 95# 取分数在 90 到 100 之间的ZRANGEBYSCORE rank90100ZREVRANGE是按 score 从大到小ZRANGE是从小到大排行榜一般用前者。分页就是改下标第二页ZREVRANGE rank 10 19。分数相同时的排序规则要留意。ZSet 在 score 相等时按 member 的字典序排不是按写入顺序。如果排行榜需要同分先到先得光靠 score 不够得把时间戳编进 score 里比如score 分数 * 10^10 - 时间戳用低位的精度存先后。延时队列也是同一个套路把 score 当成到期时间戳ZADD delay1735689600order:123# 取出所有到期的任务ZRANGEBYSCORE delay01735689600LIMIT01LIMIT 0 1只取一个取出来处理掉再ZREM。跳表和dict一起撑着这个结构所以按时间找和按任务 ID 删都快。ZSet 也被 GEO 借去用了GEOADD出来的 keyTYPE是zset底层就是跳表score 是经纬度编码成的一个整数见 《签到、UV、附近的人》。