这是 why 哥的第 89 篇原创文章

前两天，有一个读者给我发了一张图片。

我问：发什么肾么事了？

于是有了这样的对话：

.png)

他发的图，就是微信静止步数排行榜的截图：

其实扯了这么多，这就是个常见的面试场景题：如何设计一个排行榜？

这个题吧，其实就是考你面试筹备范畴的广度，见过就会答，没见过 … 就难说了。

当然，如果你在理论业务中做过排行榜，那么这题正中下怀，你也不要笑出声来，场景题面试官是会给你思考工夫的。

所以你不要张口就来，你只须要眉头稍稍一皱，给面试官说：这题我想想啊。

而后略微组织一下语言，说进去就行。

这次的文章，就带着大家剖析一下“排行榜”这个场景题，到底应该怎么做。

基于数据库

这个题，如果是真的之前没有遇见过，可能最容易进入大家视线的就是平时接触的最多的数据库了。

因为一想到“排行榜”，就想到了 order by。

一想了 order by，就想到了数据库。

一想到了数据库 …

兄弟，你路就走窄了。

尽管我已经就基于 MySQL 做过排行榜，因为过后是为了一个较量长期搭建的服务，基本就没有引入 Redis。我评估了一下搭建 Redis 的工夫和用 MySQL 间接开发的工夫。

于是抉择了 MySQL。

而让我抉择 MySQL 的根本原因还是我曾经晓得进入决赛的队伍只有 10 支，也就是说我的排行榜表外面从始至终也只有 10 条数据。

选手提交代码之后，零碎实时算分，而后更新排行榜表。

而后接口返回给前端页面上面这些数据，而上面这些数据都在一个表外面：

• 队伍依照历史最高分数排名
• 队伍名称
• 历史最高分数
• 最近一次提交得分
• 最近一次提交工夫

前端每隔一分钟调用我的接口，雷同分数，名次雷同，所以我在接口外面用一条比较复杂的 sql 去查询数据库，下面的这些字段就都有了。

你看，排行榜的确是能够用 MySQL 来做的。

不肯定非得上 Redis，记住一句话：脱离业务场景的方案设计，都是耍流氓。

然而这玩意和“万物皆对象”一样，别对着面试官说，这肯定不是面试官想要听到的答案。

或者说，这只是想要听到的一部分答复。

这个答复能用的起因是我给了一个具体的场景，用户量十分的小，怎么玩都能够。

甚至咱们不借助 MySQL 的排序，把数据查出来，在内存外面排序都能够。

然而如果，这是一个游戏排行榜，随着游戏玩家的减少，达到千万用户级别的话，这个计划必定是不行了。

当然，兴许你会给我扯什么查问慢就加索引，数据量大就分库分表的计划。

怎么说呢，下面这句话是没有错的。

然而一旦数据量大起来了，这个计划其实就不是一个特地好的计划。

这问题，得从根上治理。

基于 Redis

这个场景其实就是在考查你对于 Redis 的 sorted set 数据结构的把握。

sorted set，见名知意，就是有序汇合的意思。

在 Redis 中它大略是长这样的：

后面的 sport:ranking:20210227 是 Redis 中的 key。

value 是一个汇合，且能够看出这个汇合是有序的。汇合中的每一个 member 都有一个 score，而后依照这个 score 进行降序排序。

须要留神的是，图片中的 score/member 不是我轻易写的，官网上就是这样定义的：

https://redis.io/commands/zadd#sorted-sets-101

而且官网上说的是：score / member pairs。

所以我画图的时候，score 在前，member 在后。这可不是轻易画的，尽管谁前谁后如同也不影响什么玩意。

另一个须要留神的点是，尽管我的示意图中没有体现进去，然而在有序汇合中，元素即 member 是不能够反复的，然而 score 是能够反复的。

这个很好了解，就比方 20210227 这一天的微信步数，我能够走 6666 步，你也能够走 6666 步，这个是不抵触：

然而，问题就随之而来了：当 member 的 score 一样的时候，member 是怎么排序的呢？

看一下来自官网的答案：

当多个元素具备雷同的分数时，它们依照 lexicographically 进行排序。

哎呀，lexicographically 这个单词不意识。

不慌，你晓得的 why 哥还兼职教英文：

当分数一样的时候，依照字典序排序，所以下面的示意图 jay 在 why 之前。

接下来，看一下有序汇合的操作函数，一共有 32 个：

我这里就不一个个的做 API 教学了，官网上曾经写的很分明了，如果对于不相熟的命令，能够去官网上查看，都是有示例代码的。

https://redis.io/commands/zadd#sorted-sets-101

比方这个 ZADD 办法：

为了前面分享的顺利进行，我这里只讲几个须要用到的操作：

• 增加 member 命令格局：zadd key score member [score member …]
• 减少 member 的 score 命令格局：zincrby key increment member
• 获取 member 排名命令格局：zrank/zrevrank key member
• 返回指定排名范畴内的 member 命令格局：zrange/zrevrange key start end [withscores]

先看第一个：增加 member。

比方咱们把示意图中的数据增加到到有序汇合外面去，语法是这样的：

• zadd key score member [score member …]

意思是能够一次增加一对或者多对 score-member，比方上面这两个命令：

• zadd sport:ranking:20210227 10026 why
• zadd sport:ranking:20210227 10158 mx 30169 les 48858 skr 66079 jay

执行之后，返回的数字代表增加胜利的 member 个数。

我用专门操作 Redis 的 RDM 可视化工具来查看插入的数据，和我本人画的示意图相差无几：

接着看第二个：减少 member 的 score

微信静止排行榜的数据是实时更新的。

目前 member 为 why 的步数是 10268，假如我吃完晚饭出门跑步去了，又跑了 5000 步。

这时得更新我的步数，就用 zincrby 命令，语法是这样的：

• zincrby key increment member

对应下面场景的执行命令是这样的：

• zincrby sport:ranking:20210227 5000 why

执行实现后，会返回 why 的步数，能够看到从 10026 变成了 15026：

同时因为我的步数减少，依照 score 倒序，也导致了排序的变动：

所以咱们只须要更新 score 就行了，至于排名的变动，Redis 会帮忙保障的。

而后看第三个命令：获取 member 排名

语法是这样的：

• 获取 member 排名：zrank key member
• 获取 member 排名：zrevrank key member

首先，排名都是 0 开始计算的。

zrank 是依照分数从低到高返回 member 排名。

zrevrank 是依照分数从高到低返回 member 排名。

比方当初要获取 jay 的排名，用 zrank 返回后果就是 4。

• zrank sport:ranking:20210227 jay

当用 zrevrank 时，jay 的排名就是 0：

• zrevrank sport:ranking:20210227 jay

所以，在微信步数排行榜的这个需要中，步数越多排名越靠前，咱们应该用 zrevrank。

第四个须要把握的命令是：返回指定排名范畴内的 member。

• zrange/zrevrange key start end [withscores] 返回指定排名范畴内的 member

这个命令就很要害了。

zrange 是依照 score 从低到高返回指定排名范畴内的 member。

zrevrange 是依照 score 从高到低返回指定排名范畴内的 member。

在这里，我只演示 zrevrange 的命令。

比方我要获取步数排名前三的 member：

• zrevrange sport:ranking:20210227 0 2

这个命令有个可选参数：withscores

当带上这个参数之后，会返回对应 member 的 score：

你想，这不就是排行榜 top N 的场景吗？

假如我当初要获取所有用户的排名，怎么写呢？

如下：

• zrevrange sport:ranking:20210227 0 -1

这就是以后的微信步数排行榜，jay 步数最多，mx 步数起码。

咦，怎么回事，排行榜良久就进去了呢？

你想想，讲完几个 API 操作，如同性能就实现了呢？

是的，的确是这样的，甚至咱们只须要这两个 API 就能实现排行榜的需要：

• zadd key score member [score member …] 增加 member
• zrange/zrevrange key start end [withscores] 返回指定排名范畴内的 member

好了，如果大家喜爱的话，感激大家一键三连。本次的文章就到这里了 …

那是不可能的。

索然无味的 API 文章多没有意思啊。

尽管后面的局部咱们曾经能够基于 Redis 的有序汇合加上几个简略的命令，就能够实现排行榜需要了。

然而后面只是铺垫，接下来，好戏才刚刚开始。

再次扫视排行榜

下面的微信步数排行榜有个问题，你发现了吗？

就下面这个场景而言，所有人来看，看到的都是这样的排序：

而真实情况是，每个人看见的数据排行数据起源本人的微信好友，而微信好友各不相同，所以看到的排行榜也各不相同。

这个个性，咱们并没有体现进去。

咱们下面的场景更加相似于游戏排行榜，所有的人看到的全服排行榜都是一样的。

那么怎么保障咱们每个人看到的各不相同呢？

你思考一下，该从什么角度去解决这个问题呢？

有序汇合的 key 不同，就获取到不同的 value 汇合。

咱们以后的 key 是 sport:ranking:20210227，外面只蕴含了某一天的信息。

只有咱们在 key 外面加上用户的属性就能够了，假如我的微信号是 why。

那么 key 能够设计为这样 sport:ranking:why:20210227。

这样，因为 key 外面多了用户信息，每个人的 key 都各不相同，就像这样的：

对应的命令如下：

• zadd sport:ranking:why:20210227 10026 why 10158 mx 30169 les 48858 skr 66079 jay
• zadd sport:ranking:mx:20210227 7688 赵四 9688 刘能 10026 why 10158 mx 54367 大脚

why 和 mx 看到的都是各自好友某一天的微信步数排行榜。

只有把 key 设计好了，这个问题就迎刃而解了。

然而你认真思考一下，真的就迎刃而解了吗？

这个问题，我在写第一版的时候可能是被猪油蒙蔽了双眼，没发现。

有种“只缘身在此山中”的滋味，一心想着 Redis 了。

你想，如果每个用户都有在 redis 有一个本人的排行榜，一个用户的分数更新的时候就须要对所有好友的 zset 更新，这多大的代价啊，对吧？

当以用户为纬度做排行榜的时候，就会呈现排行榜巨多的状况，导致保护老本升高。

Redis 能做，但不是最佳计划。

那么用什么计划去做呢？

我提个思路吧：

每个用户看到的排行榜不一样，咱们其实不必时时刻刻帮用户保护好排行榜。

保护好了，用户还不肯定来看，出力不讨好的节奏。

所以还不如提早到用户申请的阶段。

当用户申请查看排行榜的时候，再去依据用户的好友关系，循环获取好友的步数，生成排行榜。

具体计划，大家本人思考一下吧。

另外多说一嘴，前段时间不是微信反对了批改微信号吗，博得一大片叫好声。

其实我过后认真的想了一下，从技术上的实现来说这个需要到底有多难。

我不晓得有没有历史技术债权在外面。

然而就说以后这个场景，key 外面蕴含了微信号，留神是微信号，不是微信昵称。

因为在设计之初，产品打包票说：释怀，微信号相对全局惟一，一旦确定，不可变更。

后果呢，当初要变动了。

产品屁颠屁颠的说：怎么实现我不论，这个需要用户呐喊很大，连忙上线。

你说，对这些相似场景的冲击有多大？

其实冲击也不算特地大，一个字段的变动而已。

然而，微信 14 亿用户啊。

一个简略的需要，波及到这个体量之后，就一句话：

质变引起量变。

好了，好了，扯远了。说回来。

当我把眼光再次放到微信排行榜上的时候，我发现，其实我只是给了一个阉割版的排行榜。

是的，咱们当初能够获取到 why 的以后步数是 1680 步，以后排名是 814 名。

比方还是沿用下面的例子，假如当初要获取我的微信好友 jay 的微信步数排行榜状况。

先获取 jay 的名次：

• zrevrank sport:ranking:why:20210227 jay

名次为 0，程序外面能够对其进行加一操作。就是第一名了。

接着获取 jay 的今日步数：

• zscore sport:ranking:why:20210227 jay

66079，步数也有了。

当初咱们晓得了：why 的好友 jay 今日静止步数 66079 步，在 why 的微信好友中排第一名。

然而你认真看，这下面我还漏了两个字段：

• 微信头像
• 敌人点赞个数

两个字段应该怎么放呢？

放数据库外面当然能够，然而咱们次要还是说一下 Redis 的解决方案。

这个时候其实咱们想要存储的是 User 对象，对象外面有这几个字段：昵称、头像图片链接、点赞数、步数。

你说，这个用 Redis 的啥数据结构来存？

可不就得用 Hash 构造了吗。

Hash 构造同样波及到 key 和 value，那么它们别离是什么呢？

key 就是咱们的有序汇合的 key 前面再加上好友昵称，比方这样的：

对应的命令是这样的：

• hmset sport:ranking:why:20210227:jay nickName jay headPhoto xxx likeNum 520 walkNum 66079

执行实现之后，在 RDM 外面看起来是这样的：

当后续有更多的赞的时候，须要调用更新命令更新 likeNum：

• hincrby sport:ranking:why:20210227:jay likeNum 500

执行实现之后点赞数就会变成 1020：

这样，排行榜上的所有字段咱们都能获取到了，微信排行榜就说完了。

呃 ……

怎么感觉还是 API 教学呢？

不得劲，换个其余的。

最近七天排行榜怎么弄？

后面咱们说的都是每日排行榜。

假如面试官要求咱们提供一个最近七天、上一周、上一月、上个季度、这一年排行榜啥的，又该怎么搞呢？

其实这还是在考查你对于 Redis 有序汇合 API 的把握水平。

也就是这个 API：

• zinterstore/zunionstore destination numkeys key [key …] [weights weight [weight …]] [aggregate sum|min|max] 获取交加 / 并集

这个 API 看起来有点简单，不要怕，一个个的讲：

• zinterstore/zunionstore 其实就是交加 / 并集
• destination 将交加 / 并集的后果保留到这个键中
• numkeys 须要做交加 / 并集的汇合的个数
• key [key …] 具体参加交加 / 并集的汇合
• weights weight [weight …] 每个参加计算的汇合的权重。在做交加 / 并集计算时，每个汇合中的 member 会把本人的 score 乘以这个权重，默认为 1。
• aggregate sum|min|max 对于各个汇合中的雷同元素是 sum(求和)、min(取最小值)还是 max(取最大值)，默认为 sum。

拿最近七天举例，咱们轻易搞点数据进来，你能够间接粘过来玩：

• zadd sport:ranking:why:20210222 43243 why 2341 mx 8764 les 42321 skr
• zadd sport:ranking:why:20210223 57632 why 24354 mx 4231 les 43512 skr 5341 jay
• zadd sport:ranking:why:20210224 10026 why 12344 mx 54312 les 34531 skr 43512 jay
• zadd sport:ranking:why:20210225 54312 why 32451 mx 23412 les 21341 skr 56321 jay
• zadd sport:ranking:why:20210226 3212 why 63421 mx 53652 les 45621 skr 5723 jay
• zadd sport:ranking:why:20210227 5462 why 10158 mx 30169 les 48858 skr 66079 jay
• zadd sport:ranking:why:20210228 43553 why 4451 mx 7431 les 9563 skr 8232 jay

能够看到咱们一共有 7 天的数据：

而且须要留神的是 20210222 这一天是没有 jay 的数据的。

当初咱们要求出最近 7 天的排行榜，就用上面这行命令，命令有点简单，然而对着命令格局看，还是很清晰的：

• zunionstore sport:ranking:why:last_seven_day 7 sport:ranking:why:20210222 sport:ranking:why:20210223 sport:ranking:why:20210224 sport:ranking:why:20210225 sport:ranking:why:20210226 sport:ranking:why:20210227 sport:ranking:why:20210228 weights 1 1 1 1 1 1 1 aggregate sum

这条命令前面的 weights 和 aggregate 都是能够不必写的，有默认值，我这里为了不暗藏数据，都写了进去。

执行实现后，能够看到多了一个 key，外面放的就是最近 7 天的数据汇总：

下面用的是并集，如果咱们的要求是对最近 7 天，每天都上传静止数据的人进行排序，就用交加来算。

命令和下面的统一，只是把 zunionstore 批改为 zinterstore 即可。

另外为了有比照，合并之后的队列名称也批改一下，命令如下：

• zinterstore sport:ranking:why:last_seven_day_zinterstore 7 sport:ranking:why:20210222 sport:ranking:why:20210223 sport:ranking:why:20210224 sport:ranking:why:20210225 sport:ranking:why:20210226 sport:ranking:why:20210227 sport:ranking:why:20210228 weights 1 1 1 1 1 1 1 aggregate sum

从执行后果能够看进去，因为 jay 同学在 20210222 这一天没有上传静止数据，所以取交加的时候没有他了：

晓得最近 7 天的做法了，咱们又有每一天数据，上一周、上一月、上个季度、这一年排行榜啥的不都是这个套路吗？

呃 ……

怎么感觉还是 API 教学呢？

还是不得劲，再换个其余的。

亿级用户排行榜

王者光荣，妥妥的亿级用户吧。比方我想看看我在亿级用户中排多少名，于是我关上了游戏，二十多分钟（玩了一局）之后我终于找到排行榜的地位。

后果，未上榜：

我这个千年老夫子，当然是未上榜了。

就算真的有排名了，排名好几千万，8 位数字，在页面上也不好放呀。

然而假如当初的需要就是要查问用户的全服排名，怎么查？

我瞎说一个我能想到的基于 Redis 的初版计划，留神是我瞎想的，理论做起来必定是异样简单的计划。

我是怎么想的呢？

我就寻思，个别面试遇到什么千万条数据、几个 G 文件、上亿的数据啥的，首先想到的计划就是分而治之。

这个亿级用户排行榜的需要也得用分治的思维。

王者一共 8 个段位：

• 1、倔强青铜
• 2、秩序白银
• 3、光荣黄金
• 4、尊贵铂金
• 5、永恒钻石
• 6、至尊星耀
• 7、最强王者
• 8、光荣王者

所以咱们能够有 8 个桶。

这个桶能够是一个 Redis 外面的 8 个不同的 key，甚至能够是 8 个 Redis 外面各一个 key，看面试官给你的经费是多少，钱多就可劲造。

如下图所示：

解释一下下面的图片中 score 为 8588 是怎么来的。

首先咱们用 Redis 的有序汇合，那么咱们就得给每个 member 一个 score。

所以，每个用户在桶外面都一个通过公式计算后得出的积分。

比方 why 哥当初的段位就是星耀，假如计算出来的分数是 8588。

那么当初要算 why 哥在全服的排名就很好算了：

写程序的时候是能够晓得我当初的段位是星耀，那么间接去星耀的桶外面，用 zrevrank 计算出以后桶外面的排名，假如为 n。

而后再通过 zcard 这个 O(1) 的命令获取到，后面的桶，也就是最强王者和光荣王者这两个桶的汇合大小，别离为 y 和 x。

那么 why 哥的全服排名就是 n+y+x。

所以获取任何一个用户的全服排名，就是看他在本人的桶外面的排名加上后面桶外面的元素个数即可。

而且当初要计算全服 top 100 就很容易了嘛。

间接取最后面的桶，也就是光荣王者外面的前 100 个就完事了。

搞定。

等等，真的搞定了吗？

思路是对了，然而对于亿级用户只分 8 个桶未免太少了吧？

那就持续分桶呗，别忘了，每个段位外面还有小段位的。

比方星耀，外面就有星耀五到星耀一五个小段位，青铜三到青铜一三个小段位。

全副算上就是 27 个桶。

然而，27 个桶也少。

那么星耀二到星耀一还须要五颗星、青铜三到青铜二要三颗星才行呢。

这样算下来，就是 160 个桶。

160 个桶还是不够？

额。。。

颠覆重来，间接把段位加上各种其余条件换算成积分，而后依照积分来拆分：

这样，想怎么拆分数段都行、拆多细都行。

完满。

等等，真的完满吗？

你看我的积分范畴，都划分的十分的平均。

依照段位拆分，有些菜鸡选手，打了两把感觉没意思，骂骂咧咧的退出游戏，就始终留在了青铜段位。

所以青铜段位的选手必定是远大于光荣王者的。

所以，理论状况下，用户的落点其实并不是平均的。

怎么办？

这个时候就须要进行数据分析，通过一系列的高数、概率、离散等常识去做个桶大小的预估。

啊，这玩意就超纲了啊。

那就告辞，出工。

技术之外的思考

做一个排行榜如同是一个很简略的事件。

然而其实不然，特地是举荐类的排行榜，须要防止马太效应：

比方作者举荐榜单，被举荐到后面的作者，曝光度很高。即便输入品质降落，然而还是很容易取得更多的关注。

位于榜单尾部的作者就很没有参与感。

于是两极分化就呈现了，马太效应就来了。

对于这种状况怎么解决呢？

外面就波及到一个简单的计算公式了，比方掘金社区的掘力值，用于音讯流举荐和作者榜单：

https://juejin.cn/book/6844733795329900551/section/6844733795380232206

所以千万不要谬误的认为排行榜是一个非常简单的需要，这外面波及到一些非常复杂的算法。

最初说一句

感激大家的浏览。

满腹经纶，难免会有纰漏，如果你发现了谬误的中央，能够在后盾提出来，我对其加以批改。