Напишите ограничитель частоты запросов: не больше N запросов от одного клиента за скользящее окно в T секунд

ЗадачаSeniorЧасто

Проверила команда СопроводОбновлено

Короткий ответ

Для каждого клиента держите 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 секунд.

Как подойти к решению

  1. Храните в словаре для каждого клиента deque с временем его пропущенных запросов
  2. Удаляйте слева отметки не новее now - T перед каждой проверкой
  3. Сравните длину очереди с лимитом и добавляйте время, только если запрос пропущен
  4. Проверьте всплеск на стыке окон, границу окна и второго клиента

Решение

В 10 и 12 секунд app-1 получил отказ: в последних 10 секундах у него уже три запроса. Фиксированное окно по 10 секунд пропустило бы оба, ведь для него это новый интервал. app-2 считается отдельно. Каждая отметка добавляется и удаляется один раз, поэтому проверка в среднем O(1), память O(N) на клиента.

Python
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 запросов в минуту на пользователя?
  • Напишите функцию, которая решает, пропустить ли запрос клиента по лимиту

Похожие вопросы

ЗадачаSeniorИногда

Ограничьте число одновременных запросов к внешнему API: из 20 задач одновременно должны выполняться не больше 5

Создайте один asyncio.Semaphore(5) на всю выгрузку и передайте его во все задачи. Каждая задача заходит в async with semaphore перед запросом: первые пять получают слот, шестая ждет, пока кто-то выйдет. Все 20 задач запускайте через gather, ограничение работает внутри них. Слот освобождается и при исключении, поэтому упавший запрос не съест лимит.

  • Python
  • asyncio
  • семафор
146
ЗадачаSeniorИногда

Сделайте обработчик оплаты идемпотентным: повторный запрос с тем же ключом не должен списать деньги второй раз

Клиент создает ключ идемпотентности до первой попытки и шлет его с каждым повтором. Сервер хранит по ключу параметры запроса и готовый ответ. Пришел знакомый ключ с теми же параметрами — верните сохраненный ответ без списания. Тот же ключ с другой суммой — ошибка: клиент перепутал запросы. Новый ключ — новая оплата.

  • Python
  • API
  • платежи
167
ЗнаниеJuniorИногда

Чем PUT отличается от PATCH и какие HTTP-методы идемпотентны?

PUT заменяет ресурс целиком: чего нет в теле запроса, то пропадет. PATCH меняет только присланные поля. Метод идемпотентен, если повтор запроса оставляет сервер в том же состоянии, что и один запрос. По RFC 9110 идемпотентны безопасные GET, HEAD, OPTIONS и TRACE, а еще PUT и DELETE. POST и PATCH такой гарантии не дают.

  • Python
  • HTTP
  • REST
219
ЗнаниеJuniorЧасто

Чем Django отличается от FastAPI и когда выбрать каждый из них?

Django — полный фреймворк для сайта: ORM, миграции, админка, пользователи и шаблоны из коробки, API к нему добавляют через DRF. FastAPI — легкий фреймворк для API: валидация через Pydantic по аннотациям типов, документация OpenAPI автоматически, асинхронные обработчики изначально. Базу, миграции и админку к FastAPI подбирают отдельно. Берите Django для продукта с админкой, FastAPI — для сервиса API.

  • Python
  • Django
  • FastAPI
256

Частые вопросы по теме

Короткие ответы на частые вопросы по этой теме.

Фиксированное окно, скользящий журнал из этого решения, скользящий счетчик из двух окон, корзину токенов и протекающее ведро. Для каждого назовите, что он хранит на клиента и как ведет себя при всплеске. Корзина токенов пускает короткий всплеск до размера корзины, журнал держит лимит строго.

Класс удобнее: лимит, окно и словарь очередей живут вместе, и в тесте легко создать новый ограничитель. Если просят декоратор @rate_limit(calls=3, period=10), оберните тот же класс: декоратор создает ограничитель и вызывает allow перед функцией.

Чаще всего на входе: в nginx, API-шлюзе или middleware веб-фреймворка, до бизнес-логики. В коде приложения его пишут, когда лимит зависит от тарифа клиента или конкретной операции. Назовите на собеседовании оба уровня и объясните, почему лишние запросы дешевле отрезать раньше.

Общие вопросы на интервью

Общий вопросС опытомЧасто

Почему вы хотите работать у нас?

Назовите две-три причины, которые связывают вас именно с этой компанией: продукт, задачи, масштаб, команда. Каждую подкрепите фактом, который нашли сами: новость, проект, текст вакансии, свой опыт клиента. Потом покажите, что принесете со своей стороны. Слова о стабильности и известном бренде подходят любой компании, поэтому на них ответ не держится.

  • мотивация
  • о компании
290
Общий вопросБез опытаЧасто

Какие у вас сильные стороны?

Хватит двух-трех сильных сторон, которые нужны на этой работе, если к каждой есть пример: что сделали и какой был результат. Берите качества из текста вакансии, а не из списка «ответственный, коммуникабельный». Без опыта примеры ищите в учебе, практике и подработке. Говорите спокойно, без лишней скромности и без хвастовства.

  • сильные стороны
  • без опыта
276
Общий вопросБез опытаЧасто

Кем вы видите себя через 5 лет?

Расскажите, какие задачи хотите решать через несколько лет и чему для этого научитесь. Свяжите план с тем, что дает эта компания, и покажите первый шаг, который уже сделали. Точную должность называть не обязательно. Важнее, чтобы план был реальным и вел через эту работу, а не мимо нее.

  • мотивация
  • карьерные планы
289
ИсторияС опытомЧасто

Расскажите о конфликте с коллегой: из-за чего он возник и как вы его решили?

Расскажите один реальный конфликт по рабочему вопросу: из-за чего разошлись, чего хотела каждая сторона и как вы договорились. Говорите спокойно, без оценок коллеги. Покажите, что вы искали решение, где-то уступили и сохранили рабочие отношения. Закончите результатом и тем, что теперь делаете, чтобы похожий спор не повторился.

  • конфликты
  • работа в команде
252
ИсторияС опытомЧасто

Каким профессиональным достижением вы гордитесь больше всего?

Назовите одно достижение, близкое к задачам новой работы, и расскажите его как историю: какая была проблема, что сделали лично вы и что изменилось в цифрах. Сильнее всего звучит результат, который держится и после вас: новый порядок работы, правило, схема. Если результат общий, прямо скажите, какая часть в нем ваша.

  • достижения
  • результат в цифрах
276
Общий вопросБез опытаЧасто

Опыта работы еще нет, а интервьюер просит рассказать о себе: что вы скажете?

Начните с того, кто вы сейчас и на какую работу пришли. Вместо стажа расскажите об учебе, практике и подработке, которые похожи на задачи вакансии, и назовите один результат с цифрой. Закончите тем, почему хотите начать карьеру именно здесь. Уложитесь в одну-две минуты и не пересказывайте резюме по порядку.

  • о себе
  • без опыта
244

Вопросы руководителю на интервью

ИсторияРуководительЧасто

Как вы делегируете задачи: что отдаете команде, а что оставляете себе?

Назовите свое правило: что вы отдаете команде и что оставляете себе, и покажите его на одной задаче. Расскажите, кому и почему передали, какие полномочия и рамки дали, как проверяли без мелкого контроля. Закончите честным итогом: что получилось хуже или медленнее, чем у вас, и что вы выиграли.

  • делегирование
  • команда
255
КейсРуководительЧасто

Два сотрудника вашей команды месяц не разговаривают друг с другом, и общий отчет уже сорвал срок — что сделаете?

Поговорите сначала с каждым по отдельности: что случилось, с чего началось и что мешает работать. Потом соберите обоих вместе и обсуждайте работу: кто за какие данные и шаги отвечает. За такой ссорой часто стоит размытая ответственность. Запишите договоренности, назовите новый срок для сорванного отчета и через пару недель проверьте, что все работает.

  • конфликт
  • ответственность
242
ИсторияРуководительЧасто

Расскажите о сотруднике, которого вы вырастили: каким он пришел и чего добился?

Возьмите одного человека и покажите путь: каким он пришел, какие задачи вы ему давали по нарастающей и чем помогали, кем он стал и за какой срок. Назовите цифру роста: новая должность, своя зона, люди в подчинении. Скажите честно, где он вырос сам, а где сработали ваши решения.

  • развитие сотрудников
  • наставничество
303
ИсторияРуководительЧасто

Расскажите о цели, которую ваша команда не выполнила: когда вы это поняли и что сделали?

Назовите цель с цифрой и честный итог. Главное в ответе — момент, когда вы поняли, что цель срывается, и по какой цифре это увидели. Дальше расскажите, кому и когда сказали, что пересобрали, чтобы спасти главное, и какой один вывод сделали для следующего плана.

  • цели
  • провал
241
Общий вопросРуководительЧасто

Как вы измеряете результат своей команды?

Назовите два-три показателя, которые отражают то, ради чего существует ваша команда, и их текущие цифры. Добавьте показатель качества, который не дает гнаться за одним числом. Скажите, как часто смотрите на цифры, кто их видит и какое решение вы приняли по ним в последний раз.

  • показатели
  • цели
216
ИсторияРуководительЧасто

Расскажите, как вы разложили цель компании на задачи для своей команды

Возьмите одну цель компании с цифрой и сроком и покажите, как вы ее разбили: на какие части, по какому признаку, какие личные цели получил каждый сотрудник. Расскажите, как следили за ходом и что меняли по дороге. Закончите итогом план-факт честно, даже если цель выполнена не целиком.

  • цели
  • планирование
227