Какие алгоритмы ограничения частоты запросов вы знаете?

Зачем: защитить сервис от перегрузки и злоупотреблений, честно разделить ресурс между клиентами (тарифы API), ограничить стоимость обращений к платным зависимостям, замедлить перебор паролей.

Token bucket. Ведро вмещает B жетонов и пополняется R жетонами в секунду (не больше B). Каждый запрос забирает жетон; если пусто — отказ (или ожидание). Хранить достаточно двух чисел: число жетонов и время последнего пополнения — пополнение считается лениво при запросе. Свойства: средняя скорость не выше R, но после затишья разрешён всплеск до B. Самый популярный вариант: AWS API Gateway, Stripe, Guava RateLimiter (с плавным выдачей), nginx limit_req с burst.

Leaky bucket. Запросы встают в очередь ограниченного размера и обрабатываются с постоянной скоростью R. Выход идеально ровный — подходит, когда нижний сервис не выносит всплесков. Цена — задержка в очереди. Как счётчик (без очереди) эквивалентен token bucket.

Фиксированное окно. Счётчик на интервал (INCR key:минута, TTL 60 с). Очень просто и дёшево. Проблема — на границе: 100 запросов в 12:00:59 и ещё 100 в 12:01:00 — 200 за две секунды при лимите 100 в минуту.

Скользящий журнал. Храним время каждого запроса за последнее окно (sorted set в Redis), выкидываем старые, считаем оставшиеся. Точно, но память пропорциональна лимиту.

Скользящий счётчик. Два фиксированных окна — текущее и предыдущее; оценка = текущее + предыдущее × доля перекрытия. Почти точно и дёшево (так делает Cloudflare).

Что учесть:

• ключ лимита — пользователь, API-ключ, IP, тенант, эндпоинт; обычно несколько уровней сразу;
• ответ — 429 Too Many Requests, Retry-After, заголовки RateLimit-Limit/Remaining/Reset;
• где считать — в шлюзе или сайдкаре, локально (быстро, но лимит на экземпляр) или в общем хранилище (Redis) — точнее, но сетевой поход;
• стоимость запроса — тяжёлые запросы могут забирать больше жетонов;
• поведение при недоступности хранилища лимитов — пропускать (fail-open) или отказывать (fail-closed).

import time

class TokenBucket:
    def __init__(self, rate, burst):
        self.rate, self.burst = rate, burst
        self.tokens, self.ts = burst, time.monotonic()

    def allow(self, cost=1):
        now = time.monotonic()
        self.tokens = min(self.burst, self.tokens + (now - self.ts) * self.rate)
        self.ts = now
        if self.tokens >= cost:
            self.tokens -= cost
            return True
        return False