lab09 — rate limiting¶

Ограничение скорости (rate limiting) — это «дозатор» запросов: сколько обращений к сервису разрешить за единицу времени, а остальные отбить. Лаборатория целиком про четыре классических алгоритма — token bucket, leaky bucket, sliding window log и sliding window counter — и про структуру, на которой строится точное скользящее окно: кольцевой буфер (ring buffer).

Главный методический приём лабы — время как параметр. Ни один лимитер не дёргает реальные часы и не делает sleep: «текущее время» приходит снаружи аргументом allow(now). Это и про тестируемость (тест детерминированно «прокручивает» время), и про честность модели — в проде «now» тоже приходит снаружи (timestamp запроса).

Кольцевой буфер (ring buffer)¶

Идея: фиксированный массив на capacity ячеек и два указателя по кругу: head (самый старый элемент) и tail (куда писать следующий). Массив выделяется один раз и не растёт. Отдельный счётчик _count отличает «пусто» от «полно», когда head == tail.

def push(self, value) -> None:
    self._data[self._tail] = value
    self._tail = (self._tail + 1) % self._capacity
    if self._count == self._capacity:
        # буфер был полон: самый старый элемент затёрт — двигаем head
        self._head = (self._head + 1) % self._capacity
    else:
        self._count += 1

Ключевое свойство — перезапись по кругу: когда буфер полон, новый push затирает самый старый элемент, а head сдвигается вперёд. Ровно это нужно скользящему окну: старые отметки времени должны «уезжать» сами. Все операции (push, pop, peek_oldest) — O(1), памяти ровно capacity ячеек.

Операция	Сложность
`push` / `pop` / `peek_oldest`	O(1)
`to_list`	O(capacity)

Token Bucket (ведро с токенами)¶

Идея: в ведро ёмкости capacity токены капают со скоростью rate штук в секунду (до потолка). Каждый разрешённый запрос съедает токен. Есть токен — запрос проходит, нет — отбивается.

def _refill(self, now: float) -> None:
    dt = now - self._last
    self._tokens = min(self._capacity, self._tokens + dt * self._rate)
    self._last = now

def allow(self, now: float, cost: float = 1.0) -> bool:
    self._refill(now)
    if self._tokens >= cost:
        self._tokens -= cost
        return True
    return False

Токены не «тикают» по таймеру — мы досчитываем их лениво при каждом allow: сколько накапало за dt = now - last. Стартуем с полным ведром, поэтому token bucket допускает всплеск (burst): можно потратить сразу до capacity запросов, а дальше — только со скоростью пополнения. Это его главное отличие: он сглаживает среднюю нагрузку, но пропускает короткие пики.

Leaky Bucket (дырявое ведро)¶

Идея: ведро с дыркой в дне. Запросы «наливаются», вода равномерно «вытекает» со скоростью rate. Если запрос помещается (ведро не переполнится) — принимаем, иначе overflow.

def _leak(self, now: float) -> None:
    dt = now - self._last
    self._water = max(0.0, self._water - dt * self._rate)
    self._last = now

def allow(self, now: float, amount: float = 1.0) -> bool:
    self._leak(now)
    if self._water + amount <= self._capacity:
        self._water += amount
        return True
    return False

В отличие от token bucket, leaky bucket сглаживает поток до равномерного: на выходе — стабильный rate, всплеск гасится переполнением. Token bucket разрешает «потратить накопленное разом», leaky bucket — нет. Выбор между ними — это выбор «разрешаем ли всплески».

Sliding Window Log (точное окно)¶

Идея: хранить времена последних запросов и считать, сколько их попало в окно (now - window, now]. Запрос проходит, если в окне меньше limit запросов. Старые отметки выкидываются.

def allow(self, now: float) -> bool:
    self._evict_old(now)                       # выкинуть протухшие отметки
    if array_length(self._log.to_list()) < self._limit:
        self._log.push(now)
        return True
    return False

Отметки лежат в кольцевом буфере на limit ячеек — больше живых отметок в окне быть не может (на limit+1-й запрос мы скажем «нет»). Самые старые отметки — в голове буфера, поэтому _evict_old просто отрезает их с головы, пока они <= now - window. Это самый точный алгоритм: окно скользит непрерывно, нет «скачка» на границе. Цена — память: храним каждый разрешённый запрос (O(limit) на клиента).

Sliding Window Counter (дешёвое приближение)¶

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

estimated = prev_count * (доля предыдущего окна в скольжении) + curr_count

Доля предыдущего окна = (window - elapsed_in_current) / window. Чем дальше мы продвинулись в текущем окне, тем меньше вес предыдущего.

def allow(self, now: float) -> bool:
    self._roll(now)                            # перемотать окна, если ушли вперёд
    if self._estimated(now) < self._limit:
        self._curr_count += 1
        return True
    return False

Память — O(1) на клиента, не зависит от числа запросов. Точность чуть ниже log (на границе окна возможна небольшая погрешность из-за допущения о равномерности предыдущего окна), но именно так считают rate limit nginx и многие API gateway — память важнее идеальной точности.

Сравнение алгоритмов¶

Алгоритм	Память	Всплески (burst)	Точность	Форма на выходе
token bucket	O(1)	разрешает до ёмкости	средняя	средняя нагрузка
leaky bucket	O(1)	гасит	средняя	равномерный поток
sliding window log	O(limit)	точно по окну	высокая	точное окно
sliding window counter	O(1)	приближённо	средняя/высокая	приближённое окно

На всплеске «10 запросов в момент t=0» (см. demo_burst) видно главное: token и leaky bucket пропустят примерно «ёмкость» запросов, скользящие окна — limit, а остальные отобьют. На равномерном потоке в пределах rate (см. demo_steady) все четыре пропускают почти всё — лимитеры успевают пополняться/вытекать между запросами.

Где это в проде¶

Троттлинг API. Публичные API (Stripe, GitHub, Cloudflare) ограничивают клиента по ключу/токену: 429 Too Many Requests + заголовки Retry-After / X-RateLimit-Remaining. Token bucket — самый частый выбор, потому что разрешает разумные всплески.
Защита сервиса от перегрузки. nginx модулем limit_req реализует ровно sliding window / leaky bucket (zone + rate + burst); API gateway (Kong, Envoy, AWS API Gateway, Apigee) дают token/sliding-window лимиты на маршрут и потребителя. Это первый эшелон против лавины запросов и DDoS-подобной нагрузки.
Лимиты на стороне клиента и сервера. Сервер защищает себя (rate limit на ingress), а клиент — соседей и себя: SDK и HTTP-клиенты встраивают token bucket, чтобы не выбивать 429 (клиентский троттлинг, backoff). Та же идея — в распределённых лимитерах поверх Redis (INCR + TTL для sliding window counter), где счётчики окна общие на весь кластер.

Параллельная реализация на Go¶

Те же четыре алгоритма естественно ложатся на Go. Стандартная библиотека уже содержит token bucket — пакет golang.org/x/time/rate (rate.NewLimiter(r, b)), и его модель «время как параметр» совпадает с нашей: у Limiter есть метод AllowN(t time.Time, n int), куда время передаётся явно — ровно как наш allow(now).

Подводный камень переноса: монотонные часы и тип времени

В Python мы передаём now как float (секунды). В Go время — это time.Time, а интервалы — time.Duration; нельзя вычитать «секунды как числа», нужно now.Sub(last) и сравнение с time.Duration. Для дельт берите монотонные часы (time.Now() в Go несёт монотонную компоненту, а в распределённом лимитере — серверный timestamp), иначе перевод часов назад (NTP-скачок) сломает refill/leak — мы защищаемся от этого проверкой now < last.

PythonGo

def allow(self, now: float, cost: float = 1.0) -> bool:
    self._refill(now)
    if self._tokens >= cost:
        self._tokens -= cost
        return True
    return False

// через стандартный golang.org/x/time/rate — время передаётся явно
lim := rate.NewLimiter(rate.Limit(1), 5) // rate=1/сек, burst=5
now := time.Now()
if lim.AllowN(now, 1) {                   // как наш allow(now, cost)
    // запрос разрешён
}