1. Preface
Recently, a real-time ranking function was implemented for the project (mobile game). The main features are as follows:
-
Real time full service ranking
-
You can query the ranking of a single player
-
Support two-dimensional sorting
The amount of data is small, roughly in the range of 1W ~ 50W (opening and closing services will lead to more and more roles of a single service)
2. Ranking classification
According to the ranking entity type, it is mainly divided into:
-
role
-
Legion (guild)
-
Tank
This project is a tank tour. Generally speaking, each character has N tanks. Tanks are divided into various types (light, heavy, etc.), and players can join a legion (guild)
Specifically, it can be subdivided into:
-
role
-Combat effectiveness ranking (1. Combat 2. Level)
-Personal arena ranking list (1. Arena ranking)
-Ranking of sky tower (1. Number of floors of sky tower 2. Customs clearance time)
-Prestige ranking list (1. Prestige value 2. Level)
-
Legion (guild)
-Legion level ranking (1. Legion Level 2. Total combat effectiveness of Legion)
-
Tank (1. Tank combat effectiveness 2. Tank level)
-Medium
-Heavy duty
-Anti tank gun
-Self propelled gun
↑ sorting dimensions in parentheses
3. Ideas
Based on the consideration of real-time performance, it is decided to use Redis to realize the ranking
If the redis command used in this article is unclear, please refer to the redis online manual
The following problems need to be solved:
-
Composite sort (2D)
-
Dynamic update of ranking data
-
How to get Leaderboard
4. Realize composite sorting
Redis based leaderboards are mainly implemented using the sorted set of redis
The operation of adding member points is through the zAdd operation of Redis
ZADD key score member [[score member] [score member] ...]
By default, if the score s are the same, they are sorted according to the dictionary order of member s
4.1 ranking list
First, take the level ranking list (1. Level 2. Combat effectiveness) as an example. The ranking list requires players of the same level, and those with high combat effectiveness rank first Therefore, the score can be set as:
Score = level * 1000000000 + combat effectiveness
In the game, the player level range is 1 ~ 100, and the combat power range is 0 ~ 100000000
The range of values reserved for combat effectiveness in this design is 10 digits, and the level is 3 digits, so the maximum value is 13 digits
The score value of an ordered set is a 64 bit integer value or a double precision floating-point number. The maximum representation value is 9223372036854775807, which can completely represent the 18 Bit score value. Therefore, the 13 bit score used here is more than enough
4.2 ranking of Tongtian tower
Another typical ranking list is the sky tower ranking list (1. Number of floors 2. Customs clearance time). This ranking list requires that those with the same number of floors and earlier customs clearance time are preferred
Since it is required that the earlier customs clearance time is preferred, it is not possible to directly calculate the score = number of layers * 10^N + customs clearance time as before
We can convert the customs clearance time into a relative time, that is, fraction = number of layers * 10^N + (base time - customs clearance time)
Obviously, the closer the customs clearance time is (the greater), the smaller the value of "base time - customs clearance time" is, which meets the requirements of the ranking list
For the selection of reference time, the far time 2050-01-01 00:00:00 is randomly selected, corresponding to the time stamp 2524579200
Finally, score = number of layers_ 10^N + (2524579200 - through time stamp) in the fraction formula, N takes 10, that is, the relative time to retain 10 digits
4.3 tank ranking
The difference between the tank leaderboard and other leaderboards is that the member in the ordered set is a composite id, which is composed of {uid_tankId = composition
This needs attention
5. Dynamic update of ranking data
Or take the ranking list as an example
The data required for the ranking list displayed in the game include (but are not limited to):
-
Role name
-
Uid
-
Combat effectiveness
-
head portrait
-
Guild name
-
VIP level
Because these data will change dynamically during the game, it is not considered to store these data directly as member s in an ordered set
The ordered collection used to store player level leaderboards is as follows
-- s1:rank:user:lv ---------- zset --
| player id1 | score1
| ...
| player idN | scoreN
-------------------------------------
member is the uid of the character and score is the composite integral
Use hash to store players' dynamic data (json)
-- s1:rank:user:lv:item ------- string --
| player id1 | json string of player data
| ...
| player idN |
-----------------------------------------
Using this scheme, you only need to add the character to the level ranking when the player creates the character, and then update {s1:rank:user:lv} the player's composite points in real time when the player's {level combat effectiveness} changes If the player's other data (used for leaderboard display) changes, the data json string in {s1:rank:user:lv:item} will also be modified accordingly
6. Take the ranking
Still take the ranking list as an example
objective
You need to get the top 100 players and their data from 's1:rank:user:lv'
Redis command used
[`ZRANGE key start stop [WITHSCORES]`](http://redisdoc.com/sorted_set/zrange.html)
Time complexity: O(log(N)+M), where N is the cardinality of the ordered set and M is the cardinality of the result set.
step
-
zRange("s1:rank:user:lv", 0, 99) obtains the UIDs of the first 100 players
-
hGet("s1:rank:user:lv:item", $uid) obtains the specific information of the first 100 players one by one
Step 2 above can be optimized for specific implementation
analysis
-
zRange time complexity is O(log(N)+M), where N is the cardinality of the ordered set and M is the cardinality of the result set
-
hGet time complexity is O(1)
-
Step 2 needs to acquire 100 player data at most, so it needs to be executed 100 times. The execution time here also needs to add the communication time with redis. Even if a single time is only 1MS, it needs 100MS at most
solve
-
With redis's Pipeline, the whole process can be reduced to only communicate with redis twice, greatly reducing the time consumption
The following example is php code
// $redis
$redis->multi(Redis::PIPELINE);
foreach ($uids as $uid) {
$redis->hGet($userDataKey, $uid);
}
$resp = $redis->exec(); / / the result will be returned as an array at one time
Tip: the difference between pipeline and Multi mode
Reference: https://blog.csdn.net/weixin_...
-
Pipeline pipeline is to buffer commands on the client side, so multiple requests can be combined into one and sent to the server However, atomicity is not guaranteed!!!
-
Multi transaction is to buffer commands at the server. Each command will initiate a request to ensure atomicity. At the same time, it can cooperate with "WATCH" to realize transactions. The purpose is different
7. Show The Code
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;
}
/**
* Add / update single person ranking data
* @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();
}
/**
* Get single person ranking
* @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];
}
/**
* Remove single person
* @param $uid
*/
public function del($uid)
{
$redis = $this->getRedis()->multi(Redis::PIPELINE);
$redis->zRem($this->rankKey, $uid);
$redis->hDel($this->rankItemKey, $uid);
$redis->exec();
}
/**
* Get top N leaderboards
* @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];
}
/**
* Clear Leaderboard
*/
public function flush()
{
$redis = $this->getRedis();
$redis->del($this->rankKey, $this->rankItemKey);
}
}This is the simplest implementation of a ranking list. The score calculation of ranking items is handled by the outside