Files

T

Slavasil 50e8aacfa9 add tests for controllers and ActionCable channels; improve main backend docs

2026-10-27 10:32:40 +03:00

16 KiB

Raw Permalink Blame History

Алгоритм матчмейкинга (Matchmaking Algorithm)

Документ содержит подробное описание алгоритма подбора соперников в Ruby Sea Battle, структур данных Redis, математической модели допуска рейтинга, механизмов атомарности и отказоустойчивости.

1. Цели и требования к системе

Матчмейкинг отвечает за сведение двух игроков в онлайн-матч и решает следующие задачи:

Баланс по навыку (рейтингу): игроки со схожим рейтингом должны играть друг с другом.
Минимизация времени ожидания: если идеального соперника нет, допустимая разница в рейтинге со временем плавно увеличивается.
Строгая атомарность и исключение race conditions: ни один игрок не может быть одновременно взят в два разных матча при конкурентных запросах.
Отказоустойчивость (Fault Tolerance): сбой процесса сервера между нахождением пары и генерацией JWT-токенов не должен приводить к потере игроков из очереди.
Надёжная доставка результата: матч должен быть доставлен игроку даже при кратковременном разрыве WebSocket-соединения.

2. Структуры данных в Redis

Все данные матчмейкинга хранятся в Redis и имеют ограниченное время жизни (TTL):

Ключ	Тип данных Redis	Значение / Элемент	Назначение
`mm:queue`	Sorted Set	`score` = `rating`, `member` = `user_id`	Основная очередь игроков, ожидающих матч. Отсортирована по рейтингу для быстрого диапазонного поиска (`ZRANGEBYSCORE`).
`mm:since`	Hash	`field` = `user_id`, `value` = `timestamp` (мс)	Время входа игрока в очередь в миллисекундах. Используется для расчёта времени ожидания.
`mm:rating`	Hash	`field` = `user_id`, `value` = `rating`	Сохранённый рейтинг игрока. Необходим для возврата игрока в очередь при сбое на этапе финализации (`requeue`).
`mm:pending`	Sorted Set	`score` = `timestamp` спаривания (мс), `member` = `user_id`	Игроки, для которых пара найдена, но генерация матча и JWT ещё выполняется в Ruby.
`mm:match:<match_id>`	String (JSON)	Полный payload матча	Данные матча (TTL = `MATCHMAKING_MATCH_TTL`, по умолчанию 120 сек).
`mm:user:<user_id>`	String (JSON)	Копия payload матча	Индивидуальный указатель для игрока для механизма `claim` при реконнекте (TTL = `MATCHMAKING_MATCH_TTL`).

3. Модель динамического допуска рейтинга (Rating Tolerance)

Чтобы игроки быстро находили матч даже при небольшом онлайне, допуск по рейтингу плавно растёт с течением времени ожидания.

Формула допуска

Для игрока с временем постановки в очередь t_{\text{start}} в текущий момент времени t_{\text{now}}:

\Delta t = \frac{t_{\text{now}} - t_{\text{start}}}{1000} \quad \text{(секунды ожидания)}

\text{tolerance}(\Delta t) = \min\Big(\text{base\_range} + \Delta t \times \text{range\_per\_second}, \; \text{max\_range}\Big)

Конфигурационные параметры (из `Rails.application.config.x.matchmaking`)

base_range = 100 — начальный допуск рейтинга в момент входа в очередь.
range_per_second = 50 — прирост допуска за каждую секунду ожидания.
max_range = 1000 — верхний предел допуска рейтинга.
queue_ttl = 60 сек — максимальное время нахождения в очереди до таймаута.

Динамика расширения диапазона

Время ожидания (`\Delta t`)	Допуск (`\pm` очков рейтинга)	Диапазон при рейтинге 1000
0 секунд	`\pm 100`	[900 ... 1100]
2 секунды	`\pm 200`	[800 ... 1200]
6 секунд	`\pm 400`	[600 ... 1400]
10 секунд	`\pm 600`	[400 ... 1600]
18+ секунд	`\pm 1000` (максимум)	[0 ... 2000]

Правило симметрии для пары

При периодической сверке очереди (sweep) пара (A, B) считается совместимой, если:

| \text{rating}_A - \text{rating}_B | \le \text{tolerance}\big(\min(t_{\text{since}}(A), t_{\text{since}}(B))\big)

То есть допуск рассчитывается по дольше ожидающему игроку из пары. Это предотвращает дискриминацию игроков, которые долго ждут в очереди.

4. Двухфазный алгоритм подбора (Two-Phase Matchmaking)

Подбор разделен на две взаимодополняющие фазы:

[Игрок отправляет start]
          │
          ▼
   Фаза 1: Немедленный поиск (enqueue в Lua)
          ├─► Подходящий соперник найден ──► [Перевод в pending] ──► [Генерация матча]
          └─► Соперник не найден ──────────► [Добавление в mm:queue]
                                                      │
                                                      ▼
                                       Фаза 2: Фоновая сверка (sweep)
                                              (каждые 2 сек)
                                                      ├─► Расширение допуска и спаривание
                                                      ├─► Таймаут (waited > queue_ttl)
                                                      └─► Requeue зависших игроков

Фаза 1: Синхронная проверка при входе (`enqueue`)

Выполняется мгновенно в контексте команды WebSocket start:

Вызывается Redis Lua-скрипт PAIR_SCRIPT с аргументом mode = "enqueue".
Из очереди принудительно удаляются предыдущие записи этого пользователя (сброс сессии ожидания).
Через ZRANGEBYSCORE mm:queue (rating - max_range) (rating + max_range) запрашиваются потенциальные кандидаты.
Среди кандидатов выбирается игрок с минимальной разницей в рейтинге, у которого: | \text{rating} - \text{other\_rating} | \le \text{tolerance}(\text{other\_since})
Если кандидат найден:
- Оба игрока атомарно удаляются из mm:queue, mm:since, mm:rating.
- Оба игрока добавляются в mm:pending с текущим временем.
- Скрипт возвращает строку вида "P:<id1>:<id2>".
Если кандидат не найден:
- Игрок сохраняется в mm:queue с весом rating.
- В mm:since записывается время входа.
- В mm:rating сохраняется рейтинг игрока.

Фаза 2: Периодическая фоновая сверка (`sweep`)

Каждые MATCHMAKING_SWEEP_INTERVAL секунд (по умолчанию каждые 2 секунды) запускается фоновая задача MatchmakingSweepJob, вызывающая MatchmakingService.sweep:

Вызывается Redis Lua-скрипт PAIR_SCRIPT с аргументом mode = "sweep".
Из mm:queue считываются все ожидающие игроки со своими рейтингами и временем ожидания.
Массив сортируется по возрастанию рейтинга: O(N \log N).
Выполняется жадный проход:
- Если текущий игрок ждёт дольше queue_ttl (60 сек): он помечается как экспирированный ("E:<id>").
- Иначе ищется ближайший по рейтингу свободный соперник в списке, для которого разница в рейтинге не превышает допуск по времени ожидания более старого игрока.
- При нахождении оба игрока помечаются как использованные и добавляются в результат ("P:<id1>:<id2>").
Все найденные пары атомарно переносятся из mm:queue в mm:pending, а экспирированные игроки удаляются из очереди.
Requeue (защита от падений):
- Запрашиваются все игроки из mm:pending, находящиеся там дольше pending_ttl (15 сек).
- Если для игрока ключ матча mm:user:<uid> так и не был создан (например, Ruby-процесс упал при генерации токена), игрок автоматически возвращается назад в mm:queue со своим исходным рейтингом.

5. Создание матча и атомарная финализация

Когда Lua-скрипт возвращает сформированную пару "P:<id1>:<id2>":

Генерация идентификаторов и токенов в Ruby:
- Генерируется уникальный UUID матча: match_id = SecureRandom.uuid.
- Генерируется JWT-токен для game-server:
```
JwtService.encode(
  match_id: match_id,
  player1_id: player1_id,
  player2_id: player2_id,
  game_server: config.game_server_url,
  exp: config.token_ttl.seconds.from_now.to_i
)
```
Атомарная финализация в Redis (FINALIZE_SCRIPT):
- Сохраняет mm:match:<match_id> с TTL.
- Сохраняет указатели mm:user:<player1_id> и mm:user:<player2_id> с тем же TTL.
- Удаляет обоих игроков из mm:pending, mm:rating, mm:since.
Push-уведомление через Action Cable:
- Для каждого игрока выполняется атомарное чтение и удаление указателя: redis.getdel("mm:user:<id>").
- Если указатель успешно прочитан, сообщение с типом matched отправляется в персональный поток пользователя: MatchmakingChannel.broadcast_to(user_id, payload).

6. Гарантия доставки (At-most-once & Reconnection)

Если в момент формирования матча у пользователя произошёл кратковременный разрыв соединения или переподключение:

Сообщение broadcast могло быть отправлено в момент отсутствия активного WebSocket-клиента.
Персональный ключ mm:user:<user_id> сохраняется в Redis до момента подтверждённой доставки.
При повторном подключении к WebSocket метод MatchmakingChannel#subscribed вызывает:
```
if match = MatchmakingService.claim(current_user.id)
  transmit(match)
end
```
Метод claim выполняет Redis-команду GETDEL mm:user:<user_id>, что гарантирует:
1. Матч будет немедленно доставлен клиенту при переподключении.
2. Никакой матч не может быть получен дважды (атомарное удаление при первой же выдаче).

7. Диаграммы взаимодействия

Sequence Diagram: Успешный подбор матча

sequenceDiagram
    autonumber
    actor PlayerA as Игрок A
    actor PlayerB as Игрок B
    participant AC as ActionCable (MatchmakingChannel)
    participant MS as MatchmakingService
    participant Redis as Redis (Lua Scripts)
    participant Game as Game Server (Go)

    PlayerA->>AC: subscribe
    PlayerA->>AC: action: "start"
    AC->>MS: enqueue(PlayerA)
    MS->>Redis: eval PAIR_SCRIPT (enqueue)
    Redis-->>MS: соперник не найден -> добавлен в mm:queue

    PlayerB->>AC: subscribe
    PlayerB->>AC: action: "start"
    AC->>MS: enqueue(PlayerB)
    MS->>Redis: eval PAIR_SCRIPT (enqueue)
    Redis-->>MS: пара сформирована! (P:PlayerB:PlayerA)

    MS->>MS: генерация match_id (UUID) и game_token (JWT)
    MS->>Redis: eval FINALIZE_SCRIPT (сохранить матч, перевести из pending)
    MS->>Redis: getdel mm:user:PlayerA & mm:user:PlayerB
    MS->>AC: broadcast_to(PlayerA, matched)
    MS->>AC: broadcast_to(PlayerB, matched)
    AC-->>PlayerA: message { type: "matched", match_id, game_token, game_server }
    AC-->>PlayerB: message { type: "matched", match_id, game_token, game_server }

    PlayerA->>Game: WebSocket connect(game_token)
    PlayerB->>Game: WebSocket connect(game_token)

State Diagram: Жизненный цикл игрока в матчмейкинге

stateDiagram-v2
    [*] --> Idle: Пользователь авторизован

    Idle --> Queued: Отправка action "start" (enqueue)
    Queued --> Pending: Найден соперник в Phase 1 или Phase 2
    Queued --> Idle: Отправка action "stop" / разрыв сокета (cancel)
    Queued --> TimedOut: Ожидание > MATCHMAKING_QUEUE_TTL

    TimedOut --> Idle: Уведомление { type: "timeout" }

    Pending --> Matched: Успешная финализация (генерация токена)
    Pending --> Queued: Сбой финализации (requeue через 15 сек)

    Matched --> InGame: Подключение к Game Server по game_token
    InGame --> Idle: Завершение игры

16 KiB Raw Permalink Blame History Unescape Escape