Sign In
Create Account
by CCP Masterplan | 2010.12.11 15:18:59
оригинал
В предыдущей серии...
В первой части блога я рассказывал что такое Destiny и как утилита Telemetry помогает оптимизировать работу сервера. В конце я указал на обнаруженную в ходе оптимизации проблему – злые плюющиеся ракетами дрейки, вызывающие чрезмерную нагрузку на Destiny.
Теперь я покажу как мне удалось решить эту проблему.
Начнем с конца, я сразу продемонстрирую результаты. На рис. 1 показано распределение вычислительной нагрузки в течении 100 секунд непрерывного спама ракет (тестовая кинфигурация описана в первой части). Слева показано как распределялось процессорное время при использовании старого кода, годами работавшего на основном сервере. Справа покаана работа нового оптимизированного кода, вышедшего в составе Incursion.
Рис. 1 : Загрузка процессора в течении 100 секунд – до и после оптимизации
Очевидно, что нагрузка на Destiny заметно уменьшилась. Теперь самыми времязатратными стали фазы инвентаризации (учета объектов) и рассчета повреждений – и у нас уже есть наработки по оптимизации этих фаз, но о них мы поговорим в другой раз.
Итак, что же произошло?
Осторожно: псевдокод прямо по курсу!
Одна из самых первых вещей, которые Destiny делает каждый тик – построение списка добавленных и удаленных шаров для каждого наблюдателя. Для добавленных шаров нам необходимо получить дополнительные данные – идентификатор корпорации, секурити статус, визуальные эффекты (например, работу сенсорбустеров и т.д.) и собственно физические параметры (положение, скорость и прочее).
В очень упрощенном виде алгоритм выглядел следующим образом:
1 для каждого наблюдателя: # (корабль игрока) 2 для каждого шара в одном пузыре с наблюдателем: 3 если шар добавлен\удален во время последнего тика: 4 собрать все даные об этом шаре, которые надо переслать на клиент наблюдателя
Если немного подумать, то становится очевидно что такая задача очень плохо масштабируется с ростом числа шаров (N) и наблюдателей (M). А именно, она масштабируется как N*M. Если при этом учесть, что четвертный шаг алгоритма всегда генерирует одни и те же данные для каждого отдельного шара независимо от наблюдателя, то становится понятно что мы тратим порядочно времени впустую.
Первая оптимизация кода заключалась в кэшировании данных шага 4. Она особенно хорошо себя показывает в случае подварпа флота, но полезна и для стационарных боев. Но она не избавляет нас от мерзкого отвратительного вложенного цикла.
Вторая оптимизация заключалась в рефакторинге самого алгоритма. Тут я бы хотел упомянуть о еще одной вещи, которую часто поминают в обсуждении на форумах. Почему вы используете Питон? Питон медленный. Если бы вы все перевели на C++ то все лаги бы сразу пропали. В данном случае я вынужден не согласиться. Обсуждаемая нами функция отжирала во время масс-тестов более 15% процессорного времени. И она полностью написана на C++. Хорошая иллюстрация того, что кривой алгоритм будет тормозить на любом языке. Для небольшого числа шаров и наблюдателей этот алгоритм прекрасно работает. Но при увеличении этих чисел, масштабируется он плохо.
Новая оптимизированная версия теперь выглядит так (тоже упрощенно):
1 для каждого пузыря: 2 создатиь список добавлений/удалений: 3 для каждого шара в пузыре: 4 если шар добавлен/удален в этом тике: 5 собрать все данные об этом шаре, необходимые для передачи клиенту и сохранить в списке 6 для каждого наблюдателя: # (корабль игрока) 7 сохранить индекс в списке из шага 2, учитывая текущий пузырь наблюдателя
Этот алгоритм масштабируется как (N+M).
Следующая проблема, которую я обнаружил – избыточные действия при сериализации обновлений данных для клиентов. Ее решение было из серии откровений приходящих в ванной, но появиться оно могло только после того как мы реализовали две описанные выше вещи. Большинство клиентов в одном пузыре будут получать сериализованные обновления данных с одинаковым содержанием. Так что мы можем отказаться от отдельной сериализации для каждого клиента и после завершения шага 5 сериализовать одно общее обновление и разослать его всем клиентам в этом пузыре. Раньше мы делали операцию сериализации (преобразования внутренних структур данных на сервере в потоковый формат, пригодный для пересылки по сети), для каждого клиента. Теперь мы делаем операцию сериализации только для каждого пузыря (грида) и по одной команде memcpy для каждого наблюдателя. (Это объяснение сильно упрощено и не покрывает некоторые ситуации, но в целом оно верно).
Долина офигенностей
Эти оптимизации были реализованы таким образом, что я мог включать и выключать их непосредственно во время работы сервера. На следующем графике хорошо виден эффект от их включения.
Рис. 2: Загрузка процессора во время стрельбы ракетами при включенной и отключенной оптимизации
Ракеты начинаю лететь в 15:21 и заканчиваются в 15:27.
Вначале оптимизация отключена. В 15:23, я ее включаю (загрузка падает). В 15:25 опять отключаю (загрузка опять увеличивается)
Для сравнения, вот результаты работы профайлера Telemetry с включенной и выключенной оптимизацией:
Рис. 3: Сравнение двух тиков Destiny с и без оптимизации (одинаковая временная шкала)
Снимок тика сверху сделан до 15:23, снизу – сразу после 15:23.
Установка
Эти оптимизации алгоритма работали на тестовом сервере в октябре и ноябре. Если вы были на одном из массовых тестов в это время, то наверняка помните как были организованы флитовые варпы, кемпы и стрельба по посам. Это делалось специально чтобы испытать работу этого кода. Мы убедились что мои экспериментальные результаты, полученные с тонкими клиентами работают в реальных условиях с реальными игроками.
Работа с новой моделью сериализации была включена в Incursion 1.0.0 и вышла 30 ноября. 1 декабря я активировал новый код Destiny на части нод Tranquillity и понаблюдал за работой соответствующих солнечных систем. Когда мы убедились что все работает правильно, код был активирован для всего сервера. Это произошло во время даунтайма 2 декабря.
Надеюсь вам было интересно почитать про внутреннее устройство и работу Destiny. Если это действительно так, сообщайте нам и мы напишем что нибудь еще. Задавайте вопросы в треде про этот блог (на оффоруме) – я буду за ним следить и по возможности отвечать.
=====
=====
Edited by Tester128, 12 December 2010 - 5:26.
Back to top
