排行榜系统设计

系统设计
,

为啥需要排行榜

推荐系统有一个避不开的问题就是冷启动问题。也就是新用户第一次进入应用的推荐，此时我们没有任何的用户行为信息，无法根据用户行为进行推荐， 根据用户基础信息的推荐也极有可能没有构建完成或者因为基础数据不完善导致效果不够好。

此时就需要一种针对所有用户通用的推荐策略，防止推荐系统出现“开天窗” 。我们一般使用以下策略来处理冷启动问题

  1. 最新内容：平台的最近发布的比较新鲜的资源
  2. 热门内容：平台上最近一段时间发布的比较热门的资源
  3. 实时基于用户属性进行分群，基于用户群进行推荐（比如，上海地区用户，女性用户，30-40岁用户）

其中的热门内容就需要排行榜系统的支持

排行榜系统

排行榜系统一般有两种， 一种是类似于“本月最火歌曲排行”或者“第N期XXX排行”之类的以自然月为统计维度的，另一种是“最近30天最火歌曲排行”之类的动态时间范围的排行榜

固定时间范围的排行榜

需求：统计本月播放次数最多的歌曲

针对“本月最火歌曲”这种需求的排行榜，处理起来相对简单

只要统计从本月从1号到现在的所有歌曲的播放数据就可以了，如果数据量不大且要求不高，可以定时每一段时间计算一次， 计算方法如下

1
select count(id) from play_record where play_time > "2019-05-01" group by itemid;

如果实时性要求较高， 也可以使用基于事件的实时增量统计的方式，同时每天处理一次批量统计，做数据矫正。

1
(add-score video_10086_play_times 1)

具体就是每天计算一个排行榜之后， 使用流处理系统，当有新的播放事件，在榜单现有基础上做incr操作即可

这种排行榜相对来说实现比较简单， 缺点也很明显

比如今天如果是本月的1号， 那你的排行榜数据就由于样本数据有限，误差较大，无法起到排行榜真正的作用

处理这种问题就需要“最近30天最火的歌曲”这种滚动排行榜

滚动排行榜

滚动排行榜是指基于最近一段时间范围的数据获得的排行榜统计结果

拿最近3天排行榜为例， 假设现在是是10号的10点钟， 那滚动排行榜覆盖的区间就是前推3天的数据

7号从10点以后的数据 + 8，9号全天数据 + 10号截至目前的数据 的统计结果

滚动排行榜相对来说难度增加了很多

如果数据量不大，对实时性要求不高的话， 也可以采用每一段时间计算一次最近3天的播放量的批量的方式

但是如果数据量较大或者对实时性有要求较高，那就需要设计一个更好的实时方案

实时的滚动排行榜

假如我要做3天的滚动歌曲榜单， 我就需要获取最近72小时的播放记录进行统计，拿数据举例来说

假设有如下的播放记录, 当前日期是 2019-04-04 13:00， 排行榜统计区间应该是 04-01 13:00 ～ 04-04 13:00

歌曲id 播放时间
1009 2019-04-01 9:00
1010 2019-04-01 14:00
1020 2019-04-02 8:00
1089 2019-04-03 10:00
1010 2019-04-04 9:00
1023 2019-04-04 12:00

那我们获取到的3天榜单应该是这样(1009的播放记录已经过期)

1
2
3
4
5
6
7
//  歌曲id:播放次数
{
     1023:1,
     1010:2，
     1089:1，
     1020:1
}

我们设计的这套方案需要存储2类信息

  1. 第一类按固定周期维度的用户点击数据，我们称之为周期榜，其中记录每个歌曲在当前周期的播放次数，比如20190401周期榜就记录当天的所有歌曲播放次数，这个数据的生成十分简单，只要用redis的zset结构实时``i ncr`即可
  2. 另一类是我们业务要用的滚动榜单，也就是我们的目标数据

排行榜处理过程最关键的有两点

  1. 对一个元素加分时，加当日周期榜、滚动榜；
    还需根据其在今日滚动榜中的分数s、及n-1天日榜中的分数r，计算出其在明日滚动榜中的初始分数s-r写入明日滚动榜中，即3个写操作。

  2. 如果一个元素在当日没有任何加分操作，那么不会触发写入初始分数操作，所以还需要一个离线工具补齐。
    该离线工具可提前一天运行，即当日运行离线工具补齐次日的滚动榜数据即可。

R：每日的周期榜统计数据 S： 每日的滚动排行榜数据

如果S(i)-R(i) > 0 ，说明该歌曲在指定周期内有播放行为，有播放行为才进行写入操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
以3天滚动榜为例，次日滚动榜初始态为当日滚动榜减去n-2天的日榜数据。
     +-------------------------------------------+
     |                                           |
+----+---+   +--------+   +--------+             |
| R(i-2) |   | R(i-1) |   |  R(i)  |             |
+----+---+   +----+---+   +---+----+             |
     |            |           |                  |
     |            |           v+                 v-
     |            |
     |            |    +  +--------+        +--------+
     |            +-----> |        |     +  |        |
     |                 +  |  S(i)  | +---+> | S(i+1) |
     +-----------------+> |        |        |        |
                          +--------+        +--------+

分数变化
                                +--------------+
                                |   AddScore   |
                                +-+----+-----+-+
                                  |+   |     |
                                  v    |     |
+--------+   +--------+   +--------+   |     |+
| R(i-2) |   | R(i-1) |   |  R(i)  |   |     |
+--------+   +--------+   +--------+   |     |
                                       |     v
                          +--------+   |    +--------+
                          |  S(i)  |<--+    | S(i+1) |
                          +--------+        +--------+
                                                 ^
                                                 |+
                                          +------------+
                                          |    Tool    |
                                          +------------+

使用flink的滑动窗口来统计

我们可以使用kafka这种消息队列来存储最近一段时间的数据，然后使用flink的窗口进行计算
为了能处理较大的数据量，我们可以先开一个tumbling窗口对1分钟维度的数据进行计算，然后在基于1分钟的维度开sliding窗口进行数据统计，如果要统计1年之类的较长周期，那可以在1分钟的基础上再做1天的聚合数据，在1天的数据基础上进行1年的聚合分析。

这种分层聚合的方式能有效降低数据量并能支持较大的数据长度

概率模型HyperLogLog

上面我们提到基于自然时间的统计也可以通过给时间分区间对数据进行统计， 但是在某些情况下，比如统计本月的月活，小公司还好，像阿里这种公司都是数亿的日活， 这种级别的数据统计，如果采用redis的hash或者 bitmap也是一种超级大的开销。

如果在极大的数据量下可以允许一定的误差， 就可以采用HyperLogLog这种概率模型来进行日活用户这种统计

HyperLogLog能达到在极大的用户登陆记录中快速做到类似distinct的效果,比如我们有100多亿的用户登陆记录，我们想统计其中一共有多少用户，传统的方案就需要select distinct(userid) from A

基本使用

由于redis已经实现了HyperLogLog,所以我们可以直接使用redis来进行操作

1
2
3
4
$ pfadd 2020:06:active:users  user1 user2 user3 user1
1
$ pfcount 2020:06:active:users
3

也可以合并两个HyperLogLog的结果

1
2
; 将6月和5月的日活合并统计
$ pfmerge 2020:06:active:users 2020:05:active:users

基本原理

HyperLogLog是一种基于概率模型

基本原理大概是如下流程

  1. 先对要计数的值进行hash，得到一个64bit的hash结果
  2. hash结果的后14位转为10进制数字m，前50位从低到高第一个1出现的位置记为n，可知$0\leq m < 16384,1\leq n <50$
  3. 然后创造一个拥有16384个桶，每个桶有6位，一共长度为 16384 * 6的12kb的数组
  4. 将第m个桶的值置为n
  5. 查询总量时，对所有桶求调和平均值