Напишите ограничитель частоты запросов: не больше N запросов от одного клиента за скользящее окно в T секунд
Проверила команда Сопровод · Обновлено
Короткий ответ
Для каждого клиента держите deque с временем его пропущенных запросов. На новом запросе выбросьте слева отметки не новее now - T и сравните длину очереди с лимитом. Меньше N — добавьте время и пропустите запрос, иначе отдайте 429. Клиенты не мешают друг другу, и скользящее окно не пускает всплеск на стыке двух фиксированных окон.
Почему этот вопрос задают
Ограничение частоты стоит перед любым публичным API, и на Senior его часто просят написать с нуля. Видно, как кандидат выбирает алгоритм, считает память и разбирается с границей окна.
Условие задачи
Публичное API метеосервиса пускает не больше 3 запросов от одного ключа за любые 10 секунд. Напишите класс с методом allow(client, now), который решает, пропустить ли запрос. Время передается аргументом в секундах. Запрос, сделанный ровно 10 секунд назад, в окно уже не входит, отказы в лимит не засчитываются. Проверьте на журнале: app-1 в 7, 8, 9, 10, 12 и 17 секунд, app-2 в 9 секунд.
Как подойти к решению
- Храните в словаре для каждого клиента
dequeс временем его пропущенных запросов - Удаляйте слева отметки не новее
now - Tперед каждой проверкой - Сравните длину очереди с лимитом и добавляйте время, только если запрос пропущен
- Проверьте всплеск на стыке окон, границу окна и второго клиента
Решение
В 10 и 12 секунд app-1 получил отказ: в последних 10 секундах у него уже три запроса. Фиксированное окно по 10 секунд пропустило бы оба, ведь для него это новый интервал. app-2 считается отдельно. Каждая отметка добавляется и удаляется один раз, поэтому проверка в среднем O(1), память O(N) на клиента.
class SlidingWindowLimiter:
def __init__(self, limit, window):
self.limit, self.window = limit, window
self.hits = defaultdict(deque)
def allow(self, client, now):
hits = self.hits[client]
while hits and hits[0] <= now - self.window:
hits.popleft()
if len(hits) >= self.limit:
return False
hits.append(now)
return True
limiter = SlidingWindowLimiter(limit=3, window=10)
log = [("app-1", 7), ("app-1", 8), ("app-1", 9), ("app-2", 9),
("app-1", 10), ("app-1", 12), ("app-1", 17)]
for client, now in log:
print(client, now, "ok" if limiter.allow(client, now) else "429")app-1 7 ok app-1 8 ok app-1 9 ok app-2 9 ok app-1 10 429 app-1 12 429 app-1 17 ok
Что спросят следом
Как сделать то же, если API работает в четырех экземплярах?
Сколько памяти уйдет при лимите 1000 запросов в минуту и 100 000 клиентов?
Что вернуть клиенту, которому отказали?
Доступно по подписке
Ответы на эти вопросы
Частые ошибки
«Засчитаю в лимит и отклоненные запросы»
Тогда клиент, который упрямо повторяет запрос, не выберется из блокировки: каждый отказ продлевает окно. Обычно считают только пропущенные запросы, а настойчивых режут отдельным правилом
«Возьму
time.time()прямо внутриallow»Системные часы могут прыгнуть назад при синхронизации, и окно поедет. Берите
time.monotonic()и передавайте время параметром: так ограничитель проверяется тестом без ожидания«Сложу запросы всех клиентов в один список и буду фильтровать его на каждом вызове»
Фильтр проходит весь список на каждом запросе, и время растет с нагрузкой. Очередь на клиента с удалением слева трогает только устаревшие отметки
«Очереди клиентов удалять не нужно, они почти ничего не весят»
allowчистит только очередь того, кто прислал запрос: разовые клиенты останутся в словаре навсегда. Раз в минуту удаляйте фоновой задачей ключи, у которых все отметки вышли из окна
Сигналы для интервьюера
Сильный ответ
Сразу спрашивает, как быть с запросами без ключа, и предлагает ограничивать их отдельно, по IP-адресу
Тревожный сигнал
Знает слова «корзина токенов» и «скользящее окно», но не может посчитать на примере, пропустит ли алгоритм запрос в 10 секунд
Красный флаг
Заводит один общий счетчик на весь сервис и при всплеске от одного клиента режет запросы всех остальных
Как еще могут спросить
- Как реализовать rate limiter на Python?
- Чем скользящее окно отличается от фиксированного при ограничении запросов?
- Как ограничить API до N запросов в минуту на пользователя?
- Напишите функцию, которая решает, пропустить ли запрос клиента по лимиту











