凉了呀,面试官叫我设计一个排行榜。 (下)

本文涉及的产品
云数据库 Tair(兼容Redis),内存型 2GB
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
简介: 凉了呀,面试官叫我设计一个排行榜。 (下)

对应的命令是这样的:

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

执行完成之后,在 RDM 里面看起来是这样的:


image.png

当后续有更多的赞的时候,需要调用更新命令更新 likeNum:

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

执行完成之后点赞数就会变成 1020:

image.png

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

呃......

怎么感觉还是 API 教学呢?

不得劲,换个其他的。


image.png


最近七天排行榜怎么弄?


前面我们说的都是每日排行榜。

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

其实这还是在考察你对于 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 天的数据:


image.png


而且需要注意的是 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 天的数据汇总:

image.png

上面用的是并集,如果我们的要求是对最近 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 这一天没有上传运动数据,所以取交集的时候没有他了:


image.png

知道最近 7 天的做法了,我们又有每一天数据,上一周、上一月、上个季度、这一年排行榜啥的不都是这个套路吗?

呃......

怎么感觉还是 API 教学呢?

还是不得劲,再换个其他的。


亿级用户排行榜


王者荣耀,妥妥的亿级用户吧。比如我想看看我在亿级用户中排多少名,于是我打开了游戏,二十多分钟(玩了一局)之后我终于找到排行榜的位置。

结果,未上榜:

微信图片_20220427221727.jpg


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

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

但是假设现在的需求就是要查询用户的全服排名,怎么查?

我瞎说一个我能想到的基于 Redis 的初版方案,注意是我瞎想的,实际做起来肯定是异常复杂的方案。

我是怎么想的呢?

我就寻思,一般面试遇到什么千万条数据、几个 G 文件、上亿的数据啥的,首先想到的方案就是分而治之。

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

王者一共 8 个段位:

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

所以我们可以有 8 个桶。

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

如下图所示:

image.png

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

首先我们用 Redis 的有序集合,那么我们就得给每个 member 一个 score。

所以,每个用户在桶里面都一个经过公式计算后得出的积分。

比如why哥现在的段位就是星耀,假设计算出来的分数是 8588。

那么现在要算why哥在全服的排名就很好算了:

写程序的时候是可以知道我现在的段位是星耀,那么直接去星耀的桶里面,用 zrevrank 计算出当前桶里面的排名,假设为 n。

然后再通过 zcard 这个 O(1) 的命令获取到,前面的桶,也就是最强王者和荣耀王者这两个桶的集合大小,分别为 y 和 x。

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

所以获取任何一个用户的全服排名,就是看他在自己的桶里面的排名加上前面桶里面的元素个数即可。

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

直接取最前面的桶,也就是荣耀王者里面的前 100 个就完事了。

搞定。

image.png


等等,真的搞定了吗?

思路是对了,但是对于亿级用户只分 8 个桶未免太少了吧?

那就继续分桶呗,别忘了,每个段位里面还有小段位的。

比如星耀,里面就有星耀五到星耀一五个小段位,青铜三到青铜一三个小段位。

全部算上就是 27 个桶。

但是,27 个桶也少。

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

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

160 个桶还是不够?

额。。。

推翻重来,直接把段位加上各种其他条件换算成积分,然后按照积分来拆分:


image.png


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

完美。

等等,真的完美吗?

你看我的积分范围,都划分的非常的均匀。

按照段位拆分,有些菜鸡选手,打了两把觉得没意思,骂骂咧咧的退出游戏,就一直留在了青铜段位。

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

所以,实际情况下,用户的落点其实并不是均匀的。

怎么办?

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

啊,这玩意就超纲了啊。

那就告辞,收工。

image.png

技术之外的考虑


做一个排行榜好像是一个很简单的事情。

但是其实不然,特别是推荐类的排行榜,需要避免马太效应:

image.png


比如作者推荐榜单,被推荐到前面的作者,曝光度很高。即使输出质量下降,但是还是很容易获得更多的关注。

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

于是两极分化就出现了,马太效应就来了。

对于这种情况怎么处理呢?

里面就涉及到一个复杂的计算公式了,比如掘金社区的掘力值,用于消息流推荐和作者榜单:

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

image.png


所以千万不要错误的以为排行榜是一个非常简单的需求,这里面涉及到一些非常复杂的算法。


最后说一句



感谢大家的阅读。

才疏学浅,难免会有纰漏,如果你发现了错误的地方,可以在后台提出来,我对其加以修改。



相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore     ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库 ECS 实例和一台目标数据库 RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
目录
相关文章
|
7月前
|
设计模式 网络协议 Java
美团面试,问的贼细~
美团校招面试涵盖网络(HTTP/TCP/UDP)、框架(Spring的IoC/AOP)、设计模式(静态代理)、编程(手写静态代理)、MySQL(事务隔离级别)、Java基础(数据类型/Integer与int的区别)、HashMap等知识点。面试从自我介绍开始,深入到技术细节,如TCP的三次握手和四次挥手,GET与POST请求的区别,以及MySQL的不可重复读示例。了解更多详情可访问[www.javacn.site](https//www.javacn.site)。
104 1
美团面试,问的贼细~
|
SQL 消息中间件 搜索推荐
面试让人画正十七边形?面试官你长点心好不好?
面试让人画正十七边形?面试官你长点心好不好?
|
人工智能 算法 Java
拼多多2019春招编程题答案
拼多多2019春招编程题答案
|
算法 架构师 中间件
怎样写出让面试官眼前一亮的简历
怎样写出让面试官眼前一亮的简历
165 0
|
XML JSON 网络协议
上月成功拿到字节跳动offer,全靠我啃烂了这份最新面试题
前言 不论是校招还是社招都避免不了各种面试、笔试,如何去准备这些东西就显得格外重要。不论是笔试还是面试都是有章可循的,我这个“有章可循”说的意思只是说应对技术面试是可以提前准备,所谓不打无准备的仗就是这个道理,以下为大家,描述了从面试准备到最后的拿到offer提供了非常详细的目录,建议可以从头看是看几遍,如果基础不错的话也可以挑自己需要的章节查看。
上月成功拿到字节跳动offer,全靠我啃烂了这份最新面试题
|
存储 NoSQL 数据可视化
凉了呀,面试官叫我设计一个排行榜。 (中)
凉了呀,面试官叫我设计一个排行榜。 (中)
489 0
凉了呀,面试官叫我设计一个排行榜。 (中)
|
SQL NoSQL 前端开发
凉了呀,面试官叫我设计一个排行榜。 (上)
凉了呀,面试官叫我设计一个排行榜。 (上)
194 0
凉了呀,面试官叫我设计一个排行榜。 (上)
再学一道算法题:奥运排行榜
再学一道算法题:奥运排行榜
|
前端开发 Java 开发工具
不吹牛,这样的面试官才牛逼!
不吹牛,这样的面试官才牛逼!
125 0
不吹牛,这样的面试官才牛逼!