Проектирование Lichess

Постановка задачи

Краткий экскурс для тех, кто мало знаком с шахматами. Два игрока ходят по очереди на одной доске, у каждого есть таймер с обратным отсчетом времени. Контроль времени бывает разным: от классических шахмат с несколькими часами на партию до блица и пули, где дается всего по минуте на игрока. В быстрых режимах у шахматистов есть буквально секунды на ход, и любая задержка сети отнимает их драгоценное время. У каждого игрока есть рейтинг (например, Эло), который определяет подбор соперников и позицию в таблице лидеров. Сначала мы спроектируем систему для одной игры, а затем углубимся в сложности масштабирования: подбор игроков, управление большим пулом игровых серверов и обеспечение честности таймеров при разной сетевой задержке у соперников.

Функциональные требования

Основные требования

1. Игроки могут находить соперников равного уровня с помощью системы подбора и запускать партию.
2. Игроки могут играть в шахматы в реальном времени.
3. Игроки могут просматривать глобальную таблицу лидеров и свое место в ней. И таблица, и место игрока обновляются вскоре после завершения партий.

За рамками задачи

1. Наблюдение за играми в реальном времени и трансляция популярных досок.
2. Внутриигровой чат, список друзей и социальные функции.
3. Задачи, обучение, послеигровой анализ или просмотр повторов партий.
4. Турниры и игры в режиме арены.
5. Защита от читерства и обнаружение шахматных движков, а также контроль честности в турнирах. В конце мы вернемся к тому, почему это интересная, но выходящая за рамки текущей задачи тема.

Нефункциональные требования

Перед тем как перейти к требованиям, определим масштаб системы, так как именно он диктует большинство архитектурных решений. Мы будем проектировать платформу под 500 тысяч одновременных партий на пике. В каждой игре участвуют два игрока со своими соединениями, что дает нам 1 миллион одновременных подключений. Кроме того, нужны вычислительные ресурсы для проверки каждого хода и ведения двух таймеров в каждой партии. Эти числа мы будем использовать во всех подробных разборах.

Основные требования

1. Низкая задержка при передаче ходов - менее 200 мс от игрока к игроку. В быстрых режимах, таких как пуля или блиц, у игроков есть считанные секунды на ход, поэтому соперник должен видеть изменения на доске мгновенно.
2. Приоритет согласованности над доступностью для состояния игры. Если игровой сервер недоступен, игра должна приостановиться, а не продолжаться с рассинхронизацией позиций на клиентах. Приостановленную игру можно восстановить, а испорченную - нет.
3. Способность масштабироваться под 500 тысяч одновременных игр (1 миллион подключений) на пике.

За рамками задачи

1. Безопасность аккаунтов и предотвращение злоупотреблений.
2. Соответствие регуляторным требованиям и конфиденциальность данных.
3. Мониторинг, журналирование и оповещения.
4. CI/CD и развертывание без простоя.

Вот как это может выглядеть на доске:

Подготовка

Планирование подхода

Будем строить систему так, как это стоит делать на реальном интервью - последовательно разбирая функциональные требования в том порядке, в каком с ними сталкивается игрок. Сначала мы объединим двух игроков в пару, затем запустим игру в реальном времени под контролем сервера и в конце обновим их позиции в таблице лидеров. Игра в реальном времени - это ядро системы, за работу которого отвечает игровой сервер, поэтому ему мы уделим максимум внимания. Когда все три основных требования заработают, мы займемся нефункциональными требованиями (масштаб, низкая задержка и честные часы) в детальных погружениях.

Основные сущности

Начнем с краткого списка основных понятий, которые понадобятся при проектировании API и модели данных. Нам пока не нужны детальные таблицы, достаточно определить общую терминологию.

1. Игрок (Player): зарегистрированный пользователь с его уникальным идентификатором и игровым рейтингом Эло. Рейтинг определяет как подбор соперников, так и положение игрока в таблице лидеров.
2. Игра (Game): отдельная шахматная партия между двумя игроками. В ней фиксируется, кто каким цветом играет, текущая позиция на доске, очередность хода, состояние таймеров и результат партии по ее завершении.
3. Ход (Move): единичное действие в игре (начальная клетка, конечная клетка, порядковый номер хода, метка времени). Ходы образуют журнал партии, который нужен для просмотра игр и разрешения спорных ситуаций.
4. Запрос на подбор (MatchRequest): заявка игрока на поиск соперника с указанием его текущего рейтинга и предпочтительного контроля времени. Контроль времени определяет длительность партии (например, 3 минуты каждому игроку плюс 2 секунды за каждый сделанный ход). Игроков можно объединять в пары только при совпадении контроля времени. Эта сущность отделена от самой игры, что упрощает проектирование подбора игроков.

Проектирование API

В системе есть два разных вида взаимодействия. Подбор игроков и таблица лидеров используют обычную модель "запрос-ответ", поэтому для них подходят REST-вызовы. Сам же игровой процесс требует непрерывного двустороннего обмена сообщениями между игроками и сервером, что делает необходимым использование WebSocket-соединения. Сначала мы спроектируем REST-эндпоинты, а затем опишем формат сообщений, передаваемых через WebSocket.

Чтобы отправить запрос на игру, игрок указывает предпочитаемый контроль времени. Мы используем метод POST, поскольку создаем новый запрос на подбор игроков MatchRequest, который система будет обрабатывать асинхронно.

POST /matchmaking -> MatchRequest
Body: {
  timeControl: string    // например, "blitz:3-2" = 3 минуты каждому, +2 секунды на ход
}

Коммуникация во время самой игры происходит через WebSocket. Как только игра создана, оба игрока подключаются к ней и обмениваются сообщениями. Здесь нет стандартных REST-методов, поэтому мы опишем сам протокол - сообщения, которые клиент отправляет серверу, и ответы, которые сервер рассылает клиентам.

WS /games/:gameId
 
Клиент -> сервер:
  sendMove   { from, to, moveNumber }
 
Сервер -> клиент:
  moveAck       { accepted, reason?, whiteTimeMs, blackTimeMs }
  opponentMove  { from, to, whiteTimeMs, blackTimeMs }
  gameEnd       { result }

Наконец, таблица лидеров - это операция чтения. Мы получаем список игроков, отсортированный по убыванию рейтинга, используя курсорную пагинацию. Также игроку нужно знать свой собственный ранг в таблице. Для этого спроектируем два GET-запроса.

GET /leaderboard?cursor={cursor}&limit={limit} -> Player[]
GET /players/:playerId/rank -> { rank, rating }

Высокоуровневый дизайн

1. Игроки могут найти соперника с помощью подбора по уровню игры и начать партию

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

Для этого добавим один сервис и одну таблицу:

1. Сервис подбора игроков: принимает запросы на игру, находит двух подходящих по уровню соперников и создает запись Game, которую затем считывает игровой сервис.
2. Таблица MatchRequests: хранит активные запросы на подбор с рейтингом игрока и выбранным им контролем времени.

Базовый сценарий работы:

1. Клиент отправляет POST-запрос в сервис подбора игроков, указывая желаемый контроль времени.
2. Сервис получает рейтинг игрока на стороне сервера и создает MatchRequest со статусом pending.
3. Сервис ищет в таблице другой ожидающий запрос с таким же контролем времени и рейтингом в определенном диапазоне, например, плюс-минус 200 очков.
4. Если подходящий запрос найден, сервис создает запись Game для двух игроков, меняет статус обоих запросов на matched и возвращает идентификатор gameId обоим участникам, чтобы они могли открыть WebSocket-соединение. Стоит заметить, что POST-запрос на подбор использует подход long polling. Он не завершается сразу после создания записи, а удерживается открытым, пока пара не будет подобрана или не истечет таймаут. В результате и тот игрок, который запустил подбор последним, и тот, кто уже ждал в очереди, получают ответ через свои незавершенные HTTP-запросы.
5. Если подходящего соперника пока нет, MatchRequest остается в состоянии pending, а связанный HTTP-запрос - незавершенным. Когда позже появится подходящий игрок и система выберет этот запрос для игры, удерживаемое соединение первого игрока завершится и вернет ему gameId. Это позволяет обойтись без дополнительных каналов уведомлений.

Можно ограничить продолжительность ожидания. Например, если за 30 секунд соперник не нашелся, мы расширяем диапазон рейтинга и повторяем попытку. Если и это не помогает, система предлагает игроку вернуться позже, вместо того чтобы заставлять его ждать бесконечно.

Этот подход хорошо работает при небольшой нагрузке. Однако при высоком трафике мы подбираем пары из сотен тысяч человек, и шаг 3 превращается в тяжелый запрос к общей таблице при каждой новой заявке. Кроме того, здесь кроется состояние гонки (race condition). Два потока сервиса подбора могут одновременно прочитать одну и ту же заявку ожидания и попытаться объединить ее со своими игроками, в результате чего один человек окажется записан сразу в две разные партии. Обычная таблица базы данных может не выдержать такой нагрузки, процесс резервирования заявки нужно защитить от гонок, а игроки с крайне высоким или низким рейтингом рискуют застрять в очереди. Все эти проблемы мы подробно разберем в детальном проектировании подбора игроков.

2. Игроки могут играть партию в реальном времени

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

Добавим игровой сервис, который будет владеть достоверным состоянием партии. Он проверяет ходы, управляет часами игроков и пересылает подтвержденные ходы оппоненту. Первое важное решение, которое нужно принять: где именно хранить активное состояние игры (позицию на доске, очередность хода и время на таймерах) во время партии.

Мы выберем вариант с состоянием и хранением доски в памяти. Шахматная партия занимает всего несколько сотен байт и длится пару минут, поэтому держать ее в памяти чрезвычайно дешево. Проверка хода в памяти гарантирует задержку на уровне микросекунд, легко укладываясь в наши требования, а журнал ходов обеспечивает быстрое восстановление. Это оставляет нам только проблемы маршрутизации и восстановления после сбоев, которые мы решим далее. Перенос состояния в общее хранилище оправдал бы себя только при очень большом объеме данных игры или при их долгой жизни, когда оперативная память стала бы дорогой, - но в шахматах это не так.

После подключения обоих игроков ход обрабатывается так:

1. После создания игры клиенты игроков открывают WebSocket-соединение с игровым сервисом, который загрузил их партию в память. Сервис связывает каждое соединение с местом игрока в партии.
2. Игрок передвигает фигуру, и его клиент отправляет сообщение sendMove по WebSocket с указанием начальной и конечной клеток.
3. Игровой сервис принимает сообщение и проверяет его по доске в памяти: является ли ход допустимым по правилам шахмат и действительно ли сейчас очередь ходить этого игрока.
4. Если ход правильный, сервис обновляет состояние доски в памяти, останавливает таймер ходившего игрока и запускает таймер его соперника.
5. Сервис сохраняет ход в надежный журнал ходов, чтобы игру можно было восстановить в случае сбоя.
6. Сервис отправляет сообщение opponentMove сопернику и подтверждение moveAck сделавшему ход игроку. Оба сообщения содержат серверное время таймеров для синхронизации сторон. При некорректном ходе отправляется отклоняющее сообщение moveAck, и состояние игры не меняется.
7. Когда игра заканчивается матом, патом, ничьей по правилам или по времени, сервис записывает результат в базу данных и отправляет сообщение gameEnd обоим игрокам. Мат и автоматические ничьи вычисляются в рамках той же проверки правил на сервере.

Доска в памяти сервера является источником истины, а база данных служит журналом восстановления вне горячего пути, который можно использовать в любой момент для пересборки текущего состояния. Обратите внимание, что шаг 5 выполняется до шага 6. Мы обязательно сохраняем ход перед тем, как разослать его. Если бы мы сначала отправили подтверждение игрокам, а затем сервер упал до записи в базу данных, восстановленная игра вернулась бы в состояние без этого хода, который игроки уже увидели на экранах. Это привело бы к несогласованности, которую мы решили избегать. Синхронное сохранение допустимо, потому что лимит в 200 мс легко вмещает запись продолжительностью несколько десятков миллисекунд. В этом случае корректность почти ничего не стоит.

3. Игроки могут просматривать глобальную таблицу лидеров и свое место в ней

Последнее требование - глобальная таблица лидеров, которая обновляется вскоре после завершения партий.

Здесь нет необходимости в новом сервисе, достаточно двух сценариев в рамках существующих компонентов:

1. Когда игра завершается, игровой сервис рассчитывает новый рейтинг Эло для обоих игроков на основе исхода партии и их рейтингов на момент начала игры (эти значения сохраняются в записи Game перед началом игры, чтобы правильно рассчитать разницу). После этого сервис обновляет рейтинг в таблице Players.
2. Эндпоинт таблицы лидеров считывает данные из таблицы Players, отсортированные по убыванию рейтинга. Для него используются курсорная пагинация и индекс по колонке рейтинга. Также игроку нужно знать свой собственный ранг. Это реализуется через два GET-запроса, которые мы описали ранее.

Поскольку рейтинги меняются только при завершении партий, таблица лидеров всегда остается актуальной без дополнительных ухищрений. А загрузка первой страницы рейтинга обходится очень дешево. При наличии BTree-индекса по колонке рейтинга запрос ORDER BY rating DESC LIMIT 50 просто считывает первые 50 записей индекса и останавливается. Поэтому даже при 10 миллионах пользователей сортировка в Postgres работает мгновенно. Не стоит пугаться большого количества строк в базе.

Проблемы начинаются при попытке узнать собственный ранг игрока. Запрос SELECT COUNT(*) FROM players WHERE rating > :myRating вынужден сканировать и подсчитывать каждую строку, которая находится выше вас. Обычный BTree-индекс гарантирует порядок сортировки, но не дает порядковый номер (позицию), поэтому здесь нет быстрого O(log n) пути, чтобы узнать, что вы находитесь, например, на 123 345-м месте. Сложность такого подсчета составляет O(rank). Дольше всего запрос работает для игроков из середины таблицы, на которых приходится большинство таких обращений. При этом место игрока входит в число самых часто запрашиваемых данных на сайте. В подробном разборе мы рассмотрим способы ускорить этот запрос.

На этом высокоуровневый дизайн готов. Игроки могут находить соперников, играть в партии с валидацией ходов на сервере и подниматься в таблице лидеров. Теперь перейдем к узким местам нашего дизайна.

Потенциальные погружения в детали

1. Как эффективно подбирать соперников при большой нагрузке?

На пике у нас запущено 500 тысяч одновременных партий, то есть в игре находятся около 1 миллиона человек. Большинство шахматных партий играется с коротким контролем времени (блиц или пуля), длится пару минут, и игроки обычно запускают новый поиск сразу после окончания партии. Таким образом, около 1 миллиона игроков создают новую заявку каждые 120 секунд. Это дает примерно 1 000 000 / 120 ~ 8000 новых заявок в секунду. Если добавить сюда вечерние пики нагрузки и турниры, эта цифра легко вырастает до пары десятков тысяч заявок в секунду.

При такой частоте сканирование таблицы для каждого запроса перестает работать. Поиск соперника - это не обычный точечный поиск по ключу. Это поиск по диапазону подходящего рейтинга при одинаковом контроле времени, за которым следует операция чтения-модификации-записи (read-modify-write) для резервирования соперника до того, как его заберет другой обработчик подбора. И десятки тысяч таких тяжелых операций в секунду будут нагружать одну и ту же таблицу ожидающих заявок.

Операция резервирования - самая сложная часть, и здесь все гораздо хуже, чем кажется на первый взгляд. Большинство игроков сосредоточены в среднем диапазоне рейтингов, где практически каждый подходит каждому. Из-за этого одни и те же несколько ожидающих игроков становятся кандидатами на подбор для большого количества входящих запросов. При использовании пессимистических блокировок (pessimistic locking) все попытки резервирования выстраиваются в очередь на блокировку популярных строк, из-за чего база данных сильно замедляется. Если выбрать оптимистическую блокировку (optimistic locking), потоки будут конкурировать за одних и тех же игроков, большинство будет проигрывать проверку compare-and-set и уходить на повторные попытки, неэффективно тратя ресурсы процессора. В обоих случаях конфликт за одни и те же записи заложен в структуре задачи, и дополнительные индексы его не устранят.

Есть и вторая проблема. У игроков с крайними рейтингами (очень сильных или очень слабых) почти никогда нет равных соперников онлайн в данный момент. Слишком узкий диапазон поиска заставит их ждать бесконечно, а широкий - приведет к игре с заведомо неравным соперником.

Мы выберем вариант с использованием Sorted Set в Redis. При обсуждении этой темы интервьюер может задать два дополнительных вопроса.

Нужно ли распределять (шардировать) пул ожидания по разным узлам Redis?

Нет, и это легко показать расчетом пропускной способности. В типичном решении для масштабирования подбора используют шардированные очереди: ожидающих игроков распределяют между множеством ключей по диапазонам рейтинга, чтобы избежать перегрузки одного ключа. Но при пиковой нагрузке около 30 тысяч запросов в секунду и примерно 4 операциях Redis на каждый запрос, суммарная нагрузка составит около 120 тысяч операций в секунду. Даже на самый популярный контроль времени будет приходиться не более 40% от этого объема, то есть около 50 тысяч операций в секунду на один ключ. Один однопоточный узел Redis выполняет несколько сотен тысяч операций над сортированными множествами в секунду. Таким образом, даже самый популярный ключ будет нагружать узел менее чем на треть, оставляя запас по производительности до того, как нам действительно понадобится шардирование.

Сам пул ожидания при этом маленький - несколько десятков тысяч небольших записей, которые занимают в памяти менее 100 МБ. Шардирование не принесет здесь ничего, кроме усложнения логики и ошибок на границах диапазонов, когда два близких по силе игрока не увидят друг друга из-за того, что попали в разные шарды. На собеседовании стоит назвать типичное решение с шардированием и на цифрах доказать, почему в данной системе оно избыточно.

Что произойдет, если узел Redis выйдет из строя?

Узел Redis - единая точка отказа ожидающего пула, поэтому запустим Redis с репликацией и автоматическим аварийным переключением. Для этого подойдет Redis Sentinel или управляемый Redis Cluster. При отказе основного узла одна из реплик станет новой основной. Смягчающим фактором здесь является то, что заявки на подбор - это эфемерные данные, а не постоянное состояние игры. Поэтому даже если при переключении текущий пул будет потерян, клиенты просто отправят запросы повторно, и очередь восстановится за несколько секунд. Требования к надежности здесь намного ниже, чем у игровых серверов, где нам нужны серьезные меры для сохранения активных партий.

2. Как масштабировать игровые серверы до 500 тыс. одновременных партий?

На этапе высокоуровневого дизайна мы выбрали архитектуру со stateful-серверами и хранением состояния партии в оперативной памяти. Теперь пришло время доказать правильность этого выбора. Именно этот аспект отличает онлайн-шахматы от обычных CRUD-приложений. Каждая активная игра удерживает два постоянных WebSocket-соединения и оперативное состояние в памяти (позицию, очередность хода и показания таймеров). При 500 тысячах одновременных игр мы получаем 1 миллион подключений и 500 тысяч небольших stateful-сессий. Один сервер может физически удерживать десятки тысяч WebSocket-соединений, но шахматный сервер при этом постоянно валидирует ходы и обновляет часы. Поэтому реальное количество игр на один узел будет скромнее, и нам понадобится от нескольких десятков до пары сотен машин. Основная сложность здесь заключается в том, что оба участника одной партии должны попадать на один игровой сервер, а падение этого сервера не должно приводить к безвозвратной потере игры.

3. Как обеспечить справедливый отсчет времени при разной сетевой задержке?

Сервер полностью контролирует шахматные часы, поэтому может запускать и останавливать таймер игрока только после фактического получения хода по сети. В результате сетевая задержка каждого игрока вычитается из его времени, хотя задержки у игроков различаются. Предположим, задержка между игроком A и сервером составляет 30 мс, а между игроком B и сервером - 200 мс. Передача каждого хода B занимает примерно на 170 мс больше, чем передача хода A, и сервер списывает эту разницу с часов игрока B. За 40 ходов трехминутной блиц-партии почти семь секунд времени B уйдет только на передачу по сети. Этого достаточно, чтобы проиграть по времени. Игроки с мобильным соединением или находящиеся далеко от сервера оказываются в невыгодном положении не по своей вине. Нужно сделать часы справедливыми.

4. Как обеспечить точность и скорость таблицы лидеров для 10 млн игроков?

В высокоуровневой архитектуре мы отметили две задачи, к которым нужно вернуться: вычисление места отдельного игрока среди 10 млн участников и надежное применение изменения рейтинга после завершения партии. Начнем с места, потому что оно создает более существенную архитектурную проблему. Обеспечение надежности записи - задача скорее техническая, поэтому рассмотрим ее в конце.

Два запроса чтения сильно отличаются по сложности. Страницу с лучшими игроками мы уже разобрали в высокоуровневой архитектуре. BTree-индекс по rating делает запрос ORDER BY rating DESC LIMIT 50 дешевым, а кэширование почти не изменяющейся страницы окончательно решает задачу. Настоящая проблема - получение места отдельного игрока. Чтобы определить место игрока среди 10 млн участников, нужен запрос COUNT(*) WHERE rating > :myRating, а BTree-индекс не может выполнить его быстрее, чем за O(rank). Индексу приходится считывать каждую запись с более высоким рейтингом. Для участника из середины таблицы это миллионы элементов индекса на один вызов, причем свое место пользователи запрашивают на этой странице чаще всего.

Остается надежно применить изменение рейтинга. Когда игра завершается, мы записываем ее исход в строку таблицы Game - это транзакционная точка фиксации результата. Рейтинг Эло игрока полностью определяется завершенными партиями. В каждой партии сохранены рейтинги участников до ее начала, поэтому изменение рейтинга можно восстановить по самой записи. Потеря значения из оперативной памяти не приводит к потере рейтинга.

Для ускорения чтения материализуем рейтинг в двух местах: в строке Players и в сортированном множестве Redis. Оба значения обновляются асинхронно после завершения игры. При этом они не расходятся, поскольку ни одно из них не является первоисточником истины. Оба значения вычисляются на основе зафиксированного исхода игры в таблице Game, а сам процесс обновления является идемпотентным. Единственная точка фиксации - запись результата партии в строку Game. После нее отдельный шаг применяет изменение Эло к строке Players и сортированному множеству. Эта операция привязана к уникальному gameId, поэтому повторное выполнение для одной и той же игры будет проигнорировано. Это гарантирует, что при сбое и повторной попытке обновления рейтинг скорректируется, а не начислится дважды.

Если какое-то обновление потеряется или Redis рассинхронизируется, периодический процесс сверки пересчитает рейтинги по истории игр и перезапишет значения, а в самом крайнем случае мы можем пересобрать отсортированное множество с нуля. Поэтому сбой в момент окончания игры не страшен: результат партии надежно сохранен, а таблица лидеров - лишь его отображение.

Дополнительные темы для обсуждения

Мы не можем охватить абсолютно все аспекты системы в рамках одного интервью. Интервьюер может продолжить обсуждение в нескольких направлениях:

1. Честная игра и борьба с читерством: использование подсказок шахматных движков - экзистенциальная угроза для онлайн-шахмат. Обнаружить игрока, который вводит позицию в движок, в рамках одной партии практически невозможно. Для выявления такого поведения нужна отдельная система машинного обучения и поведенческого анализа, работающая вне игрового контура реального времени. Она сравнивает ходы игрока с лучшими вариантами движка, изучает распределение времени на ходы, сопоставляет точность игры с историей рейтинга и передает подозрительные учетные записи на ручную проверку. Мы вынесли эту тему за рамки задачи, но упоминание ее вместе с контролем честности на турнирах показывает понимание специфики платформы.
2. Просмотр популярных партий (трансляции): партия ведущих гроссмейстеров в блиц может привлечь десятки тысяч зрителей. Это отдельная задача массовой рассылки обновлений зрителям, не имеющая ничего общего с игровым контуром "один на один". Зрителей не следует подключать непосредственно к игровому серверу, который отвечает за достоверное состояние партии. Вместо этого подтвержденные ходы должны транслироваться через шину Pub/Sub или древовидную структуру распределения данных (похожую на CDN) для подписчиков в режиме "только чтение". Небольшая задержка в пару сотен миллисекунд для зрителей абсолютно не критична, так как они не совершают активных действий в игре.
3. Хранение архива игр: каждая завершенная партия сохраняется навсегда (например, база Lichess насчитывает более 12 миллиардов игр). Это отдельная от игрового контура задача долговременного хранения данных. Архив используется для анализа после игры и для справочника дебютов, отвечающего на вопрос "какие ходы игроки обычно делают в этой позиции?". Задача проще, чем кажется: партия представляет собой последовательность ходов, сохраненную как строка. Поэтому все партии с заданным началом можно найти диапазонным поиском по префиксу последовательности без сложной структуры. Для более сложных запросов по всему архиву, например, агрегации по позиции с учетом перестановки ходов, понадобится колоночное или поисковое хранилище. Lichess индексирует партии в Elasticsearch. Но архив не должен находиться в транзакционной базе данных, обслуживающей активную игру.
4. Предходы: в сверхбыстрых шахматных режимах игроки делают ходы заранее, чтобы они выполнялись мгновенно при ходе соперника. Сильные игроки могут выстраивать целые цепочки предходов. Логика на сервере становится очень интересной: сервер должен принять, проверить и применить ход, который игрок сделал до того, как увидел реальный ответ соперника. Если ход соперника делает предход невозможным, сервер должен аккуратно сбросить цепочку. И все это должно происходить в ту самую миллисекунду, когда ход соперника доставляется на сервер, чтобы предход не отнимал время на часах игрока. Крупные шахматные платформы годами дорабатывали эти сценарии.

Чего ожидают от кандидата на каждом уровне?

Мы разобрали тему глубже, чем это обычно требуется на одном реальном интервью. Важно понимать, какие именно требования предъявляются к вам в зависимости от уровня позиции, на которую вы претендуете.

Middle

От вас ожидают работоспособный высокоуровневый дизайн, покрывающий все три основных требования: подбор игроков, игровой процесс в реальном времени с валидацией ходов сервером по WebSocket и таблицу лидеров. Самое главное - сразу понять, что валидация ходов и контроль времени происходят исключительно на сервере, а не на клиенте. Кандидат должен заметить, что 500 тыс. одновременных партий нельзя разместить на одном сервере, даже если он не предложит согласованное хеширование без подсказки. С помощью интервьюера кандидат должен прийти хотя бы к "хорошему решению" одного подробного разбора.

Senior

От инженера уровня Senior ожидается быстрое прохождение этапа высокоуровневого проектирования, чтобы основное время уделить детальному разбору сложных тем: подбору игроков при высокой нагрузке, масштабированию пула игровых серверов, честным часам и производительной таблице лидеров. Первые три темы дают максимум информации о ваших навыках, поэтому как минимум две из них нужно разобрать глубоко. Вы должны самостоятельно рассчитать масштаб системы: 1 млн соединений на 500 тысяч игр, десятки тысяч запросов в секунду на подбор. Затем этими числами нужно обосновать, почему простые подходы перестают работать. Ожидается ясное объяснение компромисса между обычными часами под управлением сервера и вариантом, который возвращает на часы игрока время, равное оценке задержки в одну сторону. Также кандидат должен объяснить маршрутизацию на основе согласованного хеширования с реестром активных игровых серверов. Решение приостановить игру при падении сервера вместо риска рассинхронизации доски - это именно то осознанное решение в пользу согласованности над доступностью, которое вы должны озвучить самостоятельно.

Staff+

От кандидата уровня Staff+ ожидается глубина анализа и инженерная зрелость, выходящие за рамки типовых ответов. Максимальный вес здесь имеет разбор темы игровых серверов. Вы должны понимать, что надежный журнал ходов сам по себе является механизмом восстановления, поэтому новому серверу достаточно проиграть несколько сотен байт ходов, а для безопасного переключения требуется только счетчик поколения, запрещающий запись замененному серверу. Ловушка избыточного проектирования - это попытки строить сложные схемы сохранения снимков или отдельные таблицы состояний, тогда как шахматная партия слишком коротка и проста для таких решений. Способность вовремя спросить: "А нужна ли здесь вообще эта сложная система?" отличает инженера уровня Staff+ от просто хорошего кандидата. Также ожидается понимание практических деталей эксплуатации системы: как маршрутизатор сессий плавно переносит игры при развертывании новых версий, как выглядит процесс переподключения со стороны клиента при аварии сервера и как настраиваются правила расширения диапазона поиска соперников на основе реальной статистики времени ожидания в очереди.