Балансування навантаження англ load balancing це процес розподілення множини задач на множині ресурсів обчислювальних од

Балансування навантаження (англ. load balancing) — це процес розподілення множини задач на множині ресурсів (обчислювальних одиниць), з метою зробити загальний час їхнього опрацювання більш дієвим. Балансування навантаження може оптимізувати час відповіді і запобігти нерівномірному навантаженню на окремі обчислювальні вузли тоді як інші обчислювальні вузли бездіють.

Діаграма, що унаочнює запити користувача до кластера Elasticsearch розподілені балансувальником навантаження.

Балансування навантаження це предмет досліджень у галузі паралельних обчислень. Головні два підходи — статичні алгоритми, які не беруть до уваги стан різних машин, динамічні алгоритми, які зазвичай загальніші і дієвіші, але вимагають обміну інформацією між різними обчислювальними одиницями, що створює ризик падіння дієвості.

Огляд питання

Алгоритм балансування навантаження завжди намагається відповідати певній задачі. Серед іншого, природа задач, алгоритмічна складність, архітектура заліза, на якому алгоритм виконуватиметься, а також вимоги до ^[en] повинні бути взяті до уваги. Отже, доводиться йти на різні поступки, щоб якнайліпше відповідати потребам певного застосування.

Природа задач

Дієвість алгоритмів балансування навантаження критично залежиться від природи задач. Тому, що більше відомо про задачі під час ухвалення рішень, то більший потенціал для оптимізації.

Розмір задач

Повне знання про час виконання кожної задачі дозволяє досягти найліпшого розподілення навантаження (див. дуже простий алгоритм ^[en], що дає хороше наближення). На жаль, таких повних знань зазвичай немає.

З цієї причини існує декілька підходів, щоб отримати якесь уявлення про різні потрібні часи виконання. По-перше, у щасливому випадку, коли ми маємо відносно однорідний розмір, можливо припустити, що кожна задача має потребує середнього часу виконання. Інакше, якщо час виконання дуже нерівний, потрібні мудрованіші підходи. Один з них це додати певні метадані до кожної задачі. Покладачаючись на статистику часу виконання задач з подібними метаданими, можна зробити висновки для майбутніх задач.

Залежності

У деяких випадках, задачі залежать одна від одної. Ці взаємозалежності можна унаочнити через спрямований ациклічний граф. Зрозуміло, що деякі задачі не можуть стартувати допоки інші ще не завершені.

Припускаючи, що час необхідний для кожної задачі відомий заздалегідь, найліпший порядок виконання мусить мінімізувати загальний час виконання. Хоча це NP-складна задача задача і тому може бути складно отримати точний розв'язок. Існують алгоритми, як-от , які обчислюють оптимальний розподіл за допомогою метаевристичних методів.

Розбиття на підзадачі

Інша властивість задач критична для дизайну алгоритму балансування навантаження це їхня здатність під час виконання бути розбитими на підзадачі. Модель деревоподібних обчислень використовує цю властивість. Наприклад, в алгоритмі видпакового опитування незадіяна одиниця виконання випадковим чином опитує інших виконавців допоки не знайде зайнятий і просить його поділити його задачу між ними.

Статичні і динамічні алгоритми

Статичні

Алгоритм балансування навантаження статичний, якщо для розподілу задач він не бере до уваги стан системи. Стан системи включає міри як-от ^[en] (а іноді й перенавантаження) деяких процесорів. Натомість, припущення про усю систему робляться заздалегідь, наприклад, про час прибуття задач і ресурсні вимоги прибулих задач. Також алгоритм має глибшу інформацію про систему, як-от кількість процесорів, їхні потужності і швидкість зв'язків. Отже, статичне балансування навантаження намагається призначити відому множину задач доступним процесорам з метою унайменшити певну функцію швидкодії.

Техніки статичного балансування навантаження зазвичай централізовані довкола маршрутизатора або (мастера), який розподіляє навантаження і оптимізує функцію швидкодії. Ця мінімізація може брати до уваги інформацію пов'язану зі задачами, що їх треба розподілити і виводить очікуваний час виконання.

Перевага статичних алгоритмів це те, що вони легкі в налаштуванні і надзвичайно дієві у разі доволі регулярних задач (таких як опрацювання HTTP-запитів). Однак, все одно присутня статистична дисперсія в призначенні задач, що може призвести до перевантаження деяких обчислювальних одиниць.

Динамічні

На відміну від алгоритмів статичного розподілу навантаження, динамічні алгоритми беруть до уваги поточне навантаження кожної обчислювальної одиниці (також відомої як вузол) системи. Зі цим підходом, задачі можуть пути перерозподілені з перенавантаженого вузла на вільніший вузол, щоб пришвидшити опрацювання. Хоча ці алгоритми і набагато складніші спроєктувати, вони можуть дати чудові показники, зокрема, коли час виконання задач сильно різниться.

Динамічне балансування навантаження може бути модульнішим, бо необов'язково мати окремий вузол присвячений розподіленню роботи. Очевидно, що, якщо для ухвалення рішення алгоритм балансування навантаження вимагає занадто багато повідомлень між вузлами, то виникає ризик сповільнення розв'язання головної задачі.

Апаратна архітектура

Неоднорідні машини

Інфрасткуртура паралельних обчислень часто утворена з машин з різними характеристиками, які треба брати до уваги під час розподілення навантаження.

Наприклад, малопотужні машини можуть отримувати запити, які вимагають меншого об'єму обчислень, або, у випадку однорідних запитів чи запитів з невідомою необхідною кількістю обчислень, отримувати менше запитів ніж потужніші машини.

Спільна і розподілена пам'ять

Паралельні обчислення поділяють на дві широкі категорії: на ті, де всі процесори користуються однією спільною пам'яттю в яку і з якою вони всі пишуть і читають паралельно (модель з PRAM) і на ті, де кожна машина має свою окрему пам'ять (модель з ^[en]), а інформацією вони обмінюються за допомогою повідомлень.

Управління суперечками запису у випадку машин зі спільною пам'яттю значно сповільнює окремих виконавців. Однак, вони можуть чудово працювати паралельно. І навпаки, у випадку обміну повідомленнями, кожен процесор можу працювати в повну силу, але коли приходить час колективного обміну повідомленнями, всі чекають на останнього.

У дійсності, мало систем потрапляють чітко в одну категорію. Загалом, кожен процесор має внутрішню пам'ять, де він зберігає дані для наступних обчислень, і всі вони впорядковані в кластери. Часто, ці машини координуються через розподілену пам'ять і обмін повідомленнями. Отже, алгоритми балансування навантаження мусять бути чітко припасовані до паралельної архітектури.

Ієрархія

З точки зору ієрархії апаратних структур існує дві головні категорії алгоритмів балансування навантаження. З одного боку це такі, де завдання призначаються «розпорядником» і виконуються «робітниками», які доповідають розпорядникові про поступ у своїй роботі, а розпорядник бере відповідальність з призначення і перепризначення завдань у разі динамічного алгоритму. Література покликається до такого розкладу як до архітектури («Розпорядник-працівник»). З іншого боку, керування може бути розподілене між різними вузлами. Тоді алгоритм балансування навантаження виконується на кожному з них і відповідальність за призначення завдань (як і за перепризначення і за потреби розбиття) спільна. Друга категорія має на увазі динамічні алгоритми.

Також можливо мати проміжні стратегії, з, наприклад, провідним вузлом у кожному підкластері, який у свою чергу підпорядковується глобальному впорядкувальнику. Існують і багаторівневі організації, де архітектура «розпорядник-працівник» і розподілена архітектура чергуються, але такі стратегії швидко стають заскладними, тому рідко зустрічаються. Проєктувальники обирають алгоритми, якими легше керувати.

Пристосування для більших архітектур (масштабовність)

Алгоритми, що у вжитку дуже тривалий час (сервери, хмара тощо), з часом переживають еволюцію комп'ютерних архітектур. Однак, бажано не проєктовувати нові алгоритми на заміну вже готовим і випробуваним.

Отже, дуже важлива властивість алгоритму балансування навантаження це здатність пристосовуватись до масштабовних архітектур апаратного забезпечення. Це зветься масштабовність алгоритму. Алгоритм вважається масштабовним щодо якогось свого входового параметра, якщо його швидкодія залишається порівняно незалежною від розміру цього параметра.

Алгоритм, який здатний пристосуватись до змінної кількості обчислювальних одиниць, але їхня кількість мусить бути закріплена перед виконанням, називається формовним (англ. moldable). З іншого боку, якщо алгоритм здатний підлаштуватись до змінної кількості процесорів під час виконання, то кажуть, що алгоритм податливий (англ. malleable). Більшість алгоритмів балансування навантаження щонайменше формовні.

Відмовостійкість

Особливо в дуже великих комп'ютерних кластерах, не прийнятне виконання паралельних алгоритмів, які не можуть витримати втрату одного складника. Тому, були розроблені відмовостійкі алгоритми, які можуть визначати збої процесорів і відновлювати обчислення.

Підходи

Статичний розподіл з повним знанням про завдання:

Якщо задачі незалежні одна від одної, і їхні відповідні часи виконання можна ділити, то існує простий і оптимальний алгоритм — обчислення приросткової суми проходячи списком задач і призначаючи поточну задачу чи її частину поточному процесору.

Залежність алгоритму балансування навантаження від подільності задач

Однак, якщо завдання неподільні, то, хоча оптимізація розподілення задач це складна задача, ми все ще можемо знайти приблизне відносно рівномірне розподілення завдань за умови, що розмір кожного завдання набагато менший, ніж час роботи кожного процесора.

Здебільшого розміри задач наперед невідомі, лише грубі наближені розв'язки наявні для такої задачі. Але алгоритм оснований на приросткових сумах непридатний для цього перебігу.

Статичне балансування навантаження без завчасних знань

Статичне балансування навантаження завжди можливе навіть геть без знання часу виконання.

Циклічне планування

В алгоритмі циклічного планування перший запит відправляють першому серверу, другий другому і так далі до останнього. Тоді знов першому і т.д.

Цей алгоритм можна оптимізувати так, щоб потужніші сервери отримували більше запитів і отримували ці запити першими.

Увипадковлений статичний

Увипадковлене статичне балансування навантаження це просто призначання завдань серверам випадковим чином. Цей метод працює вельми добре. Але, якщо кількість завдань відома наперед, то навіть ефективніше буде заздалегідь обчислити випадкову перестановку. Це виключає ціну обміну повідомленнями, бо більше нема потреби в розподільнику, бо кожен процесор знає які завдання призначені йому. Навіть якщо кількість завдань заздалегідь невідома все ще можливо уникнути додаткових комунікацій використавши псевдовипадкове породження призначень відоме всім процесорам.

Дієвість цієї стратегії (виміряна як повний час виконання для всього набору завдань) зменшується зі зростанням найбільшого розміру задачі.

Інші

Також існують інші методи призначення завдань:

Геш: розподіляти запити згідно з геш-таблицею.
Сила подвійного вибору: вибрати два сервери й обрати вдаліший з них.

Примітки

Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (11 вересня 2019). Sequential and parallel algorithms and data structures : the basic toolbox. ISBN .
Liu, Qi; Cai, Weidong; Jin, Dandan; Shen, Jian; Fu, Zhangjie; Liu, Xiaodong; Linge, Nigel (30 серпня 2016). Estimation Accuracy on Execution Time of Run-Time Tasks in a Heterogeneous Distributed Environment. Sensors. 16 (9): 1386. Bibcode:2016Senso..16.1386L. doi:10.3390/s16091386. PMC 5038664. PMID 27589753. S2CID 391429.
Asghar, Sajjad; Aubanel, Eric; Bremner, David (October 2013). A Dynamic Moldable Job Scheduling Based Parallel SAT Solver. 2013 42nd International Conference on Parallel Processing: 110—119. doi:10.1109/ICPP.2013.20. ISBN . S2CID 15124201.
Punetha Sarmila, G.; Gnanambigai, N.; Dinadayalan, P. (2015). Survey on fault tolerant — Load balancing algorithmsin cloud computing. 2nd International Conference on Electronics and Communication Systems (ICECS): 1715—1720. doi:10.1109/ECS.2015.7124879. ISBN . S2CID 30175022.

[Sequential_and_parallel_algorithms-1] Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (11 вересня 2019). Sequential and parallel algorithms and data structures : the basic toolbox. ISBN .

[2] Liu, Qi; Cai, Weidong; Jin, Dandan; Shen, Jian; Fu, Zhangjie; Liu, Xiaodong; Linge, Nigel (30 серпня 2016). Estimation Accuracy on Execution Time of Run-Time Tasks in a Heterogeneous Distributed Environment. Sensors. 16 (9): 1386. Bibcode:2016Senso..16.1386L. doi:10.3390/s16091386. PMC 5038664. PMID 27589753. S2CID 391429.

[3] Asghar, Sajjad; Aubanel, Eric; Bremner, David (October 2013). A Dynamic Moldable Job Scheduling Based Parallel SAT Solver. 2013 42nd International Conference on Parallel Processing: 110—119. doi:10.1109/ICPP.2013.20. ISBN . S2CID 15124201.

[4] Punetha Sarmila, G.; Gnanambigai, N.; Dinadayalan, P. (2015). Survey on fault tolerant — Load balancing algorithmsin cloud computing. 2nd International Conference on Electronics and Communication Systems (ICECS): 1715—1720. doi:10.1109/ECS.2015.7124879. ISBN . S2CID 30175022.