实时插入排名的设计

[yueyoum]

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

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

在github中有详细说明。

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

[keakon]

有个东西叫 sorted set……

[swulling]

Redis自带的数据结构很好用

[yueyoum]

@keakon

我的第一版就是用 sorted set 做的，但自己的实现有问题。

能否基于 sorted set 写点操作步骤之类的， 指点一下？

[yueyoum]

@swulling

见上， 我尝试了几次后， 才选定的 list 和 hash 的组合.

不知是否还有其他建议？

[swulling]

@yueyoum 你应该说下具体啥问题啊

排名可以化成score，PK就是score变动，这个能满足实现你的需求么

[HowardMei]

玩家视为cache item，记 pk 胜者为 hit:1 败者为 miss:0
剩下工作就是改造 lru/mru 算法。大致思路，感觉可行，不妨试试。

[yueyoum]

@swulling

什么问题 我在github里已经描述清楚了

而且我上面的回复也说了， 我的第一版就是基于 zset 的，
并且 他们的排名不是按照 score的，

没有积分， 只要你赢了， 你的排名就比对手高。

比如 初始排名： A B C D E F

第一轮 F 赢了 A， F A B C D E
第二轮 B 赢了 F， B F A C D E
第三轮 D 赢了 A，B F D A C E


我刚开始就是 给他们一个 虚拟积分， 每个人都有个初始积分
但这样发现实现起来并不优雅，而且结果不是100%准确

你就用 zset 实现一下，大概说说操作步骤？ 因为我用zset没实现好。

[keakon]

@yueyoum

redis 127.0.0.1:6379> ZADD rank 1 a
(integer) 1
redis 127.0.0.1:6379> ZADD rank 2 b
(integer) 1
redis 127.0.0.1:6379> ZADD rank 3 c
(integer) 1
redis 127.0.0.1:6379> ZADD rank 4 d
(integer) 1
redis 127.0.0.1:6379> ZADD rank 5 e
(integer) 1
redis 127.0.0.1:6379> ZRANGE rank 0 -1
1) "a"
2) "b"
3) "c"
4) "d"
5) "e"
redis 127.0.0.1:6379> ZSCORE rank e
"5"
redis 127.0.0.1:6379> ZSCORE rank b
"2"
redis 127.0.0.1:6379> ZADD rank 2 e
(integer) 0
redis 127.0.0.1:6379> ZADD rank 5 b
(integer) 0
redis 127.0.0.1:6379> ZRANGE rank 0 -1
1) "a"
2) "e"
3) "c"
4) "d"
5) "b"

因为你是用 eval，能保证事务性，我就不写 watch 的代码了。

[keakon]

看错了，不需要交换位置，只是提前的话是没法保证 score 唯一的=。=

[swulling]

假如 A:10 B:9 C:8 D:7

B和D PK输掉，则让D的score在A和B之间，比如9.5

但是假如用户量较多，层层PK到了double的精度极限后，就需要做局部或者全局的稀疏

但lz的方法每次PK都需要遍历，性能上肯定不如用score偶尔做稀疏来的好

[yueyoum]

@swulling 我的第一版就是和你这个差不多的办法，因为这种是最容易想到的。

但这种办法需要每隔一段时间对数据进行维护，太麻烦

list+hash 在更新排名的时候 比 zset 要耗时，
但取排名是 O(1) 的复杂度， 比 zset 的O(log(N)) 要好点。

额，不过也就这点好处…………

[swulling]

@yueyoum 局部稀疏比较方便，放到更新的方法里做就好了，不是很麻烦

[yueyoum]

@swulling
不过考虑到 取排名 比更新排名 要频繁， 所以还是选择 取排名Ｏ(1) 复杂度的吧

[est]

redis本身实现就是linkde list。直接watch一下RPOP 然后 LINSERT ... BEFORE ... 即可。

[keakon]

@est insert、index 和 pop 都是 O(N) 的