ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2014, № 5, с. 71-83
КОМПЬЮТЕРНЫЕ ^^^^^^^^^^^^^^ МЕТОДЫ
УДК 004.031.43
СРАВНЕНИЕ РАЗЛИЧНЫХ ПОДХОДОВ К РАСПРЕДЕЛЕНИЮ РЕСУРСОВ В ЦЕНТРАХ ОБРАБОТКИ ДАННЫХ
© 2014 г. П. М. Вдовин, И. А. Зотов, В. А. Костенко, А. В. Плакунов, Р. Л. Смелянский
Москва, МГУ Поступила в редакцию 24.01.14 г.
Выбраны абстракции для описания ресурсных запросов и физических ресурсов центров обработки данных. Разработана математическая модель центра обработки данных, которая позволяет описывать широкий класс их архитектур. В рамках этой модели сформулирована математическая постановка задачи распределения ресурсов, которая допускает миграцию виртуальных машин и репликацию элементов хранения данных. Приведены результаты сравнения алгоритмов распределения ресурсов для центров обработки данных с единым планировщиком для всех типов ресурсов и для центров обработки данных с раздельными планировщиками для каждого типа ресурсов, а также результаты сравнения разработанных алгоритмов с аналогичными алгоритмами из платформы OpenStack.
DOI: 10.7868/S0002338814040143
Введение. Качество работы планировщиков ресурсов в центрах обработки данных (ЦОД) определяет загрузку ресурсов ЦОД и возможность гарантированного обеспечения требуемого качество сервиса (SLA). Алгоритмы, используемые в платфороме OpenStack [1]: "назначение запроса на первый подходящий физический ресурс" или "выбор случайным образом физического ресурса из множества подходящих ресурсов" приемлемы по качеству получаемых отображений запросов на физические ресурсы ЦОД при их загрузке до 50%. При загрузке физических ресурсов больше 50% качество отображений, получаемых этими алгоритмами, значительно ухудшается. Это показано в разд. 3 данной статьи. Для отображения ресурсных запросов на физические ресурсы ЦОД требуется решить три взаимосвязанных ^Р-трудных задачи:
отображение виртуальных машин на вычислительные ресурсы ЦОД;
отображение элементов хранения данных (storage-элементов) на хранилища данных ЦОД;
отображение виртуальных каналов на физические ресурсы сети обмена ЦОД.
В случае высокой загрузки физических ресурсов ЦОД алгоритмы из OpenStack неприемлемы по качеству получаемых отображений ресурсных запросов на физические ресурсы ЦОД, а точные алгоритмы неприемлемы из-за высокой вычислительной сложности. Это обуславливает актуальность разработки эвристических алгоритмов, которые позволяют обеспечить нужный баланс между точностью и вычислительной сложностью.
Для обеспечения высокой загрузки в режиме использования ЦОД Infrastructure-as-a-Service (IaaS) [2] требуется решение следующих задач.
1. Устранение сегментации физических ресурсов за счет миграции виртуальных ресурсов в ЦОД.
2. Устранение перегрузки входящих в физическое хранилище данных каналов обмена. Данная задача возникает, когда имеются виртуальные хранилища данных с высокой интенсивностью считывания и низкой интенсивностью записи. Она может быть решена, если допускается репликация хранилищ данных. В этом случае для обеспечения консистентности данных не требуется канал с высокой пропускной способностью, и половина приложений может работать с виртуальным хранилищем данных, а другая — с его копией, которая располагается в другом физическом хранилище данных.
3. Возможность задания SLA для всех типов ресурсов ЦОД. Для этого вычислительные ресурсы, хранилища данных, сетевые ресурсы должны рассматриваться как планируемые типы ресурсов и их планирование должно проходить согласовано в смысле соблюдения соглашений о качестве сервиса.
В таблице приведено сравнение известных алгоритмов [3—16] с точки зрения возможности решать задачи 1—3.
Сравнительная характеристика алгоритмов
Рассмотренные работы
Вычислительные ресурсы как тип ресурсов
Хранилища данных как тип ресурсов
Сетевые ресурсы как тип ресурсов
Возможности
отображение виртуальных
каналов на физические
репликация
миграция
Application placement on a cluster of servers [3]
Cloud Storage and Online Bin Packing [4]
Efficient Resource Scheduling in Data Centers using MRIS [5]
Quantifying Load Imbalance on Vir-tualized EnterpriseServers [6]
On Theory of VM Placement: Anomalies in Existing Methodologies and Their Mitigation Using a Novel Victor Based Approach [7]
Optimal Mapping ofVirtual Networks with Hidden Hops [8]
Rethinking Virtual Network Embedding: Substrate Support for Path Splitting and Migration [9]
A Virtual Network Mapping Algorithm based on Subgraph Isomorphism [10]
Algorithms for Assigning Substrate Network Resources to Virtualized network Resources [11]
Virtual network embedding with coordinated node and link mapping [12]
Virtual Network Embedding Through Topology-Aware Node Ranking [13]
Coupled placement in modern data centers [14]
Server-storage virtualization: integration and load balancing in data centers [15]
Joint VM placement and routing for data center traffic engineering [16]
+
+
+
+ + +* +*
+
* Алгоритмы применимы лишь для ЦОД, имеющих иерархическую (древовидную) топологию.
Как видно из таблицы, ни один из алгоритмов не позволяет решать все вышеперечисленные задачи в совокупности.
В данной работе математически сформулирована задача отображений ресурсных запросов на физические ресурсы ЦОД и предложены алгоритмы ее решения, которые позволяют решать все вышеперечисленные задачи в совокупности для модели обслуживания 1аа8.
1. Математическая постановка задачи распределения ресурсов ЦОД. Модель физических ресурсов ЦОД будем задавать графом Н = (Р и М и К, Ь), где Р — множество вычислительных узлов, М — множество хранилищ данных, К — множество коммутационных элементов сети обмена ЦОД, L — множество физических каналов передачи данных.
На множестве Р определены функции vh(p) и qh(p), задающие производительность вычислительного узла (операций в секунду) и имеющийся объем всей памяти вычислительного узла (байт).
На множестве Мопределены функции uh(m) и type(m), задающие объем всей памяти хранилища данных (байт) и его тип.
На множестве К определена функция Л^), задающая пропускную способность коммутационного элемента (байт/с), а на множестве L — функция ), задающая номинальную пропускную способность канала передачи данных (байт/с).
Функции vh(p), qh(p), uh(m), type(m), й(Л), формируют разметку графа H.
Пример стандартной топологии ЦОД ГаИгее [17] приведен на рис. 1: каждый корневой коммутатор соединен со всеми коммутаторами первого уровня; каждый коммутатор первого уровня соединен с несколькими коммутаторами второго уровня; каждый коммутатор второго уровня объединяет либо несколько вычислительных узлов, либо несколько хранилищ данных.
Ресурсный запрос будем задавать графом О = (Ж и S, Е), где W — множество виртуальных машин, используемых приложениями, S — множество 81ога§е-элементов, E — множество виртуальных каналов передачи данных между виртуальными машинами и 81ога§е-элементами запроса.
На множестве Wопределены функции v(w) и q(w), задающие требуемую приложениями производительность виртуальных машин (операций в секунду) и объем памяти.
На множестве Sопределены функции u(s) и type(s), задающие требуемый объем памяти (байт) и тип 81ога§е-элемента.
На множестве E определена функция г^), задающая требуемую пропускную способность виртуального канала (байт/с).
Функции v(w), q(w), u(s), type(s), г^) формируют разметку графа G.
Ресурсные запросы могут быть двух типов:
слабосвязный: [({Ж}м, }м>, Е = 0];
сильносвязный: [({Щ}*=1 , ф}уК=1), Е = {(Ж с Ж}м , S с ф}^)}].
Назначением ресурсного запроса будем называть отображение A : G ^ H = P, S ^ M,
E ^ {K, L}}, удовлетворяющее следующим ограничениям.
1. Виртуальная машина w может быть назначена на выполнение на вычислительном узле p, если верны условия
^ v(w) < Vк(р) и ^ q(w) < дк(р).
м е Жр м е Жр
Здесь Wp — множество виртуальных машин, назначенных на выполнение на вычислительном узле p. Другими словами, производительность вычислительного узла должна быть не меньше требуемой суммарной производительности назначенных на него виртуальных машин и объем памяти вычислительного узла должен быть не меньше требуемой суммарной памяти назначенных на него виртуальных машин. Планирование выполнения виртуальных машин на вычислительном узле осуществляется локальным планировщиком вычислительного узла. Локальный планировщик должен гарантированно обеспечивать для каждой виртуальной машины требуемую производительность.
2. Виртуальный канал e может быть отображен на физический канал /, если верно условие
^ г(е) < гк(!).
е е Еу
Здесь El — множество виртуальных каналов, отображенных на физический канал /.
3. Виртуальный канал e может проходить через коммутационный элемент к, если верно условие
X r(e) < т h(k).
e е Ek
Здесь Ек — множество виртуальных каналов, проходящих через коммутационный элемент к.
4. Storage-элемент s может быть размещен в хранилище данных m, если верно условие
X u(s) < uh(m).
s е Sm
Здесь Sm — множество storage, размещенных в хранилище данных m, а также тип хранилища данных совпадает с типом storage-элемента.
Репликацией называется отображение R : H ^ H, дублирующее данные некоторого m е M и создающее виртуальный канал поддержки консистентности данных (m',l1,ku..., kn-1,ln,m); kt e K, lt e L, m' e M, m' — реплика хранилища m.
Если storage-элемент является репликацией некоторой базы данных s и требуется обеспечение консистентности данных, то в граф запрашиваемых ресурсов G добавляется вершина s'. В граф G также добавляется виртуальный канал между вершинами s и s', пропускная способность которого определяется исходя из требования обеспечения консистентности репликации и базы данных.
Остаточным графом доступных ресурсов называется граф Hres, для которого переопределены функции:
vhres(p) = vh(p) - X v(w), qhres(p) = qh(p) - X q(w), uhKs(m) = uh(m) - X u(s),
w e Wp w e Wp s e Sm
Thres(k) = Th(k) - X r(e), rhres(l) = rh(l) - X r(e).
e e E; e e Ek
В качестве исходных данных задачи назначения ресурсных запросов на физические ресурсы заданы:
1) множество запросов Z = {(G,, T)}, поступивших центральному планировщику; здесь T
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.