Алгоритмы рейт-лимитинга: token bucket, leaky bucket, sliding window

Rate limiting — это механизм ограничения количества запросов за единицу времени.

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

• защиты от DDoS
• предотвращения brute-force
• ограничения API по тарифам
• защиты от перегрузки backend

Хороший лимитер должен отвечать на два вопроса:

1. Сколько запросов можно сделать?
2. За какой промежуток времени?

Дальше всё зависит от выбранного алгоритма.

Token Bucket

Представим ведро с токенами.

• Ведро имеет максимальный размер (capacity)
• Токены добавляются с фиксированной скоростью (rate)
• Каждый запрос «съедает» 1 токен
• Если токенов нет — запрос отклоняется

Как работает

Пример:

• Лимит: 10 запросов в секунду
• Capacity: 20 токенов

Это означает:

• Можно сделать burst до 20 запросов сразу
• Потом скорость восстановится до 10 rps

Плюсы

• Поддерживает burst-нагрузку
• Прост в реализации
• Предсказуемое поведение
• Хорошо подходит для API

Минусы

• Нужно хранить состояние
• Не идеально отражает «строгое» окно времени

Leaky Bucket

Ведро с дыркой.

• Запросы складываются в очередь
• Они «вытекают» с фиксированной скоростью
• Если очередь переполнена — новые запросы отбрасываются

В отличие от token bucket, здесь контролируется не возможность burst, а выходной поток.

Как работает

• Пришло 100 запросов
• Обработка настроена на 10 rps
• Лишние либо ждут, либо отбрасываются

На выходе всегда ровный поток.

Плюсы

• Гарантирует стабильную скорость обработки
• Хорош для сглаживания нагрузки

Минусы

• Плохо подходит для burst API
• Может увеличивать latency
• Требует очередь

Sliding Window

Ограничение в рамках скользящего окна времени.

Пример:

• Не более 100 запросов за последние 60 секунд

Каждый новый запрос проверяет:

Сколько запросов было за последние N секунд?

Варианты реализации

1) Fixed window

Простое окно по таймеру:

• 00:00–00:59 → 100 запросов
• 01:00–01:59 → снова 100

Проблема: можно сделать 100 в конце минуты и 100 в начале следующей.

2) True sliding window

Хранится точное время каждого запроса.

При новом запросе:

• удаляются устаревшие
• считается количество оставшихся

Это наиболее точный вариант.

Плюсы

• Самый точный контроль
• Честное ограничение
• Хорош для security-ограничений

Минусы

• Требует хранения таймстампов
• Более дорогой по ресурсам

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

Token Bucket

• Поддерживает burst
• Контролирует среднюю скорость
• Идеален для API

Leaky Bucket

• Сглаживает поток
• Даёт ровный выходной rate
• Подходит для обработки задач

Sliding Window

• Самый строгий контроль
• Хорош для login / auth
• Более ресурсоёмкий

Где что использовать

API gateway

Обычно используют token bucket.

Он позволяет клиентам делать короткие burst-запросы,
но ограничивает среднюю скорость.

Защита логина

Лучше sliding window.

Например:

• не более 5 попыток за 5 минут

Здесь важна точность.

Очереди задач

Leaky bucket помогает сгладить нагрузку
и не перегружать downstream-сервисы.

Распределённые системы

В кластере возникает проблема:

• лимит должен быть глобальным
• состояние должно быть общим

Обычно используют:

• Redis
• in-memory с sharding
• или алгоритмы с approximate counters

Важно учитывать race conditions и сетевые задержки.

Вывод

Token Bucket — баланс гибкости и простоты.
Leaky Bucket — сглаживание потока.
Sliding Window — максимальная точность.

Выбор зависит от задачи:

• нужен burst → token bucket
• нужен ровный поток → leaky bucket
• нужна строгая защита → sliding window

В реальных системах часто комбинируют несколько алгоритмов
на разных уровнях архитектуры.