Код Middle Безопасность бэкенда спрашивают часто обновлено

Rate limiter на token bucket

Условие

Реализуй class TokenBucket для ограничения частоты запросов по ключу (IP, пользователь, API-ключ):

  • new TokenBucket({ capacity, refillPerSec, now = () => Date.now() }): ведро вмещает capacity токенов, пополняется со скоростью refillPerSec токенов в секунду (непрерывно, дробно), новый ключ стартует с полным ведром;
  • take(key, cost = 1): если токенов хватает, списывает cost и возвращает { allowed: true, remaining }, где remaining целая часть остатка (Math.floor); иначе ничего не списывает и возвращает { allowed: false, retryAfterMs }: через сколько мс токенов станет достаточно (Math.ceil).

Состояние ключа: число токенов и время последнего пересчёта. Пересчитывать лениво при обращении, без таймеров.

Что проверяют тесты

  • всплеск до capacity, потом отказ

  • пополнение со временем

  • не больше capacity после простоя

  • ключи независимы

  • отказ не списывает токены

  • дробное пополнение

Как подойти

Подсказки: 2
  1. При каждом take досчитай токены: + прошедшие секунды × скорость, но не выше capacity.
  2. Время ожидания: недостающие токены делить на скорость.

Решите в тренажёре

Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.

Термины по теме