Rate limiter на собеседовании: алгоритмы, Redis и код 429

Коротко

Rate limiter считает запросы каждого клиента и отклоняет лишние. На собеседовании важно не название алгоритма, а умение объяснить, какую ошибку вы готовы терпеть и сколько за это платите памятью.

Здесь $L$ — лимит на окно, $B$ — размер очереди.

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

Что уточнить в начале

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

• Кого считаем? IP, пользователя, API-ключ, пару «пользователь + ручка».
• Зачем лимит? Защита от перегрузки, от перебора паролей и тарифная квота требуют разной точности.
• Какая точность нужна? Можно ли иногда пропустить на 5% больше?
• Масштаб? Сколько активных клиентов и запросов в секунду, один регион или несколько.
• Что делать с лишними запросами? Отклонить сразу или поставить в очередь.
• Что важнее при сбое ограничителя? Пропускать всех или никого.

Возьмём для примера лимит 100 запросов в минуту и миллион активных клиентов. Оценка памяти сразу отсекает один из вариантов: журнал хранит до 100 меток на клиента, и даже при грубых 64 байтах на запись это порядка 6 ГБ. Два числа на клиента — порядка 100 МБ, с учётом накладных расходов на ключ. Цифры ориентировочные, на реальной системе их проверяют через MEMORY USAGE, но порядок разницы понятен.

Фиксированное окно и всплеск на границе

Время режется на отрезки равной длины, у каждого клиента есть счётчик на текущий отрезок. Новый отрезок обнуляет счётчик.

import threading
import time


class FixedWindowLimiter:
    def __init__(self, limit, window, clock=time.time):
        self.limit = limit
        self.window = window  # длина окна в секундах
        self.clock = clock
        self.lock = threading.Lock()
        self.counters = {}  # ключ -> (номер окна, счётчик)

    def allow(self, key):
        with self.lock:
            window_id = int(self.clock() // self.window)
            saved_id, count = self.counters.get(key, (window_id, 0))
            if saved_id != window_id:
                count = 0  # началось новое окно
            if count >= self.limit:
                return False
            self.counters[key] = (window_id, count + 1)
            return True

Часы передаются параметром, поэтому поведение можно проверить без time.sleep. Этот же приём пригодится для тестов в реальном коде.

Теперь сам дефект. Лимит 5 запросов в минуту, клиент шлёт пять запросов на 59-й секунде и ещё пять на 60-й:

class FakeClock:
    def __init__(self, now=0.0):
        self.now = now

    def __call__(self):
        return self.now


def burst(limiter, clock, at, n=5):
    clock.now = at
    return sum(limiter.allow("user:42") for _ in range(n))


clock = FakeClock()
limiter = FixedWindowLimiter(limit=5, window=60, clock=clock)

print(burst(limiter, clock, at=59.0))  # 5
print(burst(limiter, clock, at=60.0))  # 5
print(burst(limiter, clock, at=60.5))  # 0

Десять запросов за одну секунду при лимите «пять в минуту». Каждое окно по отдельности правило соблюло: 59-я секунда лежит в окне [0, 60), а 60-я уже в [60, 120).

В худшем случае за короткий промежуток проходит $2L$ запросов. Есть и родственная проблема: если клиенты запускаются по крону ровно в начале минуты, их запросы тоже приходят одной пачкой, потому что окна у всех открываются одновременно.

Для суточной квоты «1000 писем в день» это не страшно: разница в паре запросов на границе суток не перегрузит систему. Для защиты от перегрузки на коротком окне это уже настоящая дыра.

Скользящий журнал

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

from collections import deque


class SlidingLog:
    def __init__(self, limit, window, clock=time.time):
        self.limit, self.window, self.clock = limit, window, clock
        self.logs = {}  # ключ -> deque с временем пропущенных запросов

    def allow(self, key):
        now = self.clock()
        log = self.logs.setdefault(key, deque())
        while log and log[0] <= now - self.window:
            log.popleft()
        if len(log) >= self.limit:
            return False
        log.append(now)
        return True

Метки приходят по возрастанию, поэтому старые снимаются с начала двусторонней очереди за амортизированное $O(1)$. Это та же логика, что и в скользящем окне из алгоритмических задач: левая граница догоняет правую.

Ошибки на границе нет, но память растёт линейно от лимита. Лимит 100 в минуту ещё терпим, лимит 10 000 в секунду на миллион клиентов уже нет. Поэтому журнал берут там, где запросов мало, а цена ошибки высока: попытки входа, платёжные операции.

Отклонённые запросы в журнал не записываем. Иначе клиент, продолжающий стучаться после отказа, продлевает собственную блокировку бесконечно.

Скользящий счётчик

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

Здесь $t$ — сколько прошло от начала текущего окна, $W$ — длина окна. Пример: в прошлой минуте было 42 запроса, в текущей уже 18, прошло 15 секунд. Оценка: $42 \cdot 0{,}75 + 18 = 49{,}5$.

class SlidingCounter:
    def __init__(self, limit, window, clock=time.time):
        self.limit, self.window, self.clock = limit, window, clock
        self.counters = {}  # ключ -> {номер окна: счётчик}

    def allow(self, key):
        now = self.clock()
        window_id = int(now // self.window)
        elapsed = (now % self.window) / self.window  # доля прошедшего окна
        counts = self.counters.get(key, {})
        previous = counts.get(window_id - 1, 0)
        current = counts.get(window_id, 0)

        if previous * (1 - elapsed) + current >= self.limit:
            return False
        self.counters[key] = {window_id - 1: previous, window_id: current + 1}
        return True

Формула предполагает, что запросы прошлого окна шли равномерно. На практике это допущение работает неплохо: Cloudflare проверяла подход на 400 миллионах запросов от 270 тысяч источников и насчитала 0,003% ошибочных решений. Но это данные одного разбора на реальном трафике: клиент, который бьёт пачками, может получить ошибку заметно больше, как покажет сравнение ниже.

Token bucket

Корзина вмещает capacity токенов и пополняется со скоростью refill_rate токенов в секунду. Запрос забирает токен. Нет токена, нет и запроса.

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

class TokenBucket:
    def __init__(self, capacity, refill_rate, clock=time.monotonic):
        self.capacity = capacity
        self.refill_rate = refill_rate  # токенов в секунду
        self.clock = clock
        self.lock = threading.Lock()
        self.buckets = {}  # ключ -> (токены, время обновления)

    def acquire(self, key, cost=1):
        """Возвращает пару: пропускать ли запрос и сколько секунд ждать."""
        with self.lock:
            now = self.clock()
            tokens, updated = self.buckets.get(key, (self.capacity, now))
            tokens = min(self.capacity, tokens + (now - updated) * self.refill_rate)

            if tokens >= cost:
                self.buckets[key] = (tokens - cost, now)
                return True, 0.0

            self.buckets[key] = (tokens, now)
            return False, (cost - tokens) / self.refill_rate

    def allow(self, key):
        return self.acquire(key)[0]

Проверяем на примере: ёмкость 5, один токен в секунду.

clock = FakeClock()
bucket = TokenBucket(capacity=5, refill_rate=1, clock=clock)

print([bucket.allow("user:42") for _ in range(6)])
# [True, True, True, True, True, False]

allowed, retry_after = bucket.acquire("user:42")
print(allowed, retry_after)  # False 1.0

clock.now = 2.5  # за 2,5 секунды накапало 2,5 токена
print([bucket.allow("user:42") for _ in range(3)])
# [True, True, False]

clock.now = 1000.0  # долгий простой: корзина полна, но не больше ёмкости
print(sum(bucket.allow("user:42") for _ in range(10)))  # 5

Что важно проговорить:

• Ёмкость и скорость настраиваются отдельно. Скорость задаёт средний поток, ёмкость задаёт допустимый всплеск. Это главное отличие от окон.
• Лимита «за окно» здесь нет. За время $T$ пройдёт до $C + r \cdot T$ запросов, где $C$ — ёмкость, $r$ — скорость. При ёмкости 5 и скорости 5 в минуту за первую минуту клиент получит не 5, а почти 10 запросов. Если в договоре написано «не больше 100 в минуту», берите скользящее окно либо подбирайте параметры так, чтобы $C + r \cdot W \le L$.
• Параметр cost позволяет брать за тяжёлые запросы больше токенов. Запрос дороже ёмкости не пройдёт никогда, такие лучше отсекать при настройке.

Token bucket используют в Stripe для лимитов API, что описано в их разборе ограничителей на Redis.

Leaky bucket

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

Счётчик (meter). Очереди нет, ведро только считает уровень:

class LeakyBucket:
    def __init__(self, capacity, leak_rate, clock=time.monotonic):
        self.capacity, self.leak_rate, self.clock = capacity, leak_rate, clock
        self.buckets = {}  # ключ -> (уровень, время обновления)

    def allow(self, key):
        now = self.clock()
        level, updated = self.buckets.get(key, (0.0, now))
        level = max(0.0, level - (now - updated) * self.leak_rate)
        if level + 1 > self.capacity:
            self.buckets[key] = (level, now)
            return False
        self.buckets[key] = (level + 1, now)
        return True

Это зеркало token bucket: уровень воды равен capacity - tokens. Я прогнал обе реализации с одинаковыми параметрами на 100 000 случайных запросов, и решения не разошлись ни разу. Если на собеседовании говорят, что эти алгоритмы принципиально разные, стоит уточнить: разница появляется только во втором варианте.

Очередь (shaper). Запросы реально ждут в FIFO-очереди и уходят дальше с постоянной скоростью. Всплеск на выходе исчезает полностью, но появляется задержка: последний в очереди ждёт $B / r$ секунд. Такой вариант подходит, когда позади стоит сервис, не переживающий пики: внешний API со строгим лимитом, старая база.

Живой пример: модуль limit_req в nginx. Документация прямо называет метод leaky bucket. Параметр burst задаёт размер очереди, а nodelay отправляет запросы из неё сразу, не растягивая их во времени. Без burst при rate=10r/s второй запрос в пределах 100 мс уже получит отказ: nginx считает с точностью до миллисекунд.

Сравнение на одном сценарии

Прогоним все алгоритмы через одни и те же запросы. Лимит 5 в минуту, для корзин ёмкость 5 и скорость 5 в минуту.

def passed(make_limiter, times):
    clock = FakeClock()
    limiter = make_limiter(clock)
    total = 0
    for moment in times:
        clock.now = moment
        total += limiter.allow("user:42")
    return total


limiters = {
    "fixed window": lambda c: FixedWindowLimiter(5, 60, clock=c),
    "sliding log": lambda c: SlidingLog(5, 60, clock=c),
    "sliding counter": lambda c: SlidingCounter(5, 60, clock=c),
    "token bucket": lambda c: TokenBucket(5, 5 / 60, clock=c),
    "leaky bucket": lambda c: LeakyBucket(5, 5 / 60, clock=c),
}

at_boundary = [59.0] * 5 + [60.0] * 5
half_later = [59.0] * 5 + [90.0] * 5

for name, make in limiters.items():
    print(f"{name:16} {passed(make, at_boundary):3} {passed(make, half_later):3}")

Как это читать:

• На границе ломается только фиксированное окно.
• Во втором сценарии точный ответ только у журнала: между t=59 и t=90 прошло меньше минуты, новых мест нет.
• Счётчик пропустил лишние 3 запроса, потому что решил, что половина старых запросов уже в прошлом, хотя вся пачка пришла в самом конце окна. Это и есть цена допущения о равномерности.
• Корзины пропустили 2 запроса, но это не ошибка. За 31 секунду накапало $31 \cdot 5 / 60 \approx 2{,}6$ токена, они лимитируют средний поток, а не число запросов за минуту.

Распределённая версия

Одного процесса хватает ненадолго. За балансировщиком стоит несколько экземпляров, и если у каждого свой счётчик, то при $N$ экземплярах реальный лимит становится $N \cdot L$. Счётчик нужно вынести в общее хранилище, обычно это Redis: быстрый доступ, встроенный TTL и атомарные операции.

Почему нельзя читать, а потом писать

Наивный код делает GET, сравнивает с лимитом и делает SET. Между чтением и записью проходит сетевая задержка, и за это время другие запросы успевают прочитать то же значение.

Ниже имитация: настоящего Redis тут нет, вместо него объект, где каждая команда занимает 5 мс на «сеть». Лимит 10, одновременно приходит 100 запросов.

class FakeRedis:
    """Хранилище, до которого идёт «сеть»: команда занимает 5 мс."""

    def __init__(self):
        self.data = {}
        self.lock = threading.Lock()

    def get(self, key):
        time.sleep(0.005)
        with self.lock:
            return self.data.get(key, 0)

    def set(self, key, value):
        time.sleep(0.005)
        with self.lock:
            self.data[key] = value

    def incr(self, key):
        time.sleep(0.005)
        with self.lock:  # чтение и запись в одной неделимой операции
            self.data[key] = self.data.get(key, 0) + 1
            return self.data[key]


LIMIT = 10


def check_then_set(store):
    count = store.get("user:42")
    if count >= LIMIT:
        return False
    store.set("user:42", count + 1)
    return True


def atomic_incr(store):
    return store.incr("user:42") <= LIMIT


def run(strategy, requests=100):
    store = FakeRedis()
    allowed = []

    def worker():
        if strategy(store):
            allowed.append(1)

    threads = [threading.Thread(target=worker) for _ in range(requests)]
    for thread in threads:
        thread.start()
    for thread in threads:
        thread.join()
    return len(allowed), store.data["user:42"]


print("get + set:", run(check_then_set))  # (100, 1)
print("incr:     ", run(atomic_incr))     # (10, 100)

Вариант с GET и SET пропустил все 100 запросов, а счётчик остался равен 1: каждый поток прочитал 0 и записал 1. Вариант с INCR пропустил ровно 10. Счётчик у него дошёл до 100, и это нормально: важен ответ каждой отдельной команды, а не итоговое значение. В живой системе запросы приходят не так синхронно и перелёт будет меньше, но направление то же.

Счётчик: INCR и EXPIRE

Команды Redis выполняются по одной, поэтому INCR атомарна сама по себе. Но есть вторая ловушка, она описана в документации команды: если выполнить INCR и EXPIRE отдельно и клиент упадёт между ними, ключ останется без TTL. Счётчик без срока жизни значит утечку памяти, а в схеме с одним ключом на клиента ещё и вечную блокировку.

Дальше псевдокод, а не готовый скрипт. Перед продом его нужно проверить на настоящем Redis под нагрузкой.

функция allow_fixed_window(client, limit, window):
    window_id = floor(now / window)
    key = "rl:{" + client + "}:" + window_id

    MULTI
        INCR key
        EXPIRE key, window * 2
    EXEC

    count = ответ INCR
    remaining = max(0, limit - count)
    вернуть count <= limit, remaining

Номер окна зашит в имя ключа, поэтому EXPIRE на каждый запрос ничего не сломает: TTL только не даёт старым ключам копиться, а обнуление счётчика происходит за счёт нового имени. MULTI/EXEC гарантирует, что команды идут вместе и ничто не вклинится между ними.

Token bucket: нужен скрипт

Корзина требует прочитать состояние, посчитать и записать. Отдельными командами это снова гонка. Решение: скрипт на Lua, и Redis гарантирует его атомарное выполнение, на время работы скрипта сервер больше ничего не делает.

скрипт acquire(key, capacity, rate):      # выполняется внутри Redis целиком
    now = TIME
    tokens, updated = HMGET key tokens updated
    если ключа нет:
        tokens = capacity
        updated = now

    tokens = min(capacity, tokens + (now - updated) * rate)

    если tokens >= 1:
        tokens = tokens - 1
        allowed = 1
        retry_after_ms = 0
    иначе:
        allowed = 0
        retry_after_ms = ceil((1 - tokens) / rate * 1000)

    HSET key tokens tokens updated now
    PEXPIRE key ceil(capacity / rate * 1000)
    вернуть allowed, tokens, retry_after_ms

Несколько деталей, которые отличают того, кто это реально делал:

• Время берём из Redis. Часы экземпляров расходятся, а одна точка отсчёта это снимает. Команда TIME в пишущих скриптах работает с Redis 5, где репликация эффектов стала режимом по умолчанию.
• TTL равен времени полного наполнения. К этому моменту корзина всё равно полная, поэтому пропажа ключа ничего не меняет: новый клиент как раз начинает с полной корзины.
• Дробные числа. Числа Lua при возврате клиенту обрезаются до целых, поэтому 0,7 токена придёт как 0. Возвращайте целые миллисекунды либо строку.
• Скрипт должен быть коротким. Он блокирует весь сервер, никаких циклов по большим данным.

Кластер, реплики, регионы

• Шардирование. Клиента удобно шардировать по его идентификатору. В Redis Cluster все ключи одного скрипта обязаны лежать в одном слоте, поэтому у скользящего счётчика ключи двух окон объединяют хеш-тегом: rl:{user:42}:1040 и rl:{user:42}:1041.
• Реплики. Читать счётчики с реплик нельзя: репликация асинхронная, данные отстают. По той же причине при переключении на реплику часть последних увеличений теряется и клиент получит чуть больше запросов. Для ограничителя это обычно приемлемо.
• Сетевой поход на каждый запрос. Это добавляет задержку и нагрузку. Если нагрузка велика, экземпляр берёт у Redis токены партиями, например по 100, и расходует локально. Обращений становится на порядки меньше, зато точность падает: выданные партии могут простаивать на других экземплярах.
• Несколько регионов. Синхронный общий счётчик через океан убьёт задержку. Обычно считают в каждом регионе отдельно и либо делят лимит между регионами, либо обмениваются счётчиками асинхронно, соглашаясь на временное превышение.

Когда Redis недоступен

Ограничитель не должен становиться новой единой точкой отказа. Ставьте на обращение к Redis короткий таймаут и заранее решите, что делать при ошибке:

• Fail open: пропускаем. Подходит для большинства API, лимит защищает сервис, а не должен сам его ронять. Stripe советует именно это: ошибки в коде или сбой Redis не должны влиять на запросы.
• Fail closed: отклоняем. Подходит там, где пропуск дороже отказа: вход в систему, сброс пароля, отправка платных SMS.
• Запасной локальный лимит. Компромисс: при сбое экземпляр считает сам, например по $L / N$ на экземпляр.

Где разместить ограничитель

В реальности это слои. На границе простой лимит по IP против ботов, в шлюзе лимиты по ключу и тарифу, а в сервисе точечные правила вроде «три попытки сброса пароля в час».

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

• IP. За одним NAT сидит целый офис, а у IPv6-клиента обычно есть целая подсеть, поэтому считать надо по префиксу, а не по адресу.
• X-Forwarded-For. Клиент может подделать этот заголовок. Доверять можно только значению, добавленному вашим собственным прокси.
• Неавторизованный трафик. Анонимов приходится считать по IP, а авторизованных лучше по пользователю, чтобы соседи по NAT не мешали друг другу.

Заголовки ответа и код 429

Статус для превышения лимита определён в RFC 6585: 429 Too Many Requests. Стандарт разрешает добавить Retry-After, не определяет, как считать запросы и опознавать клиента, и запрещает кешировать такой ответ.

HTTP/1.1 429 Too Many Requests
Content-Type: application/json
Retry-After: 30
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1793750430

{"error": "rate_limit_exceeded", "retry_after": 30}

С заголовками ситуация такая:

• Retry-After стандартный, значение в секундах или дата. Если у вас дробное время ожидания, округляйте вверх: округление вниз обеспечит клиенту ещё один отказ.
• X-RateLimit-* не стандарт, а привычка. Например, GitHub отдаёт x-ratelimit-limit, x-ratelimit-remaining и x-ratelimit-reset, где последнее значение это UTC-время в секундах эпохи. Формат у разных API отличается: где-то секунды до сброса, где-то метка времени.
• RateLimit и RateLimit-Policy это попытка стандартизировать всё это. На ноябрь 2026 года это черновик IETF, а не RFC, и синтаксис менялся от версии к версии. Сейчас он выглядит так: RateLimit-Policy: "default";q=100;w=60 и RateLimit: "default";r=0;t=30. При наличии обоих Retry-After приоритетнее.

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

Со статусами стоит различать два случая. 429 значит, что клиент превысил свою квоту, 503 значит, что сервис перегружен сам по себе. Stripe, например, отвечает 503 при сбросе некритичной нагрузки. Учтите и умолчания: в nginx limit_req_status по умолчанию равен 503, поэтому для API его обычно переключают на 429. А GitHub при превышении основного лимита может вернуть как 403, так и 429, поэтому клиенту надёжнее смотреть ещё и на заголовки.

И не забудьте про клиентскую сторону. Если тысячи клиентов получат одинаковый Retry-After, они вернутся одновременно и устроят новый пик. Поэтому на клиенте нужен экспоненциальный backoff со случайной добавкой (jitter).

Типичные ошибки

• Считать время разными часами. В локальном token bucket берите time.monotonic, а не time.time: системное время может прыгнуть назад. В распределённом берите время Redis.
• GET, а потом SET. Разобрано выше. Классическая ошибка и на собеседовании, и в проде.
• Журнал в Redis с меткой времени как элементом. В ZSET элементы уникальны: два запроса в одну миллисекунду схлопнутся в один и лимит занизит счёт. Добавляйте к элементу случайный суффикс или идентификатор запроса.
• Никогда не чистить состояние. Словарь из примеров выше растёт вместе с числом клиентов. В коде на одном узле нужно вытеснение, например по схеме LRU, в Redis за это отвечает TTL.
• Считать лимит на экземпляр и называть его общим. Добавили реплик при автомасштабировании, и лимит незаметно вырос.
• Лимитировать только по IP. Заблокируете офис за одним NAT и не остановите ботнет.
• Округлять Retry-After вниз. Клиент послушно придёт на долю секунды раньше и получит новый 429.

Как рассказывать на собеседовании

Задача классическая: отдельная глава про rate limiter есть, например, в книге Алекса Сюя «System Design Interview». Поэтому общие слова вас не выделят, выделят компромиссы. Рабочий порядок на 30–40 минут:

1. Требования. Кого считаем, какая точность, масштаб, поведение при сбое.
2. Оценка. Клиенты, запросы в секунду, память на клиента.
3. Алгоритм. Назовите 2–3 варианта и выберите один с причиной: «нужны короткие пики, поэтому token bucket» или «лимит в договоре жёсткий, поэтому скользящий счётчик».
4. Схема. Шлюз, Redis, правила лимитов в конфигурации, метрики отказов.
5. Узкие места. Атомарность, задержка на Redis, поведение при сбое, несколько регионов.

Вопросы, которые часто идут следом (как к ним готовиться, разобрано в статье про follow-up вопросы):

• Как поменять лимиты без перезапуска? Правила лежат в конфигурации, которую экземпляры периодически перечитывают.
• Как уместить состояние корзины в одно число? Посмотрите на GCRA: вместо токенов хранится теоретическое время следующего запроса.
• Как понять, что лимиты работают? Метрики доли 429 по клиентам и ручкам, плюс теневой режим: считаем отказы, но пока никого не блокируем.
• Как написать это прямо на доске? Для одного процесса подойдёт код выше, а вариант на Go с каналом есть в подборке вопросов для Go-разработчиков.

Если запомнить одну фразу: алгоритм определяет, какие всплески вы терпите, а атомарность определяет, работает ли лимит вообще.