Ограничение скорости: алгоритмы и архитектура

Ваш API обслуживает 100 запросов/сек в среднем. Во время DDoS он получает 100 000 запросов/сек. Можно блокировать по IP, но атакующий использует тысячу разных IP, каждый из которых делает 100 запросов/сек. Любой per-IP лимит на 100 запросов/сек заблокирует и ваших легитимных пользователей. Вопрос не в «сколько запросов?», а в «какой алгоритм правильно определяет злоупотребление против нормального трафика?»

Token bucket. Токены накапливаются в bucket с фиксированной скоростью R (например, 100 токенов/сек) до максимальной ёмкости C (например, 1 000 токенов). Каждый запрос стоит один токен; если bucket пуст, запрос отклоняется. Допускает контролируемые всплески: если bucket полон в покое, первые 1 000 запросов проходят мгновенно, затем темп ограничивается до 100/сек. Самый распространённый выбор для публичных API: прост (один счётчик + timestamp) и допускает легитимные всплески трафика.

Leaky bucket. Запросы ставятся в очередь и вычерпываются с фиксированной скоростью D, сглаживая трафик. Всплеск в 1 000 запросов не проходит мгновенно — они входят в очередь и вычерпываются со скоростью D в секунду. Это добавляет задержку для легитимного всплескового трафика, но производит идеально гладкий вывод. Полезен для downstream-сервисов, которые не могут обрабатывать всплески, но не для пользовательских API, где важна задержка.

Fixed window. Считает запросы в временном окне (например, в секунду). Прост, но имеет проблему граничного всплеска: два запроса на 59,999 секунде и два на 60,001 секунде считаются двумя в каждом окне — четыре запроса за 4 миллисекунды — но логика окна видит их как отдельные окна. Атакующий, эксплуатирующий это, может удвоить эффективный лимит скорости, выбирая время запросов на границе окна.

Sliding window log. Хранит каждый timestamp запроса в списке; отклоняет, если более N timestamp за последние T секунд. Самый точный — нет проблемы границы — но память масштабируется с количеством запросов. При 10 000 запросов/сек хранение каждого timestamp за 1 секунду требует 10 000 записей на клиента. Непрактично для высоконагруженных API.

Sliding window counter. Смешивает эффективность fixed-window с точностью sliding-window. Хранит счётчики для предыдущего окна (prev) и текущего окна (curr). На момент запроса T: estimated_count = prev * (1 - elapsed/window_size) + curr. Если estimated_count < limit, разрешить; иначе отклонить. Память: O(1) на клиента (два счётчика). Точность: приблизительная, но намного лучше fixed window. Практический стандарт для распределённых систем.

Где обеспечивать ограничение скорости. Три уровня, каждый останавливает разные паттерны атак:

1. Edge (CDN/скруббинг-центр) — блокирует крупнейшие атаки до попадания в вашу сеть. Per-IP, per-ASN или per-country лимиты. Контекст приложения недоступен.
2. Шлюз/load balancer — может ограничивать скорость по пользователю, по ключу API или по origin-соединению. Имеет auth-контекст. Останавливает bot-подобные паттерны.
3. Прикладной уровень — может ограничивать скорость по бизнес-логике (например, макс 3 неудачных попытки входа в минуту). Медленнее, но наиболее контекстуален.

Обеспечивайте на всех трёх уровнях: edge останавливает объёмные наводнения, шлюз — bot-подобные паттерны, прикладной уровень — злоупотребления аутентифицированных пользователей.

Распределённое ограничение скорости через Redis. При работе нескольких app-серверов локальный in-memory счётчик недостаточен — клиент может попадать на разные серверы и каждый видит лишь свою долю трафика. Решение: общий счётчик в Redis. Каждый запрос атомарно инкрементирует ключ Redis и проверяет лимит. Стоимость: каждое решение добавляет round-trip на Redis (0,5–1 мс в той же сети). При 100k запросов/сек это 50–100 мс добавленной задержки на запрос. Смягчение: локальное ограничение скорости (per-server счётчик, нет Redis) плюс периодическая синхронизация с Redis — торгует небольшой неточностью за микросекундные решения.

Адаптивное ограничение конкурентности. Вместо лимита в секунду — ограничить количество in-flight запросов. Когда in-flight >= max_concurrency, отклонять новые запросы. Это предотвращает каскадный отказ. Load shedding: когда глубина очереди превышает порог, вероятностно отклонять новые запросы — survival probability = max_queue / queue_depth. Пользователи видят быстрые ошибки 503 вместо timeouts; сервис остаётся отзывчивым для остальных. Компромисс: пользователи получают ошибки, а не медленные ответы, при перегрузке.