- 1. 前言
- 2. 排行榜分類
- 3. 思路
- 4. 實作 複合排序
- 4.1 等級排行榜
- 4.2 通天塔排行榜
- 4.3 坦克排行榜
- 5. 排名資料的動态更新
- 6. 取排行榜
- 7. Show The Code
1. 前言
前段時間剛為項目(手遊)實作了一個實時排行榜功能, 主要特性:
- 實時全服排名
- 可查詢單個玩家排名
- 支援雙維排序
資料量不大, 大緻在 1W ~ 50W區間(開服, 合服會導緻單個服角色數越來越多).
2. 排行榜分類
按照排行主體類型劃分, 主要分為:
- 角色
- 軍團(公會)
- 坦克
該項目是個坦克手遊, 大緻情況是每個角色有N輛坦克, 坦克分為多種類型(輕型, 重型等), 玩家可加入一個軍團(公會).
具體又可以細分為:
- 角色
- 等級排行榜(1. 等級 2.戰力)
- 戰鬥力排行榜(1. 戰鬥 2.等級)
- 個人競技場排行榜(1. 競技場排名)
- 通天塔排行榜(1.通天塔層數 2.通關時間)
- 威望排行榜(1.威望值 2.等級)
- 軍團(公會)
- 軍團戰鬥力排行榜(1. 軍團總戰鬥力 2.軍團等級)
- 軍團等級排行榜(1.軍團等級 2.軍團總戰鬥力)
- 坦克(1.坦克戰鬥力 2.坦克等級)
- 輕型坦克戰鬥力排行榜
- 中型
- 重型
- 反坦克炮
- 自行火炮
↑ 括号内為排序次元
3. 思路
基于實時性的考慮, 決定使用Redis來實作該排行榜. 文章中用到的redis指令如有不清楚的, 可參照 [Redis線上手冊](http://redisdoc.com/index.html). 需要解決如下問題:
- 複合排序(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. 取排行榜
依舊以等級排行榜為例.
- 目的
- 需要從
中取出前100名玩家, 及其資料.s1:rank:user:lv
用到的Redis指令 -
ZRANGE key start stop [WITHSCORES]
- 時間複雜度: O(log(N)+M), N 為有序集的基數,而 M 為結果集的基數。
步驟
-
擷取前100個玩家的uidzRange("s1:rank:user:lv", 0, 99)
-
逐個擷取前100個玩家的具體資訊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 ? - : $rank+, $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, , $topN);
} else {
$list = $redis->zRange($this->rankKey, , $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);
}
}
這就是一個排行榜最簡單的實作了, 排行項的積分計算由外部自行處理.