ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2014, № 6, с. 80-93
КОМПЬЮТЕРНЫЕ ^^^^^^^^^^^^^^ МЕТОДЫ
УДК 004.031.43
АЛГОРИТМ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ В ЦЕНТРАХ ОБРАБОТКИ ДАННЫХ С РАЗДЕЛЬНЫМИ ПЛАНИРОВЩИКАМИ ДЛЯ РАЗЛИЧНЫХ ТИПОВ РЕСУРСОВ
© 2014 г. П. М. Вдовин, В. А. Костенко
Москва, МГУ
Поступила в редакцию 03.04.14 г., после доработки 14.05.14 г.
Рассматривается алгоритм отображения запросов на физические ресурсы для центров обработки данных с раздельными планировщиками для различных типов ресурсов: вычислительных, сетевых и систем хранения данных. Алгоритм основан на сочетании жадных стратегий и стратегий ограниченного перебора. Алгоритм позволяет выбирать требуемый баланс между вычислительной сложностью и качеством получаемых отображений путем ограничения максимально допустимой глубины перебора. Приводятся теоретические и экспериментальные результаты исследования его свойств.
DOI: 10.7868/S000233881405014X
Введение. В [1, 2] разработана математическая модель центра обработки данных (ЦОД), которая позволяет описывать широкий класс архитектур ЦОД, и сформулирована математическая постановка задачи распределения ресурсов в режиме использования Infrastructure-as-a-Service (IaaS) [3]. В предложенной модели вычислительные ресурсы, системы хранения данных и сетевые ресурсы рассматриваются как планируемые типы ресурсов, и их планирование происходит согласованно в смысле соблюдения соглашений о качестве сервиса (service-level agreement — SLA) [4]. Это позволяет задавать SLA для всех типов ресурсов ЦОД и строить такие отображения запросов на физические ресурсы, для которых возможно гарантированное выполнение запрашиваемых SLA.
В [2] проведено сравнение различных подходов к распределению ресурсов в ЦОД. В данной работе рассматривается алгоритм отображения запросов на физические ресурсы для ЦОД с раздельными планировщиками для различных типов ресурсов и приводятся результаты исследования его свойств.
Наиболее близкими задачами с точки зрения гарантированного выполнения SLA являются задачи построения расписаний для систем реального времени [5—10]. В этих задачах в качестве критерия SLA задаются ограничения на допустимое время выполнения прикладных программ или процессов программы, которые нарушаться не должны. В рассматриваемой задаче в качестве критериев SLA устанавливаются требования к "объемам" выделяемых элементам запросов физических ресурсов. Это делает проблематичным использование алгоритмов построения расписаний для данной задачи.
1. Математическая постановка задачи распределения ресурсов ЦОД. Модель физических ресурсов ЦОД будем задавать графом H = (P и M и K, L), где Р — множество вычислительных узлов, М — множество хранилищ данных, К — множество коммутационных элементов сети обмена ЦОД, L — множество физических каналов передачи данных. На множествах P, M, Kи L определены векторные функции, аргументами которых являются соответственно элементы множеств P, M, Kили L. Значениями функций выступают характеристики соответствующего вычислительного узла, хранилища данных, коммутационного элемента или канала передачи данных:
(phb ph2,..., ph„i) = fph(p), p e P,
(mhy,mh2,..., mhn2) = fmh(m), m e M,
(khy, kh2,..., khn3) = fkh(k), k e K,
(thy,lh2,..., lhn4) = flh(l), l e L.
В данной работе предполагается, что коммутационные элементы и каналы передачи данных имеют одинаковые характеристики. На практике наиболее часто используются следующие характеристики физических элементов:
1) для вычислительных узлов: (число ядер), (частота), (тип ядра), (объем оперативной памяти), (объем дисковой памяти);
2) для хранилищ данных: (объем памяти), (тип хранилища данных);
3) для коммутационных элементов: (пропускная способность), (задержка);
4) для каналов передачи данных: (пропускная способность), (задержка).
Ресурсный запрос будем задавать графом G = (W и S, E), где W — множество виртуальных машин, используемых приложениями, S — множество виртуальных хранилищ данных (storage-эле-ментов), E — множество виртуальных каналов передачи данных между виртуальными машинами и storage-элементами запроса. На множествах W, S и E определены векторные функции, аргументы которых — соответствующие элементы множеств W, S или E. Значениями функций являются характеристики (требуемое качество сервиса (SLA)) соответствующей виртуальной машины, storage-элемента или виртуального канала:
(wgb wg2,..., wgn]) = fwg(w), w e W,
(sgi,sg2,..., sgn2) = fsg(s), s e S,
(egi,eg2, • • -, egn4) = feg(e), e e E.
Характеристики SLA элемента запроса совпадают с характеристиками соответствующего ему физического ресурса.
Назначением ресурсного запроса будем называть отображение
A : G ^ H = {W ^ P,S ^ M,E ^ {K,L}}.
Выделим три типа отношений между характеристиками запросов и соответствующими характеристиками физических ресурсов. Обозначим через xi i-ю характеристику запроса и через y — соответствующую ей характеристику физического ресурса j. Тогда эти отношения можно записать следующим образом.
1. Недопустимость перегрузки емкости физического ресурса:
X х ^ yj,
i е Rj
здесь Rj — множество запросов, назначенных на выполнение на физическом ресурсе j, xi — соответствующая характеристика назначенного запроса.
2. Соответствие типа запрашиваемого ресурса типу физического ресурса:
X- = yj.
3. Наличие требуемых характеристик у физического ресурса:
Xi < yj.
Отображение A : G ^ H = {W ^ P,S ^ M,E ^ {K,L}} будем называть корректным, если для всех физических ресурсов и всех их характеристик выполняются отношения 1—3.
Остаточным графом доступных ресурсов называется граф Hres, для которого переопределены значения функций по характеристикам, которые должны удовлетворять отношению 1:
fpKes(P) = fph(Р) - X fwg(w) ,
w eWp
fmhres(m) = fmh(m) - X fsg(s), (1.1)
s e Sm
fkhres(k) = fkh(k) - X feg(e^ flhres(l) = flh(l) - X feg(e).
e e Er e e Ek
Здесь Wp — множество виртуальных машин, назначенных на выполнение на вычислительном узле p, Et — множество виртуальных каналов, отображенных на физический канал I, Ek — множество
виртуальных каналов, проходящих через коммутационный элемент к, 8т — множество 81ога§е-элементов, размещенных в хранилище данных т.
В качестве исходных данных задачи назначения ресурсных запросов на физические ресурсы заданы:
1) множество запросов Z = {О,}, поступивших планировщику;
2) остаточный граф доступных ресурсов Нге!, = (Р и М и К, Е).
Требуется: из множества Zразместить на выполнение в ЦОД максимальное число запросов, таких, что отображение А является корректным.
В случае, когда невозможно назначить виртуальное хранилище данных, возможен вызов процедуры репликации, позволяющей дублировать данные на нескольких физических хранилищах данных. Данная проблема возникает, когда имеются виртуальные хранилища данных с высокой интенсивностью считывания и низкой интенсивностью записи. В этом случае для обеспечения консистентности данных не требуется канал с высокой пропускной способностью, и половина приложений может работать с виртуальным хранилищем данных, а другая — с его копией, которая располагается в другом физическом хранилище данных.
Репликацией называется отображение Я : Н ^ Н, дублирующее данные некоторого т е М и создающее виртуальный канал поддержки консистентности данных (т', 11, к1, ..., к„-1, 1п, т); к е К, е Е, т' е М, т' — реплика хранилища т.
Если 81ога§е-элемент является репликацией некоторого виртуального хранилища данных ж, то в граф запрашиваемых ресурсов О добавляется вершина ж'. В граф О также добавляется виртуальный канал между вершинами ж и ж', пропускная способность которого определяется исходя из требования обеспечения консистентности репликации и базы данных.
На вход алгоритму назначения запросов на физические ресурсы подаются остаточный граф доступных ресурсов Нге,, и множество ресурсных запросов {О,-}. Множество {0;-} формирует диспетчер задач. В него, кроме вновь поступивших запросов, могут входить и запросы, которые выполняются и для которых допустима миграция. Диспетчер задач также определяет время запуска планировщика.
Выходом алгоритма назначения запросов на физические ресурсы является множество назначений ресурсных запросов на физические ресурсы (А, : О, ^ Н, I = 1, п} и множество репликаций (Я}, I = 0,1,...
2. Алгоритм назначения запросов на физические ресурсы ЦОД. Алгоритм назначения запросов на физические ресурсы с раздельными планировщиками состоит из трех шагов.
Шаг 1. Назначение виртуальных машин на вычислительные узлы.
Шаг 2. Назначение 81ога§е-элементов на физические хранилища данных.
Шаг 3. Для полученных отображений виртуальных машин и 81ога§е-элементов на физические ресурсы построение отображения виртуальных каналов запросов на физические каналы передачи данных и коммутационные элементы.
2.1. Назначение виртуальных машин и 81ога§е-элементов. В теории расписаний задачи назначения виртуальных машин и 81ога§е-элементов на физические ресурсы известны как задачи упаковки предметов в контейнеры [11]. Предлагаемый алгоритм основан на сочетании жадных стратегий и стратегий ограниченного перебора. Алгоритм осуществляет назначение элементов запросов по жадной схеме и в случае невозможности назначения очередного элемента вызывает процедуру ограниченного перебора. Для данной процедуры задается параметр, ограничивающий глубину перебора. Это позволяет выбирать требуемый баланс между вычислительной сложностью и точностью алгоритма.
Общая схема процедуры назначения элементов запроса (виртуальных машин или 81ога§е-эле-ментов) выглядит следующим образом.
Шаг 1. Из множества ресурсных запросов {О,-} выбрать очередной запрос О, в соответствии с жадным критерием КО.
Шаг 2. Выбрать очередной элемент е (виртуальную машину е е Ж,Ж е 01 или 81ога§е-эле-мент е е S, S е 0{) в соответствии с жадным критерием Ке.
Шаг 3. Сформировать множество физических ресурсов РН (РН с Р или РН с М соответственно), на которые может быть назначен выбранный элемент е, т.е. для которого выполнены отношения корректности отображения в случае назначения запроса е на физический ресурс.
Шаг 3.1. Если множество РН пусто, то вызвать проц
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.