Алгоритм динамического распределения ресурсов в облачной инфраструктуре (1187394), страница 3
Текст из файла (страница 3)
Контроллер облака представляет собойнабор сервисов, которые сгруппированы по трем категориям: ресурсныеслужбы, службы данных и интерфейсные службы. Он также можетобрабатывать перевод протоколов и обеспечивать управление общимисистемами. Политики брокера. Этот компонент моделирует сервисброкеров,которыеобрабатываютмаршрутизациютрафикамеждупользовательскими базами и центрами обработки данных. Политикамаршрутизации по умолчанию направляет трафик в ближайший центробработки данных с точки зрения задержки сети от исходной базыпользователей.
Кроме того, экспериментальная брокерская политика для18максимальной нагрузки для совместного использования нагрузки центраобработки данных с другими центрами обработки данных, когдапроизводительность исходного центра обработки данных ухудшаетсявыше заранее определенного порога.Решение задачи итеративного перераспределения в общем случаеимеет логическое строение, представленное на рисунке 5.Рис.5. Обобщённая архитектура менеджера ресурсов.Опишем фазы управления ресурсами в общем случае:1.
Подготовительная фаза. Менеджер на этом этапе собирает наинформацию об используемых ресурсах. Способ получения,равно как и объём собираемых данных, зависит от конкретной19реализации. На основе предварительной обработки принимаетсярешение о запуске перераспределения ресурсов в случаенарушения предварительно заданных условий.2. Фаза планирования миграций. Во время этого этапа менеджернепосредственно обрабатывает полученную информацию и наосновании конкретного алгоритма формирует план миграции,который должен устранить или минимизировать возникшиенарушения условий. Обычно такой план состоит из троек«NUMA узел-отправитель, виртуальная машина, NUMA узелполучатель».3.
Фаза выполнения миграции.На этом этапе происходитвыполнение плана ядром операционной системы.20Подходы при балансировкеСуществует два основных подхода в балансировке нагрузки,которыеможнообозначитькаквыталкивающиемиграцииипритягивающие миграции. Выталкивающие миграции – перенос полезнойнагрузки на наименее нагруженный узел с более нагруженного. Прииспользованииподходаспритягивающимимиграцияминагрузкапереносится на узел, когда этот узел начинает простаивать.Существующие алгоритмы балансировки нагрузкиУлучшение размещения виртуальных машин с учётом трафикаВсвоейработеYuxiaChengсколлегамипредлагают[10]рассматривать задачу балансировки как частный случай задачи омногомерномрюкзаке.Вкачествеизмеренийрюкзакавыбраныоперативная память, процессорное время и ресурс межпроцессорнойшины, используемые виртуальной машиной.Предложенный подход использует алгоритм “первый подходящий”для первичного размещения виртуальных машин на физической машине, адальше на каждом шаге проверяет сбалансированность потребленияпроцессорного времени.
В случае если нагрузка не сбалансирована,балансировщиком выполняются следующие действия:1. Поиск NUMA узла с наибольшей очередью на выполнениевиртуальныхцентральныхпроцессорныхустройств(ВЦПУ)иNUMA узла с наибольшим количеством неактивных ЦПУ. Первыйявляется донором нагрузки, второй реципиентом. В случае если21существует несколько реципиентов, то выбирается тот узел, которыйиспользует меньше ресурса межпроцессорной шины.2. Определение количества ВЦПУ для переноса. Это значение являетсяминимумомизнеиспользуемыхфизическихЦПУнаузле-реципиенте и ожидающих ВЦПУ на узле-доноре3.
Поиск ВЦПУ, которые будут перенесены с узла-донора.4. Перенос нагрузок. Тут авторы отмечают, что происходит толькоперенос процессорной нагрузки без миграции памяти, что приводитк увеличению нагрузки на межпроцессорную шину.Миграция памяти происходит при длительной разбалансировкеиспользованияпамятинаNUMAузлах.Вкачествемеханизмаопределения необходимости миграции предлагается вести учёт числапереносов процессорной нагрузки с “домашнего” узла (того, гдеразмещена оперативная память виртуальной машины), и в случае если запоследние 10 перебалансировок машину переносили 8 раз на другой узел,то происходит вызов алгоритма первичного размещения.К достоинствам этого подхода следует отнести то, что он учитываетдороговизну переноса памяти с одного узла и описывает один из способовизбежать лишних миграций памяти.
В то же время остался нераскрытымспособ измерения и учёта использования пропускной способностимежпроцессорной шины каждого из NUMA узлов, что является одним изключевых ресурсов в описанной модели.Взвешенная рандомизированная миграция ВЦПУПодход, описанный Jia Rao в статье [6], предлагает для каждойвиртуальной машины находить наиболее подходящий NUMA узел,22основываясь на штрафе за использование межпроцессорной шины.Исследования проводились для виртуализационной платформы Xen.Штраф,описанныйвстатье,вычисляетсяпосчётчикампроизводительности процессора. К сожалению, точная формула неприводится, но качественно это среднее время жизни запроса к памяти издругого NUMA узла в очереди к числу таких запросов.Отличительной особенностью предложенного алгоритма являетсято, что миграция нагрузки на узел с наименьшим штрафом происходитслучайно, а вероятность миграции тем выше, чем больше временинагрузка находится на неоптимальном узле.
С помощью этого подходаавторы борются с пиками в нагрузке и накладными расходами,присущими изменению привязки ВЦПУ к ЦПУ на платформе Xen.Один из недостатков метода заключается в отсутствии механизмавосстановлениялокальностиразмещенияоперативнойпамятивиртуальной машины. Также не был предложен алгоритм начальногоразмещения виртуальных машин. Возможно, перечисленные недостаткисвязаны с ограничением выбранной в исследовании платформы –гипервизор Xen не позволяет напрямую влиять на то, в каком NUMA узлебудет выделена память.Демон оптимизации и уменьшения задержек при работе с памятьюNUMAd – это сервис балансировки нагрузки с открытым исходнымкодом.
Данное решение является частью программного комплекса Red HatEnterprise Virtualization (RHEV)[12], и создан для работы в связке сгипервизором QEMU-KVM под управлением менеджера виртуальныхмашин libvirt [13].Для решения задачи первичного размещения numad использует23алгоритм поиска первого подходящего. В качестве размеров рюкзака длякаждого NUMA узла рассматривается объём оперативной памяти иколичество физических ядер с учётом гипер-трединга. Динамическая частьалгоритма выполняется следующие шаги:1. Сбор информации о потреблении процессорного времени иоперативной памяти виртуальными машинами отдельно в каждомNUMA узле.2.
Упорядочивание ВМ в порядке убывания “значительности”.Значительность – метрика, введённая для оценки степени влиянияработы отдельной ВМ на производительности системы вцелом[12], и равная произведению процессорного времени наоперативную память, потреблённую на всех узлах.3. Вычисление для всех ВМ, начиная с самых значимых, узла, накотором уже размещена большая часть занятой оперативнойпамяти, и перенос вычислений и данных на найденный узел.К безусловным преимуществам решения можно отнести глубокуюинтеграцию с существующими системами оптимизации использованиявычислительных ресурсов, таких как сервисы прозрачного для процессовпредоставления больших страниц памяти и объединения одинаковыхстраниц памяти на уровне ядра.К недостаткам алгоритма можно отнести отсутствие механизмабалансировки потребления вычислительного времени в случае отсутствияфрагментации памяти.
В рассмотренном решении общее состояниесистемы рассматривается только с позиции общего доступного дляиспользования количества ресурсов, поэтому, как показал эксперимент в24ситуации с неустранимой фрагментацией (например 3 ВМ требующие по 4гигабайта ОЗУ, на сервере с двумя NUMA узлами по 6 гигабайт ОЗУ),алгоритм зацикливается на локализации фрагментированной ВМ, котораяприводит к фрагментации другой ВМ, и, как результат, к просадкепроизводительности.Взвешенный циклический алгоритмПредлагаемыйисследователямиалгоритмпредставляетсобойвзвешенный аналог существующего циклического алгоритма (round robin)с некоторыми изменениями в нем. В этом алгоритм взвешенногоциклического алгоритма, который распределяет все входящие запросыдоступным виртуальным машинам круговым способом на основе веса безучета текущей нагрузки на каждую виртуальную машину.
Шаги припланирования следующие:1. Планировщик получает информацию о виртуальной машине отподчиненного устройства. Если главный узел не получит данные отподчиненного устройства, то это будет означать, что виртуальнаямашина выключена. Эта ситуация определяется параметром W:● Если W = 0, то мастер-система определит, что виртуальнаямашина работает.● Если W = 1, то узел выключен.2. Если планировщик получает данные от ведомого устройства, онполучает информацию об используемых ресурсах (используемаяпамять, время процессора и т. д.).3. Затем главный узел строит взвешенную таблицу с помощью данных,которые были собраны на шаге 2.254. Затем главный узел сортирует все виртуальную машину в соответствиис их производительностью.5.
Планировщикраспределяетвиртуальныесоответствии с взвешенным значением.26машиныпоузламвРебалансировка нагрузки методом первогоподходящего с весамиПостановка задачиСуществующие решения задачи распределения ресурсов в системе снеравномерным доступом к памяти либо не нашли промышленногоприменения в силу недостатков, описанных ранее, либо всё ещёпроигрывают ручному распределению на реальных нагрузках. Такимобразом, проблема распределения ресурсов с учётом NUMA архитектурыактуальна.В результате анализа имеющихся решений и предметной областибыли выделены несколько наиболее эффективных принципов, и даннаяработа призвана объединить их в одну сбалансированную политику. Вчастности, алгоритм и его реализация должны:1.
Размещать все потоки процесса виртуальной машины в пределаходного NUMA узла.2. Определять степень использования вычислительных ресурсовNUMA узла по счетчикам производительности процессора (perfcounters).3. Восстанавливать локальность размещения ВЦПУ и данныхвиртуальной машины.4. Оценивать улучшение производительности системы в целом врезультате миграции памяти отдельных ВМ для уменьшения27накладных расходов.Методология экспериментаВ качестве объектов исследования была выбрана платформа:OpenVZалгоритма7.Цельюэксперимента былобалансировкивиртуальныхсравнение разработанногоокруженийсалгоритмомбалансировки, реализованным в ядре Linux, и ручным размещением ВМ.Описание стендаВ качестве стенда для проведения экспериментов использовалсясервер IBM System x3650 M3 7945L0F с двумя одинаковыми NUMAузлами. Каждый узел включал в себя процессор Intel® Xeon® CPU E56452.39 GHz и 64 гигабайта оперативной памяти DDR3. В качествеоперационной системы и виртуализационной платформы использовалисьтестовые сборки продукта Virtuozzo седьмой версии.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
