最难不过二叉树

首页归档分类关于

游戏排行榜设计思路

2022-10-13

游戏开发中的很多活动都需要用到排行榜，用来对玩家活动参与度进行分数排名，以激发玩家的游戏积极性。从技术角度而言，我们可以根据排行榜的类型来选择不同技术方案来进行排行榜设计。

数据库直接排序

可能有人惊讶用数据库直接做排行榜？说实话，工业场景中，用数据库直接做排行榜的还真不少。举个例子，我们有个活动是指定特殊人群才能参与的，而且也不是这个人群所有人都会参与，因此从产品设计开始我们就能预料到这个活动的参与人数不会超过1万人，也就是说数据库的表里数据的量级是1万以下。对于这种量级的数据，我们还有必要去担心数据库的性能跟不上吗？完全不用考虑，这样的量级下，加好索引，取top10都不会超过200ms。在请求量小，数据量也小的情况下，我们直接使用数据库来完成我们的排行榜设计，是完全没问题的。

上面谈到的是小数据量小请求量下可以用数据库直接做排行榜，如果是大数据量大请求量的环境下，数据库也有机会做排行榜，请看下面这个案例。

我们游戏策划最爱使用的是周期刷新的排行榜，这个周期可以是1小时，也可以是1天（日榜），可以是一周（周榜），也可以是一个赛季（多个月）。这类排行榜我们都称为周期性排行榜，这种排行榜有个重要特性是，他不需要实时展示最新数据和最新排行，而这类排行榜恰恰又是我们游戏内应用最广泛的排行榜。

从技术看来，这种排行榜实现起来最为省心，因为不追求实时更新，因此我们可以直接把数据写到数据库，然后写个排行榜服务开启个定时器，定期去数据库拉取topN条数据回来就是我们的排行榜。如果是周榜就是跨周拉一次，如果是日榜就跨天拉一次，如果策划想要每个小时就刷新一次排行榜，那我们就定时器设置为1小时即可。其他服务就向排行榜服务拉取榜单供前端显示。

如果使用数据库Mysql拉取Top 100数据我们就这么写查询语句

select * from rank_info_table order by score desc limit 100;

如果使用数据库MongoDb拉取Top 100数据我们就这么写查询语句

db.col.find({}).sort({"score":-1}).limit(100)

本地排序

有一类排行榜是根据自己好友数据来生成一个排行榜，比如微信运动步数排行榜，这个榜单的生成是根据自己好友数据来排行的，像这一类榜单，无需为每一个用户都存储和维护一个数据库表，更为通用的实现是，拉取自己的好友列表，并拉好友的响应分数，在客户端本地进行本地排序，展现出好友数据排行榜，在好友不多的情况下，因为向数据库拉取好友数据是需要加CD的，比如1分钟一次拉取，因为非实时拉取，因此这类榜单对数据库的消耗是比较小的。

Redis ZSET实现

使用Redis ZSET来实现排行榜是业内最常用的的实时排行榜实践方案，这里介绍基于redis zset的实时排行榜方案。

我们使用zset来存储用户的唯一ID和分数，比如我们需要设计一个玩家能力等级的排行榜，那么玩家的唯一ID和玩家的等级分别作为zset的member和score，redis一直维持这样的有序集合。这里需要注意，我们的member存储是玩家的唯一ID而不是玩家的信息对象，如果我们需要获取排行榜上某个玩家的信息，是需要去redis重新取的，比如玩家的具体信息是set到redis上，那我们就用get指令来取；如果玩家的具体信息是hset到redis，那我们就用hget来取。

因此给排行榜插入数据就分成了2步：

  1. hset玩家详细数据，如hset user_james age 30
  2. zadd玩家分数，用于排名:zadd level_rank 50 james

取排行榜第N名的玩家的具体数据也是分为了2步：

  1. ZREVRANGE查排行榜上第N名玩家的唯一ID：ZREVRANGE level_rank 1 1
  2. 拿唯一ID用hget查玩家详细信息：hget user_james age

增加数据成员

向排行榜level_rank增加成员James,分数为100；同时使用HSET把玩家的其他一些数据设置保存。

ZADD level_rank 100 James
HSET user_James age 32

获取TopN

获取长度为100的排行榜，返回数据中是带上分数的。

127.0.0.1:6379> ZREVRANGE level_rank 0 99 WITHSCORES
1) "James"
2) "99"
3) "Durant"
4) "94"
5) "Wade"
6) "93"
7) "Curry"
8) "91"

给member加分数

给指定member加分数是个原子操作。

127.0.0.1:6379> ZINCRBY level_rank 1 James
"100"

通过排名查member

比如我想找排名第2的是哪个玩家。

127.0.0.1:6379> ZREVRANGE level_rank 1 1
1) "Wade"

通过member查排名

我想查一下James的当前排名，显示是0，也就是第一名。

127.0.0.1:6379> ZREVRANK level_rank James
(integer) 0

通过member查分数

我想查一下Wade当前的分数

127.0.0.1:6379> ZSCORE level_rank Wade
"96"

通过分数查member

我想查一下分数是91~96之间，有哪些玩家

127.0.0.1:6379> ZRANGEBYSCORE level_rank 91 96
1) "Curry"
2) "Durant"
3) "Wade"

通过分数查排名

这里分享一个特殊需求，也是有关于排行榜的：我们有一个战力榜，同时我们也有一个装备预穿系统，玩家可以在该系统内穿上装备或卸下装备，此时玩家的战力会发生改变，此时排行榜上玩家的排名也会实时变化，玩家需要感知到我穿上这个装备后的最新排名是多少。

从技术角度来分析这个需求，这是一个实时排行榜，需要时刻反应排名的变化，因此采取redis set来实现。且这个正式榜单异常巨大，已经存储了1亿玩家的数据，此时该怎么设计呢？

那技术实现思路转为了“如何通过分数查询排名”。这时候我们可以利用ZRANGEBYSCORE 来完成。因为玩家有个当前分数x，对应排名m，穿了装备后分数为y，我们需要查出对应的排名n。我们利用ZRANGEBYSCORE key x y统计处于x,y分数区间的玩家个数z，那么新排名n=m+z。

分数相同如何排序

做排行榜肯定会遇到分数相同的问题，因此需要策划给一个规则处理分数相同的情况，一般而言，策划倾向于参与活动的时间作为第二排序条件，即如果分数相同，那么早参与活动的玩家排在前面。这个排序规则在数据库中很容易实现，但是使用redis排行榜，就需要额外处理一下了，因为我们的score只表示分数，不做特殊处理没法实现第二排序条件。因此对于redis zset排行榜要实现多个排序规则，我们可以有两个方案来实现：

  1. 先从redis取回1.5倍大小的排行榜数据，内存内再次排序。比如我们的排行榜展示的是top100数据，那么我们就先从Redis拉Top150的数据回来，然后再hget每个数据的额外数据回来（例如插入时间），最后对这些数据进行第二规则排序，生成最终top100排行榜。
  2. 重组score，使其赋予更多的信息。比如我们的排序规则是首先比较等级，如果等级相同那就比较参与时间，参与时间越早的排名更靠前。这类需求可以通过拼接score来解决：整数部分设置为等级，小数部分设置为距离标准时间的秒数。比如A，B玩家的分数均为100，A数据插入时间的时间戳是1628783471,B插入时间为1628783501，显然A比B更早插入榜单，我们先设置一个基准时间戳1944316301，那么A的距离基准时间差为315532830，那A的真实分数为100.315532830，B也以一样的计算规则得到新分数100.315532800，redis zset比较时会发现A分数>B分数，自然A排在B前面。

千万级全服排行榜设计要点

基于Redis ZSET实现的实时排行榜有个致命问题：当数据量增大时，ZSET相关操作的性能会急速下降。根据经验，当ZSET的元素超过10000时，ZSET的性能会明显下降，当我们基于ZREVRANGE 取TOP N数据时，数量大的ZSET返回的速度会明显变慢。

现在我们需要设计一个全服实时排行榜，这个排行榜跟我们上面分析的排行榜不一样，上面实时排行榜取得时千万玩家的top100，也就是排行榜数据条数最多才100条。但是，这次的排行榜需求是全服所有人都需要有自己的排名，也就是说，这是个千万级数据别的排行榜。

这一类的排行榜并不少见，比如英雄联盟，会有段位排行；王者荣耀，也有自己的地区角色排名，本质上也是全服玩家排行，每个玩家都有自己真实的排行位置。当然也有一些不设置这些段位、地区的区分，单纯按照自己的战力进行全服排行，此时我们需要对ZSET进行一些策略上改造，以实现这个千万级数据排行榜。

这类排行榜排行的策略是分治，因为redis zset在达到万这个量级会性能急速下降，因此我们需要对每个zset key的数据数量保持在1万以下。假设我们的用户量是1千万，我们每个桶可以存的数据量为10000，那么我们需要1000个桶。也就是我们将在Redis 集群中建立1000个key，每个key是代表一定的分数范围。

桶1：范围0-9999，拼接key为bucket1
桶2:范围10000-19999，拼接key为bucket2
桶1000：范围9999999-无穷大,，拼接key为bucket1000

假设我的分数是19808，那么此时我们首先先算出我的分数处于哪个分数段，再算出我的数据应该处于哪一个桶内。经计算，19808处于10000~19999这个范围内，位于桶2。我们通过ZRANGEBYSCORE bucket2算出19808所处的位置N。因为我们知道每一个桶的成员数量（ZCARD定时获取，缓存在cache），因此19808所处的排名为ZCARD(bucket1000)+ZCARD(bucket999)+...+ZCARD(bucket333)+N。

值得注意的是，当分数在跳段时，这就包括升段和掉段，都需要准确选取到正确的桶来获取当前分数在该桶所处的排名。

通过这个分治策略，我们可以将海量用户数据都可以拆分为任意小的zset集合。

但是上面的策略会有另外一个问题：数据不均匀，分布在每个key的数据量是不一样的，显然分数低的桶会集中大部分的数据，比如0~100000，会集中了80%的用户。也就是说bucket1可能会有数百万的的用户。此时的解决思路就是算出用户分布，低分数段就就把分数段拆得更细，高分数段就可以适当扩大，比如100000以内就以100的间隔来分桶，一共1000个桶，100000以上的分数，以100000来分桶，一共99个桶。所以1000万用户就拆分为1099个桶来分配数据，根据数据分布来设计桶的分治机制，是更为合理的策略。