乐趣区

关于php:Chapter-10利用Redis-Zset实现双维度排行榜

jiezi

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

背景

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

外围需要

  • 能取得间断的局部的榜单：比方前 100 名、第 300～400 名的用户以及分值
  • 能取得任意单用户信息：比方用户 A 的分值与以后排名
  • 能操作榜单单用户分值：比方为用户 A 减少 3 分
  • 上述性能要求实时
  • 分值雷同时，要求依照达到分值工夫的先后排序，先达到分值的用户排在后面
  • 分值是整数（或相似金额这种无限位小数，也能够看为整数），业务上个别高精度小数无场景意义

思考过程

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

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

Redis ZSet

底层构造与操作过程

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

相干性能状况

当初只关注上述需要用到的几个操作是否反对以及性能开销状况：

  • ZADD/ZINCRBY: O(log(N))
  • ZSCORE: O(1)
  • ZCARD: O(1)
  • ZRANGE/ZREVRANGE: O(log(N)+M)；N为有序集的基数，而 M 为后果集的基数
  • ZRANK/ZREVRANK: O(log(N))

O(log(N))的工夫复杂度实践上齐全能够扛住上亿数据的并发查问（当然并不倡议真的在生产环境这么干）。

O(log(N)+M)须要特地留神，M 是线性增长的，须要严格控制下限

一些特点

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
退出移动版