Спроектируйте распределённый rate limiter: не более N запросов в секунду на пользователя для API из множества инстансов.
Короткий ответ
- Алгоритмы: token bucket, sliding window log, sliding window counter
- Token bucket допускает короткие всплески, настраивается ёмкостью
- Счётчики централизованно в Redis — лимит общий для всех инстансов
- Инкремент и проверка атомарно, обычно Lua-скриптом
- Ответ 429 с заголовком Retry-After
- При недоступности Redis решить: fail open или fail closed
- Лимиты по ключу: пользователь, API-ключ, IP, эндпоинт
Стандартное решение — token bucket со счётчиками в Redis, атомарной проверкой через Lua и осознанным выбором fail open/closed при отказе хранилища.
Как сказать вслух
пример ответаЯ начну с выбора алгоритма и объясню, почему фиксированное окно пропускает двойной лимит на границе. Предложу token bucket с состоянием в Redis, чтобы лимит был общим для всех инстансов. Проверку и списание токена сделаю атомарно Lua-скриптом.
Подробный ответ
Основной ответ
Наивное фиксированное окно (счётчик на минуту) пропускает до двух лимитов на стыке окон, поэтому берут token bucket или sliding window. Token bucket: на ключ хранится число токенов и время последнего пополнения; при запросе токены доначисляются по ставке refill, запрос проходит, если токен есть. Состояние живёт в Redis, чтобы инстансы API делили общий лимит; чтение-пересчёт-запись оборачивается в Lua-скрипт для атомарности. Превышение — ответ 429 с Retry-After и заголовками X-RateLimit-*. Лимитер ставят в API gateway или middleware. Отдельно проговаривается деградация: если Redis недоступен, либо пропускаем всех (fail open), либо режем (fail closed) — выбор зависит от того, что защищаем.
Ключевые моменты
- Token bucket. Даёт среднюю ставку плюс контролируемый всплеск до ёмкости ведра; хранит всего два числа на ключ.
- Атомарность. Без атомарного обновления два параллельных запроса читают один остаток и оба проходят; Lua-скрипт или INCR с EXPIRE закрывают гонку.
- Граница окна. Fixed window уязвим на стыке: N запросов в конце окна и N в начале следующего — 2N за секунды; sliding window counter сглаживает это взвешиванием.
- Поведение при отказе. Fail open сохраняет доступность API, fail closed защищает бэкенд; для внутренней защиты от перегрузки обычно fail open с локальным фолбэк-лимитом.
Практический контекст
Интервьюер смотрит, различаете ли вы алгоритмы и их компромиссы, и помните ли про распределённость — локальный лимит в памяти каждого инстанса не решает задачу. Уточните: лимит жёсткий или допустима небольшая погрешность (тогда можно локальные буферы с синхронизацией), какие ключи лимитирования, нужны ли разные тарифы. Хороший бонус — упомянуть защиту самого Redis от горячих ключей.
Частые ошибки
- Хранят счётчики в памяти инстанса, и общий лимит умножается на число реплик
- Выбирают fixed window и не знают про удвоение лимита на границе окон
- Делают GET, расчёт и SET тремя командами без атомарности — гонка пропускает лишние запросы