核心算法:

用 分-时间 做排序的依据, 维持一个跳表 (SkipList)
同时用维护一个 map[玩家id]跳表节点 做反向查询用
因为10w日活30日活动. 完全可以在一个4G内存中完成

整体说明

server - 一个简单的telnet server
handlers - server的消息处理
modules - 排行榜和玩家结构
toolkit - 工具包
test - 测试用代码

测试命令

• 为了方便测试.启动时默认生成了100个玩家的随机数据,id范围时1-100,分值是随机数

连接

telnet 127.0.0.1 23

更新分数

命令格式为 : update,id,score

update,1,100
update,2,200
update,10092882,200
update,10092881,19999

建立"名次"数据

build

获取自己的排行

命令格式为 : rank,id

rank,10092881

性能测试结果

(测试数据是1kw玩家,每个玩家提交5次,内存峰值是6500m左右)
2023/07/15 23:06:03 [Hello, log file!] - 启动
2023/07/15 23:06:52 [Looped once ] - 第一轮提交完毕 ,49秒
2023/07/15 23:08:31 [Looped once ] - 第二轮提交完毕 ,99秒
2023/07/15 23:10:06 [Looped once ] - 第三轮提交完毕 ,95秒
2023/07/15 23:11:43 [Looped once ] - 第四轮提交完毕 ,97秒
2023/07/15 23:13:16 [Looped once ] - 第五轮提交完毕 ,93秒
2023/07/15 23:13:16 [set data finished!]
2023/07/15 23:13:19 [Build Index finished!] -遍历 list , hash查找玩家,记录Index -3秒

关于扩展和"可用性"

协议

因为是测试.所以假设了协议为 接受的消息是字符串: 命令,参数1,参数2,参数3 返回的的消息是json

建立玩家总排名

玩家的顺序是实时维护的. 但是具体是第几名需要遍历链表来更新. 如果是生产环境,可以选择的策略是:

1. 定期更新 , 比如以5分钟为间隔
2. 活动结束时(不再可以提交时) 更新一次

其他信息-如何展示给玩家

这里假设存在一个 可以通过id获得玩家信息 的服务
构建展示给玩家数据的时候. 让客户端通过整合两个服务的信息来获得最终的"榜单"
但是这个服务应该是放在逻辑服务器后面的,不应该直接被客户端调用

备份和恢复:

通过操作日志可以回放.时间成本基本上就是遍历日志的成本
更进一步,只要在k-v库里保存玩家最后的一次操作,即可恢复整个Rank 整个恢复的时间成本几乎就是遍历一次所带来的IO成本