Системный дизайн таблицы лидеров: Redis sorted set, топ-K, ранг игрока и шардирование
Как спроектировать таблицу лидеров на system design интервью: почему SQL не тянет ранг, Redis sorted set, ничьи, дневные таблицы, шардирование, топ-K, ранг игрока и приблизительный ранг.
Коротко
| Вопрос | Решение в этом разборе |
|---|---|
| Нагрузка | 100 млн игроков, около 6 тыс. обновлений очков в секунду в среднем, 30 тыс. в пике |
| Главная структура | Redis sorted set: ZADD, ZRANGE ... REV, ZREVRANK за |
| Источник правды | база с результатами матчей; Redis — производный индекс, его можно пересобрать |
| Ничьи | очки и время упакованы в один score: кто набрал раньше, тот выше |
| Периоды | отдельный ключ на день, неделю, сезон; старые ключи истекают по TTL |
| Шардирование | по игроку: топ-K собирается слиянием, ранг — суммой ZCOUNT со всех шардов |
| Длинный хвост | точный ранг нужен топу; остальным хватает «вы в топ 8%» по гистограмме |
Таблица лидеров — любимая задача на system design интервью, потому что в ней легко начать и легко утонуть. «Возьмём Redis sorted set» — правильный первый шаг, но интервьюер почти сразу спросит: а если игроков миллиард, а если Redis упал, а как показать ранг игрока на 40-миллионном месте, а что с ничьями.
Общая схема секции описана в статье про подходы к проектированию систем. Здесь она применена к одной задаче.
Шаг 1. Требования
| Вопрос | Ответ интервьюера | Что это меняет |
|---|---|---|
| Что показываем? | топ-10 и место самого игрока | две операции: топ-K и ранг по id |
| Глобальная таблица или по друзьям? | глобальная, друзья — бонус | друзья решаются отдельно, на стороне приложения |
| Как считаются очки? | сумма очков за матчи | ZINCRBY, а не перезапись |
| Периоды? | день, неделя, весь сезон | несколько ключей, у каждого свой TTL |
| Насколько свежим должен быть рейтинг? | секунды | обновляем синхронно с результатом матча |
| Что при равенстве очков? | выше тот, кто набрал раньше | время нужно зашить в score |
| Сколько игроков? | 100 млн, из них 50 млн в день | влезает ли всё в одну машину — посчитаем |
Нефункциональные требования: запись результата не должна теряться, чтение топа — десятки миллисекунд, рейтинг может отставать на пару секунд. Строгая согласованность между записью матча и местом в таблице не нужна — это важно проговорить, это разрешает асинхронное обновление и реплики.
Шаг 2. Оценка нагрузки
Считаем грубо, как в статье про оценку на салфетке:
- 50 млн активных в день, по 10 матчей — 500 млн обновлений очков в сутки. Делим на секунд: около 5–6 тыс. записей в секунду, в пике (вечер, выходные, турнир) — около 30 тыс.
- Чтения: каждый открывает таблицу пару раз после матча — того же порядка, десятки тысяч в секунду. Топ-10 одинаков для всех, его можно кэшировать на секунду.
- Память: элемент sorted set в Redis занимает порядка 100 байт (id игрока, score, узел skip list и запись в хеш-таблице). байт 10 ГБ на одну таблицу.
Вывод, который стоит произнести вслух: одна таблица на 100 млн игроков помещается в один Redis-инстанс, и 30 тыс. операций в секунду он выдержит. Шардирование здесь — ответ на вопрос «а если в 10 раз больше», а не обязательная часть с первой минуты. Кандидат, который сразу рисует 20 шардов, показывает, что не считал.
Шаг 3. Почему не просто SQL
Первая мысль — таблица scores(user_id, points) с индексом по points.
-- Топ-10: быстро, это проход по индексу SELECT user_id, points FROM scores ORDER BY points DESC LIMIT 10; -- Место игрока: медленно SELECT COUNT(*) + 1 FROM scores WHERE points > :my_points;
Топ-10 дешёвый. А вот ранг — это COUNT по всем, кто выше. Обычный B-tree индекс не хранит размеры поддеревьев, поэтому для игрока в середине таблицы база сканирует десятки миллионов записей индекса. При тысячах запросов ранга в секунду и постоянных обновлениях очков это не работает.
Нужна структура, которая умеет и вставку, и «сколько элементов больше X» за логарифм. Это сбалансированное дерево с размерами поддеревьев или skip list с длинами ссылок. Писать её самим не нужно — она уже есть в Redis.
Шаг 4. Redis sorted set
Sorted set (zset) — это хеш-таблица member → score плюс skip list, упорядоченный по score. Хеш даёт ZSCORE за , skip list хранит длину каждого «прыжка» и поэтому знает позицию элемента.
| Операция | Команда | Сложность |
|---|---|---|
| Добавить очки за матч | ZINCRBY lb:season:12 150 user:42 | |
| Топ-10 | ZRANGE lb:season:12 0 9 REV WITHSCORES | |
| Место игрока (с нуля) | ZREVRANK lb:season:12 user:42 | |
| Соседи по таблице | ZRANGE lb:season:12 r-5 r+5 REV | |
| Сколько игроков выше score | ZCOUNT lb:season:12 (s +inf | |
| Очки нескольких друзей | ZMSCORE lb:season:12 user:1 user:7 ... |
ZRANGE ... REV появился в Redis 6.2, в старых версиях то же делает ZREVRANGE. ZREVRANK возвращает индекс с нуля, на экран выводим rank + 1.
Ничьи
У Redis при равном score порядок лексикографический по имени элемента — то есть случайный с точки зрения игры. Если правило «кто раньше набрал, тот выше», время нужно зашить в сам score.
Score в Redis — это double, точно хранит целые до . Отдадим младшие 32 бита под инвертированное время (раньше — значит больше), старшие — под очки:
MAX_TS = 2**32 # секунды, хватит до 2106 года SHIFT = 2**32 def encode(points, ts): # больше очков — выше; при равенстве выше тот, кто набрал раньше return points * SHIFT + (MAX_TS - 1 - ts) def decode(score): return score // SHIFT, MAX_TS - 1 - score % SHIFT s1 = encode(500, 1_700_000_000) s2 = encode(500, 1_700_000_100) print(s1 > s2, decode(s1)) # True (500, 1700000000) print(encode(2**21 - 1, 0) < 2**53) # True: до 2 млн очков точность не теряется
Плата за трюк: на очки остаётся 21 бит, около 2 млн. Если очков больше, сокращаем точность времени (минуты вместо секунд) или считаем время от начала сезона. И ZINCRBY с упакованным score уже не работает напрямую: обновление становится «прочитать очки, прибавить, записать новый score» — это делается Lua-скриптом атомарно на сервере Redis.
Периоды
Для каждого периода свой ключ: lb:day:2026-11-10, lb:week:2026-46, lb:season:12. Результат матча пишется во все три (в одном MULTI или Lua-скрипте), у дневного ключа EXPIRE на пару суток. Недельную таблицу можно не вести отдельно, а собрать из дневных через ZUNIONSTORE — но для 100 млн игроков это тяжёлая операция, лучше писать сразу в недельный ключ.
Шаг 5. Общая схема
Игровой сервер ──► Score API ──► БД матчей (источник правды)
│
└──► очередь ──► Leaderboard Worker ──► Redis (primary + реплики)
▲
Клиент ──► Leaderboard API ─────────────────────────────────────────┘
│
└── кэш топ-10 на 1 с
Ключевые решения:
- Redis — не источник правды. Результаты матчей пишутся в базу, а таблица лидеров — это производный индекс. Если Redis потерял данные (а при асинхронной репликации он может потерять последние секунды записей), индекс пересобирается из базы. Без этой фразы интервьюер спросит «а что если Redis упал» и будет прав.
- Очередь между записью и индексом. Событие «матч завершён» уходит в очередь сообщений, воркер обновляет Redis. Очередь сглаживает пики и позволяет перечитать события после аварии. Чтобы событие не потерялось между коммитом в базу и отправкой в очередь, используют transactional outbox.
- Дедупликация. Очередь доставляет минимум один раз, а
ZINCRBYне идемпотентен: повтор начислит очки дважды. Воркер запоминаетmatch_id(например,SET processed:<match_id> 1 NX EX 86400) и пропускает повторы — подробнее в статье про идемпотентность. - Чтение с реплик. Ранг и соседи читаются с реплик, топ-10 — из короткого кэша. Отставание реплики на долю секунды здесь никому не мешает.
- Античит — отдельный сервис до Score API: очки приходят от игрового сервера, а не от клиента.
Шаг 6. Если игроков в 10–100 раз больше
Допустим, миллиард игроков или сотни турнирных таблиц одновременно. Одного инстанса не хватает ни по памяти, ни по записи. Есть два способа резать данные — разбор шардирования в целом есть в статье про шардирование и репликацию.
Вариант А: по диапазонам очков
Шард 1 — очки от 0 до 1000, шард 2 — от 1000 до 5000 и так далее. Ранг считается просто: сумма размеров всех шардов выше плюс локальный ранг. Топ-10 — с одного верхнего шарда.
Минусы серьёзные. Распределение очков неравномерное: в нижнем шарде окажется большинство игроков. Когда игрок набирает очки, он переезжает между шардами — это удаление на одном узле и вставка на другом, не атомарно. А границы приходится двигать в течение сезона, потому что очки у всех растут.
Вариант Б: по игроку
Шард выбирается по hash(user_id) — нагрузка ровная, переездов нет, для добавления узлов подходит консистентное хеширование. Зато обе операции становятся scatter-gather:
- Топ-K: каждый шард отдаёт свой топ-K, сервис сливает списков и берёт K лучших. Глобальный топ-K обязательно содержится в объединении локальных топ-K — это та же идея, что в задаче top-k frequent.
- Ранг: узнаём score игрока на его шарде, затем на каждом шарде
ZCOUNT key (score +infи складываем. запросов по .
Модель на Python, которая проверяет, что слияние и сумма дают те же ответы, что и одна большая таблица:
import heapq import random from bisect import bisect_right class Shard: """Модель одного Redis-узла: отсортированный список (score, user).""" def __init__(self): self.items = [] def add(self, user, score): self.items.append((score, user)) def finalize(self): self.items.sort() self.scores = [s for s, _ in self.items] def top(self, k): # ZRANGE key 0 k-1 REV WITHSCORES return self.items[::-1][:k] def count_above(self, score): # ZCOUNT key (score +inf return len(self.scores) - bisect_right(self.scores, score) def global_top(shards, k): candidates = (item for sh in shards for item in sh.top(k)) return heapq.nlargest(k, candidates) def global_rank(shards, score): return 1 + sum(sh.count_above(score) for sh in shards) random.seed(7) shards = [Shard() for _ in range(4)] everyone = [] for uid in range(10_000): score = random.randint(0, 1_000_000) shards[hash(uid) % 4].add(uid, score) everyone.append((score, uid)) for sh in shards: sh.finalize() everyone.sort(reverse=True) assert global_top(shards, 10) == everyone[:10] score, uid = everyone[1234] print(global_rank(shards, score)) # 1235 — совпадает с честным подсчётом
Топ-K, который нужен всем, не стоит собирать на каждый запрос: отдельный процесс раз в секунду сливает топы шардов и кладёт результат в кэш. Ранг конкретного игрока остаётся scatter-gather, но параллельных запросов к Redis — это единицы миллисекунд.
Шаг 7. Приблизительный ранг для длинного хвоста
Игроку на 40-миллионном месте не важно, 40 128 312-й он или 40 128 900-й. Ему достаточно «вы в топ 41%». Это открывает дешёвое решение, которое любят слышать на интервью: точная таблица только для верхних, скажем, 100 тыс. игроков, а для остальных — гистограмма.
Делим диапазон очков на корзины и храним количество игроков в каждой (счётчики INCR/DECR при переходе игрока между корзинами). Ранг = все игроки в корзинах выше + доля своей корзины:
from bisect import bisect_right # Границы корзин по очкам и сколько игроков в каждой bounds = [0, 100, 500, 1_000, 5_000, 10_000, 50_000] counts = [4_000_000, 3_000_000, 1_500_000, 900_000, 80_000, 15_000, 5_000] def approx_rank(score): i = bisect_right(bounds, score) - 1 above = sum(counts[i + 1:]) lo = bounds[i] hi = bounds[i + 1] if i + 1 < len(bounds) else score + 1 # внутри корзины считаем игроков распределёнными равномерно share_above = (hi - score) / (hi - lo) return int(above + counts[i] * share_above) + 1 total = sum(counts) r = approx_rank(2_000) print(r, f"топ {100 * r / total:.1f}%") # 775001 топ 8.2%
Корзин — сотни или тысячи, они помещаются в память любого сервиса. Чем мельче корзины в плотной части распределения, тем точнее ответ. Похожим образом работают перцентили в системах метрик.
Шаг 8. Таблица среди друзей
Глобальный индекс тут не помогает: у каждого игрока свой набор из 50–500 друзей. Решение простое — ZMSCORE по списку друзей и сортировка в приложении: на запрос, для сотен друзей это ничто. Заводить отдельный sorted set на каждого игрока не нужно: одно обновление очков пришлось бы писать в сотни таблиц.
Узкие места и вопросы вглубь
| Вопрос интервьюера | Ответ |
|---|---|
| Redis упал и потерял данные | пересобираем из БД матчей; на время сборки показываем топ из кэша |
| Миллион игроков закончил турнир разом | очередь сглаживает пик, воркеры пишут батчами через pipeline |
| Горячий ключ топ-10 | кэш на 1 с в сервисе и CDN, Redis видит один запрос в секунду |
| Ранг дрожит, пока очки обновляются | нормально: явно договорились о согласованности в пределах секунд |
| Сброс сезона | новый ключ lb:season:13, старый архивируется в БД и удаляется |
| Таблица по странам | ещё один ключ на страну, запись в несколько ключей в одном Lua-скрипте |
Типичные ошибки на интервью
- Сразу шардировать. Сначала посчитайте: 100 млн записей по 100 байт — 10 ГБ, это одна машина. Шардирование — ответ на рост, а не стартовая точка.
- Ранг через
COUNT(*)в SQL без обсуждения стоимости. Интервьюер ждёт, что вы заметите линейный скан. - Redis как единственное хранилище. Нужен источник правды и способ пересобрать индекс.
- Забыть про ничьи. Вопрос «кто выше при равных очках» задают почти всегда.
ZINCRBYбез дедупликации. При доставке «минимум один раз» очки начислятся дважды.- Точный ранг для всех. Для хвоста таблицы приблизительный ответ дешевле и никого не огорчает.
Что запомнить
- Таблица лидеров — это две операции: топ-K и ранг по id. SQL хорош для первой и плох для второй.
- Redis sorted set даёт обе за благодаря skip list, который знает позиции.
- Ничьи решаются упаковкой времени в младшие биты score, помня про .
- Redis — производный индекс; правда лежит в базе, события идут через очередь с дедупликацией.
- При шардировании по игроку топ-K собирается слиянием локальных топов, ранг — суммой
ZCOUNT. - Длинному хвосту хватает гистограммы и процентов.
Соседние разборы: выдача ленты новостей, где тоже есть топ-K и кэш горячих данных, и стратегии кэширования.