228 lines
16 KiB
Markdown
228 lines
16 KiB
Markdown
# Алгоритм матчмейкинга (Matchmaking Algorithm)
|
||
|
||
Документ содержит подробное описание алгоритма подбора соперников в `Ruby Sea Battle`, структур данных Redis, математической модели допуска рейтинга, механизмов атомарности и отказоустойчивости.
|
||
|
||
---
|
||
|
||
## 1. Цели и требования к системе
|
||
|
||
Матчмейкинг отвечает за сведение двух игроков в онлайн-матч и решает следующие задачи:
|
||
1. **Баланс по навыку (рейтингу):** игроки со схожим рейтингом должны играть друг с другом.
|
||
2. **Минимизация времени ожидания:** если идеального соперника нет, допустимая разница в рейтинге со временем плавно увеличивается.
|
||
3. **Строгая атомарность и исключение race conditions:** ни один игрок не может быть одновременно взят в два разных матча при конкурентных запросах.
|
||
4. **Отказоустойчивость (Fault Tolerance):** сбой процесса сервера между нахождением пары и генерацией JWT-токенов не должен приводить к потере игроков из очереди.
|
||
5. **Надёжная доставка результата:** матч должен быть доставлен игроку даже при кратковременном разрыве 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`:
|
||
1. Вызывается Redis Lua-скрипт `PAIR_SCRIPT` с аргументом `mode = "enqueue"`.
|
||
2. Из очереди принудительно удаляются предыдущие записи этого пользователя (сброс сессии ожидания).
|
||
3. Через `ZRANGEBYSCORE mm:queue (rating - max_range) (rating + max_range)` запрашиваются потенциальные кандидаты.
|
||
4. Среди кандидатов выбирается игрок с **минимальной разницей в рейтинге**, у которого:
|
||
$$| \text{rating} - \text{other\_rating} | \le \text{tolerance}(\text{other\_since})$$
|
||
5. **Если кандидат найден:**
|
||
- Оба игрока атомарно удаляются из `mm:queue`, `mm:since`, `mm:rating`.
|
||
- Оба игрока добавляются в `mm:pending` с текущим временем.
|
||
- Скрипт возвращает строку вида `"P:<id1>:<id2>"`.
|
||
6. **Если кандидат не найден:**
|
||
- Игрок сохраняется в `mm:queue` с весом `rating`.
|
||
- В `mm:since` записывается время входа.
|
||
- В `mm:rating` сохраняется рейтинг игрока.
|
||
|
||
### Фаза 2: Периодическая фоновая сверка (`sweep`)
|
||
|
||
Каждые `MATCHMAKING_SWEEP_INTERVAL` секунд (по умолчанию каждые 2 секунды) запускается фоновая задача `MatchmakingSweepJob`, вызывающая `MatchmakingService.sweep`:
|
||
|
||
1. Вызывается Redis Lua-скрипт `PAIR_SCRIPT` с аргументом `mode = "sweep"`.
|
||
2. Из `mm:queue` считываются все ожидающие игроки со своими рейтингами и временем ожидания.
|
||
3. Массив сортируется по возрастанию рейтинга: $O(N \log N)$.
|
||
4. Выполняется жадный проход:
|
||
- Если текущий игрок ждёт дольше `queue_ttl` (60 сек): он помечается как экспирированный (`"E:<id>"`).
|
||
- Иначе ищется ближайший по рейтингу свободный соперник в списке, для которого разница в рейтинге не превышает допуск по времени ожидания более старого игрока.
|
||
- При нахождении оба игрока помечаются как использованные и добавляются в результат (`"P:<id1>:<id2>"`).
|
||
5. Все найденные пары атомарно переносятся из `mm:queue` в `mm:pending`, а экспирированные игроки удаляются из очереди.
|
||
6. **Requeue (защита от падений):**
|
||
- Запрашиваются все игроки из `mm:pending`, находящиеся там дольше `pending_ttl` (15 сек).
|
||
- Если для игрока ключ матча `mm:user:<uid>` так и не был создан (например, Ruby-процесс упал при генерации токена), игрок автоматически возвращается назад в `mm:queue` со своим исходным рейтингом.
|
||
|
||
---
|
||
|
||
## 5. Создание матча и атомарная финализация
|
||
|
||
Когда Lua-скрипт возвращает сформированную пару `"P:<id1>:<id2>"`:
|
||
|
||
1. **Генерация идентификаторов и токенов в Ruby:**
|
||
- Генерируется уникальный UUID матча: `match_id = SecureRandom.uuid`.
|
||
- Генерируется JWT-токен для `game-server`:
|
||
```ruby
|
||
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
|
||
)
|
||
```
|
||
2. **Атомарная финализация в Redis (`FINALIZE_SCRIPT`):**
|
||
- Сохраняет `mm:match:<match_id>` с TTL.
|
||
- Сохраняет указатели `mm:user:<player1_id>` и `mm:user:<player2_id>` с тем же TTL.
|
||
- Удаляет обоих игроков из `mm:pending`, `mm:rating`, `mm:since`.
|
||
3. **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` вызывает:
|
||
```ruby
|
||
if match = MatchmakingService.claim(current_user.id)
|
||
transmit(match)
|
||
end
|
||
```
|
||
- Метод `claim` выполняет Redis-команду `GETDEL mm:user:<user_id>`, что гарантирует:
|
||
1. Матч будет немедленно доставлен клиенту при переподключении.
|
||
2. Никакой матч не может быть получен дважды (атомарное удаление при первой же выдаче).
|
||
|
||
---
|
||
|
||
## 7. Диаграммы взаимодействия
|
||
|
||
### Sequence Diagram: Успешный подбор матча
|
||
|
||
```mermaid
|
||
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: Жизненный цикл игрока в матчмейкинге
|
||
|
||
```mermaid
|
||
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: Завершение игры
|
||
```
|