Jump to content

Донат
На хостинг
ISK за переводы
до 75kk за 1000зн.
Хроники EVE
Сборник
Новичкам
Полезная информация
Photo

О том, как мы сбалансировали Вселенную


  • Please log in to reply
23 replies to this topic

#1
Siberian Crab

Siberian Crab

    (\/) Oo (\/)

  • Tech III Pilots
  • PipPipPipPip
  • 839 posts
919
  • EVE Ingame:Siberian Crab
  • EVE Alt:+1
  • Channel:Night Trade Team
  • Client:Eng

Задавим их интеллектом!

- SC2 Марин

 

 

 

О том, как мы сбалансировали Вселенную

 

Девблог CCP Prism X (Оригинал) | 03.12.2013 16:19

 

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

 

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

 

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

 

*Говоря это, мы, конечно же, не учитываем «рукотворные» факторы, которые нагружают систему там, где мы этого не ждём.

 

Например: анонс новых плюшек в LP-шопе корпорации у которой всего один вкусный агент в хай секах привёл к резкому росту нагрузки на звездную систему, в которой расположен этот агент. Нагрузке,  с которой наш Premapper не справился.

 

 

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

 

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

 

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

 

OriginalEndStateWCirclesLOWRES.png
 

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

 

OriginalStats.jpg
 

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

 

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

 

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

 

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

 

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

 

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

 

binarySearch.jpg
 

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

 

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

 

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

 

FirstPythonInitStepLOWRES.png
 

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

 

FirstPythonFirstSplitLOWRES.png
 

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

 

FirstPythonSeventhSplitLOWRES.png
 

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

 

00aaa65105b13069a8c32f3380d928a09bb945ad

 

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

 

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

 

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

 

wholePowerOfTwoProblem.jpg
 

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

 

FirstTryStats.jpg
 

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

 

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

 

wholePowerOfTwoSolution.jpg
 

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

 

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

 

00aaa6520e7911637d866832c92dc24b239fe8b3
 

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

 

SecondTryStats.jpg
 

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

 

 

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

 

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

 

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

 

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

 

 

 

Критика и пожелания приветствуются.


Edited by Siberian Crab, 04 December 2013 - 21:51.

  • 20

«Мы брат, всего боимся, как положено смертным и всего хотим, как будто награждены бессмертием» - Петр Стаматин

 

EVE Drones: Engage Target


#2
Sir Zak

Sir Zak

    меня трудно найти легко потерять и невозможно забыть

  • Tech III Pilots
  • PipPipPipPipPip
  • 2844 posts
2174
  • EVE Ingame:DJ BASIL
  • Corp:X-OPS
  • Ally:N/A
  • Channel:Baraboom
  • Client:Eng

от оно че


  • 0

0cd6077657ba7f6fe393e83750b9a449.png


#3
Donnie Ergo

Donnie Ergo

    BENEATH A STEEL SKY

  • Tech III Pilots
  • PipPipPipPipPip
  • 2769 posts
1589
  • EVE Ingame:Whitmore
  • Corp:FEI

Чо тд не будет?


  • 0

#4
Ale_xXx

Ale_xXx

    Clone Grade Eta

  • Tech III Pilots
  • PipPipPipPip
  • 814 posts
54
  • EVE Ingame:CrazyAlexXx
  • Corp:FU.CK
  • Ally:IN.SP
  • Client:Eng

У меня пару картинок не прогрузилось


  • 0

#5
gl00m

gl00m

    Блохокуй

  • Tech III Pilots
  • PipPipPipPipPipPipPip
  • 6456 posts
933
  • EVE Ingame:L0M
  • Corp:CAS
  • Client:Eng

Картинки ну очень бы желательно под спойлер. <_<


  • 1

Плакали, кололись, но жрали кактус.


#6
Werdna

Werdna

    Despicable Heterolingual

  • EVE-RU Team
  • 5204 posts
4874
  • EVE Ingame:Lurking one
  • Corp:BLYA
  • Ally:X.I.X
  • Client:Eng

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


Я думаю, что в идеале это среднее отклонение должно равняться нулю. Соответственно, чем меньше это число (то есть чем ближе эти значения к среднему), тем лучше. Поэтому разница между исходными данными и результатом очень даже впечатляет.
 

В нём было слишком много упоминаний о водовозах, акведуках и Бейонсе Ноулз (Beyonce Knowles). Скорее всего, для многих из вас он так бы и остался бессмысленным набором слов.


Очередное порождение сумрачного юмора автора девблога. Казалось бы - причём тут водовозы? Задача о воде (в оригинале - water carriers) - это известная задача о том, как отмерить 4 литра двумя банками на 5 и на 3 литра (ну хз как там верно условие формируется, но вы поняли о чём речь). Соответственно, примерную задачу и решали девелоперы, когда разрабатывали алгоритм распределения нагрузки на ноды. Задача акведука - это расчёт такой нагрузки на структуру, когда с одной стороны поток достаточно быстрый, чтобы поддерживать структуру в нормальном режиме (то есть вода очищает желоб акведука), но с другой стороны - недостаточно быстрый, чтобы разрушить структуру (то есть поток размоет акведук). Очевидно, что тут речь идёт о премаппере, который распределяет нагрузку на ноды. Но на самом деле всё это выше вашего уровня знаний (Beyond your knowledge) - но напрямую дев не решился так сказать, поэтому вдруг упомянул Бейонс Ноулз (Beyonce Knowles).

Edited by Werdna, 04 December 2013 - 21:06.

  • 14

#7
gushick

gushick

    Clone Grade Eta

  • Tech III Pilots
  • PipPipPipPip
  • 523 posts
809
  • EVE Ingame:gushick
  • Corp:npc
  • Client:Eng

Так это,я не понял,лаги чтоль пофиксили ? :o


  • -1

#8
GLG

GLG

    Clone Grade Mu

  • Tech III Pilots
  • PipPipPipPipPipPipPip
  • 6205 posts
3030
  • EVE Ingame:Gang Leader Guemon
  • Client:Eng

Так это,я не понял,лаги чтоль пофиксили ? :o

В вакууме.


  • 0

#9
Siberian Crab

Siberian Crab

    (\/) Oo (\/)

  • Tech III Pilots
  • PipPipPipPip
  • 839 posts
919
  • EVE Ingame:Siberian Crab
  • EVE Alt:+1
  • Channel:Night Trade Team
  • Client:Eng

Очередное порождение сумрачного юмора автора девблога. 

 

От оно чё. Юмор у них таки да. Исладнский.

 

 

 

У меня пару картинок не прогрузилось

 

Загрузил уменьшенные версии двух ССРшных пано на фотохостинг. Должно помочь.


Edited by Siberian Crab, 04 December 2013 - 21:59.

  • 0

«Мы брат, всего боимся, как положено смертным и всего хотим, как будто награждены бессмертием» - Петр Стаматин

 

EVE Drones: Engage Target


#10
DanGion

DanGion

    Clone Grade Eta

  • Tech III Pilots
  • PipPipPipPip
  • 887 posts
131
  • EVE Ingame:Dangion Pickle
  • Corp:ФВ
  • Client:Eng

Круто конечно, но хотелось бы увидеть данные не только по качественным, но и по скоростным показателям.

 

Короче, распределяет нагрузгу быстрее чем раньше? И если да, то НАСКОЛЬКО? (хотяб время, железо то можно принять за неизменное)


Edited by DanGion, 05 December 2013 - 10:16.

  • 0

#11
starfox

starfox

    Clone Grade Gamma

  • Tech III Pilots
  • PipPip
  • 105 posts
-6
  • EVE Ingame:Mentazor
  • EVE Alt:Arbidark
  • Corp:RSSCP+Iridium

del


Edited by starfox, 05 December 2013 - 10:34.

  • 0
Улыбайтесь: это заставляет людей ломать голову над тем, что же у вас на уме.

Нельзя обойтись без необходимого и избежать неизбежного, но можно положить на неположенное и отстоять не отстойное, запихать не запихуемое.

shiru mono iwazu, iu mono shirazu

#12
Freeman055

Freeman055

    Clone Grade Theta

  • Tech III Pilots
  • PipPipPipPip
  • 1339 posts
556
  • Client:Eng

Это они делают вид что чем-то важным заняты :)


  • -3

#13
MikeChe

MikeChe

    Newbie

  • Tech II Pilots
  • 29 posts
3
  • EVE Ingame:mikecher
  • Corp:BS-D
  • Ally:DT
  • Client:Рус

Это они делают вид что чем-то важным заняты :)

Т.Е. ты считаешь что оптимизация вычислительной нагрузки это полная ерунда ?


  • 0

#14
Antidote

Antidote

    Clone Grade Beta

  • Tech III Pilots
  • Pip
  • 78 posts
16
  • Corp:BR0D
  • Ally:Disbanded
  • Client:Eng

Судя по NullSec cpuMAX, ТD, при каросфере будет, не 1%, а 2%  :troll:


  • 0

#15
Werdna

Werdna

    Despicable Heterolingual

  • EVE-RU Team
  • 5204 posts
4874
  • EVE Ingame:Lurking one
  • Corp:BLYA
  • Ally:X.I.X
  • Client:Eng

Судя по NullSec cpuMAX, ТD, при каросфере будет, не 1%, а 2%  :troll:

 

Это будет 100% прирост производительности. Ваш К.О.


Edited by Werdna, 05 December 2013 - 11:19.

  • 1

#16
Snape

Snape

    Clone Grade Kappa

  • Tech III Pilots
  • PipPipPipPipPip
  • 2420 posts
239
  • Client:Eng

Хм... А кто-то понял, в связи с чем все эти заморочки насчет физической разбросанности систем? Ну вот к примеру, если я "краблю в уютном тупичке с нулевым локалом на севере", и тут вдруг ВНЕЗАПНО "у меня начинается ТД, от которого я страдаю" - то не все ли мне равно, начался он оттого, что заруба блоб на блоб поехала в где-то в моей констелляции, или где-то далеко на юге? Страдания-то, каг бе, они и в Африке страдания - или я чего-то не понимаю?


  • 0
Давая мне совет, принимайте во внимание, плиз:

1) Меня не интересует ПВП.
2) В ближайший месяц я не планирую лезть в лоу и тем более в нули (плевать на иски, нервы дороже).
3) Я играю только в одиночку.

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

#17
kiedd

kiedd

    Clone Grade Eta

  • Tech III Pilots
  • PipPipPipPip
  • 870 posts
143
  • EVE Ingame:Eugen Kidd
  • EVE Alt:Eve Hoi
  • Corp:FETID
  • Ally:Snuffed Out
  • Client:Eng

Так что, ноды с затакленными титанами падать больше не будут?


  • 0

#18
sgetout

sgetout

    бубен нижнего мира

  • Faction pilots
  • PipPipPipPipPip
  • 3610 posts
1254
  • EVE Ingame:WhatAHek
  • Corp:Garoun Invest Bank
  • Client:Eng

Так что, ноды с затакленными титанами падать больше не будут?

Будут, но от этого ТД будет страдать только эта область карты :)


  • 0

#19
Hayashi

Hayashi

    Clone Grade Epsilon

  • Tech III Pilots
  • PipPipPip
  • 245 posts
-11
  • EVE Ingame:Ichimaru Hayashi
  • Channel:Russian

"Лучше бы лаги пофиксили" (с)  :slowpoke:


  • 1

#20
Sedrick

Sedrick

    Clone Grade Theta

  • Tech III Pilots
  • PipPipPipPip
  • 1278 posts
19
  • Client:Eng

Теперь гейты в пустых нулях будут пропускать без "попробуйте позже"?


  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users