Managing data center resources using heuristic search
The features of the cloud data center are analyzed from the point of view of resource management. The two-stage method for consolidating virtual machines based on the use of local beam search algorithm is proposed and investigated with aim to solve the problem of managing the resources of a cloud da...
Збережено в:
| Дата: | 2018 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут програмних систем НАН України
2018
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/307 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Репозитарії
Problems in programming| id |
pp_isofts_kiev_ua-article-307 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/ee/2ceb39b084c2ec3b43df565d5d6982ee.pdf |
| spelling |
pp_isofts_kiev_ua-article-3072024-04-28T11:45:30Z Managing data center resources using heuristic search Управление ресурсами облачных центров обработки данных на основе эвристического поиска Керування ресурсами хмарних центрів обробки даних на основі евристичного пошуку Zharikov, E.V. virtualization; resource management; cloud computing; heuristic search UDC 004.94; 004.4; 004.62 виртуализация; управление ресурсами; облачные вычисления; эвристический поиск УДК 004.94; 004.4; 004.62 віртуалізація; керування ресурсами; хмарні обчислення; евристичний пошук УДК 004.94; 004.4; 004.62 The features of the cloud data center are analyzed from the point of view of resource management. The two-stage method for consolidating virtual machines based on the use of local beam search algorithm is proposed and investigated with aim to solve the problem of managing the resources of a cloud data center. In this paper, the work of heuristics of the first and second stages of the proposed method is analyzed. The beam search algorithm was developed for solving the data center resource management problem. The data about tasks and physical machines from the Google cluster-usage traces are used to evaluate the proposed method. The proposed method allows to switch to a low-power mode on average 56 percent of physical servers potentially identified for switching to sleep mode based on an upper estimate of the required capacity of resources. Virtual machine consolidation is performed taking into account the limitation of the permissible number of migrations per physical server.Problems in programming 2017; 4: 016-027 Проанализированы особенности облачного центра обработки данных с точки зрения управления ресурсами. Для решения задачи управления ресурсами облачного центра обработки данных предложено и исследовано двухэтапный метод консолидации виртуальных машин на основе использования локального лучевого поиска. В статье проанализирована работа эвристики первой и второй стадий предложенного метода, разработан алгоритм лучевого поиска для решения задачи управления ресурсами. Для анализа работы метода использованы данные о поступлении задач в кластер Google. Предложенный метод позволяет переключить в режим пониженного энергопотребления в среднем 56 процентов физических серверов, потенциально определенных для переключения в режим сна на основе верхней оценки необходимой емкости ресурсов. Перераспределение виртуальных машин выполняется с учетом ограничения допустимого количества миграций на один физический сервер.Problems in programming 2017; 4: 016-027 Проаналізовано особливості хмарного центру обробки даних (ЦОД) з точки зору керування ресурсами. Для вирішення задачі керування ресурсами хмарного центру обробки даних запропоновано і досліджено двостадійний метод консолідації віртуальних машин на базі використання локального променевого пошуку. В статті проаналізовано роботу евристики першої та другої стадій запропонованого методу, розроблений алгоритм променевого пошуку для вирішення задачі керування ресурсами. Для аналізу роботи методу використані дані про надходження завдань в кластер Google. Запропонований метод дозволяє переключити в режим зниженого енергоспоживання в середньому 56 відсотків фізичних серверів, що потенційно визначені для переключення в режим сну за допомогою верхньої оцінки необхідної ємності ресурсів. Перерозподіл віртуальних машин виконується з урахуванням обмеження допустимої кількості міграцій на один фізичний сервер.Problems in programming 2017; 4: 016-027 Інститут програмних систем НАН України 2018-11-15 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/307 10.15407/pp2017.04.016 PROBLEMS IN PROGRAMMING; No 4 (2017); 16-27 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 4 (2017); 16-27 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 4 (2017); 16-27 1727-4907 10.15407/pp2017.04 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/307/301 Copyright (c) 2018 PROBLEMS OF PROGRAMMING |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2024-04-28T11:45:30Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
virtualization resource management cloud computing heuristic search UDC 004.94 004.4 004.62 |
| spellingShingle |
virtualization resource management cloud computing heuristic search UDC 004.94 004.4 004.62 Zharikov, E.V. Managing data center resources using heuristic search |
| topic_facet |
virtualization resource management cloud computing heuristic search UDC 004.94 004.4 004.62 виртуализация управление ресурсами облачные вычисления эвристический поиск УДК 004.94 004.4 004.62 віртуалізація керування ресурсами хмарні обчислення евристичний пошук УДК 004.94 004.4 004.62 |
| format |
Article |
| author |
Zharikov, E.V. |
| author_facet |
Zharikov, E.V. |
| author_sort |
Zharikov, E.V. |
| title |
Managing data center resources using heuristic search |
| title_short |
Managing data center resources using heuristic search |
| title_full |
Managing data center resources using heuristic search |
| title_fullStr |
Managing data center resources using heuristic search |
| title_full_unstemmed |
Managing data center resources using heuristic search |
| title_sort |
managing data center resources using heuristic search |
| title_alt |
Управление ресурсами облачных центров обработки данных на основе эвристического поиска Керування ресурсами хмарних центрів обробки даних на основі евристичного пошуку |
| description |
The features of the cloud data center are analyzed from the point of view of resource management. The two-stage method for consolidating virtual machines based on the use of local beam search algorithm is proposed and investigated with aim to solve the problem of managing the resources of a cloud data center. In this paper, the work of heuristics of the first and second stages of the proposed method is analyzed. The beam search algorithm was developed for solving the data center resource management problem. The data about tasks and physical machines from the Google cluster-usage traces are used to evaluate the proposed method. The proposed method allows to switch to a low-power mode on average 56 percent of physical servers potentially identified for switching to sleep mode based on an upper estimate of the required capacity of resources. Virtual machine consolidation is performed taking into account the limitation of the permissible number of migrations per physical server.Problems in programming 2017; 4: 016-027 |
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2018 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/307 |
| work_keys_str_mv |
AT zharikovev managingdatacenterresourcesusingheuristicsearch AT zharikovev upravlenieresursamioblačnyhcentrovobrabotkidannyhnaosnoveévrističeskogopoiska AT zharikovev keruvannâresursamihmarnihcentrívobrobkidanihnaosnovíevrističnogopošuku |
| first_indexed |
2024-09-16T04:07:47Z |
| last_indexed |
2024-09-16T04:07:47Z |
| _version_ |
1818568247031627776 |
| fulltext |
Моделі та засоби паралельних і розподілених програм
© Е.В. Жаріков, 2017
16 ISSN 1727-4907. Проблеми програмування. 2017. № 4
УДК 004.94; 004.4; 004.62
Е.В. Жаріков
КЕРУВАННЯ РЕСУРСАМИ ХМАРНИХ ЦЕНТРІВ ОБРОБКИ
ДАНИХ НА ОСНОВІ ЕВРИСТИЧНОГО ПОШУКУ
Проаналізовано особливості хмарного центру обробки даних (ЦОД) з точки зору керування ресурса-
ми. Для вирішення задачі керування ресурсами хмарного центру обробки даних запропоновано і дос-
ліджено двостадійний метод консолідації віртуальних машин на базі використання локального про-
меневого пошуку. В статті проаналізовано роботу евристики першої та другої стадій запропоновано-
го методу, розроблений алгоритм променевого пошуку для вирішення задачі керування ресурсами.
Для аналізу роботи методу використані дані про надходження завдань в кластер Google. Запропоно-
ваний метод дозволяє переключити в режим зниженого енергоспоживання в середньому 56 відсотків
фізичних серверів, що потенційно визначені для переключення в режим сну за допомогою верхньої
оцінки необхідної ємності ресурсів. Перерозподіл віртуальних машин виконується з урахуванням
обмеження допустимої кількості міграцій на один фізичний сервер.
Ключові слова: віртуалізація, керування ресурсами, хмарні обчислення, евристичний пошук.
Вступ
Керування ресурсами хмарного
ЦОД – важлива задача, вирішення якої в
сучасних умовах забезпечує роботу таких
сервісних моделей хмарних обчислень, як
інфраструктура як сервіс (англ. IaaS), пла-
тформа як сервіс (англ. PaaS) та застосун-
ки як сервіс (англ. SaaS). Для досягнення
бажаних показників енергоефективності
та продуктивності роботи ІТ інфраструк-
тури в центрах обробки даних застосову-
ються технології віртуалізації апаратного
забезпечення, програмних засобів, мереж,
сховищ даних, робочих місць та інші.
Сервісна модель IaaS дозволяє
більш ефективно використовувати апара-
тне забезпечення фізичного сервера (ФС)
за рахунок віртуалізації його локальних
ресурсів. ФС надає такі ресурси, як про-
цесорний час, пам'ять, локальну підсис-
тему зберігання даних та підсистему дос-
тупу до мережі. При цьому, клієнтові на-
дається частина ресурсів ФС у вигляді ві-
ртуальної машини (ВМ) або контейнеру.
Для реалізації сучасних інформаційних
послуг клієнт розгортає одну або декілька
ВМ необхідної конфігурації, яка визначе-
на провайдером хмарних послуг. Кожній
ВМ гіпервізор надає частку ресурсів ФС.
З точки зору керування ресурсами хмар-
ного ЦОД, ресурси всіх ФС об’єднуються
в пул і надаються віртуальним машинам
для використання. Таким чином, виникає
комплекс задач, пов’язаних з керуванням
ресурсами хмарного ЦОД. Один із варіан-
тів перерозподілу ресурсів пулу між вір-
туальними машинами полягає в реалізації
процесу консолідації віртуальних машин
(англ. virtual machine consolidation). Кон-
солідація віртуальних машин – це розмі-
щення віртуальних машин на фізичних
серверах на базі технологій віртуалізації з
метою досягнення певних показників
ефективності використання ресурсів ЦОД.
Фактично, керуючі впливи виробляються
для віртуальних машин, фізичних серве-
рів, мережевих пристроїв, сховищ, засто-
сувань та інших підсистем.
Для роботи кожного екземпляру
застосування в хмарному ЦОД зазвичай
створюється окрема ВМ. На відміну від
монолітних застосувань, які потребують
нарощування ресурсів вертикально (англ.
scale-up) при зростанні навантаження, за-
стосування для хмарних ЦОД (англ.
cloud-native applications) потребують на-
рощування ресурсів горизонтально (англ.
scale-out). Горизонтальне нарощування
ресурсів полягає у створенні додаткових
екземплярів застосування у вигляді ВМ
для обслуговування зростаючого наван-
таження (запитів клієнтів). Останнім ча-
сом, для забезпечення роботи хмарних за-
стосувань широко використовуються так
звані контейнери (англ. containers). Кон-
тейнер – це середовище для виконання ек-
земпляра застосування. Контейнери ізо-
Моделі та засоби паралельних і розподілених програм
17
льовані один від одного і виконуються в
спільній віртуальній машині.
В статті розглядається робота за-
стосувань на базі ВМ. Виходячи з певних
бізнес-потреб клієнт може динамічно змі-
нювати конфігурацію ВМ або налаштовує
механізми балансування навантаження,
відмовостійкості та резервного копіюван-
ня. В процесі роботи хмарного сервісу
клієнти створюють множину ВМ. В ре-
зультаті зміни навантаження, зміни кіль-
кості запитів клієнтів та кількості пакет-
них задач, кількість віртуальних машин
змінюється. Відповідно, змінюється кіль-
кість ВМ, що виконуються на окремому
ФС, тому деякі ФС виявляються незаван-
таженими до максимально можливого по-
рогу і витрачають зайву енергію.
З метою більш ефективного вико-
ристання ресурсів хмарного ЦОД засоби
віртуалізації надають можливість "живої"
міграції (англ. live migration) ВМ з одного
ФС на інший. При цьому, вплив на роботу
ВМ є мінімальним, і для клієнта міграція
ВМ не впливає на виконання задач. Але
навантаження на фізичні сервери, які
обмінюються цією ВМ, зростає.
Таким чином, однією з головних
задач при керуванні ресурсами хмарного
ЦОД є розміщення і перерозміщення
віртуальних машин таким чином, щоб
задіяти меншу кількість фізичних серве-
рів та зменшити кількість міграцій віртуа-
льних машин. Процес перерозподілу вір-
туальних машин серед фізичних серверів,
консолідацію ВМ, можливо виконувати
як неперервно, так і дискретно. Вирішен-
ня проблеми консолідації віртуальних
машин представлено в багатьох публіка-
ціях [1]. Але дослідження виконувалися
для наявних на той час технологій віртуа-
лізації та хмарних технологій. В сучасних
ЦОД впроваджуються все нові і нові
апаратні та системні засоби, які співісну-
ють з технологіями попередніх поколінь.
Таким чином, актуальною є розробка но-
вих алгоритмів і методів для керування
обчислювальними ресурсами ЦОД в ці-
лому, та розміщенням віртуальних ма-
шин, зокрема.
Для вирішення задачі керування
ресурсами хмарного ЦОД пропонується
двостадійний метод на базі використання
алгоритму променевого пошуку. Запро-
понований метод призначений для вирі-
шення однієї з підзадач керування ресур-
сами шляхом консолідації віртуальних
машин. В статті проаналізовано роботу
евристики першої та другої стадій запро-
понованого методу, розроблений алго-
ритм променевого пошуку, уточнені фун-
кція оцінювання та умови закінчення ро-
боти алгоритму. Для аналізу роботи мето-
ду використані дані про надходження за-
вдань у кластер Google.
1. Аналіз публікацій
Останнім часом запропоновано ба-
гато методів та алгоритмів для вирішення
проблеми керування ресурсами ЦОД [1–3].
Зокрема, задача консолідації віртуальних
машин розглядається як оптимізаційна за-
дача з різними цільовими функціями. Та-
кож, задача консолідації віртуальних ма-
шин розглядається як багатокритеріальна
оптимізаційна задача [4, 5]. Складність цієї
задачі полягає у наявності великої кількос-
ті станів середовища та обмежень. Крім
того, складність виявляється при форму-
люванні цільової функції, до якої входять
декілька показників, які треба оптимізува-
ти. В результаті аналізу існуючих рішень
з’ясувалося, що досягти ефективності де-
яких показників одночасно виявляється
неможливим. Наприклад, неможливо дося-
гнути одночасно високої швидкості розго-
ртання ВМ та енергозбереження, або од-
ночасно високої продуктивності та енерго-
збереження.
Для промислових ЦОД з хмарними
інфраструктурами використовуються про-
сті алгоритми керування, такі як first-fit,
best-fit та їх модифікації (Eucalyptus [6],
Microsoft [7], Google [8]). Це обумовлено
вимогами робастності застосувань клієн-
тів та участю адміністраторів в автомати-
зованому процесі керування ресурсами
ЦОД при постійному моніторингу якісних
показників.
В дослідженнях використовуються
такі цільові функції, як мінімізація
споживання електроенергії, мінімізація
порушень угод про якість сервісу
(SLA), мінімізація мережевого трафіку,
Моделі та засоби паралельних і розподілених програм
18
максимізація продуктивності та викорис-
тання ресурсів. Однією з основних умов
для сучасних кластерів ФС є можливість
роботи методів керування ресурсами в
режимі онлайн [3]. Ці методи використо-
вують потоки керування, що працюють
паралельно. Разом з цим допускається
застосування методів керування ресур-
сами, які спрацьовують при появі пев-
них умов роботи кластеру, або через
певний проміжок часу. Такі методи вико-
ристовують потоки керування, що пра-
цюють послідовно. Для такого випадку
нові завдання зазвичай розміщуються
на ФС, які не задіяні в процесі консоліда-
ції ВМ.
Крім традиційних евристик та дете-
рмінованих алгоритмів при керуванні ре-
сурсами ЦОД використовуються і алгори-
тми локального пошуку, такі як еволюцій-
ні алгоритми [9], алгоритми оптимізації
мурашиних колоній [10], табу пошук [11],
пошук з емуляцією відпалу [12]. Більш
ефективним на нашу думку є використан-
ня локального пошуку на другій стадії оп-
тимізації, після підготовки відповідного
набору станів детермінованими алгорит-
мами з метою покращити рішення, знайде-
не на першій стадії.
Таким чином, в цій статті проаналі-
зовано застосування алгоритму промене-
вого пошуку в складі двостадійного мето-
ду для керування ресурсами хмарного
ЦОД з метою зменшити кількість міграцій
ВМ та збільшити кількість ФС, переклю-
чених у режим сну.
2. Модель системи
На теперішній час більшість послуг
клієнти отримують на базі хмарних цент-
рів обробки даних. Хмарні ЦОД – це скла-
дні системи, що складаються з серверних
підсистем, підсистем зберігання даних,
мережевих підсистем та підсистем інжене-
рного забезпечення.
В статті розглянуто задачу керу-
вання ресурсами окремої підсистеми
ЦОД у вигляді кластера з використанням
віртуалізації. Для побудови кластеру в
сучасних ЦОД використовують два під-
ходи компоновки: з використанням гете-
рогенної або гомогенної конфігурації.
Обидва підходи мають свої недоліки та
переваги, однак уникнути розміщення ге-
терогенних конфігурацій в масштабі
ЦОД в більшості випадків не вдається.
Конфігурації кожного кластеру можуть
відрізнятися з причин еволюції елемент-
ної бази серверів, сховищ та мережевих
пристроїв, а також появи нових вимог
користувачів до ІТ-інфраструктури. Од-
нак має місце і найгірший випадок, коли
конфігурації фізичних серверів у класте-
рі відрізняються.
Дослідження роботи запропонова-
ного двостадійного методу, що базується
на алгоритмі променевого пошуку, вико-
нані для кластеру, який складається з
фізичних серверів різної конфігурації.
Кожен ФС надає для локальних ВМ такі
ресурси як: процесорний час (CPU), обсяг
пам’яті (RAM), доступ до підсистеми
зберігання даних (IOPS), доступ до
мережевої підсистеми (NET) та інші. В
залежності від наявної ємності ресурсів
ФС, вимог до ресурсів з боку ВМ, часу
виконання завдань всередині її та інтен-
сивності надходження завдань кількість
ВМ, що виконуються на ФС, постійно
змінюється. Зміна кількості локальних
ВМ відбувається в таких станах: розгор-
тання нової ВМ, завершення роботи ВМ,
міграція ВМ.
В сучасних умовах, при викорис-
танні промислових гіпервізорів та швидкі-
сних локальних мереж, середній час мігра-
ції віртуальної машини в середині ЦОД
складає приблизно півхвилини, в залежно-
сті від обсягу пам’яті, що використовує
ВМ.
Крім того, на процеси керування
ресурсами також впливає час включення
фізичного сервера, який складає 3–4 хви-
лини в залежності від конфігурації. Таким
чином, краще перемикати фізичний сервер
в режим сну. Переключення фізичного
сервера з режиму сну в режим роботи
відбувається значно швидше, чим холод-
ний старт сервера.
Аналіз роботи запропонованого
методу виконано з урахуванням двох
ресурсів, що надаються для ВМ: CPU
та RAM. Однак метод може бути доповне-
ний іншими ресурсами, які потребує ВМ.
Моделі та засоби паралельних і розподілених програм
19
Вибір саме двох ресурсів обумовлено
використанням вхідних даних з набору
Google cluster-usage traces (GCT) [13]. Для
аналізу роботи алгоритму променевого
пошуку використано дві таблиці з набору
GCT, а саме "Machine events" та "Task
events table". Випадковим чином з першої
таблиці обрано 6000 ФС, з другої таблиці
обрано 70000 завдань. З таблиці "Machine
events" для кожного ФС використано такі
атрибути: machine ID, capacity: CPU,
capacity: memory. З таблиці "Task events
table" для кожного ФС використано такі
атрибути: "task index within the job",
"machine ID", "resource request for CPU
cores", "resource request for RAM". Дані в
таблицях нормовані відносно ФС з найбі-
льшим значенням ємності відповідного
ресурсу серед його кластеру.
Процеси циклу керування можуть
повторюватись через певні проміжки часу
при наявності двох вимог: міграції ВМ, ви-
значені на попередньому кроці завершені
та є передумови для переключення ФС в
режим сну. Таким чином, запропонований
двостадійний метод керування ресурсами
використовує потоки керування, що пра-
цюють послідовно.
3. Постановка задачі
Кластер керування складається з
множини P з M фізичних серверів та
множини V з N віртуальних машин,
, N M . В процесі розробки та аналізу
роботи алгоритму променевого пошуку та
в процесі циклу керування міграціями кі-
лькість ФС та ВМ не змінюється.
Для кожного завдання з таблиці
"Task events table" розгортається окрема
ВМ. В загальному випадку, між запусками
алгоритму променевого пошуку кількість
ФС та ВМ може змінюватись.
Задана ємність j-ї ВМ для ресурсу
k, що позначена як ]1,0(k
jc , ,{CPUk
}RAM , визначається вимогами завдання і
нормовано відносно ФС з найбільшою єм-
ністю ресурсу k . Ємність фізичного сер-
вера i для ресурсу k , що позначена
]1,0(k
iC , визначається типом ФС і нор-
мовано відносно ФС з найбільшою ємніс-
тю ресурсу k .
Множина P складається з множини
A фізичних серверів, які визначені для
вимикання, та множини B фізичних сер-
верів, які надають ресурси для ВМ, що бу-
дуть мігрувати з ФС, які належать до мно-
жини A, PBA , BA .
Міграцію віртуальної машини j на
фізичний сервер i позначимо як 1,0ijU .
Міграція відбувається якщо 1ijU . Кожна
ВМ з множини V має свій ID, який в про-
цесі роботи алгоритму пов'язаний з номе-
ром j . Кожний ФС теж має свій ID, який в
процесі роботи алгоритму пов’язаний з
номером i .
Основною метою розробки і засто-
сування двостадійного методу керування
ресурсами хмарного ЦОД є зменшення кі-
лькості міграцій ВМ під час циклу керу-
вання та збільшення кількості ФС, що пе-
реключені в режим сну.
4. Двостадійний метод керування
ресурсами на основі променевого
пошуку
В основу метода покладено алго-
ритм променевого пошуку та евристики
для оцінки стану кластера ЦОД. Робота
методу складається з двох стадій. На пер-
шій стадії відбувається підготовка даних,
на другій стадії визначається план міграцій
ВМ.
Вхідними даними алгоритму про-
меневого пошуку є: n – ширина променя,
A – список ФС, які є претендентами для
перемикання в режим сну, B – список ФС
для обміну ВМ, в якому є вільні ресурси і є
можливість розмістити додаткові завдання
у вигляді ВМ.
Ідея алгоритму: перегляд i -го ФС зі
списку A та пошук таких або такого ФС зі
списку B , куди можливо мігрувати j -ту
ВМ з i -го ФС. Якщо вдалося звільнити всі
або частку ФС зі списку A , видаємо ре-
зультат у вигляді матриці ijU , яка є пла-
ном міграцій.
Опис роботи алгоритму променево-
го пошуку.
Перша стадія: підготовка вхідних
даних для другої стадії. Формування спис-
ку A фізичних серверів, які треба звільни-
Моделі та засоби паралельних і розподілених програм
20
ти від ВМ, та списку B фізичних серверів
для визначення плану міграцій.
Друга стадія виконується для кож-
ного ФС із списку A .
1. На кожному кроці обираємо одну
ВМ, назначену на i-й ФС і розглядаємо на-
ступні варіанти обміну (міграцій):
a) мігрувати ВМ на інший ФС, в
якого залишилось достатньо вільних ресу-
рсів CPU та RAM;
b) перевірити можливість обміну
з іншим ФС віртуальною машиною, яка
вимагає менше ресурсів (так ми розгляда-
ємо лише стани з кращою оцінкою та
уникаємо можливих зациклювань) і, в
результаті, ФС не буде перенавантаженим
після обміну.
2. З усіх можливих обмінів обира-
ється n обмінів з найвищою оцінкою.
3. Завершуємо пошук, якщо i-й ФС
вдалося звільнити від віртуальних машин
або, якщо не можна побудувати нові ста-
ни (тобто не залишилось жодного варіан-
та для реалізації допустимого обміну а)
або b)).
Порівняння станів виконується за
допомогою критерію:
n
i
i
m
i
i fuJ
1
2
1
2
, (1)
де iu – кількість використовуваних ре-
сурсів на i-му ФС, if – кількість віль-
них ресурсів на i-му ФС, m – кількість
ФС у списку B, n – кількість ФС у спис-
ку A .
Таким чином, алгоритм поступово
зменшує використовувані ресурси на ФС,
які належать до списку A , та завантажує
ФС зі списку B.
Умови завершення алгоритму
Для завершення роботи алгоритму
пропонуються умови.
1. Вичерпання списку A .
2. Неможливість мігрувати всі ВМ
з певної визначеної кількості ФС ThA
поспіль.
Якщо другу умову не застосовува-
ти, цикли пошуку виконуються занадто
довго, порівняно з часом на створення но-
вої ВМ та часом на міграцію для її з сере-
дніми вимогами до ресурсів пам’яті. Для
визначення ATh пропонується застосувати
евристику, яка полягає у розгляді певного
відсотку фізичних серверів із списку A ,
але не менше, ніж фізичних серверів. У
реалізації досліджуваного алгоритму
прийнято 05.0ATh , 10 . З меншими
значеннями алгоритм пропускає значну
кількість ФС, що могли бути переключені
в режим сну, але в результаті завершення
алгоритму були не звільнені від локаль-
них ВМ. Даний критерій завершення
вводиться для зменшення часу виконання
алгоритму.
Опис першої стадії роботи методу.
Отримання списку фізичних серве-
рів, з яких треба мігрувати всі ВМ з ме-
тою подальшого переключення ФС в ре-
жим сну пропонується здійснювати за до-
помогою двох методик: нижньої границі
та порогу вільних ресурсів. Розглянемо
кожну з методик більш детально.
Методика нижньої границі полягає
у визначенні такої кількості фізичних сер-
верів, які вимкнути в результаті міграції
усіх ВМ, що на них працює, не уявляється
можливим. Таке уявлення виникає з гіпо-
тез, що використовуються в роботі алго-
ритму визначення нижньої границі.
Пошук нижньої границі виконуєть-
ся таким чином:
1) знаходимо середній обсяг наяв-
них ресурсів за всіма ФС, на яких працю-
ють ВМ,
MQC
Q
T
Q
i
k
i
k
av
0,
1
1
.
Значення для кожного ресурсу k розрахо-
вуються окремо;
2) по кожному ресурсу окремо
рахуємо суму необхідних ресурсів для
виконання всіх наявних ВМ,
,
1
R
j
k
j
k cD NR 0 ;
Моделі та засоби паралельних і розподілених програм
21
3) окремо по кожному ресурсу
рахуємо відношення необхідних ресурсів
до середнього обсягу ресурсів та округля-
ємо значення до більшого цілого,
k k k
avE D T ;
4) нижньою границею буде найбі-
льше число kE з отриманих на кроці 3;
5) сортуємо фізичні сервери од-
ним з наступних способів:
a) за обсягом ресурсів ФС, потім
за відношенням використаних ресурсів до
кількості працюючих ВМ;
b) за обсягом ресурсів ФС, потім
за кількістю назначених завдань, потім ві-
дношенням використаних ресурсів до кі-
лькості локальних ВМ.
В результаті досліджень роботи
алгоритму з’ясувалося, що варіант b)
виявився значно ефективнішим. При його
використанні на одному й тому самому
наборі даних вдалося вимкнути в серед-
ньому 82 ФС, тоді як при використанні
варіанту а) вдалося вимкнути в середньо-
му лише 33 ФС.
В результаті, знаходимо різницю
між кількістю ФС, що використовуються,
та отриманою нижньою границею. Знай-
дене число – це кількість ФС списку А
на вимкнення, які є першими у відсорто-
ваному списку. Решта ФС потрапляє у
список В. Таким чином, методика ниж-
ньої границі дозволяє отримати оцінку
наявної вільної ємності фізичних ресур-
сів кластеру.
Ідея методики порогу вільних ре-
сурсів полягає у такому формуванні спис-
ку А, при якому до цього списку потрап-
ляють ФС, загальна кількість невикорис-
таних ресурсів яких перевищує обсяг ре-
сурсів одного з ФС кластеру.
Позначимо поріг вільних ресурсів
як . Побудова списку А з використанням
порогу вільних ресурсів виконується на-
ступним чином:
1) встановлюємо значення ;
2) з множини P відбираємо ФС, у
яких кожного вільного ресурсу більше за
значення ;
3) по кожному ресурсу окремо
рахуємо суму вільних ресурсів,
MQCF
Q
i
freek
i
k
0,
1
,
;
4) сортуємо обрані ФС аналогічно
до варіанту b) з методики нижньої границі;
5) проходимо за відсортованим
списком. Поки сума ресурсів більша за
обсяг поточного ФС віднімаємо від суми
цей обсяг, додаємо поточний ФС в список
А та переходимо до наступного ФС,
інакше завершуємо проходження списку.
Таким чином, отримуємо список А з ФС,
які треба переключити в режим сну, та
список В з ФС для обміну віртуальними
машинами.
5. Оцінка результатів
моделювання
Дослідження роботи двостадійного
методу виконане на фрагментах набору
даних GCT [13]. Дані для тестування і до-
слідження методу обрані з GCT і являють
собою частину за певний діапазон часу.
Це необхідно, щоб врахувати всі дані за
один і той самий період часу в журналах
GCT. З набору випадковим чином відіб-
рано 70000 завдань з певними вимогами
до ресурсів k . Для кожного завдання буде
розгорнута окрема ВМ в процесі моделю-
вання. Обираємо 6000 фізичних серверів,
з яких на 5832 серверах розміщено ВМ, та
на 168 серверах завдань немає, але вони
доступні для розміщення ВМ. Моделю-
вання виконане на комп’ютері з процесо-
ром i5-3570 та обсягом системної пам’яті
4024 Мб.
Якісними показниками роботи
алгоритму є кількість вимкнених ФС
PMsleep та кількість міграцій ВМ VMmig, за
допомогою яких ФС вивільнюються від
ВМ. Крім того, враховано час роботи ме-
тоду, t.
В таблиці 1 представлені результати
роботи запропонованого методу з консолі-
дації ВМ для різних значень . В таблиці
2 представлені результати роботи методу
при консолідації ВМ з використанням ме-
тодики нижньої границі.
Моделі та засоби паралельних і розподілених програм
22
Таблиця 1
Результати моделювання консолідації ВМ з використанням
методики порогу вільних ресурсів
B A PMsleep VMmig t, s
0.005 199 3 0 0 0.53
0.004 299 3 0 0 0.69
0.003 1098 9 0 0 4.05
0.002 1393 10 0 0 6.55
0.001 1868 28 13 219 38.08
0.0009 1943 31 15 263 42.29
0.0008 2002 39 22 349 67.93
0.0007 2081 43 24 399 81.02
0.0006 2204 48 28 432 94.14
0.0005 2302 55 32 504 105.48
0.0004 2407 63 36 554 141.43
0.0003 2565 73 43 683 143.16
0.0002 2764 82 48 782 166.54
0.0001 3706 95 59 992 238.06
0.00005 4323 106 68 1199 330.18
0.00001 5095 116 75 1336 463.36
0 5328 125 84 1459 518.34
Таблиця 2
Результати моделювання консолідації ВМ з використанням методики нижньої границі
B A PMsleep VMmig t, s
5707 125 82 1460 508.09
Вплив значення порогу на якіс-
ні показники роботи алгоритму є суттє-
вим (рис. 1 та 2), залежність виявилася
майже лінійною. Чим менший поріг
тим більше ФС потрапляють на вхід
алгоритму.
При 0 деякі ФС (а саме ті, у
яких хоча б один ресурс повністю зайня-
тий) не потрапляють на вхід алгоритму,
тому що при перевірці наявності ресурсів
використовується строга нерівність. При
0.0002 алгоритм з методикою порогу
вільних ресурсів починає працювати більш
ефективно і на граничних значеннях пра-
цює краще чим з методикою нижньої гра-
ниці.
Після формування списку А ефек-
тивність пошуку кінцевого стану кластера
можливо оцінити за допомогою відношен-
ня кількості ФС, що заплановані для пере-
ключення у режим сну, до кількості ФС,
що фактично визначені для перемикання в
режим сну після роботи другої стадії
методу. Ефективність перемикання ФС в
режим сну зростає з ростом значення
порогу і знаходиться в діапазоні від
45 % до 65 %.
Для перевірки роботи алгоритму з
різними методиками та їх порівняння
створено декілька наборів даних з одна-
ковою кількістю ФС та завдань за інші
періоди часу в наборі даних GCT. В ре-
зультаті моделювання отримані показни-
ки ефективності, які розрізняються не бі-
льше ніж на 7 %.
Перевагою використання методики
з порогом вільних ресурсів є можливість
адаптуватися до стану кластера шляхом
Моделі та засоби паралельних і розподілених програм
23
Рис. 1. Вплив порогу на кількість ФС, переключених в режим сну
Рис. 2. Вплив порогу на кількість міграцій
зміни порогу перед циклом керування,
враховуючи інші ресурси, час міграції ВМ
та інтенсивність надходження заявок на
створення нових ВМ.
В процесі дослідження роботи ме-
тоду, з метою встановлення впливу шири-
ни променя на якісні показники роботи ал-
горитму, ширина променю для алгоритму
променевого пошуку змінювалась в діапа-
зоні від 1 до 15 (табл. 3 та 4).
При використанні методики ниж-
ньої границі збільшення ширини променя
алгоритму призводить до суттєвого збі-
льшення часу пошуку рішення. Так, при
ширині променя n=10 час виконання ал-
горитму значно зростає і стає неприпус-
тимим для використання в кластері з ви-
сокою динамікою процесів створення ВМ
(табл. 3).
Моделі та засоби паралельних і розподілених програм
24
Таблиця 3
Результати моделювання консолідації ВМ з використанням методики нижньої границі
n PMsleep VMmig t, c
1 23 423 66.72
2 23 435 101.33
3 23 433 137.75
4 23 450 173.57
5 82 1460 508.09
6 82 1457 812.05
7 83 1471 832.64
8 81 1418 894.11
9 83 1479 1169.78
10 80 1417 -
11 82 1428 -
12 82 1449 -
13 85 1520 -
14 83 1501 -
15 84 1487 -
Таблиця 4
Результати моделювання консолідації ВМ з використанням методики
з порогом вільних ресурсів
n PMsleep VMmig t, c
1 27 422 53.51
2 35 548 116.5
3 57 986 186.26
4 57 959 204.49
5 57 940 247.78
6 57 918 331.03
7 55 922 383.36
8 59 969 466.55
9 57 943 492.38
10 56 957 471.13
11 56 944 549.1
12 58 972 584.52
13 60 1063 718.3
14 58 1021 791.87
15 61 1042 844.12
Крім того, зміна ширини променя
при використанні кожної методики може
не призводити до суттєвого покращення
якісних показників, при суттєвому збіль-
шенні часу пошуку. Так, для методики з
нижньою границею зміна ширини променя
з 5 до 15 не призводить до покращення
якісних показників, а для методики з поро-
гом вільних ресурсів покращення якісних
показників не відбувається при ширині
променя від 3 до 15 (рис. 3 та 4).
Моделі та засоби паралельних і розподілених програм
25
Рис. 3. Вплив ширини променя на кількість ФС, переключених в режим сну
Рис. 4. Вплив ширини променя на кількість міграцій
Таким чином, треба звертати увагу
на кількість міграцій, забезпечуючи їх до-
пустиму кількість. З урахуванням виснов-
ків, рекомендується обирати ширину про-
меня від 5 до 8, в залежності від умов ро-
боти методу.
Висновки
Для керування ресурсами хмарного
ЦОД на рівні кластера в статті запропоно-
вано і досліджено двостадійний метод на
базі алгоритму променевого пошуку. В
статті проаналізовано роботу евристики
першої та другої стадій запропонованого
методу, розроблений алгоритм променево-
го пошуку для вирішення задачі керування
ресурсами. Для аналізу роботи методу ви-
користані дані про надходження завдань в
кластер Google. Запропонований метод до-
зволяє переключити в режим сну в серед-
ньому 56 відсотків фізичних серверів, що
потенційно визначені для переключення в
режим сну за допомогою верхньої оцінки
необхідної ємності ресурсів.
Перерозподіл віртуальних машин
виконується з урахуванням обмеження до-
пустимої кількості міграцій. Завдяки ура-
хуванню обмеження кількості міграцій на
один фізичний сервер запропонований ме-
тод може бути застосований в реальних
умовах ЦОД.
В результаті дослідження пропону-
ється використовувати методику з порогом
вільних ресурсів, що показала більш якісні
Моделі та засоби паралельних і розподілених програм
26
результати консолідації ВМ. Перевагою
використання методики з порогом вільних
ресурсів є можливість адаптуватися до
стану кластера шляхом зміни порогу перед
циклом керування, враховуючи інші ресу-
рси, час міграції ВМ та інтенсивність над-
ходження заявок на створення нових ВМ.
Також встановлено, що рекомендо-
вана ширина променя в алгоритмі проме-
невого пошуку складає від 5 до 8, в залеж-
ності від умов роботи методу, обмежень на
кількість міграцій ВМ та обмежень на час
виконання алгоритму.
Для перевірки роботи алгоритму з
різними методиками та їх порівняння
створено декілька наборів даних з однако-
вою кількістю ФС та завдань за інші пері-
оди часу в наборі даних GCT. Отримані
показники ефективності розрізняються не
більше ніж на 7 %.
1. Pires F.L., & Barán, B. (2015, May). A virtual
machine placement taxonomy. In Proc. of the
15th IEEE/ACM International Symposium on
Cluster, Cloud and Grid Computing
(CCGrid). P. 159–168.
2. Ahmad R.W., Gani A., Hamid S.H.A., Shiraz
M., Yousafzai A., & Xia F. A survey on
virtual machine migration and server
consolidation frameworks for cloud data
centers. Journal of Network and Computer
Applications. 2015. 52. P. 11–25.
3. Telenyk S., Zharikov E., & Rolik O. An
approach to virtual machine placement in
cloud data centers. In Radio Electronics &
Info Communications (UkrMiCo), 2016
International Conference. IEEE. September,
2016. P. 1–6.
4. Pires F.L., & Barán B. Multi-objective virtual
machine placement with service level
agreement: A memetic algorithm approach. In
Proceedings of the 2013 IEEE/ACM 6th
International Conference on Utility and Cloud
Computing. IEEE Computer Society. 2013,
December. P. 203–210.
5. Saber T., Ventresque A., Brandic I., Thorburn
J., & Murphy L. Towards a multi-objective
vm reassignment for large decentralised data
centres. 8th International Conference on
Utility and Cloud Computing (UCC), 2015
IEEE/ACM. IEEE. 2015, December.
P. 65–74.
6. Eucalyptus community [Online] – Available
from: http://open.eucalyptus.com/
7. Lee S., Panigrahy R., Prabhakaran V.,
Ramasubramanian V., Talwar K., Uyeda L.,
& Wieder U. Validating heuristics for virtual
machines consolidation. Microsoft Research,
MSR-TR-2011-9. 2011. P. 1–14.
8. Sharma B., Chudnovsky V., Hellerstein J.L.,
Rifaat R., & Das C.R. Modeling and
synthesizing task placement constraints in
Google compute clusters. In Proceedings of
the 2nd ACM Symposium on Cloud
Computing. ACM. (2011, October). p. 3.
9. Mark, C. C. T., Niyato, D., & Chen-Khong, T.
Evolutionary optimal virtual machine
placement and demand forecaster for cloud
computing. IEEE International Conference on
Advanced Information Networking and
Applications (AINA), IEEE. 2011, March.
P. 348–355.
10. Gao Y., Guan H., Qi Z., Hou Y., & Liu L. A
multi-objective ant colony system algorithm
for virtual machine placement in cloud
computing. Journal of Computer and System
Sciences. 2013. 79(8). P. 1230–1242.
11. Ferreto, T., De Rose, C. A., & Heiss, H. U.
Maximum migration time guarantees in
dynamic server consolidation for virtualized
data centers. In European Conference on
Parallel Processing Springer, Berlin,
Heidelberg. 2011, August. P. 443–454.
12. Wu Y., Tang M., & Fraser W. A simulated
annealing algorithm for energy efficient
virtual machine placement. In IEEE
International Conference on Systems, Man,
and Cybernetics (SMC), IEEE. 2012, October.
P. 1245–1250.
13. Reiss C., Wilkes J., & Hellerstein J.L. Google
cluster-usage traces: format+ schema. Google
Inc., White Paper. 2011. P. 1–14.
References
1. Pires, F. L., & Barán, B. (2015, May). A
virtual machine placement taxonomy. In Proc.
of the 15th IEEE/ACM International
Symposium on Cluster, Cloud and Grid
Computing (CCGrid). pp. 159-168.
2. Ahmad, R. W., Gani, A., Hamid, S. H. A.,
Shiraz, M., Yousafzai, A., & Xia, F. (2015). A
survey on virtual machine migration and
Моделі та засоби паралельних і розподілених програм
27
server consolidation frameworks for cloud
data centers. Journal of Network and
Computer Applications, 52, pp. 11-25.
3. Telenyk, S., Zharikov, E., & Rolik, O. (2016,
September). An approach to virtual machine
placement in cloud data centers. In Radio
Electronics & Info Communications
(UkrMiCo), 2016 International Conference
(pp. 1-6). IEEE.
4. Pires, F. L., & Barán, B. (2013, December).
Multi-objective virtual machine placement
with service level agreement: A memetic
algorithm approach. In Proceedings of the
2013 IEEE/ACM 6th International
Conference on Utility and Cloud Computing
(pp. 203-210). IEEE Computer Society.
5. Saber, T., Ventresque, A., Brandic, I.,
Thorburn, J., & Murphy, L. (2015,
December). Towards a multi-objective vm
reassignment for large decentralised data
centres. 8th International Conference on
Utility and Cloud Computing (UCC), 2015
IEEE/ACM (pp. 65-74). IEEE.
6. Eucalyptus community [Online] – Available
from: http://open.eucalyptus.com/
7. Lee, S., Panigrahy, R., Prabhakaran, V.,
Ramasubramanian, V., Talwar, K., Uyeda, L.,
& Wieder, U. (2011). Validating heuristics for
virtual machines consolidation. Microsoft
Research, MSR-TR-2011-9, pp. 1-14.
8. Sharma, B., Chudnovsky, V., Hellerstein, J.
L., Rifaat, R., & Das, C. R. (2011, October).
Modeling and synthesizing task placement
constraints in Google compute clusters. In
Proceedings of the 2nd ACM Symposium on
Cloud Computing (p. 3). ACM.
9. Mark, C. C. T., Niyato, D., & Chen-Khong, T.
(2011, March). Evolutionary optimal virtual
machine placement and demand forecaster for
cloud computing. IEEE International
Conference on Advanced Information
Networking and Applications (AINA), (pp.
348-355). IEEE.
10. Gao, Y., Guan, H., Qi, Z., Hou, Y., & Liu, L.
(2013). A multi-objective ant colony system
algorithm for virtual machine placement in
cloud computing. Journal of Computer and
System Sciences, 79(8), pp. 1230-1242.
11. Ferreto, T., De Rose, C. A., & Heiss, H. U.
(2011, August). Maximum migration time
guarantees in dynamic server consolidation
for virtualized data centers. In European
Conference on Parallel Processing (pp. 443-
454). Springer, Berlin, Heidelberg.
12. Wu, Y., Tang, M., & Fraser, W. (2012,
October). A simulated annealing algorithm for
energy efficient virtual machine placement. In
IEEE International Conference on Systems,
Man, and Cybernetics (SMC), 2012 (pp.
1245-1250). IEEE.
13. Reiss, C., Wilkes, J., & Hellerstein, J. L.
(2011). Google cluster-usage traces: format+
schema. Google Inc., White Paper, 1-14.
Одержано 01.10.2017
Про авторів:
Жаріков Едуард В’ячеславович,
кандидат технічних наук,
доцент, докторант Національного
технічного університету України
"КПІ імені Ігоря Сікорського".
Кількість наукових публікацій в
українських виданнях – 86.
Кількість наукових публікацій в
зарубіжних виданнях – 17.
Індекс Хірша – 1.
http://orcid.org/0000-0003-1811-9336.
Місце роботи автора:
Національний технічний університет
України "КПІ імені Ігоря Сікорського".
Тел.: 38044 204 86 10.
E-mail: zharikov.eduard@acts.kpi.ua
|