Спроектируйте real-time лидерборд на миллионы игроков

Question

IT Interview Practice · Accepted Answer

**Используйте sorted set (ZSET) в Redis по ключу-счёту: ранг и top-N становятся встроенными операциями O(log N), так что вы никогда не сортируете миллионы строк на каждый запрос.** ZSET автоматически держит элементы упорядоченными по счёту; это ровно то, чем является лидерборд.

## Архитектура

```text
Game svc ──ZADD score──▶ Redis ZSET (sorted by score) ──ZREVRANGE 0 99──▶ Top-100 API
                              │
                              ├─ ZREVRANK user ─▶ "your rank" (around-me: rank±5)
                              └─ AOF/RDB + async ─▶ Postgres (durable source of truth)
```

## Как это работает

- **ZADD** делает upsert счёта игрока за O(log N). Redis поддерживает порядок через **skip list**, поэтому пересортировка не нужна.
- **Top-N**: `ZREVRANGE board 0 99 WITHSCORES` возвращает top-100 за O(log N + 100).
- **Ваш ранг**: `ZREVRANK board user` даёт позицию с нуля; **around-me** — это `ZREVRANGE rank-5 rank+5` — срез игроков рядом с вами.
- **Durability**: Redis in-memory. Включите **AOF** (append-only file) для переигрывания и асинхронно зеркальте счета в **Postgres** как истинную систему записи, чтобы потеря Redis была восстановима.

## Sharding для миллионов пользователей

Один ZSET нормально держит десятки миллионов элементов (ограничен памятью, ~100 МБ на 1 млн записей). За этим пределом или для глобального масштаба **шардируйте по диапазону счёта** (0–1k, 1k–10k…), чтобы каждый шард был непрерывной полосой — глобальный top-N читает только верхний шард. Избегайте шардирования по хешу пользователя: пересобирать ранги по случайным шардам дорого.

## Взгляд с точки зрения интервью

Интервьюер хочет увидеть, что вы **тянетесь к правильной структуре данных**, а не к `ORDER BY score LIMIT 100` на SQL (который пересортировывает при каждом обращении и умирает под нагрузкой записи). Хорошие ответы называют ZSET; отличные покрывают **around-me запросы, ничьи, персистентность и стратегию шардинга**. Классическая ловушка: забыть, что Redis волатилен, и относиться к нему как к источнику истины — рестарт стирает борд, если нет AOF/RDB или зеркала в БД.

## Компромиссы и сбои

- **Ничьи.** Равные счета упорядочиваются лексикографически по элементу, что выглядит случайно. Закодируйте тайбрейкер в счёт (например, `score * 1e13 - timestamp`), чтобы достигшие раньше ранжировались выше.
- **Горячий ключ.** Единственный глобальный ZSET — это один ключ на одном шарде, hotspot записи. Буферизуйте/батчите `ZADD`, либо используйте борды с временными бакетами (дневные/недельные), чтобы распределить нагрузку.
- **Консистентность.** Чтения могут отставать от асинхронного зеркала в БД на секунды — нормально для лидербордов, но не для выплат; сверяйтесь с Postgres перед выдачей призов.
- **Стоимость памяти.** Миллионы элементов стоят реальной RAM; истекайте сезонные борды через TTL.
- **Когда не нужно:** лидерборд на несколько тысяч, обновляемый раз в минуту, нормально сделать кэшированным SQL-запросом — ZSET Redis блистает, когда записи постоянны, а ранг должен быть мгновенным.

Архитектура

Как это работает

Sharding для миллионов пользователей

Взгляд с точки зрения интервью

Компромиссы и сбои

Похожие вопросы