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

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

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

==Огляд питанняАлгоритм зрівноваження навантаги завжди намагається відповідати певній задачі. Серед іншого, природа задач, алгоритмічна складність, архітектура заліза, на якому алгоритм виконуватиметься, а також вимоги до  повинні бути взяті до уваги. Отже, доводиться йти на різні поступки, щоб якнайліпше відповідати потребам певного застосування.
Природа задачДієвість алгоритмів зрівноваження навантаги критично залежиться від природи задач. Тому, що більше відомо про задачі під час ухвалення рішень, то більший потенціал для оптимізації.
Розмір задачПовне знання про час виконання кожної задачі дозволяє досягти найліпшого розподілення навантаги (див. дуже простий алгоритм , що дає хороше наближення). На жаль, таких повних знань зазвичай немає.

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

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

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

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

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

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

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

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

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

Алгоритм, який здатний пристосуватись до змінної кількості обчислювальних одиниць, але їхня кількість мусить бути закріплена перед виконанням, називається формовним (). З іншого боку, якщо алгоритм здатний підлаштуватись до змінної кількості процесорів під час виконання, то кажуть, що алгоритм податливий (). Більшість алгоритмів зрівноваження навантаги щонайменше формовні.
ВідмовостійкістьОсобливо в дуже великих комп'ютерних кластерах, не прийнятне виконання паралельних алгоритмів, які не можуть витримати втрату одного складника. Тому, були розроблені відмовостійкі алгоритми, які можуть визначати збої процесорів і відновлювати обчислення.
ПідходиСтатичний розподіл з повним знанням про завдання: приросткова сумаЯкщо задачі незалежні одна від одної, і їхні відповідні часи виконання можна ділити, то існує простий і оптімальний алгоритм — обчислення приросткової суми проходячи списком задач і призначаючи поточну таску чи її частину поточному процесору.

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

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

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

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

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

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




 