Проектирование распределенного rate limiter

Граница задачи

Сервис ограничивает запросы по устойчивому идентификатору клиента, маршруту и типу операции. Идентификатор берется после аутентификации: один только IP плохо представляет пользователя за NAT и легко меняется. В учебном примере политика для чтения заказов — 100 запросов в минуту со всплеском до 20, но это входное допущение, а не универсальное число.

Критический путь: клиент → gateway → rate-limit filter → stateless limiter → Redis → gateway → upstream. Upstream вызывается только после allow. Несколько gateway и limiter-реплик разделяют одно логическое состояние bucket, поэтому добавление реплик не умножает квоту.

Настоящий token bucket

INCR плюс EXPIRE реализует fixed window. Он считает запросы внутри дискретного окна и допускает граничный всплеск. Token bucket хранит два значения: remaining_microtokens и last_refill_ms. Одна атомарная функция выполняет:

elapsed = max(0, now_ms - last_refill_ms)
tokens = min(capacity, tokens + elapsed * refill_rate)
if tokens >= request_cost:
    tokens = tokens - request_cost
    allowed = true
else:
    retry_after = ceil((request_cost - tokens) / refill_rate)

Расчеты ведутся целыми microtokens, чтобы округление float не создавало или не теряло токены. Атомарность важна: два параллельных запроса не должны потратить один последний токен. Redis описывает и fixed-window вариант INCR/EXPIRE, и отдельный token-bucket read/refill/debit через Lua; это разные алгоритмы.

Сценарии

Запрос получает политику, атомарно пополняет и дебетует bucket, затем проходит в upstream.

Если токенов меньше стоимости запроса, состояние не уходит в минус. Gateway возвращает 429 и Retry-After. RFC 6585 разрешает Retry-After для 429 и не задает, как именно сервер идентифицирует клиента или считает запросы.

Fail-open не может быть одной глобальной настройкой. Для чувствительной записи пример закрывается с 503 и коротким Retry-After. Для низкорискового чтения отдельная политика может разрешить небольшой локальный emergency bucket и обязательно пометить ответ как degraded. Выбор фиксируется по маршруту и тестируется при отказе Redis.

Делить один ключ на 16 независимых счетчиков нельзя: каждый счетчик с полной квотой даст до 16-кратного превышения. В показанном варианте глобальный bucket атомарно выдает limiter-реплике ограниченную lease и сразу списывает выданные токены. Локальная трата снижает нагрузку на hot key, но сумма выданных lease не превышает глобальный budget. Цена — временная недоиспользованная квота, если реплика получила lease и умерла.

Конкурентность и отказоустойчивость

• Bucket key включает tenant, нормализованный route и policy version. Изменение политики не смешивает несовместимые состояния.
• Короткая Redis Function или Lua script должна обращаться только к явно переданному key. Долгий script блокирует Redis, поэтому внутри нет сетевых вызовов или циклов по пользователям.
• Retry клиента безопасен: каждая попытка является новым расходом, если API не определяет idempotency key и повтор той же операции отдельно.
• Региональная квота и строгая глобальная квота — разные продукты. Независимые региональные bucket дают bounded overshoot при разделении сети; синхронная глобальная координация повышает latency и снижает availability.
• Решение allow/deny не должно зависеть от асинхронного audit pipeline. Метрики семплируются, а deny и degraded события сохраняются с более высоким приоритетом.

Capacity model

Пусть входной пик равен 1.2M checks/s. При измеренной безопасной производительности одной limiter-реплики 80K checks/s и целевой загрузке 60% нужно ceil(1.2M / (80K × 0.60)) = 25 реплик. Это пример расчета; числа capacity на диаграмме нельзя принимать без benchmark, распределения ключей и теста failover.

Один точный bucket является последовательной точкой согласования для одной identity. Шардирование Redis распределяет разные identity, но не распараллеливает один hot key. Lease уменьшает частоту обращений ценой bounded under-utilization. Если продукт допускает overshoot, можно выбрать локальные quota slices; их сумма, а не каждая slice, должна равняться глобальной квоте.

Безопасность

Rate limiting дополняет, но не заменяет authentication, authorization, WAF и resource quotas. Дескриптор нельзя строить из непроверенного X-Forwarded-For. Ошибки policy lookup закрываются безопасным default для чувствительных маршрутов. Ответ не раскрывает внутренний shard или tenant policy.

Связанные темы

Продолжение: [CONCEPT]rate-limiting-algorithms, [CONCEPT]consistency-models, [CONCEPT]sharding-strategies и [CONCEPT]observability-pillars. Практический cache-aside разобран на странице Cache-Aside; это explore-материал, поэтому здесь используется обычная Markdown-ссылка.

Первичные источники

• RFC 6585, status 429 and Retry-After: https://www.rfc-editor.org/rfc/rfc6585.html
• Redis rate-limiter guide, distinction between fixed window and token bucket: https://redis.io/docs/latest/develop/use-cases/rate-limiter/
• Redis token bucket with atomic Lua: https://redis.io/docs/latest/develop/use-cases/rate-limiter/redis-py/
• Redis programmability and atomic execution: https://redis.io/docs/latest/develop/programmability/
• Envoy global rate limiting and local protection: https://www.envoyproxy.io/docs/envoy/latest/intro/arch_overview/other_features/global_rate_limiting.html

Источники подтверждают протокол и свойства компонентов. Конкретные quota, threshold и capacity выше являются явно указанными design assumptions этого упражнения.