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

背景

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

外围需要

  • 能取得间断的局部的榜单：比方前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:30user=user2；score=100；time=2022-12-15 13:30:35

而存储时将time+user作为member：

member=2022-12-15 13:30:30_user1；score=100member=2022-12-15 13:30:35_user2；score=100

这样就借助了member来实现了工夫维度的排序。

  • 长处: 从计划上说实现也比较简单
  • 毛病：在保护上仍旧须要另一个构造来辅助映射用户以后工夫（比方hash），否则获取用户排行信息的时候无奈确定member的值；同时每次批改用户分值时必须管制并发和原子操作删除原member和增加新member
思路3：拆/合score

后面还提到score的存储类型是double，也就是说有很多位（不论二进制位也好、十进制位也好），而数字的比拟是高位相等时以低位来决定后果，这不是跟多维度排序的需要一样吗？那如果我把这么多位拆成两局部别离代表分值和工夫，存储时计算合并呢？

比方（以十进制位举例）原始数据是这样：

user=user1；score=100；time=3092user=user2；score=100；time=3093

而存储时将score+time作为score（当然这样工夫维度是程序反了，用一个大数去减就能够把程序带回来）：

member=user1；score=1003092member=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