内容简介: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在线手册 .
需要解决如下问题:
- 复合排序(2维)
- 排名数据的动态更新
- 如何取排行榜
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
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》 这本书的介绍吧!