О программировании, ошибках и опыте на примере сервера онлайн игры

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


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


Задача:  необходимо разработать сервер и клиент для игры через интернет, с количеством одновременно играющих игроков не менее 1000.


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


Выбор языка программирования


Из знакомых мне языков, с помощью которых можно было бы реализовать, были следующие: php, c#, c++. Из плохо известных: Java. Остальные не рассматривались ввиду отсутствия опыта работы с ними.


За год до этого был опыт разработки более упрощенной задачи подобного вида, при этом стояло жесткое условие: язык программирования PHP. Так что я сполна оценил все недостатки этого языка применительно к подобной задаче (все же он предназначен для других целей, хотя при желании и топором можно торт нарезать, но что из этого выйдет – вопрос интересный). С# представлялось сложным использовать на Debian. Java был отклонен ввиду маленького опыта работы с ним. Вероятно, люди, хорошо в нем разбирающиеся, смогли бы качественно реализовать подобный сервер. В итоге: C++.


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


Вывод: стоит использовать наиболее подходящий инструмент, исходя из требований, окружения, своих знаний, желания расширить свои профессиональные качества (конечно если это не идет вразрез, например, со временем выполнения задачи, а то ведь я и Java хотел получше изучить, но боюсь, заказчик остался бы недоволен сроками :).



Выбор инструментов языка


Тут тоже было просто. Исходя из того, что разработка велась на Windows 7, а работать должно на Debian, все средства должны быть переносимы. В качестве основы кроссплатформенности была выбрана библиотека boost. Основную роль сыграло то, что boost является основой для вышедшего и следующих стандартов языка C++, других значительных «за и против» применительно к данной задаче я не нашел (сравнивания например с Qt). Как позже выяснилось, нужны были только базовые возможности библиотеки (потоки, работа с файловой системой), а потому не было особой разницы, что выбирать.


Вывод: если не находишь разницы между вариантами, выбери любой :), и делай, там будет видно.



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


Любопытна склонность к необоснованному преувеличению сложности программы. Это проявляется как на уровне алгоритмов и структур данных (желание сразу все оптимизировать), так и на уровне архитектуры приложения (к примеру, попытка сделать все сверхпараллельно). И как следствие: рост сложности программы, отсюда большее число ошибок и возрастающая трудность в их исправлении, отсюда затягивание сроков, нервы и т.д. Кому такое надо? Правильно, никому.


Как сказано в одной книге: «программирование – есть управление сложностью».


Взять хотя бы конкретный пример (задачи конкурса Acceller8). За время конкурса решение эволюционировало и прошло следующие этапы:


  1. Используем библиотеку TBB. И сразу пошло-пошло распараллеливание по задачам. Что будет дальше не знаю, но точно будет много потоков (не сделал, осталось только в планах).

  2. Запущенны N потоков стандартной функцией, они из общего массива каждый в своем порядке (чтобы не мешать друг другу) берут матрицы для вычисления и считают, когда очередь заканчивается они просматривают сначала потоки, запущенные на этом же процессоре, чтоб им помочь. Если на этом процессоре потоки всё посчитали, то поиск производиться на других (реализовано).

  3. Запущенны N потоков стандартной функцией, они из очереди подряд берут матрицы для вычисления и считают, когда очередь заканчивается они просматривают подряд все другие потоки, чтоб им помочь (реализовано).

  4. Запущенны N потоков стандартной функцией, они из очереди берут матрицы и считают (уже не было времени рефакторить старый код из п.3 чтоб убрать лишний функционал. Это ж надо, что получается: реализовываешь этот лишний функционал, реализовываешь, время тратишь... Так чтоб его еще и убрать потом, нужно время тратить!


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



Вывод: если хочется сделать суперпрограмму, то стоит обосновать действительную необходимость тех или иных «улучшений», иначе, в лучшем случае, они не нанесут вреда. Хотя, с другой стороны, это лишь вопрос опыта и времени, требуемого на его приобретение.  

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



Реализация сервера: от сложного к простому


Далее рассматриваются основные сложности, которые возникли по ходу реализации сервера, описывается, как они были разрешены.


Параллельная обработка бывает разная


Главное требование к серверу – справляться с текущей нагрузкой, а также иметь возможность улучшения/расширения/масштабируемости для увеличения нагрузки в будущем. Очевидное решение – параллельная обработка. Схема первоначально реализованного варианта работы потока представлена ниже:



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


Минусы, из-за которых пришлось отказаться от данной модели:


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

  2. Сложность контроля за выполнением потоков в менеджере. Выполнил он потоки? Или еще выполняет?




В результате была реализована модель представленная ниже:




Создается необходимое кол-во потоков. Каждый поток обрабатывает часть сражений и соединения, относящиеся к этим сражениям. 


Алгоритм обработки внутри потоков:



  1. последовательно проверить поступление новых команд от пользователей и передать им данные,

  2. последовательно обработать сражения,

  3. подождать до следующего цикла.



Преимущества данной модели в отсутствии недостатков прошлой:




  1. состояние сражения может измениться либо из-за команд пользователя, либо во время обработки внутриигрового времени, но не одновременно без дополнительного кода. Как результат можно вызывать любые функции из класса «соединение с игроком» и внутри класса «сражения» не задумываясь о том, что кто-то еще может изменить состояние игры.

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






Проблема большого кода



Для представления сражения реализован класс Game. И все бы хорошо, если бы в итоге он не разросся до 70 функций. Большое количество времени стало уходить на поиск нужного участка кода. Проблемой стал поиск ошибок, ибо любая функция может взаимодействовать с любой другой и менять любые данные, т.к. всё внутри одного класса.



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





Рыцарь атакует орка, которого убивает эльф


Рассмотрим пример с добрым рыцарем, спящим орком и славным эльфом. Добрый рыцарь видит спящего орка, решает атаковать его и начинает подкрадываться к нему, делая себе пометку, что на это уйдет 10 сек. Славный эльф тоже видит сложившуюся ситуацию и решает помочь доброму рыцарю, и потому в течении 5 сек выпускает пять стрел, которые убивают орка. В реальной жизни славный рыцарь прокравшись в течении 10 сек (в соответствии со своей пометкой), понял что его опередили и стал бы подкрадываться к следующему спящему орку. В игре же возможен вариант, что подкравшись к орку, он увидит «Access violation at address 0A6C77BE», и, вероятно, упадет вместе с сервером.


Решение очевидно – хранения счетчика ссылок на орков, а в общем случае – на игровые объекты. Ниже приведена первоначальная реализация:


           


Происходит следующее, объект «рыцарь» создает событие «нанести удар через 10 сек», вызывая функцию AddEvent менеджера событий. Одновременно с этим, он сообщает менеджеру объектов, что он рассчитывает, что объект «орк» (или то, что от него останется) будет дожидаться его в том же самом месте (через вызов функции AddDependency).       


После наступления события, «рыцарь» сообщает менеджеру объектов, что «орк» не представляет для него интереса (через вызов RemoveDependency). Если от объекта больше никто не зависит, то объект удаляется.    Проблема возникла, когда стало понятно, что на каждое событие приходиться писать по две строчки кода для добавления зависимостей (по одной при создании и наступлении события).


Если есть работа, которую можно не делать, то ее лучше не делать. Потому модель была изменена на следующую:



Параметры событий были стандартизированы, так, чтобы менеджер событий смог  разобраться, к каким объектам требуется добавить зависимости, чем он теперь и занимается. Соответственно, объектам теперь требуется создать только само событие.



Сохранение сражения


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




В общем случае всё сражение строится на объектах и событиях, поэтому задача сохранения – есть задача сохранения всех объектов и событий (в реальной игре также необходимо сохранять: текущее время, количество очков у игроков и т.д., эта часть задачи рассмотрена не будет– на смысл примера это не повлияет). Итак,  первоначальный вариант предполагал сохранение данных путем их сериализации и последующей десериализации. Каждый объект наследуется от базового класса с виртуальными функциями сериализации и десериализации, объекты событий – аналогично. В качестве формата хранения данных предполагалось использовать JSON. А в качестве места хранения - базу данных.


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




Фактически, сохраняется область памяти, в которой размещены данные менеджеров объектов и событий. Здесь пришлось модифицировать программу таким образом, чтобы все данные сражения (класс Game) располагались в памяти последовательно (сюда относятся пулы для выделения памяти под объекты и события, информация о ресурсах, игроках и т.д.). Сейчас сохранение занимает порядка 250КБ, сюда входит возможность одновременного присутствия в сражении 1000 игровых объектов (монстров, зданий и т.д.) и 3000 событий (ничего не мешает при необходимости увеличить их количество в будущем).


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


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


Заключение


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


For more complete information about compiler optimizations, see our Optimization Notice.