METHODS AND MODELS OF THE RESOURCE ALLOCATION SERVICE IN CLUSTERS WITH LOAD BALANCING OF DATA CENTERS

Full Text

Введение Информационная структура центра обработ- ки данных (ЦОД) включает в себя: серверный комплекс, представленный в виде кластеров с балансировкой нагрузки (Load Balancing Clus- ter), в котором применяются многоплатформен- ные решения, обеспечивающие равномерное распределение нагрузки между серверами, сред- ства памяти, включающие множество устройств хранения данных в виде дисковых массивов, си- стему хранения данных, средства копирования и восстановления, средства связи и коммутации, средства телекоммуникации, обеспечивающие взаимодействие между операторами и пользова- телями ЦОД. Формальная модель кластера ЦОД приведе- на на рисунке 1. При использовании кластера с балансировкой нагрузки множество ресурсных запросов пользователей поступает на распреде- литель нагрузки, который по определенным пра- вилам равномерно распределяет их между сер- верами кластера. При этом может производиться направление поступившего запроса на первый доступный ресурс кластера или выбор случай- ным образом ресурса из множества доступных и обеспечивающих реализацию данного запроса. В основу подобных решений могут быть положе- ны также широко известные эвристические алго- ритмы на основе жадных стратегий. Например, методы распределения нагрузки, заложенные в циклическую логику алгоритма Round Robin, формируют на любой запрос соответствующий IP-адрес, обеспечивая тем самым формирование запросов к серверам по круговому циклу и реа- лизуя одинаковое количество запросов к каждому серверу. И хотя время работы данного алгоритма не является слишком большим, он мало пригоден для практического применения. Данный алго- ритм не учитывает доступные объемы ресурсов серверов, их состояние, производительность, текущую загрузку, количество поддерживаемых подключений. Более совершенные варианты этого алгоритма, разработанные специально для улучшения характеристик кластеров, Least Connections, Weighted Least Connections, Locality- Based Least Connections Scheduling, Destination Hash Scheduling, Source Hash Scheduling, Sticky Sessions, хотя и используют методы поиска серве- ров с наименьшей загрузкой и передачи им ново- го запроса, также не обеспечивают в полной мере реализацию оптимальной технологии баланси- ровки нагрузки, достижения эффективности кла- стеризации, оптимальной загрузки серверов при минимальном времени реализации приложений. В основе широко используемых систем рас- пределения нагрузки современных гипервизо- ров (VMware Infrastructure, VMware ESXi Server, Microsoft Hyper-V) лежат как методы прямого распределения приложений, так и настройки, использующие статистику прогнозирования ис- пользования вычислительных ресурсов [1-3; 7]. Например, при применении планировщика ре- сурсов на базе алгоритмов платформы OpenStack не учитывается в полной мере динамически из- меняющаяся, непредсказуемая интенсивность нагрузки, динамика происходящих процессов, не обеспечивается в полной мере решение задачи балансировки нагрузки, распределения ресурсов физических серверов между виртуальными ма- шинами (ВМ) и сетевыми приложениями в ре- альном времени, а значит, и гарантированное обе- спечение качества обслуживания [4-6; 9]. Повышение эффективности функционирова- ния аппаратно-программной платформы ЦОД вы- зывает необходимость разработки рациональных методов и моделей реализации сервиса распре- деления ресурсов в кластерах с балансировкой нагрузки, оптимизационных алгоритмов распре- деления запросов и программных приложений на физических серверах в реальном времени. Для исключения проблемы перегрузки ресур- сов виртуального ЦОД, ввиду ограниченности его производительности, размеров оперативной памяти вычислительных серверов, пропускной способности системы коммутации и каналов пе- редачи данных, обеспечения соответствия между типом запросов и техническими параметрами запрашиваемых ресурсов, на отношения между параметрами системы запросов и соответству- ющих им характеристик ресурсов ЦОД необхо- димо наложить ряд ограничений. В качестве кри- терия оптимальности могут быть использованы параметры максимизации производительности системы, достигаемые за фиксированный период времени. Математическая постановка задачи распределения ресурсов в кластерах с балансировкой нагрузки ЦОД Каждый запрос на реализацию прикладных функций может выполняться на одном из серве- ров кластера при соблюдении корректных отно- Рисунок 1. Формальная модель кластера ЦОД Рисунок 2. Структура системы управления аппаратно-программной платформы ЦОД шений между параметрами запроса, реализуемо- го программными приложениями разного уровня сложности и соответствующими характеристи- ками физических ресурсов ЦОД. Структура си- стемы управления аппаратно-программной плат- формы ЦОД приведена на рисунке 2. По требованию пользователей ЦОД систе- ма управления производит формирование ВМ с определенными ресурсными параметрами. Ло- кальный менеджер осуществляет контроль за- грузки физических серверов и размещение запро- сов на ресурсы ВМ. Система мониторинга ЦОД проводит передачу полученной информации глобальному менеджеру, который осуществляет миграцию ВМ и управляет перераспределением физических серверов. При этом последовательно реализуются следующие задачи: прием запросов от абонентов на реализацию услуг; распределение запросов по серверам кластера; выбор сервера в кластере, способного реали- зовать запросы пользователей; направление запросов к выбранному серве- ру кластера; распределение реализуемых программных где i - время реализации i-го приложения, имеприложений по серверам кластера; формирование совокупности виртуальных машин, реализующих приложения; ющего наименьшее отклонение от t t1 - tçàä. min; çàä.: (7) прием результатов решения задач; отправление полученных результатов поль- зователям. переходим к порядковому номеру приложения p 1 и повторяем эту процедуру примени- тельно к оставшимся приложениям. Последова- Состав и структуру серверного комплекса тельно получаем t2 , t3 и т. д.; ЦОД [5; 8] можно представить в виде кортежа H P M K , L , (1) - выделенные группы соответствующих запросов распределяем на соответствующих серве- рах кластера. где P - множество серверов кластера; M - множество устройств хранения данных; K, L - мно- Распределение программных приложений жество ресурсов телекоммуникационного обору- F f1 , f2 ,... , fn по k K ВМ осуществляется дования. Запросы на реализацию приложений можно формализовать следующим образом: с учетом ограниченных объемов ресурсов ЦОД. При этом необходимо определить число задей- ствованных ВМ и состав распределенных на них программных приложений с учетом следующих G W S, E , (2) ограничений: где W - множество атрибутов запросов; S, E - ха- рактеристики запрашиваемых ресурсов кластера. - приложение может быть реализовано только на одной из ВМ Отношение между характеристиками доступных физических ресурсов и параметрами запро- сов можно формализовать в виде следующего где ajn 1, n (8) отображения: G H W P, S M , E K , L . (3) a jn 1, åñëè ïðèëîæåíèå âûïîëíÿåòñÿ íà n ÂÌ; Данное отображение будет корректным при выполнении системы ограничений на отношения 0, â ïðîòèâíîì ñëó÷àå, между запросами и ресурсами. j 1, n , n 1, k; Модель ограничений при распределении за- просов по серверам кластера: - назначенные на ВМ приложения запрашивают суммарные объемы ресурсов не больше име- - каждое приложение i, только на одном сервере j, i 1, n j 1, m: выполняется ющихся в наличии: ajnCj Cn , ajnmj Mn , (9) m n n xij 1, xij 0,1 , (4) где Cn , Mn - производительность и память j j 1 где m - число серверов; i 1, n - число приложе- ВМ; - реализуется условие неделимости приложений; причем время реализации приложений, рас- пределенных на j сервер, не должно превышать заданного значения tçàä.: ний для всех временных интервалов tn их выпол- нения: tn ò ajn t j ajn . (10) xij ij tçàä. , ij Qi S j , (5) t 0 n n где Qi i 1 - сложность реализации приложений; Данная задача относится к классу NP-полных. Для её решения можно использовать приведен- S j - характеристика производительности сервера. Приведенный далее метод распределения заный ниже эвристический алгоритм [10; 12]: - упорядочиваем программные приложения просов по серверам кластера обеспечивает вполj r в порядке убывания их запросов на объёмы не приемлемые результаты при краткосрочном планировании: ресурсов ВМ; ранжируем ВМ k K в порядке возрастания упорядочиваем все реализуемые приложения их производительности. Для каждого очередного по возрастанию длительности их выполнения; приложения j k на каждом временном интеропределяем такой порядковый номер p приложения, при котором вале tn подбираем ВМ, способную реализовать p t1 i , i 1 (6) соответствующее приложение; - если ВМ не удается подобрать, то приложе- ние не будет выполнено. В противном случае на ВМ фиксируются требуемые объемы ресурсов. Данный алгоритм имеет полиномиальную слож- ность и обеспечивает близкое к оптимальным распределение [11; 15]. 3. Модель ограничений при распределении виртуальных машин по серверам кластера. ЦОД содержит определенное множество серверов П и K - суммарная пропускная способность фи- зических каналов и системы коммутации. В качестве критериев оптимальности при рас- пределении ресурсов ЦОД будем использовать показатели: наиболее полной загрузки оборудования ЦОД приложений Si , i (1, L) и файл-серверов H j , L M N ; j (1, M ), необходимо распределить по ним мно- K1 CPU k xijk RAM k xijk i 1 j 1 k 1 (17) жество BM k , k (1, N ) при соблюдении следу- - максимальной производительности системы ющих ограничений: - каждая ВМ может быть размещена только на ввода-вывода L M N одном сервере L M N K2 IOPSk xijk ; i 1 j 1 k 1 (18) где xijk 1, i 1 j 1 k 1 (11) - максимальной производительности системы коммутации и передачи данных n L 1, åñëè ÂÌ k ðàñïîëàãàåòñÿ K3 ri l. (19) xijk íà S i èëè H j ; i 1 l 1 Задача оптимального распределения ресурсов 0, â ïðîòèâíîì ñëó÷àå; - требования ВМ, предъявляемые к ресурсу оперативной памяти RAM физических серверов, должны удовлетворять ограничению L M N ЦОД с учетом рассмотренных ограничений яв- ляется NP-трудной, поэтому для ее решения не- обходимо воспользоваться не полиномиальными алгоритмами офлайн- или онлайн-размещения [13; 17]. RAM k xijk RAMij . i 1 j 1 k 1 (12) Предлагаемый в данной работе алгоритм производит последовательную обработку запросов Используемые ресурсы всех ВМ не должны быть больше ресурсов серверов: - ограничение на производительность серверов L M N на реализацию услуг. Для этого осуществляется их первоначальное ранжирование по убыванию запрашиваемых ресурсов. При этом внешний планировщик ЦОД выделяет каждой ВМ мак- CPU k xijk CPU j ; i 1 j 1 k 1 - ограничение на объем памяти дисков L M N Sk xijk Sij ; i 1 j 1 k 1 (13) (14) симальное значение ресурсов CPU, RAM, disk, IOPS и т. д. Определяется физический ресурс с минимальной остаточной суммой его параме- тров, и идет размещение на нем ВМ в соответ- ствии со следующей схемой. - ограничение на производительность систе- Производится ранжирование ВМ по показа- K мы ввода-вывода данных телю [4] V C V i , где i L M N i j j j 1 Vj - требование BMi к IOPSk xijk IOPSij . i 1 j 1 k 1 (15) ресурсу j, j 1, K; Cj - коэффициент значимо- Физические серверы и системы хранения дан- ных соединены между собой системой коммута- ции. Поэтому при распределении ресурсов физи- ческих серверов необходимо учитывать основные параметры системы коммутации и каналов связи между ВМ и системой хранения данных. Суммарная пропускная способность данной системы должна удовлетворять следующим ус- ловиям: n L n L сти ресурса. В соответствии с исходной схемой выбира- ется ВМ с наибольшими требованиями к ресур- сам и размещается на физическом элементе с ми- нимальным ресурсом. Наиболее целесообразно использовать при этом итерационный алгоритм, основанный на подходах динамического про- граммирования. Например, итерационный жадный алго- ритм работает следующим образом [14; 16]. ri l Ï, ri l K , (16) В качестве входных процессов ai множества i 1 l 1 i 1 l 1 S a1 , a2 , ... , an выступают конечные моменгде ri l - требуемая пропускная способность i-й ты fi их реализации. Последовательно выбран- ВМ при использовании l виртуальных каналов; ные процессы объединяются процедурой Greedy Рисунок 3. Модель кластера серверов Activity Selector s, f в множество A, в котором Значение данной вероятности определяется fi является максимальным временем окончарекуррентным способом [18]: ния всех процессов fi max fk : ak A . Greedy B n -1, a Activity Selector s, f : P B n, a , (21) n length s ; A a1 ; где n 1, 2,..., B n - a n a B 0, a 1. i 1; do if Sm fi ; for m 2 to n; then A A am ; В случае достаточно больших значений n и a можно уменьшить время вычисления P путем i m; return A. задания разницы P i - P i -1 и останов- Внешний планировщик ЦОД осуществляет ки выполнения процедуры перестановки при её оценку производительности размещенной на сердостижении [10]. Значение P i - P i -1 вере ВМ. Если производительность ВМ ниже уста- новленного уровня, внешний планировщик пере- мещает её на физический элемент с более высо- ким уровнем ресурсов и переходит на шаг 3. Если производительность ВМ выше уста- новленного уровня, внешний планировщик пере- мещает её на физический элемент с более низким уровнем ресурсов и переходит на шаг 3. В случае невозможности распределения ВМ осуществляется переход к процедуре ограничен- ного перебора. Глубина перебора, определяющая максимальное число серверов, для которых на- значается распределение, должна обеспечивать требуемый баланс между качеством сервиса и временем распределения ВМ, то есть находить приемлемое решение за допустимое время. Каче- ство сервиса можно оценить вероятностью блокировки P запросов на обслуживание, иначе - вероятностью отсутствия допустимых серверов в единицу времени. Для этого можно использовать формулу Эрланга n определяет здесь точность вычислений. Если ресурс не найден, то происходит раз- мещение следующей ВМ, требование к уровню ресурсов предыдущей ВМ понижаются и она ста- новится в общую упорядоченную очередь. Если ресурс найден, то ВМ удаляется из очереди. Выбор наилучшего по времени размещения при соблюдении всех ограничений. Модельный эксперимент Формальная модель кластера серверов с моду- лем распределения нагрузки, представленная на рисунке 3, разработана на основе характеристик платформы Huawei 2488, процессора Intel(R) Xeon(R) Gold 6154 в среде кроссплатформенно- го программного обеспечения AnyLogic 7 [19; 20]. При реализации модели, а также разработке системы распределения запросов использованы элементы библиотеки Enterprise Library. На данном рисунке представлены следующие блоки: Source - блок генерации; Queue - блок формирования очереди; Delay - блок задержки; P , a n! n (20) Match - блок согласования; Sink - блок удаления ak k ! k 0 где P - вероятность блокировки; n - число сер- веров; a - интенсивность запросов. транзактов. Уровень запрашиваемых ресурсов ВМ равно- мерно распределен в интервале 20-80 % уровня ресурсов сервера. Соотношение процессорного времени и оперативной памяти распределено равномерно. На пропускную способность систе- мы коммутации и каналов связи наложены огра- ничения до 1 Гб/с. Длительность миграции ВМ задавалась нормальным законом распределения. Исследование характеристик системы осу- ществлено в три этапа: путем последовательного использования предлагаемых методов распреде- ления запросов, запросов и ВМ, ВМ и приложе- Число прило- жений Число серве- ров T , мс T0 T1 T2 T3 50 5 4576 4112 3742 2976 100 7 5844 5231 4806 3217 150 10 6733 5820 4173 3580 200 12 6915 6113 5633 4512 300 15 7062 6549 5321 4893 Таблица. Время обработки запросов кластером ЦОД ний. Количественная оценка качества распреде- Примечание. Здесь T0 - время обработки запросов ления ресурсов ЦОД проведена путем сравнения при реализации алгоритма Round Robin; T1 - время времени обработки запросов получаемых при обработки запросов при реализации метода распредеиспользовании предложенных алгоритмов и алления запросов; T2 - время обработки запросов при горитма Round Robin. совместной реализации метода распределения запро- Предлагаемые методы распределения нагрузсов и ВМ; T3 - время обработки запросов при соки обеспечивают допустимые показатели време- ни обработки запросов при числе серверов кла- стера не более 15. С увеличением числа серверов время распределения растет по экспоненциаль- ному закону. Из результатов моделирования, представленных в таблице, следует, что наиболь- шую производительность обеспечивают методы, последовательно реализующие алгоритмы раци- онального распределения запросов, ВМ и при- ложений. При этом время обработки запросов, по сравнению с применением алгоритма Round Robin, уменьшается в среднем на 15 %. Заключение В работе рассмотрена задача построения эф- фективного механизма реализации запросов пользователей на реализацию услуг ЦОД за счет использования рациональных способов распре- деления его ресурсов. Представленные в данной статье методы и модели сервиса распределения ресурсов в кластерах с балансировкой нагрузки используют систему корректных отображений совокупности параметров запросов на известные характеристики физических ресурсов ЦОД, ите- рационный жадный алгоритм. Сокращение времени вычислений достигается при этом путем введения ограничений на допу- стимую глубину перебора. Рассмотрены методы эффективного распределения запросов по серве- рам кластера, модель распределения программ- ных приложений по множеству виртуальных ма- шин кластера, метод распределения виртуальных машин по серверам кластера и соответствующая ему модель. Разработаны имитационные модели алгоритмов функционирования системы управ- ления виртуализацией кластеров ЦОД (см. Сви- детельства о регистрации программы для ЭВМ № 2019664647 от 11.11.2019 и № 2020617795 от 17.07.2020), проведено их экспериментальное вместной реализации метода распределения запросов, ВМ и приложений. исследование. Использование предлагаемых ме- тодов позволит обоснованно выполнять распре- деление программных приложений по ВМ кор- поративного ЦОД, выбирать состав виртуальных машин и решать задачи рационального их разме- щения по физическим серверам ЦОД.

About the authors

V. P Mochalov

North Caucasus Federal University

Email: mochalov.valery2015@yandex.ru
Stavropol, Russian Federation

G. I Linets

North Caucasus Federal University

Email: kbytw@mail.ru
Stavropol, Russian Federation

N. Yu Bratchenko

North Caucasus Federal University

Email: n.b.20062@yandex.ru
Stavropol, Russian Federation

I. S Palkanov

North Caucasus Federal University

Email: ilya0693@yandex.ru
Stavropol, Russian Federation

References

Supplementary files