Рейтинги и таблицы лидеров на sorted sets
Почему рейтинг «топ-100 игроков и моё место среди миллиона» в Redis считается мгновенно и без единой сортировки на стороне приложения.
Sorted set (отсортированное множество) — структура Redis, где каждый элемент-член хранится вместе с числовым score, и Redis всегда держит элементы упорядоченными по этому score. Это идеальная основа таблицы лидеров: добавили очки — порядок пересчитался сам, и можно мгновенно спросить топ или ранг конкретного игрока.
Зачем это нужно на практике
Рейтинги встречаются повсюду: очки в игре, лайки постов, баллы лояльности, «самые активные за неделю». В реляционной базе на каждый показ таблицы пришлось бы выполнять ORDER BY score LIMIT по миллионам строк, а «какое у меня место» — это и вовсе подсчёт всех, у кого очков больше. На горячих экранах это дорого. Sorted set держит данные уже отсортированными в памяти, поэтому и топ-N, и ранг отдельного игрока берутся за логарифмическое время — рейтинг честно обновляется в реальном времени.
Заполняем таблицу: ZADD
Команда ZADD добавляет члена с его score или обновляет score существующего. Ключ — это вся таблица лидеров, члены — игроки, score — их очки.
ZADD game:leaderboard 1500 alice
ZADD game:leaderboard 2300 bob
ZADD game:leaderboard 1800 carol
ZADD game:leaderboard 900 dave
# набрать очки игроку прямо в рейтинге — атомарно, без чтения в приложение:
ZINCRBY game:leaderboard 250 alice # alice: 1500 -> 1750Обратите внимание на ZINCRBY: он прибавляет очки и тут же переставляет игрока на новое место одной атомарной командой, без гонок «прочитал-прибавил-записал».
Топ игроков: ZREVRANGE
Sorted set по умолчанию отсортирован по возрастанию score. Для таблицы лидеров нужен обратный порядок — самые большие очки сверху, поэтому берём ZREVRANGE (range в обратном порядке). Индексы — с нуля, оба конца включительно; флаг WITHSCORES вернёт ещё и очки.
ZREVRANGE game:leaderboard 0 2 WITHSCORES
# топ-3: bob 2300, carol 1800, alice 1750
ZREVRANGE game:leaderboard 0 -1 # вообще все игроки сверху внизЧтобы показывать рейтинг страницами по 20, запрашивайте диапазоны 0 19, 20 39 и так далее — пагинация по рейтингу получается естественно.
Ранг конкретного игрока: ZREVRANK
Главная боль обычных БД — «какое у меня место» — в sorted set решается одной командой. ZREVRANK возвращает позицию члена в порядке убывания score (с нуля), ZSCORE — его очки. Смоделируем поведение на Python, включая важную деталь: как Redis разрывает ничью по очкам.
# Мини-модель sorted set: пары (участник, score). Покажем ZREVRANGE и ZREVRANK.
scores = {} # member -> score, как в ZADD
def zadd(member, score):
scores[member] = score
# Заполняем таблицу очков
zadd("alice", 1500)
zadd("bob", 2300)
zadd("carol", 1800)
zadd("dave", 900)
zadd("erin", 2300) # ничья по очкам с bob
# ZREVRANGE 0 2 WITHSCORES: топ-3 по убыванию.
# Redis при равных score сортирует по члену лексикографически — воспроизводим это.
ranking = sorted(scores.items(), key=lambda kv: (-kv[1], kv[0]))
print("Топ-3:")
for i, (member, score) in enumerate(ranking[:3]):
print(f" {i+1}. {member} — {score}")
# ZREVRANK carol: позиция (с нуля) в порядке убывания
rank = [m for m, _ in ranking].index("carol")
print(f"Ранг carol (с нуля): {rank}")
print(f"Место carol для игрока: {rank + 1}")Вывод:
Топ-3: 1. bob — 2300 2. erin — 2300 3. carol — 1800 Ранг carol (с нуля): 2 Место carol для игрока: 3
Заметьте: bob и erin набрали поровну (2300), и Redis ставит их рядом, разрывая ничью лексикографически по имени члена («bob» идёт раньше «erin»). Ранг carol равен 2 (с нуля), то есть для человека это 3-е место. Так из ранга легко получить привычную «позицию в таблице», прибавив единицу.
Диапазоны очков: ZRANGEBYSCORE и подсчёт
Sorted set умеет выбирать и считать не по позиции, а по диапазону самих очков. Это удобно для лиг и порогов: «кто набрал от 1000 до 2000», «сколько игроков перешагнули 2000».
ZRANGEBYSCORE game:leaderboard 1000 2000 # члены с очками в [1000, 2000]
ZCOUNT game:leaderboard 2000 +inf # сколько игроков набрали 2000 и больше
ZREVRANGEBYSCORE game:leaderboard +inf 2000 # те же «сильные», но сверху внизСкобка перед границей делает её строгой: (2000 означает «строго больше 2000». Так нарезают лиги (бронза/серебро/золото) прямо запросом, без перебора в приложении.
Как это работает под капотом
Внутри sorted set — это связка из хеш-таблицы (член → score, чтобы за O(1) узнать очки) и структуры skip list, которая держит члены упорядоченными по score. Skip list — это многоуровневый связный список с «лестницей» указателей, по которой поиск, вставка и вычисление позиции идут за логарифмическое время. Поэтому ZADD вставляет элемент в нужное место за O(log N), ZREVRANK вычисляет позицию тоже за O(log N), а ZREVRANGE 0 K отдаёт топ за O(log N + K). При равенстве score порядок определяется лексикографическим сравнением самих членов — отсюда предсказуемый разрыв ничьих, который мы видели в выводе. Именно это сочетание делает рейтинг по миллионам игроков дешёвым в реальном времени.
Частые ошибки
- Перепутать ZRANGE и ZREVRANGE.
ZRANGE 0 2вернёт худших (наименьшие очки), для таблицы лидеров нуженZREVRANGE. - Сортировать в приложении. Тянуть всех через
ZRANGE 0 -1и сортировать кодом — потеря смысла структуры; пусть Redis отдаёт уже нужный диапазон. - Забыть про разрыв ничьих. При равных очках порядок задаёт имя члена; если нужна стабильность по времени, кодируйте время в score (например, дробной частью).
- Хранить лишнее в score. Score — это число (double); метаданные игрока держите отдельно (в хеше), а в рейтинге — только очки.
- Безграничный рост ключа. Для «топа за неделю» заводите отдельный ключ на период и вешайте TTL, иначе таблица будет копить неактуальных игроков.
Итоги
- Sorted set хранит члены упорядоченными по числовому score — готовый движок таблиц лидеров.
ZADD/ZINCRBYзаносят и наращивают очки атомарно, без гонок чтения-записи.ZREVRANGE 0 K— мгновенный топ-K,ZREVRANK— ранг конкретного игрока (с нуля).ZRANGEBYSCORE/ZCOUNTнарезают и считают игроков по диапазону очков (лиги, пороги).- Под капотом skip list даёт O(log N) на вставку и ранг; ничьи по score разрешаются по имени члена.