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

Round robin — по очереди. Просто и без состояния. Работает, когда серверы одинаковы и запросы примерно одинаковые. Плохо, когда один сервер начал тормозить (GC, соседи, тяжёлый запрос): он продолжает получать ту же долю, его очередь растёт, хвост задержки — тоже. Взвешенный — серверам разной мощности пропорционально весу.

Случайный выбор — то же в среднем, но хуже: по случайности некоторые серверы получают серию запросов подряд.

Least connections / least outstanding requests — тому, у кого сейчас меньше всего запросов в работе. Медленный сервер автоматически получает меньше: его запросы дольше висят. Хорошо для разнородных запросов и долгих соединений. Минус — нужно знать актуальную загрузку всех серверов; при нескольких балансировщиках каждый видит только свои запросы, и все разом шлют на «самый свободный» — стадный эффект.

Power of two choices (p2c) — выбрать двух случайных и отправить менее загруженному. Удивительный результат теории вероятностей: максимальная загрузка падает экспоненциально по сравнению со случайным выбором, и это почти так же хорошо, как глобальный минимум. Не нужно опрашивать всех, нет стадного эффекта. Используется в Envoy, Finagle, NGINX (random two least_conn), gRPC.

Пиковая EWMA (peak exponentially-weighted moving average, Linkerd, Finagle) — учитывает и число запросов, и недавнюю задержку сервера.

По хешу ключа — один и тот же пользователь или ключ всегда попадает на тот же сервер. Нужен, когда у сервера есть состояние: локальный кэш, сессии в памяти, шард данных, WebSocket-комнаты. Обычный hash % N при изменении N перетасует почти всё — поэтому consistent hashing. Минус — горячие ключи создают горячие серверы.

Как выбрать:

• одинаковые stateless-серверы, короткие запросы — round robin;
• разная длительность запросов или риск медленных экземпляров — least requests или p2c;
• много балансировщиков или клиентская балансировка — p2c;
• серверы с состоянием по ключу — consistent hashing (с ограничением нагрузки, bounded load).

Вместе с алгоритмом нужны проверки здоровья, выбрасывание медленных (outlier detection), медленный старт для только что поднятых экземпляров (иначе least connections завалит холодный сервер).

import random

def p2c(servers):
    a, b = random.sample(servers, 2)
    return a if a.in_flight <= b.in_flight else b

# 100 серверов, случайный выбор: максимальная очередь ~ ln n / ln ln n
# power of two choices: максимальная очередь ~ ln ln n — на практике в разы меньше