Сети и протоколы

Алгоритмы балансировки: от round-robin до power-of-two-choices

Суть Round-robin слеп к нагрузке; least-connections вызывает синхронизированный herding; power-of-two-choices работает за O(1) с ~12% дисбалансом — современный стандарт и его обоснование.

Высота — путь к senior

НольJuniorMiddleSenior

Ты на middle-высоте — в небе

◷ 12 min

У вас 4 backend-сервера. Запросы должны распределяться равномерно. Round-robin делает именно это — пока один сервер не начинает тормозить и всё равно получает свою очередь. Каждый выбор алгоритма имеет цену. Неверный превращает медленный backend в лавину.

Round-robin: просто, но слеп к нагрузке

LB поддерживает вращающийся указатель по списку backends: B1, B2, B3, B4, B1, B2, …. Каждый запрос сдвигает указатель на один шаг.

Свойства:

O(1) на решение маршрутизации.
Равномерно распределяет количество запросов, а не фактическую нагрузку.
API-вызов на 1 мс и upload файла на 100 мс — оба считаются «одним запросом».

Когда ломается: Если один backend медленнее (GC-пауза, тяжёлые запросы), он накапливает открытые соединения быстрее, чем round-robin успевает это обнаружить. LB продолжает отправлять ему его долю запросов; медленный backend отстаёт всё больше.

Weighted round-robin назначает каждому backend вес, пропорциональный ёмкости. B1 (вес 2) получает в два раза больше запросов, чем B2 (вес 1). Веса задаются вручную и не адаптируются к изменениям нагрузки в реальном времени.

Least-connections: адаптируется, но создаёт herding

Маршрутизировать каждый новый запрос на backend с наименьшим числом активных соединений в данный момент. Это напрямую учитывает медленные backends: backend, обрабатывающий длинные запросы, накапливает больше соединений и получает меньше новых.

Проблема herding. Предположим, B1 перегружен, накапливает 1 000 соединений, и LB перестаёт маршрутизировать к нему. GC-пауза B1 заканчивается. Его счётчик падает до 10. В этот точный момент все клиенты, отслеживающие обновлённый счётчик, одновременно направляются к B1 — новый spike. Синхронизированный бросок может снова перегрузить B1 за миллисекунды. Стадо устремилось.

Least-connections также требует O(log N) сканирования min-heap на запрос для точного отслеживания или O(1) приближённого отслеживания с одним указателем «последний минимум».

Power-of-two-choices: современный стандарт

Алгоритм (на запрос):

Выбрать два backend равномерно случайным образом.
Маршрутизировать на тот, у которого меньше активных соединений.

Всё. Два сравнения, никакого глобального сканирования.

Почему он превосходит оба варианта:

Чистый random → ~100% дисбаланс (некоторые backends получают в 2× больше среднего).
Least-connections → O(N) сканирование + синхронизированный herding.
Power-of-two-choices → ~12% дисбаланс (доказано Adler 1996), O(1) на запрос, случайный шум десинхронизирует herding.

Случайность предотвращает одновременное обнаружение восстановления backend всеми клиентами. Сравнение предотвращает наихудший сценарий чистого random. Вместе: близко к оптимальному при постоянных затратах.

Nginx, Envoy, HAProxy и AWS ALB используют этот алгоритм или его вариант по умолчанию.

Сравнение алгоритмов балансировки

Стоимость решения round-robin: O(1)
Стоимость решения least-connections: O(log N)
Стоимость решения power-of-two-choices: O(1)
Дисбаланс при чистом random: ~100%
Дисбаланс power-of-two-choices: ~12%
Дисбаланс least-connections: ~0% (но herding)

Трассировка power-of-two-choices над 1 000 запросами

1/3

1. Запрос 1: выбрать B2 (8 conns) и B4 (12 conns) случайно → маршрутизировать на B2 (меньше). 2. B2 теперь имеет 9 conns, B4 имеет 12. 3. Запрос 2: выбрать B1 (11 conns) и B3 (11 conns) → ничья, выбрать B1 (tiebreaker: меньший ID). 4. Запрос 3: выбрать B2 (9 conns) и B4 (12 conns) → маршрутизировать на B2. 5. После 1 000 запросов: все четыре backend кластеризуются около 6–7 активных соединений каждый, ~12% дисбаланс. 6. Для сравнения: чистый random оставил бы один backend на ~14 conns пока другой сидит на ~3.

Викторина

Почему power-of-two-choices предотвращает проблему 'herding', которую создаёт чистый least-connections?

Расставь шаги по порядку

Расставьте backends по числу соединений и проследите победителя power-of-two-choices:

1 Выбрать backend A (2 соединения) и backend D (10 соединений) случайно.
2 Так как у A меньше соединений, маршрутизировать запрос на A.
3 A теперь имеет 3 соединения, D всё ещё 10.
4 Следующий запрос: выбрать backend B (5 соединений) и backend C (6 соединений).
5 Маршрутизировать на B (меньше).
6 После многих запросов все backend кластеризуются около одинаковой нагрузки (≈6–7 соединений каждый), ≈12% дисбаланс.

Граничные случаи

Weighted power-of-two-choices. Когда backends имеют разную ёмкость (один 4 ядра, другой 16), чистый power-of-two-choices распределяет соединения поровну, а не пропорционально ёмкости. Взвесьте вероятность случайного выбора по ёмкости backend: более мощный backend в 4× чаще становится одним из двух кандидатов. Это сохраняет O(1) свойство, адаптируясь к разнородным парку серверов.

Викторина

Round-robin равномерно распределяет запросы по количеству. Почему это ломается при большой вариации стоимости запроса?

Вспомните перед уходом

01
Что такое проблема herding при least-connections и почему power-of-two-choices её избегает?
02
Какой дисбаланс нагрузки достигает power-of-two-choices и почему это лучше чистого random?
03
Когда вы предпочтёте weighted round-robin перед power-of-two-choices?

Итог

Три семейства алгоритмов балансировки — каждое с разным трейдоффом. Round-robin O(1), но распределяет количество запросов, а не фактическую нагрузку — медленный backend тонет в своей справедливой доле. Least-connections маршрутизирует к backend с наименьшим числом открытых соединений и адаптируется к реальной нагрузке, но обновление глобального минимума создаёт синхронизированный бросок herding при восстановлении backend. Power-of-two-choices сэмплирует ровно два случайных backend и маршрутизирует к менее нагруженному: O(1), ~12% дисбаланс (против ~100% у чистого random), случайность десинхронизирует стадо. Nginx, Envoy и AWS ALB используют power-of-two-choices или вариант именно за эти свойства.

Связанные уроки

углубляется в

встречается в162

Продолжить восхождение ↑L4 vs L7 балансировка и сохранение IP клиента