文档章节

想知道谁是你的最佳用户?基于Redis实现排行榜周期榜与最近N期榜

腾讯云开发者社区
 腾讯云开发者社区
发布于 2018/12/13 18:09
字数 2432
阅读 44
收藏 0

【推荐】2019 Java 开发者跳槽指南.pdf(吐血整理) >>>

本文由云+社区发表

前言

业务已基于Redis实现了一个高可用的排行榜服务,长期以来相安无事。有一天,产品说:我要一个按周排名的排行榜,以反映本周内用户的活跃情况。于是周榜(按周重置更新的榜单)诞生了。为了满足产品多变的需求,我们一并实现了小时榜、日榜、周榜、月榜几种周期榜。本以为可长治久安了,又有一天,产品体验业务后说:我想要一个最近7天榜,反映最近一段时间的用户活跃情况,不想让历史的高分用户长期占据榜首,可否?于是,滚动榜(最近N期榜)的需求诞生了。

周期榜

周期榜实现还是很容易的,给每个周期算出一个序号,作为榜单名后缀,进入新的周期自然切换读写新榜单,平滑过度。以日榜为例,根据时间戳ts计算每日序号s=ts/86400,以日序号s作为后缀即可实现零点后自动读写新日榜。小时榜与此雷同,不再赘述。

对于周榜,可以选定某一个周一(或周日,看需求)的时间戳为基准,计算基准到当前经过的周数为周序号,以此作为榜单后缀。

对于月榜,稍有不同,因为月份天数不固定,所以不能按照上述方法计算。但我们可以根据时间戳取得年、月信息,以年月做标志(如201810)后缀,即可实现月榜。

滚动榜

方案探讨

滚动榜需要考虑多个周期榜数据的聚合与自动迭代更新,实现起来就没那么容易了。下面分析几个方案。

方案1:每日一个滚动榜,当日离线补齐数据

还以日榜为例,最近N天榜就是把前N-1天到当天的每一个日榜榜单累加即可,比如最近7天榜,就是前6天到当天的每一个日榜中相同元素数据累加。因此,最直观的一个方案是:首先记录每天的排行榜R,那么第i天的最近N天榜Si=∑N−1n=0Ri−n,其中,Ri−x表示第i天的前x天的日榜。实现上,可以每日生成一个滚动榜S和当天日榜R,加分时同时写入S和R,每日零点后跑工具将前N-1天数据累加写入当日滚动榜S。

这个方案的优点是直观,实现简单。但缺点也很明显,一是每日一个滚动榜,消耗内存较多;二是数据更新不实时,需要等待离线作业完成累加后S中的数据才完全正确;三是时间复杂度高,7天榜还好,只需要读过去6天数据,如果是100天榜,该方案需要读过去99天榜,显然不可接受。

方案2:全局一个滚动榜,当日离线补齐数据

基于方案1,如果业务无需查询历史的S,可以只使用全局一个S,无需每日创建一个Si。加分操作还是同时加当日的Ri和全局唯一的S,但每日零点的离线作业改为从S中减去Ri−(N−1)的数据(即将最早一天的数据淘汰,从而实现S的计数滚动)。

此方案减少了内存使用,同时离线任务每次只需读取一个日榜做减法,时间复杂度为O(1);但仍需要离线作业完成才能保证数据正确性,还是无法做到平滑过渡。

方案3:每日一个滚动榜,实时更新

要做到每日零点后榜单实时生效,而不需要等待离线作业的完成,一种方案是预写未来的榜单。不难得出,当日分数会计入往后N-1天的滚动榜中。因此,可以写当天的滚动榜Si的同时,写往后N-1天的榜单Si+1到Si+N−1。

该方案不仅能脱离离线作业做到实时更新,且可以省略每天的日榜。但缺点也不难看出,对于7天滚动榜,每次写操作需要更新7个榜单,写入量小时还勉强能接受,如果写操作量大或者需要的是30天、60天滚动榜,此方案可行性几乎为零。

方案4:实时更新,常数次写操作

有不有办法做到既能实时更新,写榜数量也不随N的增加而增加呢?不难看出,第i天滚动榜Si=∑N−1n=0Ri−n,而第i+1天的滚动榜Si+1=∑N−1n=0R(i+1)−n=∑N−2n=0Ri−n+Ri+1。显然,Si+1=Si−Ri−(N−1)+Ri+1。由于Ri+1在刚达到零点时必然为空且可以在次日实时加到Si+1上,因此如果我们能提前准备好Si−Ri−(N−1)这部分数据,那么在零点进入i+1天后,Ri+1自然就是可用状态了。

以3天滚动榜为例,次日滚动榜初始态为当日滚动榜减去n-2天的日榜数据。
     +-------------------------------------------+
     |                                           |
+----+---+   +--------+   +--------+             |
|        |   |        |   |        |             |
| R(i-2) |   | R(i-1) |   |  R(i)  |             |
|        |   |        |   |        |             |
+----+---+   +----+---+   +---+----+             |
     |            |           |                  |
     |            |           |                  |
     |            |           |                  |
     |            |           v+                 v-
     |            |
     |            |    +  +--------+        +--------+
     |            +-----> |        |     +  |        |
     |                 +  |  S(i)  | +---+> | S(i+1) |
     +-----------------+> |        |        |        |
                          +--------+        +--------+

那么,如何提前准备好Si−Ri−(N−1)这部分数据呢?可以如下处理:

  • 对一个元素加分时,加当日周期榜Ri、滚动榜Si;还需根据其在今日滚动榜中的分数s、及n-1天日榜中的分数r,计算出其在明日滚动榜中的初始分数s-r写入明日滚动榜中;即3个写操作;
  • 如果一个元素在当日没有任何加分操作,那么不会触发写入初始分数操作,所以还需要一个离线工具补齐。与方案1、2不同的是,该离线工具可提前一天运行,即当日运行离线工具补齐次日的滚动榜数据即可。

简而言之:第一步是运行离线工具生成次日的滚动榜;第二步是在写操作时同时更新次日的滚动榜。

该方案也是每日一个滚动榜。相对方案3而言,是空间换时间。如果空间不足且无保留历史的需求,可在离线工具中清理历史数据。

                                +--------------+
                                |              |
                                |   AddScore   |
                                |              |
                                +-+----+-----+-+
                                  |    |     |
                                  v    |     |
+--------+   +--------+   +-------++   |     |
|        |   |        |   |        |   |     |
| R(i-2) |   | R(i-1) |   |  R(i)  |   |     |
|        |   |        |   |        |   |     |
+--------+   +--------+   +--------+   |     |
                                       |     v
                          +--------+   |    ++-------+
                          |        |   |    |        |
                          |  S(i)  +<--+    | S(i+1) |
                          |        |        |        |
                          +--------+        +----+---+
                                                 ^
                                                 |
                                                 |
                                          +------+-----+
                                          |            |
                                          |    Tool    |
                                          |            |
                                          +------------+

方案4的实现

以下是实现参考。此处仅列出核心的lua脚本。Redis命令调用脚本的参数定义为:

eval script 4 当日日榜key 当日滚动榜key 即将淘汰的日榜key 明日滚动榜key 榜单元素名 加分数

lua脚本script如下:

--加今日日榜分数
redis.call('ZINCRBY', KEYS[1], ARGV[2], ARGV[1])

--加今日滚动榜分数
local rs = redis.call('ZINCRBY', KEYS[2], ARGV[2], ARGV[1])
local curRoundScore = 0
if (rs) then
    curRoundScore = tonumber(rs)
end

--取即将淘汰的日榜分数
rs = redis.call('ZSCORE', KEYS[3], ARGV[1])
local oldCycleScore = 0
if (rs) then
    oldCycleScore = tonumber(rs)
end

--计算次日滚动榜初始分数
local nextRoundScore = curRoundScore - oldCycleScore
if nextRoundScore < 0 then
    nextRoundScore = 0
end

--设置次日滚动榜分数
redis.call('ZADD', KEYS[4], nextRoundScore, ARGV[1])

--返回今日分数
rs = redis.call('ZREVRANK', KEYS[2], ARGV[1])
return {curRoundScore, rs}

关于榜单key计算准确度的探讨 我们的业务是在排行榜接入层逻辑中计算榜单后缀的,这种方案对逻辑层多台机器的时间一致性要求较高,如果逻辑层服务器时钟不一致,可能在时间切换点上出现不同机器读写不同榜单的问题。如果业务对时间精确度要求严格,可以考虑通过lua脚步在redis端计算后缀。

.

关于内存容量限制的探讨 基于ZSet实现的排行榜,每个元素约需要100字节内存。如果榜单长度为1000万,则每个榜单约需要1G内存。滚动榜的计算需要每日保留一个日榜,如果滚动周期较长,则可能单机内存容量不足以容纳所有需要的榜单。 考虑到历史日榜数据是不会变更的,因此不在lua脚本中读取历史日榜数据也无一致性问题。故可以将榜单打散到多个Redis实例,在接入层做逻辑读取历史日榜的分数,再以参数形式传入给lua脚本处理。

总结

在榜单长度不大且并发量不高的场景下,使用关系数据库+Cache的方案实现排行榜有更高的灵活性。而在海量数据与高并发的场景下,Redis是一个更好的选择。本文基于Redis实现的滚动榜,不论滚动周期多长,都只需要常数(3)次数的写操作,有较好的性能和可扩展性。且通过离线+在线的双预生成机制,确保了榜单实时生效,可用性较强。

此文已由作者授权腾讯云+社区发布


© 著作权归作者所有

腾讯云开发者社区
粉丝 184
博文 250
码字总数 668695
作品 0
深圳
私信 提问
使用 Redis 实现排行榜功能

排行榜功能是一个很普遍的需求。使用 Redis 中有序集合的特性来实现排行榜是又好又快的选择。 一般排行榜都是有实效性的,比如“用户积分榜”。如果没有实效性一直按照总榜来排,可能榜首总是...

Mr_Jing
09/29
0
0
SpringBoot应用篇之借助Redis实现排行榜功能

更多Spring文章,欢迎点击 一灰灰Blog-Spring专题 在一些游戏和活动中,当涉及到社交元素的时候,排行榜可以说是一个很常见的需求场景了,就我们通常见到的排行榜而言,会提供以下基本功能 ...

小灰灰Blog
2018/12/25
531
0
榜单 | 《我和我的祖国》、百因必有果热歌热词刷爆网络 - 知乎

【直观大数据·短视频达人榜】第八期数据(2019.09.24-09.30)显示,@小阿七凭借活动路演,上传多首抖音热歌,如《那女孩对我说》、《信仰》等,获得大量点赞和关注粉丝。前者获赞达到335.3...

透过数据谈谈当下直播
10/21
0
0
榜单 | 国庆阅兵、女兵方队,遥遥领跑各类短视频排行榜 - 知乎

▼ 【直观大数据·短视频达人榜】第九期数据(2019.09.30-10.06)显示,@人民日报、@人民网、@央视新闻凭借国庆70周年阅兵、女兵方阵、各类优秀国家英烈楷模事迹等,获得最高点赞和粉丝增长数...

透过数据谈谈当下直播
10/21
0
0
用户反映的热搜问题

我想知道每个第一的位置是谁。当前的点进去之后,有个很棒的功能,就是看持续时间,这个很好,但是我除了这个,还想知道这个热搜词的获益者是谁。热搜其实大部分都是刷的,所以某个词,上来后...

风中的矿泉水
2016/08/10
3
0

没有更多内容

加载失败,请刷新页面

加载更多

阿里云视频云正式支持AV1编码格式 为视频编码服务降本提效

今天我们要说的 AV1 可不是我们平时说的 .AVI 文件格式,它是由AOM(Alliance for Open Media,开放媒体联盟)制定的一个开源、免版权费的视频编码格式,可以解决H.265昂贵的专利费用和复杂的...

一肥仔
22分钟前
8
0
软件缺陷静态分析 CodeSonar 5.2 新版发布

对于使用C和C++构建安全关键软件的开发团队而言,CodeSonar一直是首选的静态分析解决方案。在近期发行的版本中,CodeSonar通过使用开放标准来扩展其语言覆盖范围,并增加了对Java、C#、Obj...

旋极科技
23分钟前
5
0
数据迁移

1. insert into values 或 insert into select批量插入时,都满足事务的原子性与一致性,但要注意insert into select的加锁问题。 2. replace into与insert into on duplicate key update都可...

qiang123
30分钟前
6
0
Linux装Windows系统后还不会激活?3招教你搞定

     相信大家已经发现荣耀MagicBook科技尝鲜版有多“香”了,不但可以轻松的将Linux系统装回Windows系统,还足足省下了300大洋!但是装回系统就万事大吉了吗?NoNoNo,我们还需要去激活...

梅丽莎好
32分钟前
6
0
Tomcat8源码分析-请求处理过程

上一篇:Tomcat8源码分析-启动流程-start方法 此篇主要讲Tomcat8从接收请求到处理请求的时序图画出来,并用文字描述一下主要流程 时序图 说明 文字描述流程之前先提示如下两点: 1.Acceptor...

特拉仔
34分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部