Всем привет, меня зовут CCP Prism X.

Вместе с обновлением EVE Online: Odyssey, вышедшим этим летом, популяция сервера Транквилити значительно увеличилась. Обычно, чтобы отпраздновать подобные события мы достаём из бара шампанское, надеваем наши японские штаны за $1000 и устраиваем бои подушками. Однако в этот раз приток игроков был столь масштабен, что нам стало не по себе – Империя вот-вот готова была взорваться. В Новом Эдеме было так много капсулиров и они одновременно делали столько вещей, что физические ядра CPU (которые дальше мы будем называть «нодами»), отвечавшие за обработку Империи, были перегружены. Это привело к тому, что в различных разрозненных уголках Имперского Космоса активировалось Замедление Времени (Time Dilation или ТД). ТД – отличная вещь, если вы с друзьями устроили массовый заруб в нуль секах. Но если вы просто крабите в тупичке с нулевым локалом и внезапно включается slow-mo… ну вы понели ©.

Вообще, нагрузка на ноды, обрабатывающие Империю, должна быть настолько предсказуемой*, что ТД в принципе не должно там активироваться. В крайнем случае, Static Cluster Premapper должен в дальнейшем предотвратить повторение подобных проблем. Для этого мы отслеживаем расчетную нагрузку всех звездных систем и, основываясь на полученных данных, Premapper распределяет их на различные ноды. В идеале, до тех пор, пока Premapper работает в штатном режиме, а в вышеупомянутые расчёты не вкрадётся ошибка, вся система должна работать как часы. Однако звездные системы определялись на ноды, которые и так работали на полную. Возник сбой, и мы не были до конца уверены, что знаем всё о его причинах.

Шаг 1: Поиск проблемы

Описывая принцип перераспределения звёздных систем по нодам, я умолчал об одной немаловажной детали: системы, приписанные к одному созвездию (constellation или констеляция) стремятся остаться на одной ноде. Это стремление настолько сильно, что они покинут «любимую» ноду только в том случае, если нагрузка на неё более чем на 20% превышает нагрузку на ноду, которая выбрана как «оптимальная для перехода». Всё это приводило к значительным различиям в нагрузке на ноды, даже не смотря на то, что Premapper пытался её перераспределить. Помимо этого констеляции распределялись по нодам так, что на одной ноде их могло быть несколько, и далеко не все из них были рядом. Например, первая была на Юге галактики, а вторая – на Севере. Из-за этого бой на Юге мог вызвать ТД на Севере, что в свою очередь вызывало глубокое огорчение у Северных капсулиров!

Вот примерное распределение звёздных систем по нодам при использовании старых принципов перераспределения (следует отметить, что данное изображение – проекция 3D карты на 2D плоскость, поэтому его нельзя считать на 100% верным). Системы, помеченные одним цветом, находятся на одной ноде. Невооруженным взглядом видно, что вся эта схема представляет собой кучу малу из разноцветных точек. Красными кругами обведены два кластера, расположенные на одной ноде, о которых мы разговаривали выше. Расстояние между ними впечатляет, не так ли?

Помимо всего прочего эта система не очень-то хорошо справлялась с распределением нагрузок. Разница между нагрузкой на ноды просто ошеломительная. Это хорошо видно на показателях значения среднеквадратического отклонения (standard deviation values – хз что это – прим. перев.):

Спрашивается: а зачем мы вообще сгруппировали звёздные системы на уровне констелляций? Отвечаем: потому что давным-давно была выдвинута теория о том, что прыжки через звездные врата внутри одной ноды потребляют меньше серверных ресурсов, чем прыжки между несколькими нодами. Предполагалось, что причиной этого были возможные трудностями, связанными с сетевыми задержками. Теперь же мы знаем, что подобные предположения совершенно неверны и прыжки между нодами даже менее ресурсоёмки, нежели другие. Прыжок через звёздные врата подразумевает удаление игрока из одной системы и появление его в другой. Распределение нагрузки между двумя нодами естественно способствует ускорению загрузки.

Поняв это, мы в первую очередь решили отказаться от подобной привязки систем к нодам и теперь системы перераспределялись на наименее загруженные ноды. В итоге появился прекрасно сбалансированный алгоритм распределение звёздных систем по нодам, который решил множество проблем с прогрузкой! Но, не смотря на это, проблема с ТД никуда не делась. Системы распределялись по случайным нодам, вне зависимости от своего «географического» положения. И из-за этого пилоты Севера всё ещё страдали от боёв на Юге. И нам пришлось начать всё сначала.

Шаг 2: Поиск решения

Итак, мы должны были перераспределить нагрузку между нодами так, чтобы все звёздные системы на каждой ноде были соседями по космосу. Также мы не хотели увеличивать время на подобное перераспределение, поэтому мы использовали эту возможность, чтобы окончательно отказаться от T-SQL кода и переписать его под Python. Последнее (что, в общем-то, не удивительно) стало наиболее значимым изменением, так как процедурный язык, с хорошим инструментарием гораздо лучше справится с процедурной проблемой, нежели весьма ограниченный реляционный язык.

С помощью Python мы нашли простое и доступное решение. Все это время мы пытались разделить скопление звёздных систем так, чтобы обе части были близко друг к другу, а также одинаково загружены. Так почему бы действительно не сделать это? Если разделить любую систему координат пополам, то обе её части будут друг напротив друга. Это решает проблему близости. Все что осталось – сбалансировать нагрузку на каждую из них. Так как мы уже следим за каждой из звёздных систем, то всё что нам нужно – это немного переместить границу между двумя частями в ту или иную сторону. Это не сложнее, чем пользоваться Бинарным Поиском (Binary Search)! Теоретически, постепенно сдвигая границу то в одну, то в в другую стороны через некоторое время мы добьемся оптимального распределения нагрузки. Я говорю «теоретически» потому, что работая над этой проблемой, мы не искали «идеальное решение». Мы пытались найти просто хорошее решение, и сделать это как можно быстрее.

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

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

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

Первоначальное состояние Империи:

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

Седьмое разделение Империи (серый сектор на самом деле состоит из двух частей разных оттенков):

Итоговый результат (заметьте, как теперь сгруппированы разноцветные системы):

Шаг 3: Решение проблемы

Собственно вот что представляла собой первоначальная версия новой системы распределения звёздных систем за пару недель до релиза Рубикона. Думаю, что те из вас, кто разбирается в информатике, уже поняли, с какой проблемой мы столкнулись. Новая система работала, только если количество доступных для распределения нод было кратно двум. При любых других условиях распределение было неравномерно. Каждый раз, когда в какой-то ветке этого Бинарного Дерева не хватало одного листочка, нагрузка на неё удваивалась.

Вот очень простая иллюстрация проблемы двойственности, возникающей при использовании трёх нод (хотя по плану нужно 2*2=4 ноды). Следует сказать, что это упрощенный пример. Мы не ждём того, что каждое разделение будет происходить на две идеально равные части.

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

Совершенно очевидно, что в этом случае оптимальной было бы 33% распределение нагрузки на каждую ноду, но с виду безупречный и простой алгоритм даёт сбой. Однако, мы точно знаем, что этот алгоритм прекрасно работает, если мы делим первоначальную систему на количество нод, кратное двум. Нужно лишь сделать так, чтобы это условие выполнялось! Конечно, можно сделать так, чтобы количество работающих нод всегда было кратно двум, но это стало бы довольно глупым искусственным ограничением для EVE. Особенно, если вы знаете, что любое число в десятичной системе счисления можно представить в двоичной системе счисления. Затем нужно сделать так, чтобы количество ветвей бинарного дерева было равно количеству нод, кратному двум, и запустить алгоритм, подробно описанный ранее.

Используя немного боле сложный пример, нежели выше, мы получим следующее:

Этого результата довольно легко добиться. Нужно лишь немного изменить первоначальный код, который и так основан на разделении системы координат на две равные части. Заставить его разделиться вначале на часть Х и часть Y не составило особого труда.

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

Ну а среднеквадратическое отклонение по CPU значительно снизилось!

Надеемся, что эти нововведения будут установлены на Транквилити уже в среду, 4-го декабря.

Шаг 4: Написать девблог

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

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

Вот и всё, ребята! Если у вас есть какие-либо вопросы, то не стесняйтесь, задавайте их на официальном форуме EVE.

Перевод © Siberian Crab