带老弟做个实时排行榜

阿巴可懂的实时排行榜系统设计和实现思路。

大家好,我是鱼皮,暑假快到了,我的老弟小阿巴听说我家有很多好康的,就跑来找我玩。

结果我摆出了几个以前开发过的小系统,准备在这段时间带着小阿巴多做些作品,学习编程项目的设计思路。这样等他开学了,就可以更轻松地跟着老师做做项目了。

今天,就先带他做一个很常见的小功能:用户实时积分排行榜。

实时积分排行榜

需求

先描述下需求,在我的编程导航项目(//www.code-nav.cn)中,为了鼓励大家共同维护网站,用户可以通过推荐资源、积极评论、举报违规资源等方式获取积分。

为了进一步激励大家,网站需要提供一个用户积分排行榜,分为 实时总积分榜周榜月榜,均 只取前 10 名 。所有用户都能够查看当前排行榜,以及查看自己的 实时 总积分排名,后续管理员就可以给上榜用户颁发奖品了。

效果如下图:

点击 我的排名 按钮,可以查看自己的实时排名:

本文篇幅有限,先仅讨论 实时总积分榜 的设计实现。

听了需求后,小阿巴爽朗一笑:这有啥难的?且让我设计一波,再给你娓娓道来。

设计实现

先看下数据库的结构,总共有 2 个表:用户表用户积分表

用户表存储了用户信息,以及用户的总积分(实时更新),也就是说总积分榜需要的数据可以直接从这里取到,不需要再去计算。

用户表内容:

用户 id 用户名 积分(score)
1 小阿巴 10
2 李鱼皮 1000
3 小李 100
……
100 李老热 66

如果要取前 10 名,只需要把所有用户的信息先取出来,再排个序就好啦,写 SQL 语句查询的话就是:

select * from `user` order by score;

然后如果要取自己的总排名,就对查到的有序数据进行一次遍历,找到自己所在的位置下标就行,伪代码如下:

// 从数据库查询全部用户列表
list = getAllDataList()
for(i = 0; i < total; i++) {
  // 找到自己的位置
  if(list[i].id == '我的id') {
    return i + 1;
  }
}

小阿巴得意到:这不就实现总积分榜了么?你这需求太简单,啧啧。

我笑到:还不错,总积分榜的思路是正确的,起码知道要对所有的数据进行排序。但如果用户数特别多呢?比如几十万个,你只需要查自己的总排名,还需要把全部的数据都做一个排序么?

小阿巴陷入沉思,想了半天,没想出来。

于是我提示到:假如在一次考试中你想知道自己的排名,是不是只需要知道有多少人的分数比自己高就行了,不用去管其他人排第几对吧?

小阿巴一拍脑袋:对啊,我只需要先查出自己的分数,然后统计分数大于我的用户数量,不就知道自己的排名了?

先用 SQL 语句查出用户的分数:

/* 只取需要的列 */
select score as myScore
from `user`
where id = "用户 id";

然后再用 SQL 语句统计分数大于该用户分数的数量:

select count(*) from `user`
where score > myScore;

最后只需要将该查询结果加 1,就是自己的排名啦~

小阿巴感叹到:原来转换一点点思路,就能省去多余的排序带来的性能开销,起飞~

更多思考

鱼皮:先别起飞,其实对于一般用户量的系统,上面的方案就已经足够了。下面让我们加大难度,假如用户数再多一点点呢,比如说一亿个,怎么实时获取前 10 名呢?

小阿巴:还真是 “亿点点”,就您那破编程导航还想着有一亿个用户?

鱼皮:少废话,梦想还是要有的,万一有亿个用户呢?快想想系统怎么做!

小阿巴:且不说对一亿个数据排序有多慢,能不能存的下都是个问题啊。。。啊,等等,这难道就是面试常见的 Top N 问题!

鱼皮:不错,我面试的时候被问过好几次 Top N 问题,如何从海量数据中找出前 N 个数呢?

小阿巴:这我完全不懂啊,算法不会,真要命。

鱼皮:其实 Top N 问题的核心在于保证空间和时间复杂度,先要考虑数据能存入内存运算,在怎样算得更快。

通常 Top N 问题有下列几种解决方案。

Top N 解决方案

全部排序

直接对所有数据进行排序(快排等),缺点是需要将数据一次性加载到内存中。

局部淘汰

内存中维护一个大小为 N 的容器,再让剩余的数一个个进入容器,并淘汰容器内的最小值。最终容器内剩下的数就是前 N 名。优点是能节省内存,缺点是太慢了。

分治

把数据分为多个小组,小组内先分别选出前 N 名小组长,最后再让这些小组长同台竞技,选出最终的前 N 名。

哈希预处理

假如数据重复度很高,可以通过 hash 的方式,去掉很多重复数据。比如 1 亿个数据里,一半是 0,一半是 1,那么取前 10 名时,可以直接淘汰掉另一半为 0 的数据。

但是预处理本身也需要时间和空间,这就需要我们对数据的重复度有一个清晰的判断,否则自作聪明、适得其反。

小根堆

面试算法中的高频考点 —— 堆排序,可以先取前 N 个数组成小根堆,堆顶始终是最小值。 然后遍历后续数字,大于堆顶就替换掉堆顶并调整最小堆结构。该算法时间复杂度和空间复杂度(为 N,常数)都不错,所以必须要掌握。

小根堆

但是具体选择哪种方案呢?还是要结合我们实际的项目和业务场景来分析。

实际解决

由于我们的数据库来记录积分,所以当用户量级很大时,首先要 分库分表 ,通常是水平分表,根据一定规则(比如 id)把用户数据行分批存储在多个数据表中。

分表

然后就和大数据 Map / Reduce 处理机制一样了,可以采用 分治 的方式 并行计算 每个表的前 10 名(map),都计算好后,再汇总到一起计算最终的前 10 名(reduce)。

一次大数据并行处理过程

用这种方式,别说 1 亿了,2 亿、3 亿的计算模式都是一样的,加机器水平扩容就好了~

所以遇到 Top N 问题的时候,大家可以先答一下上面的几种方案,再结合具体的场景分析,分治和最小堆是我觉得相对 核心 的点。

Redis

最后,对于实时排行榜的设计,肯定很多背过八股文面试题的朋友在第一时间会想到使用 Redis 的有序集合 zset,的确也是一种方案,但也要结合场景去分析利弊,不要秒答。

使用基于内存的 Redis zset 的确运算更快,且天然支持排序、使用方便。但数据量大时同样面临数据更新、维护、同步、持久化存储等问题,而且对于我们这种实时性要求不高的需求来说,有些大材小用了哈哈。

zset 数据结构


我是鱼皮,肝文不易,点赞 还是要求一下的,祝大家都能心想事成、发大财、行大运。

最后再送大家一些 帮助我拿到大厂 offer 的学习资源 ,视频教程 + 习题 + 答案 + 源码、编程书籍、大厂面经、实战项目等。

指路:跑了,留下 6T 的资源!

我是如何从零开始通过自学,拿到腾讯、字节等大厂 offer 的,可以看这篇文章,不再迷茫!

指路:我学计算机的四年,共勉!