🏄 6+ главных алгоритмов балансировки нагрузки

Балансировка нагрузки – процесс распределения входящих запросов между доступными серверами. Популярные подходы к балансировке по-разному решают проблему перегрузки системы. В этой статье мы рассмотрим принципы работы, преимущества, недостатки и оптимальные сценарии использования самых известных алгоритмов.

Круговой алгоритм (Round Robin) и его вариации – квантовая, взвешенная и динамическая

Другие названия этого алгоритма – круговая ротация и метод круговой очередности.

Круговая ротация – алгоритм балансировки нагрузки, который распределяет входящие запросы между несколькими серверами в порядке циклической очередности. Название Round Robin происходит от старинного метода подписания общественных обращений и петиций: подписи намеренно ставили по кругу, чтобы нельзя было определить инициатора.

Принцип работы кругового алгоритма максимально прост:

• Предположим, у нас есть список серверов.
• Алгоритм начинает распределение запросов с первого сервера в списке.
• Каждый новый запрос направляется на следующий сервер в списке.
• Когда достигается конец списка, алгоритм возвращается к началу.

Главные плюсы этого подхода – простота реализации и справедливость распределения: каждый сервер получает равное количество запросов. Но, как очевидно, эта простейшая версия алгоритма будет эффективно работать только в сферической среде в вакууме, где все серверы обладают почти одинаковой конфигурацией, а все входящие запросы (задачи, процессы) имеют одинаковые приоритет и продолжительность. Поэтому на практике круговой алгоритм обычно снабжают различными улучшениями:

• Выделяют фиксированные временные промежутки (кванты) для каждой задачи. Если задача не завершается в течение своего кванта, она перемещается в конец очереди.
• Используют Weighted Round Robin, взвешенный циклический перебор, учитывающий мощность серверов. Например, если у нас есть три сервера с весами 4, 2 и 1, это означает, что первый сервер примерно в два раза мощнее второго и в четыре раза мощнее третьего. Вместо равномерного распределения запросов, как в обычном Round Robin, WRR распределяет запросы пропорционально весам серверов: из каждых 7 запросов 4 запроса пойдут на первый сервер, 2 запроса на второй, 1 запрос на третий.
• Применяют динамический круговой алгоритм Dynamic Round Robin, который учитывает текущую нагрузку на серверы при распределении запросов. При поступлении запроса алгоритм запрашивает актуальную информацию о нагрузке с каждого сервера (DRR может использовать различные метрики для оценки нагрузки на сервер – количество активных соединений, загрузку процессора, использование оперативной памяти, время отклика сервера, или комбинацию нескольких показателей). На основе полученных данных вычисляется показатель нагрузки для каждого сервера, после чего запрос направляется на сервер с наименьшим показателем.

💻 Библиотека программиста

Больше полезных материалов вы найдете на нашем телеграм-канале «Библиотека программиста»

Наименьшее количество соединений (Least Connections) и его взвешенный вариант

Наименьшее количество соединений

Наименьшее количество соединений – динамический алгоритм балансировки нагрузки, который направляет входящие запросы на сервер с наименьшим количеством активных соединений в данный момент времени. Цель Least Connections – равномерно распределить запросы между серверами, предотвращая перегрузку отдельных узлов.

Принцип работы алгоритма

• Балансировщик нагрузки отслеживает количество активных соединений на каждом сервере в пуле.
• При поступлении нового запроса балансировщик анализирует текущее состояние всех серверов.
• Запрос направляется на сервер с наименьшим количеством активных соединений.

Преимущества

• Адаптивность к различным мощностям серверов – более мощные серверы естественным образом будут обрабатывать больше запросов и, следовательно, иметь больше соединений. И напротив, менее мощные серверы будут получать меньше запросов, что предотвращает их перегрузку.
• Гибкость – если один сервер начинает работать медленнее, он будет получать меньше новых запросов.
• Улучшенное распределение нагрузки по сравнению с неоптимизированным круговым алгоритмом, который распределяет запросы равномерно без учета текущего состояния серверов.

Недостатки

• Алгоритм считает все соединения одинаковыми, не учитывая, что некоторые запросы могут быть более сложными (ресурсоемкими), чем другие.
• Количество соединений не всегда точно отражает реальную нагрузку на сервер. Например, сервер с меньшим числом соединений может выполнять более ресурсоемкие задачи.
• Вновь добавленный сервер может получить непропорционально большое количество запросов, так как изначально у него нет активных соединений.

Когда использовать

• В гетерогенной серверной инфраструктуре, где серверы имеют разную производительность.
• Когда запросы имеют относительно одинаковую сложность и требуют примерно одинакового времени обработки.

Взвешенное наименьшее количество соединений

Взвешенное наименьшее количество соединений (Weighted Least Connections) – усовершенствованный метод балансировки нагрузки, который объединяет принципы алгоритмов наименьшего количества соединений и взвешенного циклического перебора: он направляет запросы на сервер с наименьшим соотношением активных соединений к его назначенному весу.

Принцип работы

• Каждому серверу присваивается вес, отражающий его мощность.
• Балансировщик отслеживает количество активных соединений на каждом сервере.
• При поступлении нового запроса вычисляется соотношение (Активные соединения) / (Вес сервера).
• Запрос направляется на сервер с наименьшим значением этого соотношения.

Пример

Допустим, у нас есть три сервера:

• Server A – 10 активных соединений, вес 5
• Server B – 15 активных соединений, вес 10
• Server C – 8 активных соединений, вес 3

Вычисляем отношения:

• Server A – 10/5 = 2
• Server B – 15/10 = 1.5
• Server C – 8/3 ≈ 2.67

В результате новый запрос будет направлен на Server B, так как у него наименьший показатель.

Статья по теме

🤔 Инварианты: проектирование эффективных алгоритмов

Хеш IP-адреса

Алгоритм IP Hash использует IP-адрес клиента (и иногда сервера) для определения, на какой сервер направить запрос. Таким образом он обеспечивает постоянство сессии и гарантирует, что запросы от одного и того же клиента всегда попадают на один и тот же сервер.

Принцип работы:

• При поступлении запроса балансировщик нагрузки извлекает IP-адрес клиента.
• Вычисляется уникальный ключ с помощью любой подходящей хеш-функции.
• Результат хеш-функции делится по модулю на число доступных серверов.
• Все последующие запросы с этого IP будут направляться на тот же сервер.

Вывод:

Преимущества IP Hash

• Постоянство сессии – алгоритм гарантирует, что запросы от одного клиента всегда попадают на один и тот же сервер.
• Эффективность для статических IP – метод отлично работает в средах, где IP клиентов меняются редко.
• Облегчает кеширование данных на стороне сервера для конкретных клиентов.

Недостатки

• Если много пользователей приходят из одного диапазона IP, один сервер может быть перегружен.
• Неэффективен в средах, где IP клиентов часто меняются (мобильные сети).
• Может привести к неравномерной нагрузке, если некоторые клиенты генерируют больше трафика.

Статья по теме

🤤 Жадные алгоритмы: все, что нужно знать для собеседования

Наименьшее время отклика

Алгоритм Least Response Time балансирует нагрузку, направляя запросы на сервер, которые демонстрируют наилучшую производительность в данный момент. Он учитывает два ключевых фактора: время отклика сервера и количество активных соединений.

Принцип работы

• Для каждого сервера в системе балансировщик нагрузки постоянно мониторит время, которое требуется серверу для обработки запроса и отправки ответа.
• Также отслеживается количество активных соединений на каждом сервере.
• При поступлении нового запроса выбирается сервер с наименьшим временем отклика и наименьшим количеством активных соединений.
• Помимо времени отклика и количества активных соединений могут учитываться дополнительные веса: score = (response_time * weight1) + (active_ connections * weight2)

Преимущества

• Учет текущей производительности серверов и динамическая адаптация обеспечивают оптимальный баланс и наилучший пользовательский опыт.
• Метод хорошо работает с серверами разной мощности и приложениями с разными характеристиками.

Недостатки

• Сложность реализации – алгоритм требует постоянного мониторинга и анализа производительности серверов.
• Необходимость обработки большего объема данных для принятия решений создает повышенную нагрузку на балансировщик.
• Определение и динамическое обновление дополнительных весов может стать нетривиальной задачей.

Случайный выбор (Random) и лучший из двух вариантов

Случайный выбор (Random, Randomized Load Balancing) распределяет входящие запросы между серверами случайным образом. Каждый новый запрос направляется на произвольно выбранный сервер из доступного пула, и для того, чтобы у каждого сервера был равный шанс (1/n, где n – число серверов) быть выбранным, для реализации алгоритма следует использовать не генератор псевдослучайных чисел, а тасование Фишера-Йетса.

Преимущества

• Обеспечивает равномерное распределение нагрузки в долгосрочной перспективе.
• Простота реализации и низкие вычислительные затраты.
• Не требует хранения состояния предыдущих запросов.

Недостатки

Недостаток – не учитывает текущую нагрузку на серверы и их производительность, поэтому лучше всего подходит для систем, где серверы имеют примерно одинаковую производительность, а задачи – более-менее равную сложность.

Алгоритм Power of Two Random Choices (лучший из двух случайных вариантов), представленный в 1996 году Майклом Митценмахером – усовершенствованная версия случайного выбора: вместо выбора одного случайного сервера, алгоритм выбирает два случайных сервера и направляет запрос на тот из них, который имеет меньшую нагрузку. Преимущества этого подхода перед простым случайным выбором:

• Более равномерное распределение нагрузки и максимальное снижение вероятности перегрузки отдельных серверов.
• Скорость – требует сравнения метрик всего лишь двух серверов вместо анализа состояния всей системы.

Разработчики NGINX рекомендуют этот метод для высоконагруженных систем и распределенных сценариев балансировки нагрузки, например, в кластерах Kubernetes с несколькими Ingress-контроллерами.

Статья по теме

🅾️ Что такое «О» большое: объясняем на простых примерах

Наименьший объем трафика

Наименьший объем трафика (Least Bandwidth, буквально – наименьшая пропускная способность) – динамический алгоритм балансировки нагрузки, который направляет входящие запросы на сервер, передающий наименьший объем данных в текущий момент. Особенно эффективен в средах, где пропускная способность сети является критическим фактором производительности.

Принцип работы

• Балансировщик нагрузки постоянно мониторит использование пропускной способности каждого сервера.
• При поступлении нового запроса выбирается сервер с наименьшим текущим использованием полосы пропускания.
• Запрос направляется на выбранный сервер.

Преимущества

• Оптимизация использования сетевых ресурсов – алгоритм эффективно предотвращает перегрузку отдельных сетевых каналов.
• Улучшение производительности за счет избежания задержек, связанных с перегрузкой сети.
• Адаптация к изменениям в пропускной способности системы в реальном времени.

Недостатки

• Постоянное измерение пропускной способности может создавать дополнительную нагрузку на систему.
• Не учитывает использование CPU и памяти.

В заключение

В масштабных инфраструктурах часто используется взвешенный круговой алгоритм (Weighted Round Robin), поскольку он сочетает простоту реализации с эффективностью распределения нагрузки. Однако универсального решения, разумеется, не существует: в зависимости от специфики системы, более подходящим может оказаться метод наименьшего количества соединений, или хеш IP-адреса.

Стоит заметить, что абсолютное большинство крупных платформ используют комбинацию методов. Распространена практика многоуровневой балансировки: глобальное распределение по географическому принципу на верхнем уровне, с последующим применением специализированных алгоритмов на уровнях сети и приложений. Такой комплексный подход позволяет добиться оптимальной производительности и отказоустойчивости в сложных, географически распределенных системах.

То же самое касается и инструментов – популярнейший веб/прокси-сервер NGINX, который также исполняет роль балансировщика, использует все перечисленные выше методы, от кругового алгоритма до лучшего варианта из двух случайных.

Какой алгоритм балансировки нагрузки вы используете в своей инфраструктуре и почему?

***

Если вас заинтересовала тема алгоритмов балансировки нагрузки, возможно, вам стоит углубить свои знания в области алгоритмов и структур данных. На курсе «Алгоритмы и структуры данных» от Proglib Academy вы научитесь:

• Работать с популярными алгоритмами и структурами данных.
• Применять полученные навыки при разработке программ.
• Писать более короткий и эффективный код.
• Решать сложные алгоритмические задачи.

Знание алгоритмов – это не только подготовка к собеседованиям, но и расширение вашего профессионального инструментария для решения практических задач в реальных проектах.

Интересно, хочу попробовать

(function () { let link = document .getElementById ("7772e1b0-a9ef-420a-8bfe-3d323fcb1417-https://proglib.io/w/9b8479f6-78"); if (! link) return; let href = link .getAttribute ("href"); if (! href) return; let prefix = link .dataset .prefix; let action = link .dataset .action; link .addEventListener ("click", function (e) { let data = new FormData (); data .append ("url", href); apiFetch (action, { method: "POST", body: data }) .then (function (res) {}) .catch (function (err) { console .error (err); }); }) })();