ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2015, № 1, с. 61-71
КОМПЬЮТЕРНЫЕ МЕТОДЫ
УДК 004.031.43
АЛГОРИТМ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ В ЦЕНТРАХ ОБРАБОТКИ ДАННЫХ С ЕДИНЫМ ПЛАНИРОВЩИКОМ ДЛЯ РАЗЛИЧНЫХ ТИПОВ РЕСУРСОВ*
© 2015 г. И. А. Зотов, В. А. Костенко
Москва, МГУ Поступила в редакцию 15.09.14 г.
Рассматривается алгоритм отображения запросов на физические ресурсы для центров обработки данных с единым планировщиком для различных типов ресурсов: вычислительных, сетевых и систем хранения данных. Алгоритм основан на "компактном" размещении в центре обработки данных запроса на создание виртуальной сети. Требуемый баланс между вычислительной сложностью и качеством получаемых отображений может задаваться путем ограничения максимально допустимой глубины перебора. Приводятся теоретические и экспериментальные результаты исследования его свойств.
БО1: 10.7868/8000233881501014Х
Введение. В [1] представлены результаты сравнения алгоритмов отображения запросов на физические ресурсы центра обработки данных (ЦОД) для режима его использования Infrastructure-as-a-Service (IaaS) [2]. В [1] рассматривались следующие алгоритмы:
используемые в платформе OpenStack [3]: "назначение элемента запроса на первый подходящий физический ресурс" или "выбор случайным образом физического ресурса из множества подходящих ресурсов";
основанный на применении схемы муравьиных колоний [4];
сочетающие жадные стратегии и стратегии ограниченного перебора.
Первый алгоритм, сочетающий жадные стратегии и стратегии ограниченного перебора, наиболее эффективен в случае, когда критическими ресурсами являются вычислительные ресурсы или ресурсы хранения данных. Он детально описан в работе [5].
Второй алгоритм, сочетающий жадные стратегии и стратегии ограниченного перебора, наиболее эффективен в случае, когда критическими ресурсами являются сетевые ресурсы. Основные подходы к обслуживанию ЦОД в подобных условиях рассмотрены в [6]. Алгоритм основан на "компактном" размещении в ЦОД запроса на создание виртуальной сети. В данной работе приведены детальное описание алгоритма и результаты экспериментального исследования его свойств. Предлагаемый алгоритм допускает возможность задания SLA (Service Level Agreement — соглашения об уровне услуг) для всех типов ресурсов ЦОД. Вычислительные ресурсы, системы хранения данных и сетевые ресурсы рассматриваются как планируемые типы ресурсов, и их планирование происходит согласованно в смысле соблюдения соглашений о качестве сервиса. Типы и виды SLA представлены, в частности, в [7].
1. Математическая постановка задачи распределения ресурсов ЦОД. Приведем математическую постановку задачи из работы [4] без изменений, так как она необходима для понимания работы алгоритма.
Модель физических ресурсов ЦОД будем задавать графом H = (P и M и K, L), где Р — множество вычислительных узлов, М — множество хранилищ данных, К — множество коммутационных элементов сети обмена ЦОД, L — множество физических каналов передачи данных. На множествах P, M, K и L определены векторные функции скалярного аргумента, задающие соответственно характеристики вычислительных узлов, хранилищ данных, коммутационных элементов и каналов передачи данных:
* Работа выполнена при финансовой поддержке Министерства образования и науки Российской Федерации. Соглашение № 14.607.21.0070.
ph(p) = (phi(p),phjip),..., phni(p)), mh(m) = (mhx(m),mh2(m),..., mhni(m)), kh(k) = (kh1(k), kh2(k),..., khni(k)), lh(l) = (lh1(l),lh2(l), ..., lhn4(l)).
Здесь p e P, m e M, k e K,l e L. Компоненты векторной функции могут принимать целочисленные и вещественные значения. В данной работе предполагается, что для коммутационных элементов и каналов передачи данных определяются одинаковые характеристики.
Ресурсный запрос будем задавать графом G = (W u S, E), где W — множество виртуальных машин, используемых приложениями, S — множество виртуальных хранилищ данных (storage-эле-ментов), E — множество виртуальных каналов передачи данных между виртуальными машинами и storage-элементами запроса. На множествах W, S и E определены векторные функции скалярного аргумента, задающие характеристики запрашиваемого виртуального элемента (требуемое качество сервиса (SLA)):
wg(w) = (wgx(w), wg2(w), ..., wgn1(w)),
sg(s) = (sgi(s), sg2(s), ..., sgn2(s)),
eg(e) = (egl(e),eg2(e),..., egn(e)).
Здесь w e W, s e S, e e E. Компоненты векторной функции также принимают целочисленные или вещественные значения. Характеристики SLA элемента запроса совпадают с характеристиками соответствующего ему физического ресурса.
Назначением ресурсного запроса будем называть отображение
A : G ^ H = {W ^ P,S ^ M,E ^ {K,L}}.
Выделим три типа отношений между характеристиками элементов запросов и соответствующих характеристик физических ресурсов. Обозначим через характеристику i -го элемента запроса, через yj — соответствующую ей характеристикуу-го физического ресурса. Тогда эти отношения можно записать следующим образом.
1. Недопустимость перегрузки емкости физического ресурса:
Z х ^ yj,
i е Rj
здесь R — множество элементов запросов, назначенных на выполнение на физическом ресурсе у.
2. Соответствие типа запрашиваемого ресурса типу физического ресурса:
xi = yt.
3. Наличие требуемых характеристик у физического ресурса:
X ^ yt.
Отображение A : G ^ H = {W ^ P, S ^ M, E ^ {K, L}} будем называть корректным, если для всех физических ресурсов и всех их характеристик выполняются отношения 1—3.
Остаточным графом доступных ресурсов называется граф Hres, для которого переопределены значения функций по характеристикам, которые должны удовлетворять отношению 1:
pKes(p) = ph(p) - Z wg(w), mhreS(m) = mh(m) - Z sg(s),
w e Wp s e Sm
khres(k) = kh(k) - Z eg(e), lhres(l) = lh(l) - Z eg(e). (1.1)
e e Ek e e Ei
Здесь Wp — множество виртуальных машин, назначенных на выполнение на вычислительном узлеp, El — множество виртуальных каналов, отображенных на физический канал l, Ek — множество виртуальных каналов, проходящих через коммутационный элемент k, Sm — множество stor-age-элементов, размещенных в хранилище данных m.
В качестве исходных данных задачи назначения ресурсных запросов на физические ресурсы заданы:
1) множество запросов Z = {О(}, поступивших планировщику;
2) остаточный граф доступных ресурсов Нге5 = (Р и М и К, Е).
Требуется: из множества Zразместить на выполнение в ЦОД максимальное число запросов, таких, что отображение А является корректным.
В случае, когда невозможно назначить виртуальное хранилище данных, возможен вызов процедуры репликации, позволяющей дублировать данные на нескольких физических хранилищах данных. Данная проблема возникает, когда имеются виртуальные хранилища данных с высокой интенсивностью считывания и низкой интенсивностью записи. В этом случае для обеспечения консистентности данных не требуется канал с высокой пропускной способностью. При этом часть приложений может работать с виртуальным хранилищем данных, а другая — с его копией, которая располагается в другом физическом хранилище данных.
Репликацией называется отображение Я : Н ^ Н, дублирующее данные некоторого т е М и создающее виртуальный канал поддержки консистентности данных (т', 11,къ ..., кК_ь 1п,т); к е К,¡1 е Е,т' е М, т' — реплика хранилища т.
Если 81ога§е-элемент является репликацией некоторого виртуального хранилища данных 5, то в граф запрашиваемых ресурсов О добавляется вершина В граф О также добавляется виртуальный канал между вершинами 5 и & , пропускная способность которого определяется исходя из требования обеспечения консистентности репликации и базы данных.
Входом алгоритма назначения запросов на физические ресурсы являются остаточный граф доступных ресурсов Нге5 и множество ресурсных запросов {^}. Множество [01} формирует диспетчер задач. В него кроме вновь поступивших запросов могут входить и запросы, которые выполняются и для которых допустима миграция. Диспетчер задач также определяет время запуска планировщика.
Выходом алгоритма назначения запросов на физические ресурсы является множество назначений ресурсных запросов на физические ресурсы {А, : С, ^ Н, I = 1, п} и множество репликаций
{Я,-}, - = 0,1,...
2. Алгоритм назначения запросов на физические ресурсы для ЦОД с единым планировщиком для всех типов ресурсов. 2.1. Общая схема работы алгоритма. Алгоритм осуществляет назначение элементов запроса в соответствии с жадной схемой, в случае невозможности назначения очередного элемента вызывается процедура ограниченного перебора. В качестве основного критерия оптимизации рассматривается наиболее компактное размещение элементов запроса с точки зрения использования сетевых ресурсов. Подобный подход рассмотрен в [8]. Для процедуры ограниченного перебора задается параметр, ограничивающий глубину перебора, что позволяет задавать требуемый баланс между вычислительной сложностью и точностью алгоритма.
Общая схема алгоритма выглядит следующим образом.
Шаг 1. Если множество ресурсных запросов {0{} не пусто, то выбрать очередной запрос в соответствии с жадным критерием Кв, в противном случае — завершение работы алгоритма.
Шаг 2. Сформировать из элементов запроса множество и = {Ж и .
Шаг 3. Выбрать очередной элемент е е и в соответствии с жадным критерием Ку, поместить е в очередь Q элементов, ожидающих назначения.
Шаг 4. Выбрать из Q элемент е в соответствии с жадным критерием KQ, выполнить следующие действия:
4а) сформировать множество физических ресурсов РН, на которые может быть назначен данный элемент е, т.е. для которого выполнены отношения корректности отображения в случае назначения запроса е на физический ресурс. Если данное множество пусто, то вызвать процедуру ограниченного перебора. При неуспешном завершении процедуры удалить ранее назначенные элементы запроса 01 и переопределить значения характеристик физических ресурсов в соответствии с функциями (1.1), удалить запрос из множества {0{}, перейти к шагу 1;
4Ь) выбрать физический ресурс ph е Ph в соответствии с жадным критерием Kph;
4с) сформировать пути между ph и физическими ресурсами, на которые назначены элементы запроса, связанные виртуальными
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.