Python · задача 10 из 10

Ограничитель частоты вызовов

Продвинутый 25 минут token bucketвремямногопоточность

Условие

Реализуйте ограничитель: не больше N вызовов за период T, но с возможностью короткого всплеска. Метод allow() возвращает True, если вызов разрешён, и False, если лимит исчерпан.

Что требуется

Ограничение вида «10 запросов в секунду»
Короткий всплеск допустим, если до этого было затишье
Без фоновых потоков и таймеров — пересчёт при обращении

Пример

limiter = TokenBucket(rate=10, capacity=10)   # 10 запросов в секунду

limiter.allow()   # True  -> есть токены
# ... 10 вызовов подряд ...
limiter.allow()   # False -> токены кончились, ждём пополнения

Сначала уточните

Вопросы до кода — половина оценки. Молча начать печатать хуже, чем задать два вопроса.

Лимит общий или на каждого пользователя (тогда нужен словарь вёдер и их очистка)?
Процесс один или их несколько — во втором случае состояние должно жить в Redis
Нужно ли ждать разрешения (блокирующий вариант) или достаточно ответить «нельзя»?

Показать решение Скрыть решение

Решение

import threading
import time


class TokenBucket:
    def __init__(self, rate, capacity=None):
        self.rate = rate                       # токенов в секунду
        self.capacity = capacity or rate       # предел всплеска
        self._tokens = float(self.capacity)
        self._updated = time.monotonic()
        self._lock = threading.Lock()

    def allow(self, tokens=1):
        with self._lock:
            now = time.monotonic()

            # пополняем ведро за прошедшее время, но не выше ёмкости
            self._tokens = min(
                self.capacity,
                self._tokens + (now - self._updated) * self.rate,
            )
            self._updated = now

            if self._tokens >= tokens:
                self._tokens -= tokens
                return True

            return False

Почему так

Почему token bucket, а не счётчик за окно

Счётчик «N запросов за минуту» даёт эффект границы: 10 запросов в конце одной минуты и 10 в начале следующей — 20 за две секунды
Ведро сглаживает нагрузку: токены копятся равномерно, и всплеск ограничен ёмкостью
Ёмкость — это явная ручка «насколько разрешён всплеск», и её отдельность от rate стоит подчеркнуть

Почему пополняем по времени, а не по таймеру

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

Почему monotonic и почему lock

monotonic не прыгает от перевода часов и синхронизации NTP — на системном времени лимитер мог бы «пополниться» на час вперёд
Чтение и запись _tokens — это read-modify-write: без блокировки два потока пройдут лимит одновременно
GIL здесь не спасает: он не делает последовательность операций атомарной

Что спросят дальше

Спросят про несколько процессов: состояние уезжает в Redis, и пересчёт делают Lua-скриптом, чтобы он был атомарным
Спросят про лимит на пользователя: словарь вёдер плюс вытеснение неактивных, иначе утечка памяти
Спросят про честное ожидание: сколько осталось до следующего токена — (tokens_needed - self._tokens) / self.rate, это же значение уходит в заголовок Retry-After

Тема пройдена

Это была последняя задача темы «Python». Возьмите следующую тему или вернитесь к разобранным через неделю — на собеседовании важно вспомнить, а не узнать.

Ко всем задачам