Спроектируйте rate limiter
Вопрос
Спроектируйте распределённый rate limiter для публичного API: лимиты на пользователя и на IP, общий для всех экземпляров API.
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
Требования: лимиты по ключу (user, IP, эндпоинт), правила настраиваются, ответ 429 с Retry-After, добавка к задержке не больше пары миллисекунд, поведение при отказе хранилища
Оценка нагрузки: 100 000 RPS на шлюз → 100 000 проверок в секунду; 1 млн активных ключей × ~100 байт ≈ 100 МБ памяти; Redis-узел держит порядка 100 000+ простых операций в секунду, поэтому кластер из нескольких шардов
API: внутренний вызов allow(key, rule) → {allowed, remaining, reset}; заголовки RateLimit-* и Retry-After в ответе клиенту
Данные: счётчики в Redis с TTL: sliding window counter (два окна) или token bucket (токены и время последнего пополнения); правила в конфиге или БД с кешем
Компоненты: middleware на API-шлюзе, Redis Cluster, атомарная проверка Lua-скриптом, сервис правил
Узкие места: атомарность (гонки GET/SET), горячие ключи, задержка до Redis, fail open или fail closed при отказе Redis, локальная предварительная фильтрация, синхронизация между ДЦ
Что могут спросить следом
- Какой алгоритм выберете и почему?
- Что делать при недоступности Redis?
- Как ограничить скорость в нескольких дата-центрах?
Разбор
Требования: лимиты на пользователя, IP и эндпоинт, общие для всех экземпляров, ответ 429 с Retry-After, лишняя задержка не больше пары миллисекунд. Нагрузка: 100 000 RPS значит столько же проверок, активных ключей около миллиона, это всего около 100 МБ, но по операциям нужен кластер Redis из нескольких шардов. Алгоритм: token bucket, если хотим разрешать короткие всплески, или sliding window counter для ровного лимита; оба хранят пару чисел на ключ. Проверка делается одним Lua-скриптом в Redis, чтобы чтение и обновление были атомарны, иначе параллельные запросы проскочат лимит. Middleware на шлюзе вызывает проверку и пишет заголовки. Правила хранятся в конфиге и кешируются в процессе. Узкие места: при недоступности Redis для большинства API выбираю fail open, чтобы не уронить продукт, а для чувствительных эндпоинтов вроде логина fail closed. От горячих ключей при DDoS защищает локальный лимит в процессе перед Redis. Для нескольких ДЦ лимит делят между ними или принимают небольшое превышение.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.