Динамическое управление питанием в задаче динамического управления ресурсами вариации планировщика и эксперименты (1187399), страница 3
Текст из файла (страница 3)
Не теряя общности,C p =1C v =s гдеs ∈R .Итак, пусть в момент времени vпроисходит SLAV и продолжаетсядо K. По определению подзадачи перегруженности ФМ, ВМ должнамигрировать с ФМ. Пусть время миграции равно T. В ходе миграции новаяФМ принимает мигрирующую ВМ, и общие затраты в этом процессесоставляют2C p T . Введём также вспомогательную переменную r—время, прошедшее с начала SLAV.Задача: найти момент времени m, в который нужно инициироватьмиграцию с целью минимизации общей функции стоимости, имеющей вданной постановке вид:{( v −m ) C p ,m< v , v − m≥ TC ( v , m )= ( v −m ) C p + ( r − m+ v ) C p + ( m −v +T ) C v , m≤ v , v −m<TrC p + ( r − mv ) C p +rC v ,m>vДалее,наоснованиитеории[19],формулируютсятеоремы(доказательства приведены в работе[20]):Теорема1.Оптимальныйодиночной ВМ даёт затратыНаоснованииофлайн-алгоритмдляTи достигается приsсоревновательногоанализазадачимиграцииv−m=1 .Tформулируетсяидоказывается теорема 2.Теорема 2.
Соревновательная точность оптимального онлайн-алгоритмаравна 2+s и достигается при m=v .183.3.1.2. Оптимальный онлайн-алгоритм: динамическая консолидацияВМ.В данном подразделе задача 3.3.1.1 обобщается на случай n ФМ ёмкостьюAhкаждая и максимальными требованиями ВМ к ресурсам являетсявеличинасоставляетA v , таким образом, максимальная плотность ВМ на ФМm=AhAvВМ, иmn -максимальное число ВМ в гомоменнойсистеме, использующейся для построения самого общего доказательства(гетерогенная система расширяется «приведением» к гомогенной сёмкостью, равной ёмкости максимально ёмкой ФМ, и увеличениемтребований ВМ до требований максимально требовательной ВМ).
ФМдинамически выключаются и включаются по требованию. Аналогично3.3.1.1, вводится функция стоимостиT(nni=0j=0С=∑ C p ∑ ati +C v ∑ v tjt=0),где ati — индикаторная функция активности ФМ i в момент t, v tj —индикаторная функция SLAV на ФМj . В соответствии с оптимизациейкоторой и строится оптимальный офлайн-алгоритм.Теорема 3. Верхняя граница соревновательного соотношения онлайналгоритма для динамической консолидации ВМ для любого входасоставляетIALG ( I )ms⩽1+, где OPT — оптимальный офлайнOPT ( I )2 ( m+1 )алгоритм. Доказательство приведено в работе [20].С одной стороны, введённая модель доказывает эффективностьпостроения взаимосвязанных онлайн-решений подзадач 1 и 3, с другой вводит дополнительное ограничение на эффективность.
Следовательно,для различных типов онлайн-алгоритмов, описанных в следующей главе,теоретически можно ожидать соревновательное соотношение на уровне19границы из теоремы 3.3.3.2. Эвристические алгоритмы.В данном подразделе представлен ряд эвристик для подзадачиопределения перегруженности ФМ, основанных на модели системы,описанной выше. Данные эвристики предоставляют устойчивое кнестационарным нагрузкам решение, которое значительно сокращаетэнергопотребление всей системы, одновременно обеспечивая высокийуровень поддержки SLA. Высокая эффективность выбранных методовпродемонстрирована экстенсивной симуляцией на данных, собранных сболее тысячи ВМ, описанной в главе 5.3.3.2.1. Алгоритм статической верхней границы.Простейшим подходом к определению перегруженности ФМ являетсяопределение статического значения загруженности CPU , по достижениикоторогоФМсчитаетсяперегруженной.Темнеменее,методы,выставляющие жестко фиксированные значения границ плохо применимыв случае динамических и плохо предсказуемых нагрузок, которые могутвозникать в ходе работ разнородных приложений на ВМ, что вынуждаетисследователей и разработчиков искать методы адаптивного измененияграниц.3.3.2.2.Адаптивнаяверхняяграница:абсолютноемедианноеотклонение.Представим эвристический алгоритм адаптивного изменения верхнейграницы на основании робастного статистического анализа истории работы20ВМ.
Выбор робастных методов осуществляется по причине лучшейтеоретической эффективности работы с данными, содержащими большоечисло выбросов и порожденными распределениями, не являющимисянормальными.Робастные статистики предоставляют альтернативу классическим методам,существенно теряющим точность предсказания при малых отклонениях отмодели.Предлагается выставлять границу в зависимости от величиныотклонения загрузки CPU: чем выше отклонения, тем ниже граница.Обоснование метода лежит в связи роста отклонения с приближениемзагрузки к 100%, потенциально приводящим к SLAV. Используется MADробастная статистика, оперирующая медианой абсолютного отклонения отмедианы выборки:MAD=mediani|( X i −median j ( X j ) )|Граница задаётся какT u =1− s MAD , гдеs — параметр жесткости:меньшие значения s приводят к большему «безразличию» к вариациямзаргузки CPU и увеличивают уровень SLAV при консолидации ВМ.Зависимость s от значения SLAV-метрик определяется экспериментально.Таким образом, система должна быть предварительно откалибрована длясоответствия некоторому QoS, прямое управление параметрами которого втерминах SLAV-метрик метод не предоставляет.3.3.2.3.
Адаптивная верхняя граница: межквартильный размах.Метод основан на анализе размаха между 1 и 3 квартилями выборки:MR=Q3 − Q 1 ,позволяющего оценить разброс 50% элементов без учёта влиянияэкстремальных элементов. При вычисленииQ1иQ3не учитываетсявлияние элементов, меньших Q1 и больших Q3 , следовательно, метод21безразличен к наличию выбросов и является робастным. Граница задаётсякакT u =1− s MR , гдеs — параметр жесткости, обладающий теми жесвойствами, что и параметр раздела 3.3.2.3.3.2.4.
Локальная регрессия Кливланда.Регрессия Кливланда[22] представляет собой робастное улучшениелокальнойрегрессииЛоесса[21],превращающееданныйметод витерационный метод с «размытием» выбросов по невязке. В качествевесовой функции выбирается трикубическая[21]:{3T ( u ) = ( 1−|u| )3,|u|<1 ,,|u|≥ 10и вес соседей в рассчитывается по формулеw i ( x )=Tгдеdi ( x )— расстояние от( ),доxdi ( x )d (q ) ( x )d (q ) ( x )xi ,— расстояние междудвумя максимально удалёнными элементами из всех q элементов даннойвыборки.Производится поиск функции из параметрического семействаa+bx , гдекоэффициенты a , b методом наименьших квадратов:n∑ wi ( x ) ( y i − a −bx i )2 → Mini=1Применим данный поиск кk =⌈ q /2⌉последним наблюдениям CPU.Пусть x k — последнее наблюдение, x 1 — k -е наблюдение от правойграницы.
Пусть нагрузка возрастает монотонно: x 1 ≤ xi ≤ x k , d t ( x k )=x k — x i, так что значение аргументастрого меньше 1 по модулю. ПоэтомуTвесовые коэффициенты имеют вид:3 3( ( ))x −xw i ( x )= 1− k ix k − x122В немодифицированном методе для каждого нового наблюдениянаходится новая линия тренда ^g ( x ) =a^ + b^ x , используемая для оценки^g ( x k+1 ) .нового наблюденияФМ считается перегруженной, есливыполнены следующие условия:s g^ ( x k +1 ) ≥ 1 ; x k+1 − x k ≥ t m ,где s — параметр жесткости, t m — максимальное время миграции ВМиз расположенных на данной ФМ.Немодифицированный метод достаточно эффективен и широкораспространён, однако плохо применим в при наличии выбросов,обусловленныхостроконечнымиили«тяжелохвостными»распределениями[22].Представим модифицированный метод, ликвидирующий вышеописаннуюуязвимость.
Пусть задано начальное приближение в точке^yi ,так что невязканаблюдению( xi , yi )e^i= y i − ^yi .x i , равноеНа следующем шаге каждомуставится в соответствии робастный весri ,зависящий от e^i :r i=B(e^i), где6 median|^e i|— биквадратная весовая функция вида:B{2B ( u )= ( 1 −|u| )20,|u|<1,|u|≥ 1После нахождения коэффициентов по «размытым» невязочным весам,получается«робастныйтренд»,ккоторомуужеприменяетсяоригинальный метод оценки нового измерения.Трудности применения того или иного регрессионного методазаключаются в компромиссе между реакцией на резкие изменения загрузкиCPUиинертностьюЭкспериментальноевслучаесравнение«размытия»Кливланду.немодифицированногомодифицированного методов приведены в разделе 5.23пои3.3.2.5.
Заключение.Рассмотренныеметодыпозволяютоперативноанализироватьсостояние ФМ и принимать решение о необходимости миграции ВМ,однако не позволяют вы явно выставить уровень QoS в терминах той илииной SLAV-метрики: достижение QoS целей обеспечивается калибровкой иподбором параметров алгоритма. В этом и заключается эвристичность всехвышеперечисленных подходов.3.4. Марковские алгоритмы.Несмотря на то, что данная работа предлагает вывод определённыхзависимостей из теории Марковских цепей именно для подзадачиопределения перегруженности ФМ, данный подраздел выделен отдельно.Это связано, во-первых, с более строгим теоретическим подходом иполучением некоторых важных свойств, влияющих на задачу DRS-DPMвцелом, а во-вторых, с целью выделить данный класс алгоритмов попостроению, на базе которых автор в будущем предполагает строитьразличные решения по оптимизации в IaaS.3.4.1.
Марковский алгоритм определения перегруженности ФМ.Момент обнаружения перегруженности ФМ напрямую влияет на QoS,т. к. если объём ресурсов практически полностью используется, вероятноснижение производительности приложений. Сложность обнаруженияперегруженностизаключается«усреднённоговремени»повнеобходимостиповедениясистемы,оптимизацииобрабатывающейразличные гетерогенные нагрузки. При этом эвристические и адаптивные24методы, описанные выше, имеют существенный недостаток с точки зренияуправления: их применение приводит , вообще говоря, к нестрогооптимальным результатам, вследствие чего у системного администраторанетвозможностиявнозадатьцельQoS.Инымисловами,производительность в отношении QoS задаётся неявно вариациейпараметров алгоритма.Подход, предлагаемый в данном разделе, позволяет системномуадминистратору явно указать цель QoS в терминах нагрузконезависимойQoS-метрики.
Аналитическая модель, лежащая в его основе, позволяетвывести оптимальную политику управления для любой известнойстационарной нагрузки и состояния системы. Обработка нестационарныхнагрузок осуществляется конкатенацией стационарных политик.3.4.2. Вывод предельных зависимостей.В данном разделе покажем, что эффективный алгоритм консолидацииВМ должен, одновременно с минимизацией числа активных ФМ,максимизировать интервалы между миграциями ВМ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
