Software & Systems

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

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

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

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

В данной работе предложен и рассмотрен подобный метод с перераспределением ресурсов PRR (Placement of virtual machines with Resource Redistribution), целью которого является увеличение количества размещенных ВМ и уменьшение длительности процесса размещения, сформулирована задача размещения группы ВМ в общем виде, приведены результаты экспериментов.

Постановка задачи планирования размещения группы ВМ

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

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

·       Задача размещения множества новых ВМ. Одним из ее основных показателей является количество размещенных ВМ.

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

·       Задача обеспечения высокой готовности и отказоустойчивости. После возникновения отказа требуется быстрый перезапуск одной или группы ВМ на других хостах в кратчайшие сроки. В данном случае основными показателями являются длительность процесса размещения ВМ и их количество.

Остановка ИС или отдельных ее компонентов для перераспределения ресурсов в большинстве случаев недопустима или сопровождается высокими издержками. Поэтому перемещение ВМ между хостами должно выполняться с сохранением их активности. Для этой цели применяется технология горячей миграции [3], которая обеспечивает возможность перемещения ВМ без нарушения ее работы и поддерживается всеми наиболее распространенными платформами виртуализации.

Таким образом, необходима разработка метода планирования размещения группы ВМ с учетом перераспределения ресурсов и сохранения активности ВМ. Как уже было сказано, цели планирования размещения ВМ могут быть различными. Целью настоящей работы является улучшение двух показателей – количество размещенных ВМ и продолжительность их размещения. Следовательно, данная задача является задачей многокритериальной оптимизации. Существует несколько подходов к решению многокритериальных задач [4]. Очевидно, что первый критерий, то есть количество восстановленных ВМ, значительно важнее второго. Поэтому в данной работе выбран метод лексикографического упорядочения критериев, предполагающий, что последовательность, в которой перечислены критерии, определяет их значимость: каждый предшествующий критерий несравненно важнее любого из следующих за ним:  где D – множество допустимых решений; f1(x) – первый критерий; f2(x) – второй критерий.

Сначала решается однокритериальная задача:

Пусть D1ÍD – множество оптимальных решений данной однокритериальной задачи. Если D1 – одноэлементное множество, то данное единственное решение и является оптимальным для всей задачи. В противном случае решается следующая однокритериальная задача:

Пусть D2ÍD1 – множество оптимальных решений второй однокритериальной задачи. Если D2 – одноэлементное множество, то данное единственное решение и является оптимальным для всей задачи. В противном случае может оказаться, что оптимальных (при имеющемся лексикографическом упорядочении критериев) решений этой задачи более одного и все они эквивалентны.

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

Решение сформулированной задачи осложняют следующие факторы:

–      взаимное влияние параметров размещения ВМ; например, изменение параметров размещения одной ВМ может повлечь за собой снижение показателей оптимальности, если параметры размещения других ВМ не будут изменены;

–      наличие множества локальных оптимумов;

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

Поэтому для решения задачи размещения группы ВМ был предложен метод на основе разбиения исходной задачи планирования на более простые подзадачи определения порядка размещения ВМ и планирования размещения каждой из них.

Метод планирования размещения группы ВМ

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

На глобальном уровне осуществляется поиск наилучшей последовательности размещения ВМ с точки зрения количества, которое будет размещено. На каждом шаге глобального уровня выбирается ВМ из оставшихся с наименьшими требованиями к ресурсам. При размещении ВМ обычно учитываются требования по нескольким типам ресурсов, а значит, задача выбора ВМ является многокритериальной. Для ее решения используется метод линейной свертки векторного критерия в одну функцию – обобщенный (агрегированный) критерий [4]:  где  – требование ВМ i к ресурсу типа j;  – обобщенная оценка требований ВМ к ресурсам; ci – некоторые положительные числа, характеризующие относительную важность ресурса типа j.

Для объединения различных критериев в один агрегированный необходимо привести их к общей единице измерения. Для этого перед запуском алгоритма определяются максимальные значения по каждому типу ресурсов среди всех хостов. Затем выбираются такие коэффициенты для этих критериев, что , где j=1, …, K, в абсолютных безразмерных единицах. Коэффициенты важности приняты одинаковыми и равными 1/K, поскольку ни одному из типов ресурсов не отдается предпочтение при формировании последовательности освобождения хоста.

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

1.     Формирование решений-кандидатов на данной итерации. Решение-кандидат представляет собой распределение ресурсов, отличающееся от исходного на q перемещений ВМ, где q – номер итерации. На первой итерации распределение ресурсов отличается от исходного на одно перемещение ВМ, на второй – на два последовательных перемещения и т.д.

2.     Оценка длительности размещения группы рассмотренных ВМ для каждого решения-канди­дата. Длительность размещения группы ВМ  для решения-кандидата u на итерации q принимается равной сумме длительностей перемещения и размещения ВМ с учетом одновременности данных операций.

3.     Выбор наилучшего решения-кандидата по двум условиям:

–      реализация данного решения-кандидата не приводит к нарушению требований ВМ к ресурсам: , где , k=1, …, K, j=1, ..., C, – объем свободного ресурса типа j на хосте k после реализации решения-кандидата;

–      данное решение-кандидат является наилучшим, если  где  – наименьшая длительность размещения группы ВМ после итерации q;  – длительность размещения для решения-кандидата u итерации q; Zq  – множество решений-кандидатов итерации q.

Работа алгоритма планирования размещения ВМ завершается, если множество решений-канди­датов пусто или дальнейший поиск не ведет к улучшению решения. В качестве окончательного решения принимается наилучшее из найденных. Работа метода планирования размещения группы завершается после рассмотрения всех ее ВМ.

Модельный эксперимент

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

Моделирование проводилось для кластера, состоящего из 15 хостов и 80 ВМ. Рамещалась группа из 20 ВМ. В эксперименте принимались во внимание два типа ресурсов – объем памяти и загрузка процессора. Требования ВМ по каждому типу ресурсов задавались случайным образом в соответствии с равномерным распределением в интервале от 5 % до 30 % от базового уровня ресурсов хостов. Начальное количество ВМ на каждом хосте составляло от 4 до 8 и выбиралось в соответствии с законом равномерного распределения. Объем свободных ресурсов на каждом хосте, оставшийся после размещения ВМ, равномерно распределялся между ВМ таким образом, чтобы весь базовый уровень ресурсов хостов был занят. Длительность перемещения и размещения ВМ выбиралась в соответствии с нормальным распределением и математическим ожиданием 90 секунд.

Для тестирования разработанного метода планирования размещения группы ВМ проведено несколько серий опытов. Для каждой серии устанавливался максимальный свободный объем ресурса каждого типа, который может быть добавлен к базовому объему хоста. Данный объем задавался как процент от базового объема ресурса хоста, представляющий собой произведение номера серии опытов на 10. В каждом опыте серии к базовому объему ресурсов каждого хоста прибавлялся дополнительный объем свободного ресурса, он выбирался в пределах от 0 до заданного максимального объема для данной серии в соответствии с законом равномерного распределения.

Для сравнения проведена оценка количества размещенных ВМ при использовании алгоритма без учета возможности перераспределения ресурсов. Выбор хоста для размещения ВМ выполнялся на основе метода наилучшего из подходящих (Best Fit, BF) [5], обеспечивающего выбор хоста с объемом свободных ресурсов, более всего соответствующего требованиям ВМ.

На графиках рисунка 1 показано количество размещенных машин для методов PRR и BF.

Результаты эксперимента (рис. 1) показывают, что метод PRR при малом объеме свободного ресурса (максимальная величина дополнительного ресурса соответствует 5–15 %) позволяет выполнить размещение ВМ, в то время как второй метод не позволяет этого сделать. Кроме того, метод PRR обеспечивает размещение всей группы ВМ, начиная со 120 %, а метод BF – только со 170. Метод PRR, учитывающий распределение ресурсов между хостами, в среднем позволяет повысить количество размещенных ВМ на 50 % по сравнению с методом, не учитывающим такую возможность.

На рисунке 2 приведен график длительности размещения группы ВМ для метода PRR.

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

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

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

Из результатов экспериментов видно, что разработанный метод позволяет разместить в среднем на 50 % больше ВМ при ограниченном объеме ресурсов, чем при использовании метода без учета распределения ресурсов.

Другим преимуществом предложенного метода является планирование размещения группы ВМ с учетом одновременного размещения/перемеще­ния нескольких ВМ, что значительно сокращает длительность размещения всей группы.

Литература

1.     Орлов С. Виртуализация «от и до» // Журнал сетевых решений / LAN. 2010. № 2.

2.     Джонс Т. Обзор методов виртуализации, архитектур и реализаций // IBM developerWorks. 2007. URL: http://www.ibm. com/developerworks/ru/library/l-linuxvirt/index.html (дата обращения: 12.06.2011).

3.     Clark С. [et. al.]. Live Migration of Virtual Machines // 2nd Symposium on Networked Systems Design and Implementation. 2005. Vol. 2, pp. 273–286.

4.     Коган Д.И. Задачи и методы конечномерной оптимизации: Ч. 3. Динамическое программирование и дискретная многокритериальная оптимизация. Н. Новгород: Изд-во НГУ, 2004. 157 с.

5.     Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 439 с.