В игре есть различные таблицы лидеров, такие как рейтинг уровня игрока, рейтинг очков и т. Д. Рейтинг игрока в рейтинге является символом его силы.Игроки на вершине рейтинга имеют беспрецедентную славу в виртуальном мире, поэтому рейтинг стал целью основных игроков.
Типичная таблица лидеров игры включает в себя следующие общие функции:
- Возможность записывать счет каждого игрока;
- Возможность обновлять очки игроков;
- Возможность запрашивать счет и рейтинг каждого игрока;
- Возможность запрашивать N лучших игроков по рейтингу;
- Возможность запрашивать игроков с рейтингом M до и после указанного игрока.
Кроме того, вышеуказанные операции необходимо выполнять в режиме реального времени за короткий промежуток времени, чтобы максимально повысить эффективность таблицы лидеров.
Поскольку повышение ранга игрока на x приведет к изменению ранга игроков x+1 (включая самого игрока), если для реализации таблицы лидеров используется традиционная база данных (такая как MySQL), то при большом количестве игроков она будет привести к влиянию на базу данных.Частое изменение, производительность не устраивает, поэтому мы можем только думать о других способах.
Как член NoSQL, Redis широко используется в последние годы. По сравнению с Memcached Redis имеет больше типов данных и интерфейсов операций, а также имеет более широкую область применения.Отсортированный набор (также называемый zset) очень подходит для построения таблиц лидеров. Ниже приводится краткое изложение.
1. Установка Redis
Установить Redis под Ubuntu очень просто, достаточно выполнить следующую команду:
$ sudo apt-get install redis-server
После установки запустите клиент командной строки redis-cli, чтобы получить доступ к локальному серверу redis.
$ redis-cli redis 127.0.0.1:6379>
Если вы хотите использовать последнюю версию, вам нужно перейти на официальный сайт Redis (redis.io) Загрузите последний код и скомпилируйте его самостоятельно, шаги опущены.
2. Общие команды ZSet
Упорядоченный набор — это, во-первых, набор, и его элементы уникальны, а во-вторых, каждый элемент связан со счетом, так что элементы можно сортировать по счету. Общие сведения об упорядоченных наборах см.Redis.IO/темы/данные…, чьи команды видятRedis.IO/команды#так….
Вот несколько команд, которые можно использовать с таблицами лидеров.
Допустим, lb — это название таблицы лидеров, а user1, user2 и т. д. — уникальные идентификаторы игроков.
1) zadd - установить счет игрока
Формат команды:zadd список лидеров имя счет идентификатор игрокаВременная сложность: O (log (N))
Счет для 4 игроков указан ниже, если счет игрока уже существует, он перезапишет предыдущий счет.
> redis 127.0.0.1:6379> zadd lb 89 user1
> (integer) 1
> redis 127.0.0.1:6379> zadd lb 95 user2
> (integer) 1
> redis 127.0.0.1:6379> zadd lb 95 user3
> (integer) 1
> redis 127.0.0.1:6379> zadd lb 90 user4
> (integer) 1
2) zscore - Посмотреть счет игрока
Формат команды:имя игрока в таблице лидеров zscoreВременная сложность: O(1)
Следующее, чтобы увидеть счет игрока user2 в таблице лидеров lb.
redis 127.0.0.1:6379 > zscore lb user2 "95"
3) zrevrange - Просмотр списков лидеров по рангу
Формат команды:zrevrange имя в таблице лидеров стартовая позиция конечная позиция [набранные баллы]Временная сложность: O(log(N)+M)
Поскольку таблица лидеров, как правило, сортируется по количеству очков от большего к меньшему, мы используем zrevrange, а команда zrange сортируется по количеству очков от меньшего к большему.
Начальная и конечная позиции представляют собой индексы, начинающиеся с 0, и обе включаются. Если конечная позиция равна -1, диапазон просмотра составляет всю таблицу лидеров.
Приведение withscores вернет счет игрока.
Проверьте все результаты игроков ниже.
> redis 127.0.0.1:6379> zrevrange lb 0 -1 withscores
> 1) “user3”
> 2) “95”
> 3) “user2”
> 4) “95”
> 5) “user4”
> 6) “90”
> 7) “user1”
> 8) “89”
Ниже приведены результаты трех лучших игроков.
> redis 127.0.0.1:6379> zrevrange lb 0 2 withscores
> 1) “user3”
> 2) “95”
> 3) “user2”
> 4) “95”
> 5) “user4”
> 6) “90”
4) zrevrank - Посмотреть рейтинг игрока
Формат команды:zrevrank имя игрока в таблице лидеровВременная сложность: O (log (N))
Подобно zrevrange, zrevrank возвращает рейтинг игрока в порядке от большого к меньшему (фактически возвращает индекс, начинающийся с 0), а соответствующий zrank возвращает рейтинг в порядке от низкого к высокому.
Ниже приведен рейтинг игроков запросов user3 и user4.
> redis 127.0.0.1:6379> zrevrank lb user3
> (integer) 0
> redis 127.0.0.1:6379> zrevrank lb user1
> (integer) 3
5) Zincrby - увеличить или уменьшить счет игрока
Формат команды:Zincrby Leaderboard Name Score Increment Player IDВременная сложность: O (log (N))
Некоторые списки лидеров сбрасывают счет игрока при изменении, в то время как другие изменяют счет игрока постепенно, что может быть положительным или отрицательным. Если игрок не находится в таблице лидеров, когда выполняется цинкрби, его необработанный счет считается равным 0, что эквивалентно выполнению zdd.
Следующее увеличит оценку пользователя 4 на 6, так что его рейтинг поднимется на первое место.
> redis 127.0.0.1:6379> zincrby lb 6 user4
> “96”
> redis 127.0.0.1:6379> zrevrange lb 0 -1 withscores
> 1) “user4”
> 2) “96”
> 3) “user3”
> 4) “95”
> 5) “user2”
> 6) “95”
> 7) “user1”
> 8) “89”
6) zrem - удалить игрока
Формат команды:zrem имя игрока в таблице лидеровВременная сложность: O (log (N))
Следующее удаляет игрока user4.
> redis 127.0.0.1:6379> zrem lb user4
> (integer) 1
> redis 127.0.0.1:6379> zrevrange lb 0 -1 withscores
> 1) “user3”
> 2) “95”
> 3) “user2”
> 4) “95”
> 5) “user1”
> 6) “89”
7) del - удалить таблицу лидеров
Формат команды:имя списка лидеров
Объект таблицы лидеров создается, когда мы вызываем zadd или цинкрби в первый раз.Когда мы хотим удалить его, мы можем вызвать общую команду redis del.
> redis 127.0.0.1:6379> del lb
> (integer) 1
> redis 127.0.0.1:6379> get lb
> (nil)
3. Вопросы с одинаковой оценкой
В бесплатном плане всегда есть некоторые недостатки. Из предыдущего примера мы видим, что user2 и user3 имеют одинаковую оценку, но при сортировке в обратном порядке оценок user3 опережает user2. В сценариях практического применения мы бы предпочли, чтобы пользователь 2 был впереди пользователя 3, потому что пользователь 2 присоединяется к таблице лидеров раньше пользователя 3, а это означает, что пользователь 2 набирает очки первым.
Однако, когда Redis встречает один и тот же результат, он сортирует в соответствии с лексикографическим порядком элементов самой коллекции. Здесь он сортируется в соответствии с двумя строками «user2» и «user3». естественно выйдет на передний план.
Чтобы решить эту проблему, мы можем рассмотреть возможность добавления метки времени к оценке, которая рассчитывается как:
Отметка времени = фактическая оценка * 10000000000 + (9999999999 – отметка времени)
Для метки времени мы используем функцию time(), предоставленную системой, то есть количество секунд с 1 января 1970 года. Мы используем 32-битную метку времени (это может длиться до 2038 года), потому что 32-битная метка времени 10-значное десятичное целое число (максимальное значение — 4294967295), поэтому мы позволяем метке времени занимать младшие 10 бит (десятичное целое число), фактическая оценка увеличивается в 10 ^ 10 раз, а затем результат сложения двух частей равен используется в качестве оценки zset. Учитывая обратный хронологический порядок, часть временной метки необходимо перевернуть, поэтому временная метка вычитается из 9999999999. Когда мы хотим прочитать фактический счет игрока, просто удалим последние 10 цифр.
На первый взгляд, это решение выглядит хорошо, но есть две проблемы.
Первая проблема — небольшая проблема. Использование секунд в качестве метки времени может быть недостаточным, чтобы различить их. Если два счета с одинаковым счетом появятся в одну и ту же секунду, предыдущая проблема все равно возникнет. Конечно, мы можем выбрать отметка времени с более высокой точностью, но в практических сценариях не имеет значения, кто впереди в ту же секунду.
Вторая проблема — большая проблема, потому что дробный тип Redis — double, а 64-битное число с плавающей запятой двойной точности имеет только 52 значащих цифры. Диапазон целых чисел, который он может точно выразить, — от -2^53 до 2^. 53, а самое высокое только Представляет 16-битное десятичное целое число (максимальное значение — 9007199254740992, на самом деле даже 16 бит не могут быть представлены полностью). То есть, если предыдущая метка времени занимает 10 бит, для счета остается только 6 бит, чего недостаточно для некоторых результатов таблицы лидеров. Мы могли бы рассмотреть возможность уменьшения количества битов в метке времени, например, начиная с 1 января 2015 года, но это все равно не добавляет несколько битов. Или уменьшите степень дискриминации и используйте минуты и часы в качестве единиц измерения времени.
Если дробный тип Redis — int64, у нас нет проблем, описанных выше. Кстати говоря, на самом деле Redis должен предоставить дополнительный ZSet типа int64, но на данный момент это может быть только иллюзией, если только вы не измените его исходный код.
Поскольку Redis не может идеально решить проблему ранжирования, нужно ли в конце концов реализовывать специальную структуру данных ранжирования? Ведь есть много мест, которые можно оптимизировать для таблицы лидеров в практических приложениях.По сравнению с игроками, она распределяется в пирамиде.Чем ниже сегмент, тем больше игроков.Один и тот же счет имеет большое количество игроков, а игрок может превзойти многих игроков, добавив одно очко.Это оптимизация.при условии возможности.
Эта статья также опубликована в общедоступной учетной записи WeChat [Trail News]. Пожалуйста, отсканируйте код, чтобы следовать!