Перейти к содержанию

Средняя

Rate Limiter

ограничение частоты запросов

Условие

Решить за две миллисекунды, пропустить запрос или отдать 429. Данных здесь почти нет: вся задача в том, как держать общий счётчик на десятках инстансов API и что делать, когда хранилище счётчиков недоступно.

Спроектируйте сервис ограничения частоты запросов.

Перед вашим API стоит проверка: по ключу — пользователю, IP или API-ключу — она решает, пропустить запрос дальше или ответить 429. Правила разные: анонимный читатель и авторизованный пользователь живут по разным лимитам, а POST дороже GET. Короткий всплеск выше среднего темпа разрешён.

Считайте, что:

  • проверка добавляет к запросу не больше ~2 мс на 99-м перцентиле;
  • небольшое превышение лимита допустимо, точный счёт каждого запроса — нет;
  • инстансов API десятки, и их количество меняется автоскейлом;
  • правила меняются руками примерно раз в неделю.

Детект ботов, captcha и WAF в задачу не входят: это ограничитель частоты, а не система безопасности.

Требования

Функциональные 6

  • Проверка по ключу: пропустить или отдать 429 с Retry-After
  • Ключ — user_id, IP или API-ключ; после аутентификации приоритет у user_id
  • Разные правила на route, на тип клиента и на метод
  • Короткий всплеск выше среднего темпа (burst)
  • Стоимость запроса в токенах: загрузка дороже чтения
  • Заголовки RateLimit-Policy и RateLimit в каждом ответе

Нефункциональные 4

  • Проверка добавляет к запросу < 2 мс на p99
  • При исправном хранилище клиент на всплеске проходит не больше 105% от rate × окно + burst
  • При исправном хранилище клиент в пределах лимита получает 429 не чаще чем в 0,1% проверок
  • Сбой хранилища счётчиков не останавливает API целиком: часть операций продолжает работать

Задачи того же уровня

Решите задачу у доски

Интервьюер задаст вопросы по вашей схеме, проверка разберёт её по семи осям