分享 实时插入排名的设计

yueyoum · 2013年05月21日 · 最后由 zhangyuan 回复于 2013年05月22日 · 4369 次阅读

应用场景就是 游戏中玩家与玩家PK,排名低的人如果赢了,就直接插入到排名高的人前面。 相应受影响的人排名都后移。

https://github.com/yueyoum/redis-lua-scripts

在 github 中有详细说明。

也欢迎大家提供不同解决办法!

排名对换更简单点

@doitian

是啊,但现在需要的是 插入,这种相对好点,

对换的话,名次很容易 大起大落

业务逻辑方面考虑,插入更合理一些!

曾经也用 redis 实现过一个实时排名系统

给每个人一个值,用来做排序用,PK 赢的人,将他的值改成被 PK 赢的人和他之前那个人的值平均,比如初始:

A   B   C   D   E   F
0   10  20  30  40  50

然后 E 赢了 C,E 的值就变成了 (B+C)/2 = 15

A   B   C   D   E   F
0   10  20  30  15  50

如果多次 PK 出现值平均重复的话,可以指定前后 N 个数据重分隔出固定的空间。

好处是,实现简单,对 PK 赢的人,只用改动一个值,用数据库排序就能解决,不需要 NoSQL。 考虑到大数据量,可以添加一个分组表,平均 N 个人分为一组。

我觉得这样做排名有小瑕疵 第一名的人拿到第一以后 再也不跟别人 PK 了 那他就永远第一了呗...

#5 楼 @quakewang

没太理解,其实我的第一版和你这个比较像,但有下面的问题:

如果再来一轮,F 赢了 C,那么 此时就是

A B C D E F 0 10 20 30 15 15

那么此时 E 和 F 如何排序?

出现这种情况的概率非常高,不用多次,只要两次 就行。

#6 楼 @zj0713001

忘了说一个前提,

这种 PK,不用对方同意。

只要有人挑战,就会自动战斗

#7 楼 @yueyoum 引入小数,精度长一些

#7 楼 @yueyoum F 赢了 C,F 是 (20+15) / 2 = 17 或 18,不是 15

#10 楼 @quakewang 哦,对,这样跑一段时间,就有小数了。

这种方式要随机取某一用户排名 是否有方便的办法?

#11 楼 @yueyoum 不要用小数,用整数,扩大间隔值,如果出现重复的,取前后 N 个重算间隔。 假设数据库栏位叫 rank_value,给这个栏位建 index,取某个用户排名就是:

select count(*) from users where rank_value <= self.rank_value

大数据量下,加分组栏位,来解决性能问题。

#12 楼 @quakewang 恩,不错的思路。

我刚开始 也是每个人都附带一个积分,但发现每过一段时间 需要 重新把所有人的积分按照当时排名要 normalize 一遍,觉得麻烦,所以后来就想了其他办法。不用维护

感觉这个东东用 redis 的 lists 比较好使。

ranked model 提供了不错的算法

链表可以吗?静态链表?

需要 登录 后方可回复, 如果你还没有账号请 注册新账号