游戏中的实时排行榜实现

jiezi

6 年前

Last-Modified: 2019 年 5 月 10 日 16:13:35

前段时间刚为项目 (手游) 实现了一个实时排行榜功能, 主要特性:

实时全服排名
可查询单个玩家排名
支持双维排序

数据量不大, 大致在 1W ~ 50W 区间(开服, 合服会导致单个服角色数越来越多).

按照排行主体类型划分, 主要分为:

角色
军团(公会)
坦克

该项目是个坦克手游, 大致情况是每个角色有 N 辆坦克, 坦克分为多种类型(轻型, 重型等), 玩家可加入一个军团(公会).

具体又可以细分为:

角色

- 等级排行榜(1. 等级 2. 战力)
- 战斗力排行榜(1. 战斗 2. 等级)
- 个人竞技场排行榜(1. 竞技场排名)
- 通天塔排行榜(1. 通天塔层数 2. 通关时间)
- 威望排行榜(1. 威望值 2. 等级)

军团(公会)

- 军团战斗力排行榜(1. 军团总战斗力 2. 军团等级)
- 军团等级排行榜(1. 军团等级 2. 军团总战斗力)

坦克(1. 坦克战斗力 2. 坦克等级)

- 轻型坦克战斗力排行榜
- 中型
- 重型
- 反坦克炮
- 自行火炮

↑ 括号内为排序维度

基于实时性的考虑, 决定使用 Redis 来实现该排行榜.

文章中用到的 redis 命令如有不清楚的, 可参照 Redis 在线手册.

需要解决如下问题:

复合排序(2 维)
排名数据的动态更新
如何取排行榜

基于 Redis 的排行榜主要使用的是 Redis 的有序集合 (SortedSet) 来实现

添加成员 - 积分的操作是通过 Redis 的 zAdd 操作
ZADD key score member [[score member] [score member] ...]

默认情况下, 若 score 相同, 则按照 member 的字典顺序排序.

首先以等级排行榜 (1. 等级 2. 战力) 为例, 该排行榜要求同等级的玩家, 战斗力大的排在前. 因此分数可以定为:
分数 = 等级 *10000000000 + 战斗力

游戏中玩家等级范围是 1~100, 战力范围 0~100000000.

此处设计中为战斗力保留的值范围是 10 位数值, 等级是 3 位数值, 因此最大数值为 13 位 .
有序集合的 score 取值是是 64 位整数值或双精度浮点数, 最大表示值是 9223372036854775807, 即能完整表示 18 位 数值, 因此用于此处的 13 位 score 绰绰有余.

另一个典型排行榜是 通天塔排行榜(1. 层数 2. 通关时间), 该排行榜要求通过层数相同的, 通关时间较早的优先.

由于要求的是通关时间较早的优先, 因此不能像之前那样直接 分数 = 层数 *10^N+ 通关时间.

我们可以将通关时间转换为一个相对时间, 即 分数 = 层数 *10^N + (基准时间 – 通关时间)
很明显的, 通关时间越近 (大), 则 基准时间 – 通关时间 值越小, 符合该排行榜要求.

基准时间的选择则随意选择了较远的一个时间 2050-01-01 00:00:00, 对应时间戳 2524579200

最终, * 分数 = 层数 10^N + (2524579200 – 通过时间戳)
上述分数公式中, N 取 10, 即保留 10 位数的相对时间.

坦克排行榜跟其他排行榜的区别在于, 有序集合中的 member 是一个复合 id, 由 uid_tankId 组成.
这点是需要注意的.

还是以等级排行榜为例

游戏中展示的等级排行榜所需的数据包括(但不限于):

角色名
Uid
战斗力
头像
所属公会名
VIP 等级

由于这些数据在游戏过程中是会动态变更的, 因此此处不考虑将这些数据直接作为 member 存储在有序集合中.
用于存储玩家等级排行榜有序集合如下

-- s1:rank:user:lv ---------- zset --
| 玩家 id1    | score1
| ...
| 玩家 idN    | scoreN
-------------------------------------

member 为角色 uid, score 为复合积分

使用 hash 存储玩家的动态数据(json)

-- s1:rank:user:lv:item ------- string --
| 玩家 id1    | 玩家数据的 json 串
| ...
| 玩家 idN    | 
-----------------------------------------

使用这种方案, 只需要在玩家创建角色时, 将该角色添加到等级排行榜中, 后续则是当玩家 等级战斗力 发生变化时需实时更新s1:rank:user:lv 该玩家的复合积分即可. 若玩家其他数据 (用于排行榜显示) 有变化, 则也相应地修改其在 s1:rank:user:lv:item 中的数据 json 串.

依旧以等级排行榜为例.

目的

需要从 `s1:rank:user:lv` 中取出前 100 名玩家, 及其数据.

用到的 Redis 命令

[`ZRANGE key start stop [WITHSCORES]`](http://redisdoc.com/sorted_set/zrange.html)
时间复杂度: O(log(N)+M)，N 为有序集的基数，而 M 为结果集的基数。

步骤

zRange("s1:rank:user:lv", 0, 99) 获取前 100 个玩家的 uid
hGet("s1:rank:user:lv:item", $uid) 逐个获取前 100 个玩家的具体信息

具体实现时, 上面的步骤 2 是可以优化的.

分析
: zRange 时间复杂度是 O(log(N)+M)，N 为有序集的基数，而 M 为结果集的基数
: hGet 时间复杂度是 O(1)
: 步骤 2 由于最多需要获取 100 个玩家数据, 因此需要执行 100 次, 此处的执行时间还得加上与 redis 通信的时间, 即使单次只要 1MS, 最多也需要 100MS.

解决
: 借助 Redis 的事务, 整个过程可以降低到只与 redis 通信 2 次, 大大降低了所耗时间.

以下示例为 php 代码

// $redis
$redis->multi(Redis::PIPELINE);
foreach ($uids as $uid) {$redis->hGet($userDataKey, $uid);
}
$resp = $redis->exec();    // 结果会一次性以数组形式返回

<?php
class RankList
{
    protected $rankKey;
    protected $rankItemKey;
    protected $sortFlag;
    protected $redis;

    public function __construct($redis, $rankKey, $rankItemKey, $sortFlag=SORT_DESC)
    {
        $this->redis = $redis;
        $this->rankKey = $rankKey;
        $this->rankItemKey = $rankItemKey;
        $this->sortFlag = SORT_DESC;
    }

    /**
     * @return Redis
     */
    public function getRedis()
    {return $this->redis;}

    /**
     * @param Redis $redis
     */
    public function setRedis($redis)
    {$this->redis = $redis;}

    /**
     * 新增 / 更新单人排行数据
     * @param string|int $uid
     * @param null|double $score
     * @param null|string $rankItem
     */
    public function updateScore($uid, $score=null, $rankItem=null)
    {if (is_null($score) && is_null($rankItem)) {return;}

        $redis = $this->getRedis()->multi(Redis::PIPELINE);
        if (!is_null($score)) {$redis->zAdd($this->rankKey, $score, $uid);
        }
        if (!is_null($rankItem)) {$redis->hSet($this->rankItemKey, $uid, $rankItem);
        }
        $redis->exec();}

    /**
     * 获取单人排行
     * @param string|int $uid
     * @return array
     */
    public function getRank($uid)
    {$redis = $this->getRedis()->multi(Redis::PIPELINE);
        if ($this->sortFlag == SORT_DESC) {$redis->zRevRank($this->rankKey, $uid);
        } else {$redis->zRank($this->rankKey, $uid);
        }
        $redis->hGet($this->rankItemKey, $uid);
        list($rank, $rankItem) = $redis->exec();
        return [$rank===false ? -1 : $rank+1, $rankItem];
    }

    /**
     * 移除单人
     * @param $uid
     */
    public function del($uid)
    {$redis = $this->getRedis()->multi(Redis::PIPELINE);
        $redis->zRem($this->rankKey, $uid);
        $redis->hDel($this->rankItemKey, $uid);
        $redis->exec();}

    /**
     * 获取排行榜前 N 个
     * @param $topN
     * @param bool $withRankItem
     * @return array
     */
    public function getList($topN, $withRankItem=false)
    {$redis = $this->getRedis();
        if ($this->sortFlag === SORT_DESC) {$list = $redis->zRevRange($this->rankKey, 0, $topN);
        } else {$list = $redis->zRange($this->rankKey, 0, $topN);
        }

        $rankItems = [];
        if (!empty($list) && $withRankItem) {$redis->multi(Redis::PIPELINE);
            foreach ($list as $uid) {$redis->hGet($this->rankItemKey, $uid);
            }
            $rankItems = $redis->exec();}
        return [$list, $rankItems];
    }

    /**
     * 清除排行榜
     */
    public function flush()
    {$redis = $this->getRedis();
        $redis->del($this->rankKey, $this->rankItemKey);
    }
}

这就是一个排行榜最简单的实现了, 排行项的积分计算由外部自行处理.

游戏中的实时排行榜实现

1. 前言

2. 排行榜分类

3. 思路

4. 实现复合排序

4.1 等级排行榜

4.2 通天塔排行榜

4.3 坦克排行榜

5. 排名数据的动态更新

6. 取排行榜

7. Show The Code