Pixel-Battle backend

Бэкенд-приложение, разрабатываемое с расчётом на нагрузки выше, чем у VK Pixel-Battle и Reddit r/place.

Предметная область

• В игре есть холст размером 1000х1000 пикселей
• Пользователи могут перекрашивать любой пиксель на холсте раз в минуту
• Новые пользователи могут начать редактировать холст только через минуту после присоединения к игре (это сделано для предотвращения обхода ограничения на редактирование раз в минуту)
• Пользователи не могут редактировать холст, когда пиксель-батл не активен
• Конфигурированием времени проведения пиксель-батла занимаются админы
• Админ может запланировать или изменить время проведения пиксель-батла, если у него есть админский ключ, соответствующий админскому ключу самого пиксель-батла
• Холст разбит на 100 чанков — областей размером 100х100 пикселей
• Каждый чанк характеризуется своим номером — ужатой минимальной позиции в своей области. Как пример, минимальная позиция чанка 1, 0 — это 100, 0, чанка 5, 6 — это 500, 600

Сценарии

Редактирования холста:

1. пользователь регестрируется в системе
2. ожидает одну минуту
3. перекрашивает пиксель
4. повторяет шаги 2 и 3 до окончания пребывания в игре

Просмотр холста:

1. пользователь собирается просматривать области холста, расположенные в рамках определённых чанков
2. клиент пользователя начинает отслеживать изменения этих чанков
3. через некоторое время просматривает их устаревшие представления вместе с актуализирующими изменениями
4. применяет актуализирущие изменения
5. применяет накопленные отслеженные изменения
6. отображает представления
7. по мере поступления новых изменений применяет их
8. повторяется шаг 7
9. пользователь прекращает просмотр областей холста, расположенных в рамках определённых чанков
10. чанки больше не отображаются и не отслеживаются

Планирование пиксель батла:

1. админ получает админский ключ вне системы.
2. планирует проведение пиксель-батла в рамках определённого временного промежутка

Реализация

Important

Все сервисы — это один сервис, разворачиваемый как несколько сервисов для точечного масштабирования.

В системе два Redis-кластера:

1. Кластер холста
2. Кластер метаданных холста

Кластер холста

Хранит данные состояния чанков.

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

Данные шарда:

• два варианта изображения чанка
• поток изменений чанка. Каждое событие — это данные отдельного пикселя, закодированные в 5 байт, где первые два — позиция, остальные три — RGB цвет (позиция хранится относительно минимальной позиции чанка, поэтому максимальное значения позиции это не 999, 999, а 99, 99)
• смещение потока изменений чанка, определяющее какие события были применены к хранимому изображению, а какие нет. Используются именно ручное хранение смещений, вместо consumer groups, из-за того, что в системе необходимо читать события, которые не нужно после этого комитить. При этом чтение может быть конкуретным
• разные распределённые локи, в рамках которых изменяются вышеперечисленные данные

Изображение чанка представляется в таких вариантах:

1. png картинка, не требующая каких-либо дополнительных преобразований для операций чтения
2. сырые пиксельные данные, не закодированные в какой-либо формат, использующиеся библеотекой Pillow в качестве данных при редактировании изображений

Вобщем, если не брать в расчёт время ввода-вывода, то с этим разделением операции чтения выполняются в ~1000 раз быстрее, а операции рефреша на 10%~30% быстрее.

Кластер метаданных холста

Хранит данные, не относящиеся к конкретным чанкам:

• Состояние пиксель-батла (временной интервал) -Оркестрирующая очередь задач (номера чанков для рефреша)
• Распределённые локи оркестратора рефреша

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

Поток данных при изменении пикселя

1. запись нового состояния пикселя происходит в chunk_writing_service, где он добавляется в очередь изменений чанка, к которому относится
2. посредством вебсокетов, chunk_streaming_service посылает новое состояние пикселя всем слушающим клиетам того чанка, к которому относится пиксель
3. копиться микробатч в очереди, перед его записью в представления
4. до тех пор, пока пиксель в микробатче, операции chunk_reading_service-а читают его (и все остальные незафиксированные состояния пикселей) из очереди как актуализирующую дельту основного изображения
5. chunk_refresh_worker приступает к рефрешу и применяет микробатч к изображениям и фиксируют его смещением

Оркестрация рефреша чанков

• chunk_refresh_worker пулит очередь задач из кластера метаданных холста и рефрешит тот чанк, команду которого он вытащил.
• chunk_refresh_orchestrator пушит очередь задач, таким образом, что команды хранятся зациклированно.

Зациклированно значит, что если существуют комманды А, Б, С, то после пулинга A, будет спулет Б, потом спулет C, а после него опять спулет A и по кругу.

Caution

В случае одновременной работы нескольких оркестраторов присутвует риск того, что команд в очереди будет больше 100 и что рефреш будет происходить немного чаще, тем самым уменьшая микробатчи некоторых чанков и увеличивая избыточное потребление ресурсов.

Несмотря на это, можно убрать риск уменьшения времени хранения микробатчей, храня расписания оркестрации (пуша), но пока это не реализовано.

При сбое всех воркеров рефреш можно запустить вручную через admin_cli.

Данные пользователей

Всего на одного пользователя необходимо сохранять только время, когда он обретёт право на перекрашивание пикселей, поэтому эти данные не хранятся на сервере, а их хранит сам клиент пользователя в качестве JWT, через http-only куку.

В действительности

Это приложение уже развёрнуто, но из-за того, что оно не испытывает нагрузку, под которую проектировалось, оно работает не в виде 8+ сервисов и 2 кластеров на множество нод, а в виде одной ноды с 1 ядром и 1 GB RAM. Оно развёрнуто как единый сервис в рамках одного процесса с тремя процессами Redis-сервера, образующими один кластер (минимально необходимое количество для создания кластера), который заменяет оба запланированных кластера.