Метод доповнювальних навантажень для розподілу задач в хмарних системах

Дмитренко, Олександра Анатоліївна

Метод доповнювальних навантажень для розподілу задач в хмарних системах

dc.contributor.advisor	Скулиш, М. А.
dc.contributor.author	Дмитренко, Олександра Анатоліївна
dc.date.accessioned	2025-06-23T08:41:04Z
dc.date.available	2025-06-23T08:41:04Z
dc.date.issued	2025
dc.description.abstract	Дмитренко О.А. Метод доповнювальних навантажень для розподілу задач в хмарних системах. — Кваліфікаційна наукова праця на правах рукопису. Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 172 — Телекомунікації та радіотехніка. — Навчально-науковий інститут телекомунікаційних систем КПІ ім. Ігоря Сікорського, Київ, 2025. Завдання оптимізації використання ресурсів хмарних систем має високий пріоритет, оскільки ця технологія стала широко розповсюдженою та легкодоступною. Поширеною практикою є створення ефективних сервісів, які легко адаптуються до різних типів продуктів, наприклад, безсерверні технології, платні підлаштовані під потреби бізнесу бази даних та програмне забезпечення, оптимізоване для хмари. Тестування продуктивності хмарних застосунків стало значно простішим із появою засобів розгортання, т.я. Docker та засобів оркестрації, т.я. Kubernetes, що додатково збільшило попит на хмарні ресурси. Оскільки значна кількість ресурсів витрачається на розробку та обслуговування хмарної інфраструктури, важливо розуміти, як ці ресурси можна оптимізувати. Для організації роботи застосунків на хмарі використовується планувальник. В його функції входить аналіз вимог до роботи контейнерів з обчислювальними задачами та пошук кластера та вузла розміщення для них. Також виконується збір метрик роботи контейнера. В ході аналізу наявних підходів до розподілення навантаження задач виявлено певні їх недоліки. Для оцінки потреб роботи контейнеризованої задачі використовуються наступні параметри: бажані та максимальні значення requests та limits по RAM та CPU (можна додавати додаткові показники). Ці значення є основоположними при створенні подів наKubernetes чи їх аналогів на хмарах. Якщо ці значення задані, то у задачі більший пріоритет та менша ймовірність бути вилученою з вузла в разі його перевантаження. Водночас задача може бути вилучена, якщо потребує більше ресурсів, ніж вказано у граничному значенні. Інша проблема, що виникає при роботі ПЗ, є вивільнення RAM. Якщо обчислювальна задача нею заволоділа, то при зменшенні необхідності в оперативній пам’яті її вивільнення може не відбуватись без особливих налаштувань програми. Ідея роботи — трансформувати роль бажаних та максимальних значень ресурсів що виділяються на роботу пода з вирішального чинника на координаційний параметр, прибираючи права критичного впливу на вилучення справних задач з вузла. Це можливо замінивши підхід до виділення вузлового ресурсу. Проаналізувавши історичні дані та в разі їх однорідності, можна оцінити потреби задач в кожен окреслений період часу. Відповідно до потреб однієї задачі, буде знайдено доповнення її «прогалин» у навантаженні, та заповнене в результаті комбінації цієї задачі з іншими. Робота присвячена обґрунтуванню цієї ідеї за допомогою розробки математичної моделі з використанням нечіткої теорії ґраток, та доведенню її життєздатності через розробку методу та алгоритму пошуку доповнювальних навантажень та проведенню експериментальних та аналітичних розрахунків її якості. З метою забезпечити стале повне використання виділеного ресурсу була побудована математична модель. Вона базується на принципі доповнюваності (комплементарності) та теорії нечітких ґраток (об’єднання теорії ґраток та нечіткої логіки). Параметрами моделі є RAM, CPU, мережевий ресурс, а також вона враховує дисковий простір. Під комплементарністю мається на увазі що поди в межах доповнювальних груп сумарно формують повне навантаження на доступні вузли, розподілене відповідно до часових періодів. Задача оптимізації, яку ставить матмодель є максимізувати ефективність використання ресурсів, мінімізуючи їх простій. Як обмеження, розглядається прив'язаністьконтейнера до вузла або іншої частини ПЗ та подільність обчислювальної задачі на менші. Вперше запропоновано метод доповнювальних навантажень для формування груп сталої навантаженості. Алгоритм методу спрямований на оптимізацію використаних ресурсів під час роботи багатокомпонентної системи, зокрема, при масштабуванні її вузлів для забезпечення покриття навантаження всіх користувацьких запитів. Суть методу доповнювальних навантажень. Під час пошуку комплементарних навантажень обчислювальних задач алгоритм виконує кластеризацію, в результаті чого екземпляри мікросервісів групуються за схожістю робочих шаблонів у класи еквівалентності. В межах кожної групи екземпляри сортуються за амплітудою використання ресурсів. Далі групи, що визначені як доповнювальні, перетинаються з метою знайти пари комплементарних мікросервісів. Екземпляри з протилежними шаблонами навантаження, але схожими амплітудами, комбінуються для ефективнішого використання ресурсів. Також можуть розглядатися пари з низькою амплітудою для заповнення «пробілів». Далі відбувається пошук екземплярів мікропослуг, що відповідають критеріям доповнення. Коли доповнення в межах першого підхожого кластера, чи наступних, не знаходиться, виконується збереження статистики комбінацій з усіма екземплярами, і пошук триває до знаходження доповнень або вичерпання доповнювальних груп. Процес повторюється до знаходження всіх можливих пар без повторних включень; залишкові екземпляри мікропослуг є очікуваними. Для мікросервісів, що не знайшли доповнень, застосовується додатковий аналіз екстремумів з використанням середнього та стандартного відхилення, щоб підвищити ймовірність знайти доповнення. Кластеризація і пошук продовжуються до останньої успішної спроби. Якщо залишається невелика кількість мікросервісів без пари, вони комбінуються в більшій кількості, ніж по два для досягнення мети.При реалізації алгоритму на основі методу застосовувалось Z-масштабування для нормалізації та виділення шаблону роботи мікропослуги, KMeans кластеризація для групування за схожим шаблоном роботи нормалізованих рядів. Додатково для візуалізації використовувались алгоритми FastDTW для накладання графіків шаблонів, та PCA — для зображення двовимірного простору для часових рядів замість n-вимірного. При пошуку доповнень використовувались сортування, бінарний пошук та жадібний алгоритм. Поділ на основі середнього значення та стандартного відхилення застосовувався для написання алгоритму пошуку екстремумів та розширених екстремумів для виділення їх в окремі контейнери. Групування малозатратних мікропослуг здійснювалось за допомогою розв'язання задачі про множинний рюкзак. Доповнювальний розподіл навантажень сприятиме суттєвому зменшенню необхідності розв'язання проблеми перегрупування навантаження в режимі реального часу, коштом розміщення на серверах заздалегідь сформованих груп навантажень, що утворюють доповнені ґратки. У роботі розглядаються ключові показники комп'ютерних систем, які можна виміряти та на які можна впливати. Ці характеристики включають пропускну здатність каналів передачі, оцінку продуктивності на основі затримки, обсяг оперативної та постійної пам'яті, обчислювальну потужність та кількість ядер. Запропоноване удосконалення підходу до автомасштабування у хмарній системі, спрямоване на зниження частоти необхідності масштабування шляхом ефективного планування навантаження на вузли на етапі розподілу заSдач, яке апріорі не вимагатиме масштабування. У традиційних підходах до автомасштабування хмарних ресурсів, масштабування відбувається у відповідь на зміну поточного навантаження, що призводить до частих операцій створення та видалення екземплярів обчислювальних вузлів, споживаючи додаткові ресурси для управління цими процесами. Якщо ж навантаження не змінюватиметься, то інеобхідності в масштабуванні не буде. Все ж, воно відбуватиметься в екстремальних випадках, коли ПЗ переживатиме незвичайні навантаження та відбуватиметься не для одної задачі, а для всієї групи. У дисертаційній роботі запропоновано новий підхід до планування навантаження в хмарних системах, що забезпечує оптимальне формування та розподіл пакетів задач у багатосерверному середовищі. Основою запропонованого підходу є моніторинг метрик використання ресурсів та застосування методу доповнювальних навантажень. Такий підхід оптимізує використання ресурсів хмарної системи шляхом ефективного розподілу навантаження доповнених мікропослуг між різними серверними групами. Оптимізація полягає в максимізації використання серверних ресурсів шляхом заповнення його вільного часу іншими мікросервісами й, таким чином, зменшення простою серверів. Це, своєю чергою, сприятиме покращенню загальної продуктивності РС та зменшенню витрат на обслуговування хмарних інфраструктур. Наведений підхід застосовується як до мікросервісів, так і до монолітів та безсерверні технологій, з описаними мінімальними змінами. Апробація підходу виконувалась методом імітаційного моделювання, проведенням наукового експерименту та із застосуванням методу інтелектуального аналізу даних. Для виконання апробації було розроблено алгоритм та програму для визначення комплементарних екземплярів мікросервісів, які могли б ефективно використовувати серверні ресурси. Запропонований алгоритм може бути корисним для постачальників хмарних послуг та організацій, які використовують хмарні середовища для розгортання своїх застосунків. Апробація показала, що залежно від обраного ключового критерію: CPU, RAM чи мережевий ресурс, можна зменшити кількість технічного забезпечення на 8%, 10% та 17% відповідно, що сумарно становить понад 9% з врахуванням частки присутності кожного критерію. До технічних покращень також відноситься підвищення енергоефективності послуг хостингу на 10–15% та подовження строку служби на 8–12% на вузлахповністю з доповнювальним навантаженням. Причиною цього є сталість навантаження та відсутність стрибків електроенергії. Також, запропонований підхід сприяє зменшенню кількості перепланувань розміщення обчислювальних задач на 25–35%, що становить 9–15% від задач вузлів-планувальників. Таких вузлів на кожному кластері залежно від розміру від 3 до 7. Це дозволяє зменшити технічні вимоги до вузлів, або ж підвищити на них навантаження шляхом додавання нових вузлів у кластер. У зв’язку з тим, що кількість доповнювальних груп складатиме 20–30%, відповідно спостерігатиметься зменшення потреб в автомасштабуванні до 20%. На вузлах, де частково чи повністю будуть розміщені доповнювальні групи, можна зменшити кількість запасного ресурсу headroom відповідно до пропорції присутності доповнювальних груп на обчислювальних вузлах. Пропорція буде ефективною щодо кількості запасного ресурсу, якщо доповнювальні групи складатимуть 20–24% залежно від ключового ресурсу, а отже запасний ресурс можна зменшити на максимально 20%. В разі виділення вузлів, повністю заповнених групами доповнювальних навантажень, можна забезпечити збільшення пропускної можливості багатосерверної системи в години пік, яке становитиме 5–15% на 10–15% відсотках серверів. Основні ідеї методу доповнювальних навантажень впроваджені у курсі «Big Data», що викладається аспірантам НН ІТС на кафедрі ІТТ.
dc.description.abstractother	O.A. Dmytrenko. Method of complementary loads for task distribution in cloud systems. — Qualifying scientific work on manuscript rights. Thesis for graduation scientific degree of Philosophy Doctor by speciality 172 — Telecommunications and radio engineering. — Educational and Scientific Institute of Telecommunication Systems of KPI named after Igor Sikorsky, Kyiv, 2025. The task of optimizing cloud system resource usage has high priority, as this technology has become widespread and easily accessible. Creating efficient services that easily adapt to different types of products is a common practice, for example, serverless technologies, paid databases customized for business needs, and software optimized for the cloud. Testing cloud application performance has become significantly easier with the emergence of Docker and Kubernetes, which has further increased demand for cloud resources. Since a significant amount of resources is spent on developing and maintaining cloud infrastructure, it's important to understand how these resources can be optimized. A scheduler is used to organize applications on the cloud. Its functions include analyzing the requirements for running containers with computational tasks and finding a cluster and placement node for them. The scheduler also collects container performance metrics. When analyzing existing approaches to task load distribution, certain drawbacks were identified. The following parameters are used to assess the needs of a containerized task: desired and maximum values of requests and limits for RAM and CPU (additional indicators can be added). These values are fundamental when creating pods on Kubernetes or their analogs on clouds. If these values are set, the task has higher priority and less likelihood of being evicted from a node in case of overload. At the same time, a task can be evicted if it requires more resources than specified in the limit value. Another problem that occurs during software operation is the release of RAM. If a computationaltask has seized it, then when the need for RAM decreases, its release may not occur without special program settings. The idea of this work is to transform the role of desired and maximum resource values allocated for pod operation from a decisive factor to a coordination parameter, removing the right of critical impact on the eviction of functioning tasks from a node. This is possible by changing the approach to node resource allocation. By analyzing historical data and in case of their homogeneity, it's possible to estimate the needs of tasks in each outlined time period. According to the needs of one task, a complement to its «gaps» in the load will be found and filled as a result of combining this task with others. The work is dedicated to substantiating this idea through the development of a mathematical model using fuzzy lattice theory, proving its viability through the development of a method and algorithm for finding complementary loads, and conducting experimental and analytical calculations of its quality. To ensure consistent full use of allocated resources, a mathematical model was built. It is based on the principle of complementarity and the theory of fuzzy lattices (combining lattice theory and fuzzy logic). The model parameters are RAM, CPU, network resource, and it also takes into account disk space. By complementarity, it means that pods within complementary groups collectively form a complete load on available nodes, distributed according to time periods. The optimization task set by the mathematical model is to maximize resource utilization efficiency while minimizing idle time. As constraints, the attachment of a container to a node or other part of the software and the divisibility of a computational task into smaller ones are considered. For the first time, a method of complementary loads for forming groups of stable loading is proposed. The algorithm of the method is aimed at optimizing the resources used during the operation of a multi-component system, in particular, when scaling its nodes to ensure coverage of the load of all user requests. The essence of the complementary loads method: During the search for complementary loads of computational tasks, the algorithm performs clustering,as a result of which microservice instances are grouped according to the similarity of working patterns into equivalence classes. Within each group, instances are sorted by the amplitude of resource use. Then, groups defined as complementary intersect to find pairs of complementary microservices. Instances with opposite load patterns but similar amplitudes are combined for more efficient resource use. Pairs with low amplitude may also be considered to fill «gaps.» Next, a search is conducted for microservice instances that meet the complementary criteria. When a complement within the first suitable cluster or subsequent ones is not found, statistics of combinations with all instances are saved, and the search continues until complements are found or complementary groups are exhausted. The process is repeated until all possible pairs are found without repeated inclusions; residual microservice instances are expected. For microservices that didn't find complements, additional analysis of extremes is applied using mean and standard deviation to increase the probability of finding a complement. Clustering and search continue until the last successful attempt. If a few microservices remain without pairs, they are combined in larger quantities than two to achieve the goal. When implementing the algorithm based on the method, Z-scaling was used for normalization and highlighting the microservice operation pattern, KMeans clustering for grouping by similar normalized series operation pattern. Additionally, for visualization, FastDTW algorithms were used to overlay pattern graphs, and PCA to represent a two-dimensional space for time series instead of n-dimensional. When searching for compliments, sorting, a binary search, and a greedy algorithm were used. Division based on mean value and standard deviation was applied to write an algorithm for finding extremes and extended extremes to separate them into individual containers. Grouping of low-cost microservices was carried out by solving the multiple knapsack problem. Complementary load distribution will significantly reduce the need to solve the problem of load regrouping in real-time, at the cost of placing pre-formed load groups on servers that form complemented lattices.The paper considers key indicators of computer systems that can be measured and influenced. These characteristics include channel bandwidth, latency-based performance assessment, RAM and permanent memory capacity, computing power, and number of cores. An improvement to the approach to auto-scaling in the cloud system is proposed, aimed at reducing the frequency of scaling needs through effective planning of node load at the task distribution stage, which a priori will not require scaling. In traditional approaches to auto-scaling cloud resources, scaling occurs in response to changes in current load, leading to frequent operations of creating and deleting computing node instances, consuming additional resources to manage these processes. If the load doesn't change, there will be no need for scaling. Still, it will occur in extreme cases when the software experiences unusual loads and will occur not for a single task but for the entire group. The dissertation proposes a new approach to load planning in cloud systems, providing optimal formation and distribution of task packages in a multi-server environment. The basis of the proposed approach is monitoring resource usage metrics and applying the complementary loads method. This approach optimizes the use of cloud system resources through efficient distribution of the load of complemented microservices between different server groups. Optimization consists in maximizing the use of server resources by filling its free time with other microservices and thus reducing server downtime. This, in turn, will contribute to improving the overall cloud performance and reducing the cost of maintaining cloud infrastructures. The approach applies to microservices as well as monoliths and serverless technologies, with described minimal changes. The approach was tested using simulation modelling, conducting a scientific experiment, and applying the data mining method. For testing, an algorithm and program were developed to determine complementary instances of microservices that could efficiently use server resources. The proposed algorithm can be useful for cloud service providers and organizations that use cloud environments to deploy their applications. Testing has shown that depending on the selected key criterion: CPU, RAM, or network resources, it's possible to reduce the amount of technicalequipment by 8%, 10%, and 17% respectively, which in total represents over 9% when accounting for the proportion of each criterion. Technical improvements also include increasing the energy efficiency of hosting services by 10–15% and extending the service life by 8–12% on nodes fully loaded with complementary workloads. This is due to the stability of the load and the absence of power surges. Also, the proposed approach helps reduce the number of computational task placement rescheduling by 25–35%, which represents 9–15% of scheduler node tasks. Depending on the size, there are 3 to 7 such nodes in each cluster. This allows for reducing technical requirements for nodes or increasing their load by adding new nodes to the cluster. Since the number of complementary groups will comprise 20–30%, there will be a corresponding reduction in auto-scaling needs of up to 20%. On nodes where complementary groups are partially or fully placed, the amount of headroom reserve resource can be reduced in proportion to the presence of complementary groups on computational nodes. The proportion will be effective regarding the amount of reserve resource if complementary groups make up 20–24% depending on the key resource, thus headroom can be reduced by a maximum of 20%. In the case of allocating nodes fully loaded with complementary workload groups, it is possible to increase the throughput capacity of a multi-server system during peak hours, which will amount to 5-15% on 10-15% of servers. The main ideas of the method of complementary loads are implemented in the course «Big Data», which is taught to graduate students of the National Institute of Information Technology at the Department of Information Technology
dc.format.extent	272 с.
dc.identifier.citation	Дмитренко, О. А. Метод доповнювальних навантажень для розподілу задач в хмарних системах : дис. … д-ра філософії : 172 Телекомунікації та радіотехніка / Дмитренко Олександра Анатоліївна. – Київ, 2025. – 272 с.
dc.identifier.uri	https://ela.kpi.ua/handle/123456789/74367
dc.language.iso	uk
dc.publisher	КПІ ім. Ігоря Сікорського
dc.publisher.place	Київ
dc.subject	хмарна інфраструктура
dc.subject	горизонтальне масштабування
dc.subject	Kubernetes
dc.subject	оптимізація витрат
dc.subject	розподіл завдань
dc.subject	телекомунікаційні сервіси
dc.subject	конфігурація ресурсів
dc.subject	мікросервісна архітектура
dc.subject	оркестрація контейнерів
dc.subject	часові ряди
dc.subject	енергоефективність
dc.subject	комп’ютерні системи
dc.subject	доповнювальні навантаження
dc.subject	багатосерверні системи
dc.subject	класифікація трафіку
dc.subject	мікропослуги
dc.subject	безсерверні технології
dc.subject	cloud infrastructure
dc.subject	horizontal scaling
dc.subject	cost optimization
dc.subject	traffic classification
dc.subject	task distribution
dc.subject	telecommunications services
dc.subject	resource allocation
dc.subject	microservice architecture
dc.subject	container orchestration
dc.subject	time series
dc.subject	energy efficiency
dc.subject	computer systems
dc.subject	complementary workloads
dc.subject	multi-server systems
dc.subject	serverless technologies
dc.subject.udc	004.75
dc.title	Метод доповнювальних навантажень для розподілу задач в хмарних системах
dc.title.alternative	Method of complementary loads for task distribution in cloud systems
dc.type	Thesis Doctoral

Файли

Контейнер файлів

Зараз показуємо 1 - 1 з 1

Назва:: Dmytrenko_dys.pdf
Розмір:: 15.55 MB
Формат:: Adobe Portable Document Format

Завантажити

Ліцензійна угода

Зараз показуємо 1 - 1 з 1

Назва:: license.txt
Розмір:: 8.98 KB
Формат:: Item-specific license agreed upon to submission
Опис:

Завантажити

Зібрання

Дисертації (ІТТ)
Дисертації (вільний доступ)