游戏中的实时排行榜实现

栏目: 数据库 · 发布时间: 5年前

内容简介:Last-Modified: 2019年5月10日16:13:35前段时间刚为项目(手游)实现了一个实时排行榜功能, 主要特性:数据量不大, 大致在 1W ~ 50W区间(开服, 合服会导致单个服角色数越来越多).

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

1. 前言

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

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

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

2. 排行榜分类

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

  • 角色
  • 军团(公会)
  • 坦克

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

具体又可以细分为:

  • 角色

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

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

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

↑ 括号内为 排序 维度

3. 思路

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

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

需要解决如下问题:

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

4. 实现 复合排序

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

添加 成员-积分 的操作是通过Redis的zAdd操作

ZADD key score member [[score member] [score member] ...]

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

4.1 等级排行榜

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

分数 = 等级*10000000000 + 战斗力

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

此处设计中为战斗力保留的值范围是 10位数值, 等级是 3位数值, 因此最大数值为 13位 .

有序集合的score取值是是64位整数值或双精度浮点数, 最大表示值是 9223372036854775807, 即能完整表示 18位 数值, 因此用于此处的 13位score 绰绰有余.

4.2 通天塔排行榜

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

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

我们可以将通关时间转换为一个相对时间, 即 分数=层数*10^N + (基准时间 - 通关时间)

很明显的, 通关时间越近(大), 则 基准时间 - 通关时间 值越小, 符合该排行榜要求.

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

最终, *分数 = 层数 10^N + (2524579200 - 通过时间戳)

上述分数公式中, N取10, 即保留10位数的相对时间.

4.3 坦克排行榜

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

这点是需要注意的.

5. 排名数据的动态更新

还是以等级排行榜为例

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

  • 角色名
  • 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串.

6. 取排行榜

依旧以等级排行榜为例.

目的

需要从 `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)
hGet("s1:rank:user:lv:item", $uid)

具体实现时, 上面的步骤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();    // 结果会一次性以数组形式返回

7. Show The Code

<?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);
    }
}

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


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

The Algorithm Design Manual

The Algorithm Design Manual

Steven S Skiena / Springer / 2011-11-14 / GBP 55.07

....The most comprehensive guide to designing practical and efficient algorithms.... Written by a well-known algorithms researcher who received the IEEE Computer Science and Engineering Teaching Aw......一起来看看 《The Algorithm Design Manual》 这本书的介绍吧!

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具