Проектируем лидерборд в реальном времени

После этого урока ты точно поймёшь, почему SQL ORDER BY ломается на масштабе, как skip list (список с пропусками) отвечает «каков мой ранг среди миллионов» за O(log n) и когда пора переходить от одного узла к шардингу.

Требования

• Функциональные: обновить очки игрока; читать top-k (топ 10/100); читать текущий ранг и очки любого игрока; часто читать малое окно вокруг игрока («ты и 5 выше и ниже»).
• Нефункциональные: горяча на запись (очки постоянно меняются в игре) и горяча на чтение (все смотрят таблицу). Низкая задержка и обновлений, и запросов ранга. Достаточно сильная свежесть — ранг должен отражать недавние очки за секунды. Доска может быть большой: десятки миллионов записей.

Определяющее требование — комбинация. Top-k сам по себе прост (держи кучу). Ранг-одного сам по себе несложен (счётчик). Нужда в обоих, плюс быстрые обновления, плюс «окно вокруг меня», на доске из миллионов — вот что исключает очевидную таблицу и указывает на упорядоченную, осознающую ранг структуру.

Оценки

Пусть игра с 50 млн игроков в месяц, 5 млн одновременно на пике и смена очков примерно каждые 10 секунд активной игры — назовём 5×10^6 / 10 = 5×10^5 обновлений/с на пике, плюс тяжёлый трафик чтения, пока игроки смотрят таблицу. Сама доска мала в байтах: 50 млн записей (player_id, score) — порядка пары ГБ — влезает в память на одном мощном узле, поэтому in-memory отсортированное множество — естественный дом. Давление не в хранилище; оно в выполнении O(log n) работы полмиллиона раз в секунду и ответе на запросы ранга без сканирования.

Высокоуровневая схема

Событие очков идёт к сервису лидерборда, обновляющему отсортированное множество в Redis; чтения (top-k, мой-ранг, окно) бьют в ту же структуру. Долговечное хранилище-источник истины (база данных) держит авторитетную историю очков; ZSET — быстрый индекс, перестраиваемый из неё при потере.

Глубокие погружения — почему отсортированное множество выигрывает, как оно отвечает «мой ранг среди миллионов» и что делать, когда доска перерастает один узел.

Глубокое погружение

Отсортированное множество (ZSET) и почему оно выигрывает

Отсортированное множество Redis хранит члены, каждый с числовым score, упорядоченные по score, реализованы как skip list рядом с хеш-таблицей. Skip list даёт упорядоченный обход и ранг за O(log n); хеш даёт O(1) поиск score по члену. Эта комбинация — ровно список желаний лидерборда:

• Обновление: ZADD board <score> <player> вставляет или перемещает за O(log n).
• Top-k: ZREVRANGE board 0 9 WITHSCORES возвращает топ-10 за O(log n + k).
• Мой ранг: ZREVRANK board <player> возвращает 0-базовую позицию игрока за O(log n) — без сканирования других.
• Окно вокруг меня: взять ранг, затем ZREVRANGE board r-5 r+5 для соседей.

Реляционная альтернатива отвечает на top-k нормально с индексом, но «мой ранг» становится SELECT COUNT(*) WHERE score > mine — счёт O(n) на запрос, разрушительный, когда миллионы игроков опрашивают свой ранг. ZSET держит информацию о ранге в самой структуре, так что ему никогда не нужно считать.

Top-k и «мой ранг среди миллионов»

У двух чтений очень разные профили стоимости, и их смешение — классическая ошибка. Top-k разделяем: есть один топ-10 на всю доску, так что вы считаете его один раз и кэшируете для всех, обновляя на коротком интервале — миллионы зрителей, одно вычисление. Мой-ранг персонален: у каждого игрока свой, так что его нельзя кэшировать глобально; его надо считать на запрос. Спасение в том, что ZREVRANK — O(log n), так что даже на запрос он дёшев — а чтение окна-вокруг-меня переиспользует тот же ранг. Так что архитектура агрессивно кэширует глобальный top-k и обслуживает персональные ранги вживую из ZSET, вместо попытки предвычислить ранг каждого игрока (что было бы O(n) на поддержку и бессмысленно, ведь большинство никогда не смотрят).

Шардинг, когда одна доска слишком велика

У одиночного ZSET на одном узле есть пределы: память и однопоточная пропускная способность одного инстанса Redis против 5×10^5 записей/с. Когда вы его перерастаете, вы шардите по диапазону очков — узел A держит очки 0–1000, узел B 1001–2000 и так далее. Top-k тогда читает лишь шард высшего диапазона (или сливает топы нескольких). Обновления маршрутизируются на шард, владеющий новым счётом (и удаляются из старого шарда при смене, пересекающей границу). Трудная часть — глобальный ранг: истинный ранг игрока — его ранг внутри своего шарда плюс полный счёт всех в более высоких по очкам шардах. Вы держите по-шардовые кардинальности (дешёвые счётчики), так что глобальный ранг — «мой внутришардовый ранг + сумма размеров более высоких шардов» — сложение O(шарды), не скан. Это тот же инстинкт грубо-потом-точно и обработки границ, что во всём юните, теперь как партиционирование диапазона на оси очков.

Узкие места и компромиссы

Первый компромисс — память против долговечности: ZSET живёт в RAM ради скорости, так что должен подкрепляться долговечным источником истины и перестраиваться при рестарте — относитесь к отсортированному множеству как к быстрому индексу, никогда как к системе записи. Второй — конкуренция записи: на сотнях тысяч обновлений/с один инстанс — узкое место, поэтому шардинг по диапазону очков (или разбиение на временны́е доски — дневная/недельная/всё-время, каждая свой меньший ZSET) — путь масштабирования. Третий — свежесть против стоимости персонального ранга при волатильности: когда очки постоянно меняются, точный ранг игрока — движущаяся цель, и пересчёт его на каждое обновление для каждого зрителя расточителен — так что вы считаете ранг на чтение (дёшево через ZREVRANK) и принимаете, что это снимок почти-реального-времени, а не непрерывно толкаемое значение, если продукт реально не требует стрима своего ранга.