Внедрение таблицы лидеров в реальном времени на основе игры redis

[TOC]

Последнее изменение: 18:18:37, 4 июня 2019

Недавно для проекта (мобильной игры) была реализована функция ранжирования в реальном времени с основными функциями:

Рейтинг полного сервиса в режиме реального времени
Можно запросить рейтинг одного игрока
Поддержка двумерной сортировки

Объем данных невелик, примерно от 1 Вт до 50 Вт (количество ролей в одной службе будет увеличиваться с открытием и закрытием службы).

В зависимости от типа предмета ранжирования он в основном делится на:

роль
Легион (гильдия)
Бак

Этот проект представляет собой танковый тур. Общая ситуация такова, что у каждого персонажа есть n танков. Танки делятся на различные типы (легкие, тяжелые и т.д.), и игроки могут вступать в корпус (гильдию).

Его можно далее разделить на:

роль
Легион (гильдия)
Танк (1. Боевая мощь танка 2. Уровень танка)

↑ размер сортировки в скобках

Основываясь на учете реального времени, мы решили использовать redis для реализации ранжирования

Если команда redis, используемая в этой статье, неясна, пожалуйста, обратитесь к онлайн-руководству redis

Необходимо решить следующие проблемы:

Составная сортировка (2D)
Динамическое обновление данных ранжирования
Как попасть в таблицу лидеров

Таблицы лидеров на основе Redis в основном используют набор отсортированных redis для достижения

Операция добавления участников и баллов выполняется с помощью операции zadd в redis Ключевой участник ZADD [[участник оценки] [участник оценки] ...]

По умолчанию, если оценки одинаковы, они сортируются в порядке словаря участников

4.1 ранжирование

Прежде всего, возьмем в качестве примера ранговый рейтинг (1. Ранг 2. Боевая мощь). Для этого рейтинга требуются игроки одного уровня, и те, у кого высокая боевая мощь, занимают первое место. Таким образом, оценка может быть определена как: Оценка * 100000000000 + боевая эффективность

Диапазон уровней игроков в игре составляет 1-100, а диапазон боевой мощи-0-100000000

В этой конструкции диапазон значений, зарезервированных для боевой эффективности, составляет 10 цифр, а уровень-3 цифры, поэтому максимальное значение составляет 13 место . Значение оценки упорядоченного набора равно 64-разрядному целочисленному значению или числу с плавающей запятой двойной точности, а максимальное значение представления равно 9223372036854775807, то есть оно может быть выражено полностью 18 место Значение, поэтому используемой здесь оценки из 13 цифр более чем достаточно

4.2 рейтинг башни Тунтянь

Другой типичной таблицей лидеров является Рейтинговый список башни Тунтянь (1. Количество этажей 2. Время таможенного оформления) , рейтинговый список требует, чтобы предпочтение отдавалось тем, у кого одинаковое количество этажей и более раннее время оформления

Из-за приоритета более раннего времени оформления, оно не может быть таким же прямым, как раньше Количество этажей * 10 ^ n + время таможенного оформления .

Мы можем преобразовать время оформления в относительное время, т. е. Количество этажей * 10 ^ n + (базовое время оформления) Очевидно, что чем ближе время оформления, тем Базовое время – время таможенного оформления Чем меньше значение, тем лучше оно будет

Выбор опорного времени случайным образом выбирает далекое время 2050-01-01 00:00:00 , соответствующая метка времени 2524579200

Наконец, *Доля слоев 10 ^ n + (2524579200 – через метку времени) В приведенной выше формуле дроби n принимается за 10, то есть относительное время сохранения 10 цифр

4.3 рейтинг танков

Разница между таблицами лидеров танков и другими таблицами лидеров заключается в том, что элемент в упорядоченном наборе является составным идентификатором, который определяется формой uid_tankId . Этот момент требует внимания

Возьмем в качестве примера рейтинговый список

Данные, необходимые для ранжирования, отображаемые в игре, включают (но не ограничиваются):

Имя роли
Жидкость
Боевая эффективность
Портрет головы
Название гильдии
VIP-уровень

Поскольку эти данные будут динамически изменяться в процессе игры, не считается, что эти данные хранятся непосредственно в виде участников в упорядоченном наборе, здесь они используются для хранения упорядоченной коллекции таблиц лидеров уровня игрока следующим образом

-- s1:rank:user:lv ---------- zset --
|Player Id1 | Score1
| ...
|Player IDN | scoren
-------------------------------------

Участник-это идентификатор роли, а оценка – составной интеграл

Использование хэша для хранения динамических данных игроков (JSON)

-- s1:rank:user:lv:item ------- string --
|Player Id1 | JSON string of player data
| ...
|Player IDN| 
-----------------------------------------

При такой схеме вам нужно только добавить персонажа в рейтинговый список, когда игрок создает персонажа, а затем, когда игрок Уровень боевой эффективности Обновление в реальном времени при изменении s1:ранг:пользователь:lv Если другие данные игрока (используемые для отображения рейтинга) будут изменены, то составные очки игрока будут изменены соответствующим образом s1:ранг:пользователь:lv:предмет Данные JSON stringify в

Возьмем в качестве примера рейтинговый список

цель

You need to retrieve the top 100 players and their data from 'S1: Rank: user: LV'

Используется команда Redis

[`ZRANGE key start stop [WITHSCORES]`](http://redisdoc.com/sorted_set/zrange.html)
Time complexity: O (log (n) + m), n is the cardinality of the ordered set, and M is the cardinality of the result set.

шаг

диапазон("s1:ранг:пользователь:lv", 0, 99) Получите идентификаторы 100 лучших игроков
получить("s1:ранг:пользователь:lv:предмет", $uid) Получить конкретную информацию о 100 лучших игроках по одному

Описанный выше шаг 2 может быть оптимизирован в конкретной реализации

Анализ

Временная сложность диапазона равна O (log (n) + m), n-мощность упорядоченного набора, а M-мощность результирующего набора
Получить временную сложность O (1)
Шаг 2 поскольку вам нужно получить не более 100 данных об игроках, вам нужно выполнить 100 раз. Время выполнения здесь должно быть добавлено ко времени связи с redis. Даже если однократное время составляет всего 1 мс, вам нужно не более 100 мс

Решать

С помощью конвейера redis весь процесс может быть сокращен до двухкратного взаимодействия с redis, что значительно сокращает затрачиваемое время

Следующий пример-PHP-код

// $redis
$redis->multi(Redis::PIPELINE);
foreach ($uids as $uid) {
    $redis->hGet($userDataKey, $uid);
}
$resp = $redis - > exec(); // the result will be returned as an array once

Совет: разница между конвейером и мультирежимом

Ссылка: https://blog.csdn.net/weixin

Конвейер Конвейер используется для буферизации команд на стороне клиента, поэтому несколько запросов могут быть объединены в один и отправлены на сервер Нет гарантии атомарности !!!
Мультитранзакция предназначена для буферизации команд на стороне сервера, и каждая команда инициирует запрос, Гарантируя атомарность В то же время он может сотрудничать с ЧАСАМИ Цель осуществления транзакции иная

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

    /**
     *Add / update single 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 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
     * @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);
    }
}

Это самая простая реализация таблицы лидеров. Интегральный расчет таблиц лидеров выполняется внешним