Оптимизация размещения виртуальных машин по серверам

Какое-то время назад один мой коллега рассказал, что место в ДЦ кончается, сервера ставить больше некуда, а нагрузка растет и непонятно, что делать, и наверно придется все имеющиеся сервера поменять на более мощные.

Я в это время занимался задачей составления оптимальных расписаний, и подумал — а что, если применить оптимизационные алгоритмы для повышения утилизации серверов в ДЦ? Отсюда и родился проект, про который я хочу написать.

Для продвинутых сразу скажу, что в этой статье речь пойдет про bin packing, а остальным, кто хочет узнать, как с помощью относительно несложных расчетов сэкономить до 30% серверных ресурсов, добро пожаловать под кат.

Итак, у нас есть ДЦ с примерно 100 серверами, на которых размещены примерно 7 000 виртуальных машин. Что внутри виртуальных машин — мы не знаем и знать не должны. Нужно разместить виртуальные машины по серверам так, чтобы выполнить SLA и при этом использовать минимальное количество серверов.

Мы знаем:

• список серверов
• количество ресурсов на каждом сервере (CPU time, CPU cores, RAM, disk, disk io, network io).
• список виртуальных машин (VM)
• количество ресурсов, потребляемых каждой виртуальной машиной (CPU time, CPU cores, RAM, disk, disk io, network io).
• потребление ресурсов хост-системой на серверах.

Нам нужно распределить виртуальные машины по серверам так, чтобы по каждому из ресурсов на каждом сервере не превысить доступное количество ресурса, и при этом задействовать минимальное количество серверов.

Данная задача в научной литературе называется bin packing problem (как это будет по-русски?). По простому, это задача о том, как распихать маленькие коробочки произвольных размеров по большим коробкам, и при этом использовать минимальное количество больших коробок. Задача в математике известная, NP-полная, точно решается только полным перебором, стоимость которого комбинаторно растет.

Картинка ниже иллюстрирует суть алгоритма bin packing для одномерного случая:

Рис. 1. Иллюстрация bin packing problem, неоптимальное размещение

На первом рисунке айтемы как-то распределены по корзинам и для их размещения используется 3 корзины.

Рис. 2. Иллюстрация bin packing problem, оптимальное размещение

На второй картинке нарисовано оптимальное распределение, для которого нужно всего 2 корзины.

Стандартная формулировка bin packing алгоритма также предполагает, что все корзины одинаковы. У нас же сервера не одинаковы, так как закупались в разное время и их конфигурация отличается — разное количество ядер процессора, памяти, диска, разная мощность процессоров.

Субоптимальное решение можно получить, используя эвристики, генетические алгоритмы, monte-carlo tree search и глубокие нейронные сети. Мы остановились на эвристическом алгоритме BestFit, который сходится к решению не более чем 1.7 раз хуже оптимального, а также на некоторой вариации генетического алгоритма. Ниже я приведу результаты их применения.

Но сначала обсудим, что делать с метриками, изменяющимися во времени, такими как CPU usage, disk io, network io. Самый простой способ — заменить переменную метрику константой. Но как выбрать значение этой константы? Мы взяли максимальное значение метрики за какой-то характерный период (предварительно сгладив выбросы значений). Характерным периодом в нашем случае оказалась неделя, так как основная сезонность в нагрузке была связана с рабочими и выходными днями.

В этой модели каждой виртуальной машине выделяется полоса ресурса размером с максимально потребляемое значение ресурса, и каждая VM описывается константами max CPU usage, RAM, disk, max disk io, max network io.

Далее применяем алгоритм расчета оптимальной упаковки и получаем карту размещения VM по физическим серверам.

Практика показывает, что если не оставить некоторый запас по каждому из ресурсов на сервере, то при плотном размещении VM сервер становится перегружен. Поэтому по CPU usage мы оставляем запас 30%, по RAM 20%, по disk io — 20%, по network io — 20%, эти лимиты подобраны опытным путем.

Также у нас есть несколько типов дисков (быстрые SSD и медленные дешевые HDD), по каждому из типов дисков мы снимаем метрики disk и disk io отдельно, так что итоговая модель становится несколько сложнее и имеет больше измерений.

Результат оптимизации размещения VM показан на диаграмме:

Рис. 3. Результат оптимизации размещения VM по серверам

По горизонтали — количество серверов, которое оптимизировали, по вертикали — количество освобожденных серверов для эвристики BestFit и для генетического алгоритма.

Какие выводы можно сделать из диаграммы?

1. Для выполнения текущих задач можно использовать на 20-30% серверов меньше.
2. Чем больше серверов за раз оптимизируете, тем больше вы выигрываете в %, при количестве серверов 40 и выше происходит насыщение.
3. Генетический алгоритм несколько превосходит эвристический BestFit. Если мы захотим еще улучшить наши результаты, то будем копать в эту сторону.

Какие еще проблемы всплыли на практике?

1. Если вы захотите перетрясти около 100 серверов с 7 000 виртуальных машин, то объем миграций окажется весьма значительным, таким, что вся затея окажется нереализуемой. Но если вы будете работать с группами по 20-40 серверов последовательно, то эффект вы получите практически такой же, но количество миграций будет многократно меньше. И вы сможете оптимизировать свой ДЦ по частям.
2. Если вы обязательно должны делать live-миграции, то вы можете столкнутся с ситуацией, когда миграция не может закончиться. Это значит, что внутри VM происходит интенсивная запись на диск и/или изменяется состояние памяти, и состояния VM между старой и новой репликами не успевают синхронизироваться до изменения состояния старой реплики. В этом случае нужно заранее определять такие VM машины и помечать их как неперемещаемые. В свою очередь, это требует модификации алгоритмов оптимизации. Что радует, так это то, что общий выигрыш практически не зависит от количества таких машин, если их не более 10-15% от всего числа VM.

Как изменяется нагрузка на сервера после оптимизация размещения VM?

Ок, мы оптимизировали размещение VM. Может быть, получившееся новое состояния весьма хрупкое относительно увеличения нагрузки? Может быть, сервера работают на пределе и любой рост нагрузки их убъет?

Мы сравнили утилизацию ресурсов серверов до оптимизации и после за период в 1 неделю. То, что получилось, нарисовано на рисунке 2:

Рис. 4. Изменение нагрузки на CPU после оптимизации размещения VM

По CPU usage: средний CPU usage вырос с 10% до всего лишь 18%. Т.е. у нас есть трехкратный запас производительности по CPU, при этом сервера будут оставаться в так называемой «зеленой» зоне.

Как это было сделано в софте?

Мы собираем нужные нам метрики в Yandex.ClickHouse (пробовали InfluxDB, но на наших объемах данных запросы с агрегацией в ней выполняются слишком медленно) с периодичностью в 30 сек. Оттуда задача на расчет оптимального состояния читает метрики, рассчитывает по ним максимумы потребления и формирует задание на расчет, которое ставится в очередь. Как только задание на расчет выполняется, запускаются тесты, проверяющие, что результат не выходит за пределы заданных ограничений.

А кто-то это уже сделал?

Из известного нам, аналогичные алгоритмы есть внутри VMware vSphere и Nutanix и появляются внутри OpenStack (проект OpenStack Watcher).

Можно ли сделать еще лучше?

Да, можно. В следующей статье я расскажу, как можно еще плотнее упаковать виртуальные машины без нарушения SLA, и зачем для этого нужны нейронки.

Автор: actorai

Источник ^[1]