tekBlueprint

Сводная статья по теме выбора подхода балансировки нагрузки в зависимости от задачи. Решил собрать основные алгоритмы и подходы. Думаю, часть информации пересекается с тем что описано в книге “Designing Data-Intensive Applications” (та что с кабаном). Хотя могу путать, так как читал давно.

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

Введение

Зачастую при разработке современных сервисов/микросервисов возникает необходимость в масштабировании доступных ресурсов при росте нагрузки. Но невозможно бесконечно масштабироваться вертикально, поэтому используется подход с горизонтальным масштабированием. При этом появляется необходимость в правильном выборе способа балансировки нагрузки. От эффективности и правильности выбора алгоритма балансировки напрямую зависят ключевые характеристики системы: задержки (latency), надежность (reliability) и корректность сохранения состояния (state consistency).

Казалось бы, задача проста – принять входящий запрос и направить его на один из доступных серверов в пуле. Однако реальность гораздо сложнее. Не все серверы одинаковы: они могут иметь разную вычислительную мощность, разное количество свободных ресурсов (CPU, RAM, I/O), разную текущую нагрузку (количество активных соединений, время обработки запроса). Запросы также не одинаковы: одни требуют миллисекундного ответа (API вызовы), другие – постоянного соединения (WebSockets, стримы gRPC, подключения к базам данных), третьи связаны с сохранением состояния сессии пользователя или работы с кэшем. Неправильный выбор алгоритма может привести к:

• Перегрузка серверов, в то время как другие будут простаивать.
• Увеличению задержек, когда запросы попадают на серверы, где очередь обработки уже перегружена.
• Потери предыдущего состояния, когда при балансировке кэшированных данных или сессий запросы могут уходить на “неправильный” сервер, требуя повторной аутентификации или перезагрузки кэша.
• Нарушение отказоустойчивости, если трафик продолжает поступать на упавший сервер, пока health check не обнаружит проблему.

Балансировщики нагрузки могут размещаться на разных уровнях OSI модели:

• L4 (Transport Layer):
  • Работают на уровне TCP/UDP.
  • Видят только IP-адреса и порты.
  • Не анализируют содержимое запроса (HTTP-хедеры, куки).
  • Быстрее, но “глупее”.
  • Примеры: Linux IPVS, HAProxy в режиме TCP, AWS NLB, DSR.
• L7 (Application Layer):
  • Работают на уровне протокола приложения (HTTP, HTTPS, gRPC и т.д.).
  • Понимают содержимое запроса (URL, заголовки, тело запроса), что позволяет принимать решения на основе данных запроса (например, sticky-сессии на основе кук, маршрутизация на основе пути URL).
  • Примеры: HAProxy в режиме HTTP, Nginx, Envoy, Yandex Application Load Balancer, AWS ALB/ELB.

Примеры размещения для L7 балансировщиков:

• Sidecar Proxy:
  • Легковесный прокси, развернутый рядом с каждым приложением в контейнере (Kubernetes) или микросервисе.
  • Балансировка происходит локально для каждого сервиса, часто с дополнительными возможностями наблюдаемости и управления трафиком.
  • Примеры: Могут создаваться с Service Mesh (например, Istio, Linkerd).
• Client-Side Load Balancer:
  • Клиентское приложение или библиотека.
  • Приложение само выбирает сервер из списка, полученного от службы обнаружения (Discovery Service) или по заранее определенному списку серверов.
  • Алгоритмы балансировки встроены в приложение или библиотеку.
  • Примеры: Ribbon в Spring Cloud, gRPC Client Load Balancing.

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

Базовые алгоритмы

Эти алгоритмы подходят для простых сценариев, когда серверы в пуле однородны (одинаковая мощность, конфигурация) и запросы относительно короткие и одинаковые по характеру нагрузки. Их главные преимущества – простота реализации и предсказуемость распределения (кроме случайного выбора).

Round Robin (RR)

Балансировщик поддерживает внутренний счетчик или указатель на следующий сервер в пуле. Каждый новый запрос последовательно направляется на следующий сервер в списке, после чего указатель перемещается к следующему. Если список серверов [S1, S2, S3], то порядок будет: S1 -> S2 -> S3 -> S1 -> S2 -> S3 ....

Weighted Round Robin (WRR)

Каждому серверу присваивается вес (weight), пропорциональный его мощности или желаемому доле трафика. Балансировщик “виртуально” дублирует сервер в списке пропорционально его весу. Например:

• Сервер S1 (weight=2), S2 (weight=1), S3 (weight=1).
• Виртуальный список: [S1, S1, S2, S3].
• Порядок запросов: S1 -> S1 -> S2 -> S3 -> S1 -> S1 -> S2 -> S3 ...
• В результате S1 получит 50% трафика (2 из 4 “виртуальных” слотов), S2 и S3 – по 25% каждый.

Идеально подходит, когда серверы в пуле имеют разную производительность (например, разное количество CPU/ядер, разный тип дисков) или когда вы хотите постепенно вводить новые, менее мощные серверы в эксплуатацию с меньшим процентом трафика.

Random

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

1. Для каждого входящего запроса генерируется случайное число.
2. Это число используется для выбора одного сервера из пула (например, random_index = random(0, N-1), где N - количество серверов).
3. Запрос направляется на выбранный сервер.

Адаптивные алгоритмы с учётом текущей нагрузки

Когда запросы сильно различаются по времени обработки (например, набор из простых GET и сложных POST с запросами к СУБД) или серверы неоднородны, простые алгоритмы RR/WRR становятся неэффективными. Адаптивные алгоритмы помогают решить такие задачи, отслеживая текущее состояние серверов.

Least Connections (LC)

Балансировщик постоянно отслеживает количество активных (открытых, обрабатываемых) соединений на каждом сервере. Новый запрос направляется на сервер с минимальным текущим числом активных соединений. Например:

• Сервер S1 (connections=0), S2 (connections=1), S3 (connections=5).
• Порядок запросов: S1 -> S1 -> S2 ...
• В результате S1 получит 2 соединения, S2 одно соединение и S3 останется без новых соединений.
  • S1 (connections=2), S2 (connections=2), S3 (connections=5)

Этот алгоритм отлично подходит для долгоживущих соединений. Для соединений, которые долго удерживаются (WebSockets, стримы gRPC, подключения к базам данных, FTP), количество соединений – гораздо более показательная метрика нагрузки, чем просто количество запросов (которое может быть фиксированным для таких соединений). LC эффективно распределяет “вес” таких долгих соединений.

Weighted Least Connections (WLC)

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

• S1: weight=2, connections=10 -> priority=5.0
• S2: weight=1, connections=8 -> priority=8.0
• S3: weight=1, connections=6 -> priority=6.0
• Следующий запрос уйдет на S1 (5.0 < 6.0 < 8.0), несмотря на высокое число соединений, так как его относительно большая мощность позволяет обрабатывать их.

Формула расчёта приоритета сервера.

Далее выбирается сервер с минимальным приоритетом.

Least Response Time (LRT)

Балансировщик измеряет среднее время ответа (Round Trip Time - RTT) или последнее время ответа от каждого сервера и направляет новый запрос на сервер с минимальным измеренным временем ответа. Например:

• S1: rtt=10ms
• S2: rtt=20ms
• S3: rtt=30ms
• Следующий запрос уйдет на S1, так как последний запрос выполнился за 10 миллисекунд.

Resource-based

Более продвинутые адаптивные алгоритмы могут выполнять более сложные расчёты, чем простой подсчет соединений или измерение RTT. Для получения точной картины реальной нагрузки выполняется отслеживание использования системных ресурсов на каждом сервере: CPU, память, дисковый I/O, сеть. Идея в том, чтобы направлять запросы не просто на менее загруженные серверы, а на серверы, где есть достаточные свободные ресурсы для эффективной обработки нового запроса. Балансировщик периодически получает метрики от агентов мониторинга (или встроенных модулей) на каждом сервере. На основе этих метрик вычисляется некоторый “индекс нагрузки” или “ресурсный приоритет”. Новый запрос направляется на сервер с минимальным значением этого индекса.

Например, есть такое распределение.

Следующий запрос попадёт на сервер S1, так как его приоритет самый наименьший.

Пример формулы расчета приоритета.

Где w1, w2, w3, w4 – веса, отражающие важность каждого ресурса для вашего конкретного сервера. Например, для приложения с интенсивным использованием CPU вес CPU будет выше, чем для тех которые интенсивно используют дисковый I/O.

Примеры использования:

• Когда в пуле есть серверы с разной конфигурацией (разное количество CPU, разный тип дисков SSD/HDD), этот тип балансировки может более точно распределять нагрузку с учетом реальных возможностей.
• В пуле одновременно работают и тяжёлые задачи требующие CPU (обработка видео, вычисления), и I/O задачи (работа с файлами, базами данных). Алгоритм может попытаться балансировать между этими типами нагрузками.

Балансировка с учётом состояния

Базовые и адаптивные алгоритмы отлично подходят для stateless-сервисов, где каждый запрос независим и может быть обработан любым сервером. Однако для stateful-приложений (кэши, сессии пользователей, очереди, базы данных) критически важно, чтобы связанные запросы (например, от одного пользователя или для одного ключа кэша) попадали на тот же самый сервер, где сохранено состояние. Здесь могут применяться алгоритмы, основанные на хешировании.

IP Hash

Это один из самых простых и распространенных алгоритмов для обеспечения “sticky-сессий”. Вместо того чтобы распределять запросы равномерно или на основе текущей нагрузки, балансировщик вычисляет хэш от IP-адреса клиента и направляет все запросы с одинаковым хэшем на один и тот же сервер. Например:

• Пул серверов: [S1, S2, S3]
• IP клиента: 192.168.1.100
• hash("192.168.1.100") % 3 = 1 → запрос направляется на S2
• Все последующие запросы от 192.168.1.100 также будут направляться на S2

Info

Проблемы с потерей сессий при изменении количества серверов могут решаться выделением внешнего хранилища для хранения данных сессии пользователя вне сервиса (Redis, Memcached, Hazelcast и так далее).

Consistent Hashing

Если используется балансировка по IP Hash и нет внешнего хранилища сессий, то может происходить следующая ситуация. При добавлении нового сервера в пул или удалении существующего будет теряться активная сессия для пользователя. Почему? Потому что хэш-функция (например, hash(key) % N, где N - количество серверов) будет давать совершенно разные результаты для того же ключа при изменении N. Например:

• hash("User 1") % 3 = 0 (сервер S1)
• Добавляем S4. Теперь hash("User 1") % 4 = 1 (сервер S2). Весь кэш для User 1 потерян.
• Согласованное хеширование решает эту проблему, минимизируя количество ключей, которые “перемещаются” при изменении топологии (добавлении/удалении серверов).

Упрощённый концепт работы (детали и исследования можно найти отдельно):

1. Кольцо – абстрактное кольцо со значениями от 0 до 2^32-1 (или 2^64). Это пространство хэш-значений.
2. Виртуальные ноды – каждый физический сервер в пуле представляется не одной точкой на кольце, а множеством (например, 100 или 200) виртуальных нод. Хэш-значение для имени сервера (или его IP:порта) вычисляется, и это значение “ставится” на кольцо. Затем вокруг этого хеша на кольце (не рядом) распределяются виртуальные ноды этого сервера. Это обеспечивает более равномерное распределение. По виртуальной ноде всегда можно вычислить физический сервер.
3. Хэш ключа (например, ID сессии, ключ кэша) вычисляется и также “ставится” на кольцо. Ключ принадлежит тому серверу, чья ближайшая виртуальная нода находится по часовой стрелке.
4. При добавлении сервера вычисляются хэши для него и его виртуальных нод. Ключи, которые раньше принадлежали серверам, чьи виртуальные ноды находятся между новой точкой и ее ближайшей “соседкой” по часовой стрелке, перераспределятся на новый сервер. Все остальные ключи остаются на своих местах.
5. При удалении сервера удаляются все виртуальные ноды сервера. Ключи, которые на него указывали, перераспределятся на сервер, чья ближайшая виртуальная нода теперь находится противоположной часовой стрелке (т.е. следующий по кольцу после удаленных виртуальных нод).

Resilient Hashing

Термин “устойчивое хеширование” не всегда строго определен и часто используется как синоним Consistent Hashing в контексте его способности устойчиво переносить изменения топологии. Однако он также может относиться к конкретным улучшениям или альтернативным алгоритмам, таким как:

• Rendezvous Hashing (Highest Random Weight - HRW) – алгоритм, не требующий кольца. Для ключа и списка серверов вычисляется “вес” для каждой пары (ключ, сервер). Ключ всегда направляется на сервер с максимальным весом. При добавлении/удалении сервера перераспределяется только ключи, которые ранее принадлежали удаленному серверу (или теперь принадлежат новому). Не требует виртуальных нод.
• Maglev Hashing – алгоритм, стремящийся к равномерному распределению и предсказуемому маршруту (в отличие от Consistent Hashing, где маршрут может меняться при добавлении сервера). Использует идею идеальной хэш-таблицы для построения таблицы поиска.

В Envoy/Nginx прокси под “Resilient Hashing” часто понимают именно Consistent Hashing с тщательно настроенными параметрами (количество виртуальных нод) для достижения оптимального баланса между равномерностью и устойчивостью к изменениям.

Главная ценность этих алгоритмов для stateful-систем – устойчивость к сбоям и изменениям топологии. Как уже обсуждалось в Consistent Hashing, если из 100 серверов падает 1, перераспределяется трафик только для ключей, которые были “привязаны” к этому серверу (1% при 100 виртуальных нод на сервер).

Балансировка с использованием ML-моделей

Отдельно можно выделить балансировку с использованием моделей построенных на машинном обучении. Это позволяет переходить от статических и адаптивных алгоритмов к проактивным и предиктивным подходам. Вместо того чтобы реагировать на текущую нагрузку, ML-модели могут прогнозировать поведение системы и оптимизировать распределение трафика заранее.

Основные концепции ML-балансировки:

1. Прогнозирование нагрузки (Load Forecasting). ML-модели анализируют исторические данные о трафике, сезонности, пользовательском поведении и внешних факторах (праздники, маркетинговые кампании) для прогнозирования будущей нагрузки. Прогноз позволяет заранее подготовить ресурсы или перераспределить нагрузку до пиковых периодов.
   • Входные данные (Features):
     • Временные метки (час суток, день недели, месяц).
     • Исторические метрики (RPS, CPU, Memory, Network I/O).
     • Внешние события (праздники, релизы, маркетинговые активности).
     • Географическое распределение пользователей.
     • Поведенческие паттерны (частота запросов, типы операций).
   • Модели прогнозирования:
     • ARIMA/SARIMA – традиционные временные ряды для сезонных паттернов.
     • Prophet – facebook библиотека для прогнозирования с сезонностью и праздниками.
     • LSTM/GRU – нейросети для сложных нелинейных зависимостей.
     • Gradient Boosting (XGBoost, LightGBM) – для комбинирования множества признаков.
2. Кластеризация серверов (Server Clustering). Вместо использования всех серверов в качестве единого пула, ML может автоматически группировать серверы по схожести характеристик.
   • Алгоритмы кластеризации:
     • K-means – группировка по текущей загрузке ресурсов.
     • DBSCAN – обнаружение аномалий и естественных групп.
     • Hierarchical Clustering – построение иерархии серверов по производительности.
   • Как пример, серверы могут быть сгруппированы в кластеры:
     • “High-CPU, Low-I/O” для вычислительно интенсивных задач.
     • “Low-CPU, High-I/O” для задач с интенсивным диском вводом-выводом.
     • “Balanced” для смешанных нагрузок.
3. Оптимизация маршрутизации. ML-модели могут находить оптимальные маршруты для запросов на основе множества факторов:
   • Multi-armed Bandit (MAB) алгоритмы – балансируют между исследованием (отправка на новые серверы) и эксплуатацией (отправка на проверенные серверы).
   • Reinforcement Learning (RL) – агент обучается принимать решения о маршрутизации для максимизации награды (минимизация задержки, максимизация пропускной способности).
   • Neural Networks – прогнозирование оптимального сервера на основе сотен признаков.

ML-балансировка – это не замена традиционным алгоритмам. Она наиболее эффективна в комбинации с классическими подходами, где ML отвечает за сложные прогнозные задачи, а традиционные алгоритмы обеспечивают базовую отказоустойчивость и простоту.

Сравнительная таблица

Практические советы

У вас 3 идентичных веб-сервера, обрабатывающих статические файлы и простые stateless API? Round Robin – ваш лучший друг. Простота, предсказуемость, отсутствие накладных расходов на мониторинг. Не внедряйте Envoy или Consistent Hashing “на всякий случай”.

Используете Weighted Round Robin? У вас есть сервер S1 с весом 10 (мощный) и S2 с весом 1 (тестовый). Если S1 вдруг начинает обрабатывать очень долгие запросы (например, из-за сбоя в БД), WRR будет продолжать отправлять на него 90% трафика, пока S2 почти простаивает. Комбинируйте WRR с адаптивными алгоритмами (LC, WLC) или активно мониторьте задержки и внедряйте Circuit Breaker.

Health Checks обязательно необходимы для обеспечения устойчивости:

• Независимо от выбранного алгоритма балансировки, он должен быть устойчив к сбоям серверов. Неважно, насколько умный алгоритм, если он шлет трафик на мертвые серверы.
• Балансировщик сам периодически “пингует” серверы (HTTP GET на /health, TCP connect) по заданному интервалу. Если сервер не отвечает или возвращает ошибку, он исключается из пула.
• Балансировщик отслеживает ответы пользовательских запросов. Слишком много ошибок (5xx, 4xx) или высокое время ответа от конкретного сервера? Исключаем его. Требует аккуратной настройки пороговых значений.

Обеспечьте наблюдаемость серверов:

• Необходимо собирать метрики:
• Количество запросов в секунду. Равномерно ли распределен трафик? Нет ли “горячих” серверов?
• Задержки (P50, P90, P99). Один ли сервер тормозит всех? Помогает ли адаптивный алгоритм (LC/WLC/LRT)?
• Количество активных соединений. Для LC/WLC — ключевые метрики. Соответствует ли распределение соединений ожиданиям?
• Частота ошибок (4xx, 5xx). Помогает выявить проблемы конкретного сервера.
• Health Check. Сколько серверов в пуле “здоровы”?
• Какие инструменты можно использовать? Prometheus + Grafana, Datadog, New Relic, встроенная статистика в Nginx/HAProxy/Envoy.

Не доверятея теоретическим расчетам. Используйте инструменты вроде vegeta, wrk, locust, jmeter, k6 для имитации реальной нагрузки и проверки распределения, задержек и поведения системы при сбоях (kill -9 сервера, ограничение сети).

В архитектурных документах (ADRs) или в комментариях к конфигурации всегда указывайте, почему выбран именно этот алгоритм балансировки. Это поможет будущим вам и коллегам понять контекст и trade-offs.

Заключение

Не существует универсального “лучшего” алгоритма. RR прост, но не адаптивен. LC/WLC адаптивны, но не учитывают разницу в мощности. Consistent Hashing идеален для кэша/сессий, но сложен в реализации и настройке. Ваш выбор всегда будет компромиссом. Необходимо понимать характер ваших запросов (короткие/долгие, stateful/stateless) и серверов (однородные/разнородные).

Немаловажно помнить, что устойчивость системы обеспечивается не только алгоритмом балансировки, но и обязательными Active/Passive health checks, Circuit Breaker для быстрой реакции на тормозящие серверы и обеспечением наблюдаемости для мониторинга состояния в реальном времени.

Проще всего начинать с простейшего подхода (RR), который решает текущую задачу. Далее можно усложнять (WRR, LC, Consistent Hashing), когда текущий подход становится узким местом.