Chapter 10.利用Redis Zset实现双维度排行榜

站长

2022年12月29日 23:40 · 阅读数 16

欢迎来到「我是真的狗杂谈世界」，关注不迷路

背景

最近需要将遇到的几个排行需求点抽出来做一个独立的通用排行组件，整理记录一下。

核心需求

能获得连续的部分的榜单：比如前100名、第300～400名的用户以及分值
能获得任意单用户信息：比如用户A的分值与当前排名
能操作榜单单用户分值：比如为用户A增加3分
上述功能要求实时
分值相同时，要求按照达到分值时间的先后排序，先达到分值的用户排在前面
分值是整数（或类似金额这种有限位小数，也可以看为整数），业务上一般高精度小数无场景意义

思考过程

说白了就是排序问题，相关的算法和结构有很多了，可问题是总不能自己从零开始实现吧（也不是不可以）～～

那么在现有的存储介质上很容易想到Redis的ZSet数据类型(MySQL不是今天的主题，假装想不到咳咳)

Redis ZSet

底层结构与操作过程

ZSet数据类型的主要数据结构是跳表，具有多层级结构（因此对内存要求稍稍高一点），具体的结构和操作过程在「Tool 1.Redis捣腾系列」中继续捣腾。

一些特点

ZSet在使用上是member->score结构：

member: 被排序的标识，也是默认的第二排序维度（score相同时，redis以member的字典序排列）
score: 被排序的分值，存储类型是double

双维度问题

如果直接按照上述用法进行使用，那么只有第一排序维度score是我需要的，虽然有第二排序维度member，而需要的第二排序维度是时间。那怎么办呢？

思考技巧

我常常用来解决问题的思考技巧有：

加：加入其他模块、组件来满足需求
借：借助现有的但不满足需求的模块、组件利用转换来满足需求
合：将几个模块、组件合并起来实现一个需求，跟拆可以互相转换只是视角层次不同
拆：将一个模块、组件拆分为多个，以满足需求，跟合可以互相转换只是视角层次不同

实现思路

思路1：加结构

粗暴一点：一个ZSet只有一个score满足需求，那就同时维护两个ZSet，一个存分值一个存时间
优点：从方案上说实现比较简单
缺点：具体实现上需要同时维护两个ZSet，需要的空间略大；且对并发控制粒度要求大（读写锁+锁范围是操作两个ZSet期间）

思路2：借member

前面提到member是默认的第二排序维度，但直接使用是无法满足时间排序的需求的，那如果member的内容中涵盖了时间呢？
比如原始数据是这样：
user=user1；score=100；time=2022-12-15 13:30:30
user=user2；score=100；time=2022-12-15 13:30:35
而存储时将time+user作为member：
member=2022-12-15 13:30:30_user1；score=100
member=2022-12-15 13:30:35_user2；score=100
这样就借助了member来实现了时间维度的排序。
优点: 从方案上说实现也比较简单
缺点：在维护上仍旧需要另一个结构来辅助映射用户当前时间（比如hash），否则获取用户排行信息的时候无法确定member的值；同时每次修改用户分值时必须控制并发和原子操作删除原member和添加新member

思路3：拆/合score

前面还提到score的存储类型是double，也就是说有很多位（不管二进制位也好、十进制位也好），而数字的比较是高位相等时以低位来决定结果，这不是跟多维度排序的需求一样吗？那如果我把这么多位拆成两部分分别代表分值和时间，存储时计算合并呢？
比如（以十进制位举例）原始数据是这样：
user=user1；score=100；time=3092
user=user2；score=100；time=3093
而存储时将score+time作为score（当然这样时间维度是顺序反了，用一个大数去减就可以把顺序带回来）：
member=user1；score=1003092
member=user2；score=1003093
这样就将一个score拆成了多个存储（或者说将多个存储合存在一个score中）了。
优点：无需维护额外的结构，空间开销少；且只需要控制写锁，不会干扰读并发
缺点：score的计算相对复杂一点，且缩小了分值和时间的取值范围；另外score的可读性不那么好（取值范围和可读性在实践中进行了优化）

实践过程

细化方案

方案1：以十进制对整数位进行划分

Redis ZSet的score值在超过2^54后存储和计算会出现问题，保险起见，采用2^53最为最大整数：900719 9254740992
秒级时间戳需要10位，因此低10位由秒级时间戳填充
高6位则可以由分值填充，但分值最大为900718
优点：可读性较高
缺点：分值范围小

方案2：以二进制对整数位进行划分

仍旧是2^53作为最大整数
采用低32作为时间戳（可表示到2106-02-07 14:28:16）
剩余高21位作为分值（可表示到2097152）
优点：分值范围较方案1变大了一些（如果压缩时间戳位数，还可以再变大一倍）
缺点：可读性更差了（想象一下两个数转换成二进制后再组合成一个新的数）

方案3：利用double的浮点计算

double的有效位可以保证在15位以上
将分值作为score的整数部分
将时间戳逆向后作为score的小数部分
优点：可读性较高；利用浮点数特点，分值取值范围可以很大（起码2^53没有问题了）
缺点：也是因为浮点数特点，随着分值（整数部分）的逐渐增大，时间戳（小数部分）精度逐渐变小

选择

最后我选择了方案3，因为考虑到有分值大小和时间精度高低两个维度的指标，方案3在不同场景下的匹配度如下：

	分值小	分值大
时间精度高	匹配度高	匹配度低
时间精度低	匹配度高	匹配度高

根据上表，业务业务需要：

对于分值上限小（百万级别以下）的业务场景，方案3可以保障时间高精度
对于分值上限高（千万级别以上）的业务场景，分值往往是从小累计到大的且在小分值时竞争激烈（容易出现同分多，达到同分的时间间隔小的情况）大分值时则不激烈，采用方案3可以在分值较小时仍旧保障时间高精度，分值大时一般对时间精度要求也低了
另外还可以根据业务来收缩时间戳（小数部分）的范围来扩大秒级时间精度下的分值（整数部分）范围

DEMO

// lock acquire

// 计算分值部分
$nowScore = $redis->zScore($key, $member);
$setScore = $addScore + intval($nowScore);

// 计算时间戳部分（可做到百万级别分值仍旧保持秒级时间戳精度，还可以继续优化这块提升分值上限）
$maxTime = 4102415999; // 2099-12-31 23:59:59
$nowTime = $maxTime - time();
$timeScore = bcdiv($nowTime, $maxTime, 10);
$finalScore = bcadd($setScore, $timeScore, 10);

// 设置
$redis->zAdd($key, $finalScore, $member);

// lock release