游戏排行榜

背景

对于大部分游戏来说 基本上都是有排行榜的 排行榜的作用更多的是激发玩家之间攀比的心理 从而促进玩家的动力   所以排行榜是游戏不可缺少的一部分

排行榜数据更新一般分两步

1更新玩家的数据

2排序

所以提高排行榜性能从两个方面

1排行榜算法和结构

2架构设计

排行榜类型

根据排行榜的作用分以下类型（笔者都默认排行榜的数据是需要频繁更新的）

1 数据量大而且要实时更新的（最复杂）

2 数据量大不需要实时更新

3 数据量小需要实时更新的

4 数据量小不需要实时更新

更新分类

当排行榜上的一个玩家数据发生变换 需要重新排序 或者有新玩家上榜时 排行榜都需要变动

那时候有两种选择

全量排序 

说明:就是整个排行榜用排序算法重新排序 这个是保证数据绝对没有乱序的情况

缺点:就是比较浪费性能 在数据量不大的情况的还可以使用

增量排序

说明:就是对有变换的数据进行排序

例如:竞技场玩家打完了一场 胜利之后积分增加

那么在排行榜上找到该玩家的数据 如果没有就判断是否能上榜

找到玩家数据后 更新玩家对应的积分 然后再读取出排在玩家前一名的玩家的积分 如果比前一个玩家的积分就多 那么换位置 继续读前一个玩家的数据 直到积分比前一个玩家的数据小为止 反之 如果是减积分 就读后一名玩家的数据

预防：一般来说这种做法排行榜是不会乱序的 不过笔者的经验来说 排行榜久了因为某个不知道的bug 或多或少排行榜最后都会有些乱序 所以笔者在实际中会选择凌晨5点对排行榜再做一次全量排序

1 [玩家a 积分100]
2 [玩家b 积分68]
3 [玩家c 积分50]

玩家c胜利一场后 积分从50升到了70

那么找到玩家排名在第3 则找第2名的玩家 发现积分68 则调换位置

1 [玩家a 积分100]
2 [玩家c 积分70]
3 [玩家b 积分68]

排序算法

redis的zset

现在游戏的排行榜一般会使用redis的zset结构去处理 key一般为玩家id score一般为排行积分

底层结构为字典+跳表

跳表的查询时间复杂度为O(logN)、

用redis的这个结构呢 就不用程序员自己去设计排序算法 比较轻松

常见问题

1.一般不止需要通过积分来排行 还要通过上榜的时间 相同积分的情况下 先上榜的在前

那么这个时候score就要采用拼接的方式 积分+时间戳作为新的score

这个时候又会有新的问题

score太长了怎么办 当分数超过18014398509481982时，Redis的ZSCORE命令可能无法正确返回原始值

那么时间戳就采取截断的方式 一般来说同一天的话时间戳的前几位是相同的

只需要积分+时间戳的后几位作为新的score

如果排行榜需要保存很久 要保存完整的时间戳怎么办

笔者想到一个一劳永逸但实现比较复杂的方案

那就是弄两个排行榜 

一个排行榜的score的是积分

另一个排行榜的score是时间戳

当读第一个排行榜发现有积分相同的情况下 去读第二个排行榜 对积分相同的玩家再进行排序

同理 如果是在积分相同 时间戳相同情况下 一般会按照玩家的vip等级（这就是充钱的好处）vip高的排前面 在弄多个排行榜 score记录的是vip等级

在最极端的情况下 积分 时间戳 vip都相同 笔者在多年的开发中真遇到过 这个时候跟策划商量 最终玩家id小的排前面 玩家id肯定是全局唯一的了 这就能彻底解决这个排序的问题了（所以早创号还是有好处的）

2一个排行榜数据量很大的时候怎么办

redis的qps大概是10W 那假如极端情况下 一个排行榜的数量几百万 同时有大量的玩家不断更新排行榜数据

就需要分段了 使用redis集群了

比如说 每个排行榜只保存1000条数据 同时记录最后一名玩家的积分

第一个排行榜是1-1000名的玩家

第二个排行榜记录的是1001-2000名的玩家

以此类推 

同时玩家身上也记录自己的积分数据

如果怕redis消化不过来 还可以加一层kafka

排行榜保存机制

笔者之前做的游戏不是用redis的情况下需要自己做排行榜的保存

在做跨服玩法的时候 排行榜每更新一次 就持久化保存一次 导致最终io爆了

之后做了个保存机制

当有第一条数据更新时 做个定时器 笔者做的是30秒

30秒后才持久化一次

同时还做个计数器  超时30条数据要更新的话 就直接持久化 不等30秒了

排行榜的实现

数据量大而且要实时更新的

这种就使用redis的集群 将排行榜数据分段 同时还可以加一层kafka

数据量大不需要实时更新

1可以做个容器存储所有数据 玩家积分更新的时候只需要更新对应的数据 不进行排序

做个定时器 到时做个全量排序

2加个kafka 每次更新发消息给kafka 排行榜管理器作为消费者慢慢消费

数据量小需要实时更新的

直接使用redis的zset结构保存

数据量小不需要实时更新

这个就随便了

其他实现方案

笔者还有一些思路

比如不使用redis的话

自己用对应的编程语言实现树结构的容器或者用标准库 例如C++的std：map就是红黑树实现

然后每次更新直接save到mongodb中 mongodb支持集群部署

在使用redis还有一些思路

根据积分分段而不是根据排名

比如1-100分为一段

100-500为第二段

每一段的积分区间可以不一样 

如果某个区间玩家人数过多 可以动态再分成多段

每一段交给一个redis示例去排行