Алгоритмы балансировки — round-robin, least-connections, consistent hashing

LB распределяет запросы по backend-ам — это мы поняли. Но как именно он выбирает, на какой backend отправить очередной запрос? Это не один алгоритм, а несколько разных подходов, каждый со своими свойствами. От выбора алгоритма зависит, насколько равномерной получится нагрузка и насколько эффективно использовано железо.

В этом уроке разберём четыре самых популярных алгоритма: round-robin, least-connections, weighted variants и consistent hashing. Каждый имеет конкретные ситуации, где он лучший, и ситуации, где он провальный. Понимать их разницу важно: вы не настроите хороший LB, не понимая, что значит balance roundrobin против balance leastconn.

Round-robin — простой и предсказуемый

Самый простой алгоритм: запросы идут по кругу по списку backend-ов. Первый — на server1, второй — на server2, третий — на server3, четвёртый — снова на server1.

Плюсы:

• Простота. В коде это next_backend = backends[counter % len(backends)]. Никакого state, никаких вычислений.
• Равномерность по числу запросов. Каждый backend получит ровно 1/N всех запросов.
• Предсказуемость. Поведение не зависит от прошлой истории. Легко отлаживать.

Минусы:

• Не учитывает реальную нагрузку. Если один запрос обрабатывается 10 мс, а другой — 5 секунд, round-robin распределит их поровну по числу, но не по сложности. Один backend может оказаться завален долгими запросами, а другой — бездельничать.
• Не учитывает разную мощность серверов. Если в пуле один сервер с 16 CPU и один с 4 CPU, round-robin даст им поровну запросов. Это плохо.
• Не учитывает sticky sessions. Один пользователь может попадать на разные backend-ы. Если приложение stateful — сессия теряется.

Конфиг в NGINX (default) и HAProxy:

upstream backend {
    server 10.0.0.1:8000;
    server 10.0.0.2:8000;
    server 10.0.0.3:8000;
}

backend pool
    balance roundrobin
    server s1 10.0.0.1:8000 check
    server s2 10.0.0.2:8000 check
    server s3 10.0.0.3:8000 check

Round-robin — разумный дефолт. Если все запросы примерно одинаковые по тяжести и серверы одинаковые — работает отлично. Большинство веб-API подпадают под это описание.

Weighted round-robin — серверы разной мощности

Если серверы в пуле неодинаковые (например, унаследованные железки разной мощности, или часть инстансов AWS EC2 типа c5.2xlarge, часть — c5.4xlarge), хочется отправлять на более мощные больше запросов. Решение — weighted round-robin: каждому backend назначается вес (целое число), и запросы делятся пропорционально весам.

upstream backend {
    server 10.0.0.1:8000 weight=3;  # большой сервер: 3 запроса из каждых 5
    server 10.0.0.2:8000 weight=1;  # маленький: 1 запрос из 5
    server 10.0.0.3:8000 weight=1;  # маленький: 1 запрос из 5
}

Алгоритм: на каждые 5 запросов первый получит 3, остальные — по одному. По кругу. Можно представить это как «виртуальный» round-robin по списку [s1, s1, s1, s2, s3].

Когда полезно:

• Канареечный деплой. Новая версия деплоится с весом 1, старая — с весом 99. 1% трафика идёт на новую, остальное на старую. Если новая работает — увеличиваете её вес. Это базовый canary rollout.
• Heterogeneous fleet. Серверы разной мощности в одном пуле.
• A/B тесты на инфраструктурном уровне. Разные настройки — разный вес.

backend pool
    balance roundrobin
    server s1 10.0.0.1:8000 weight 3 check
    server s2 10.0.0.2:8000 weight 1 check
    server s3 10.0.0.3:8000 weight 1 check

Least connections — учёт текущей нагрузки

Round-robin плох, когда запросы сильно неравные по времени обработки. Например, ваш API имеет endpoint /quick (50 мс) и endpoint /report (5 минут). Если запросы на /report пришли подряд и попали на разные серверы, round-robin продолжит слать новые на тот же сервер, который занят отчётами.

Least-connections решает это: LB ведёт счётчик активных соединений к каждому backend, и следующий запрос идёт на backend с минимумом активных соединений.

Когда полезно:

• Запросы сильно разной длительности. Часть быстрые, часть медленные — least-conn выровняет реальную нагрузку.
• Long-lived connections. WebSocket, gRPC streams, SSE — соединение живёт минутами. Round-robin даст «холодные» сервера, но реальная нагрузка останется на «горячих». Least-conn это видит.
• Backend разной производительности (с поправкой через вес).

Минусы:

• Не идеальная метрика. «Активные соединения» != «реальная нагрузка». 100 idle WebSocket-ов нагружают меньше, чем 10 запросов с тяжёлой обработкой. Но это лучшая proxy-метрика, доступная LB без cooperation с backend.
• Чуть сложнее в реализации. LB ведёт state.

upstream backend {
    least_conn;
    server 10.0.0.1:8000;
    server 10.0.0.2:8000;
}

backend pool
    balance leastconn
    server s1 10.0.0.1:8000 check
    server s2 10.0.0.2:8000 check

Большинство современных систем выбирают least-conn по умолчанию. Особенно для API с переменной нагрузкой и для микросервисов.

IP hash и source-based hashing

Иногда нужно, чтобы запросы одного клиента всегда попадали на один backend (sticky sessions без cookie). Простой способ — хешировать IP клиента и брать hash % N как индекс backend.

upstream backend {
    ip_hash;
    server 10.0.0.1:8000;
    server 10.0.0.2:8000;
    server 10.0.0.3:8000;
}

Клиент с IP 1.2.3.4 всегда попадает на server2 (потому что hash(1.2.3.4) % 3 = 1). Это даёт sticky sessions без cookie, но с проблемами:

• При добавлении/удалении backend меняется hash % N. Все клиенты внезапно попадают на другой сервер. Catastrophic re-hash.
• NAT убивает балансировку. Сотни сотрудников одной компании выходят с одного публичного IP — все попадают на один backend.
• Mobile networks. IP клиента может меняться — sticky session ломается.

IP-hash — грубое решение для случаев, когда L4 LB и нужна хотя бы какая-то stickiness. Для серьёзных задач лучше cookie-based sticky (L7) или внешний state store (Redis).

Consistent hashing — продвинутый sticky

Главная проблема IP-hash: при изменении числа backend (N) — все хеши пересчитываются и все клиенты внезапно перемигрируют. Это катастрофично для кэшей и stateful-систем.

Consistent hashing решает это: добавление/удаление одного backend перенаправляет только ~1/N клиентов, остальные остаются на тех же серверах.

Идея:

1. Все backend размещаются на воображаемом «кольце хешей» (0 .. 2^32-1).
2. Для входящего запроса (ключ — например, IP, или user_id, или session) считаем хеш и ставим на то же кольцо.
3. Идём по часовой стрелке до первого backend — это наш target.

Когда добавляется новый backend, перемигрируют только те ключи, чей хеш «между» новым backend-ом и предыдущим. В среднем — 1/N ключей.

Где используется:

• Распределённые кэши (Memcached, Redis cluster): каждый ключ должен быть на одном backend, при добавлении нового сервера — минимальная миграция.
• CDN edge selection: Cloudflare выбирает edge-сервер по consistent hash от URL.
• Sticky sessions с минимальной миграцией: добавление нового сервера не сбрасывает все существующие сессии.

Реализация в HAProxy:

backend cache_pool
    balance hash $http_host
    hash-type consistent
    server s1 10.0.0.1:11211 check
    server s2 10.0.0.2:11211 check
    server s3 10.0.0.3:11211 check

hash-type consistent — ключевая директива. Без неё balance hash будет использовать обычный hash % N, со всеми его проблемами.

Когда какой алгоритм выбирать

Шпаргалка:

В современной практике дефолт меняется с round-robin на least-conn для API. Для CDN/cache — consistent hash. Для канареечных деплоев — weighted round-robin. Sticky session — стараются избегать через stateless backend.

Алгоритм + health checks = production-ready

Любой алгоритм работает поверх health checks. LB не должен слать запросы на мёртвые backend, независимо от выбранного алгоритма. Поэтому в реальной жизни алгоритм всегда комбинируется с активным мониторингом здоровья:

backend api_pool
    balance leastconn
    option httpchk GET /healthz
    http-check expect status 200
    timeout check 5s
    default-server inter 5s rise 2 fall 3

    server s1 10.0.0.1:8000 check
    server s2 10.0.0.2:8000 check
    server s3 10.0.0.3:8000 check

Что это значит:

• option httpchk GET /healthz — каждый health check это GET /healthz.
• http-check expect status 200 — ожидаем 200 OK.
• inter 5s — интервал между проверками 5 секунд.
• rise 2 — после 2 успешных подряд проверок backend помечается UP.
• fall 3 — после 3 неуспешных подряд — DOWN.

Таким образом если backend начал отвечать 5xx, через 15 секунд (3 проверки x 5 сек) он будет выкинут из пула. Все ваши balance leastconn будет автоматически работать только со здоровыми серверами.

Slow start — защита от перегрузки новых backend-ов

При добавлении нового backend в пул, особенно после холодного старта (новый Docker-контейнер, новый AWS instance), он может быть «холодным»: пустые кэши, прогрев JIT-компилятора, медленные первые запросы. Если LB сразу нагрузит его на 100%, новые запросы будут тормозить.

Решение — slow-start: новый backend получает увеличивающуюся долю трафика плавно, за 30-60 секунд.

upstream backend {
    least_conn;
    server 10.0.0.1:8000 weight=10 slow_start=30s;
    server 10.0.0.2:8000 weight=10 slow_start=30s;
}

NGINX будет постепенно увеличивать «эффективный вес» нового backend от 0 до 10 за 30 секунд. Это даёт серверу время прогреться: подключиться к БД, заполнить in-memory кэши, прогреть JIT.

Попробуй сам

Давайте сравним round-robin и least-connections в действии. Используем тот же setup с двумя backend-ами, но один из них «тормозит».

# Создаём «быстрый» сервер на порту 8001:
python3 -c "
from http.server import BaseHTTPRequestHandler, HTTPServer
class FastHandler(BaseHTTPRequestHandler):
    def do_GET(self):
        self.send_response(200)
        self.end_headers()
        self.wfile.write(b'fast 8001')
    def log_message(self, *args): pass
HTTPServer(('localhost', 8001), FastHandler).serve_forever()
" &

# «Медленный» на порту 8002:
python3 -c "
import time
from http.server import BaseHTTPRequestHandler, HTTPServer
class SlowHandler(BaseHTTPRequestHandler):
    def do_GET(self):
        time.sleep(2)
        self.send_response(200)
        self.end_headers()
        self.wfile.write(b'slow 8002')
    def log_message(self, *args): pass
HTTPServer(('localhost', 8002), SlowHandler).serve_forever()
" &

Создайте два NGINX конфига — один с round-robin, другой с least-conn:

# rr.conf
events {}
http {
    upstream backend {
        server 127.0.0.1:8001;
        server 127.0.0.1:8002;
    }
    server {
        listen 18080;
        location / { proxy_pass http://backend; }
    }
}

# lc.conf
events {}
http {
    upstream backend {
        least_conn;
        server 127.0.0.1:8001;
        server 127.0.0.1:8002;
    }
    server {
        listen 18081;
        location / { proxy_pass http://backend; }
    }
}

Запустите оба NGINX (nginx -c $PWD/rr.conf и nginx -c $PWD/lc.conf) и пустите 20 параллельных запросов на каждый:

echo "Round-robin:"
time (for i in {1..20}; do curl -s http://localhost:18080/ & done; wait) | sort | uniq -c

echo "Least-conn:"
time (for i in {1..20}; do curl -s http://localhost:18081/ & done; wait) | sort | uniq -c

При round-robin вы увидите 10 ответов «fast» и 10 ответов «slow» — но общее время определяется самым медленным. При least-conn быстрый backend получит больше запросов, потому что он быстрее завершает старые. Соотношение будет смещено в его сторону.