Rate limiting на практике: token bucket, leaky bucket и где какой нужен
Rate limiting — это не «защита от DDoS», как часто думают. DDoS лечится на уровне инфраструктуры (CDN, anti-DDoS-прокси). Rate limiting в API-сервисе решает другие задачи: справедливое распределение ресурсов между клиентами, защита от лавины ретраев, контроль над расходом квот к платным внешним API, простой fairness между пользователями одного тенанта.
За двенадцать лет я ставил rate limiting в трёх вариантах: token bucket, leaky bucket и sliding window. Они дают разный профиль ограничений — и выбор не «что лучше», а «что подходит вашей задаче». Разберу алгоритмы, реализации и подводные камни.
Что вы хотите ограничивать
Перед выбором алгоритма стоит ответить на вопрос: что значит «ограничить» в вашем случае.
- Average rate. «Не больше 100 запросов в минуту в среднем». Допускает всплески сверх 100 RPM, если они компенсируются спокойными периодами.
- Burst capacity. «Можно делать до 10 запросов сразу, но потом восстанавливаемся».
- Strict throughput. «Ровно 10 запросов в секунду, никаких всплесков».
Это разные требования, и они реализуются разными алгоритмами.
Token bucket
Самый популярный алгоритм. Каждому клиенту выделяется «ведро» с токенами. Токены добавляются с заданной скоростью (например, 10 токенов в секунду). Каждый запрос забирает один токен. Нет токена — отказ.
Ведро имеет максимальный размер (capacity). Это и есть burst capacity: если клиент долго не делал запросов, ведро заполнено, и он может сразу сделать N запросов подряд.
class TokenBucket(
private val capacity: Long,
private val refillRate: Long, // tokens per second
private val clock: Clock = Clock.systemUTC()
) {
private var tokens: Long = capacity
private var lastRefill: Long = clock.millis()
@Synchronized
fun tryAcquire(n: Long = 1): Boolean {
refill()
if (tokens >= n) {
tokens -= n
return true
}
return false
}
private fun refill() {
val now = clock.millis()
val elapsed = (now - lastRefill).coerceAtLeast(0)
val newTokens = elapsed * refillRate / 1000
if (newTokens > 0) {
tokens = (tokens + newTokens).coerceAtMost(capacity)
lastRefill = now
}
}
}Простая идея, гибкая. Capacity и refillRate настраиваются независимо: «10 RPS со всплесками до 50» — это refillRate=10, capacity=50.
Подходит когда: всплески допустимы, главное — средняя нагрузка. AWS, Stripe, GitHub — все используют token bucket в своих API.
Leaky bucket
Альтернативная метафора. Запросы попадают в «ведро». «Ведро» вытекает с фиксированной скоростью (leak rate). Если запросы попадают быстрее, чем ведро вытекает, ведро переполняется — отказ.
Часто реализуется как FIFO-очередь:
class LeakyBucket(
private val capacity: Int,
private val leakIntervalMs: Long
) {
private val queue = ArrayDeque<Long>()
@Synchronized
fun tryAcquire(): Boolean {
val now = System.currentTimeMillis()
// выбрасываем старые
while (queue.isNotEmpty() && queue.first() < now - capacity * leakIntervalMs) {
queue.removeFirst()
}
if (queue.size < capacity) {
queue.addLast(now)
return true
}
return false
}
}Главное отличие: leaky bucket выдаёт запросы с равномерной скоростью. Token bucket позволяет всплеск 50 запросов в одну секунду, leaky bucket будет выдавать их по одному за заданный интервал.
Подходит когда: нужна равномерная нагрузка на downstream-сервис, всплески противопоказаны. Например, если вы вызываете внешний API с лимитом 10 RPS, и провайдер сказал «не делайте больше», leaky bucket гарантирует ровно 10 RPS даже при всплеске входящих запросов.
Fixed window
Простейший алгоритм: считаем запросы в интервале времени (например, минута). Превысили — отказ. Новый интервал — счётчик сбрасывается.
class FixedWindow(private val limit: Int, private val windowSizeMs: Long) {
private var windowStart: Long = 0
private var count: Int = 0
@Synchronized
fun tryAcquire(): Boolean {
val now = System.currentTimeMillis()
if (now - windowStart >= windowSizeMs) {
windowStart = now
count = 0
}
if (count < limit) {
count++
return true
}
return false
}
}Простой, но имеет неприятный эффект: на границе окон может произойти двойной всплеск. Лимит 100 в минуту, клиент сделал 100 в последнюю секунду одной минуты и ещё 100 в первую секунду следующей. Технически в каждом окне он не превысил, но за 2 секунды сделал 200.
Подходит когда: ограничения «по часу», «по дню» — где двойной всплеск на границе минуты не критичен. Не подходит для жёсткой защиты от пика.
Sliding window
Решает проблему fixed window. Считаем запросы в скользящем окне последних N секунд.
Реальная реализация чаще приближённая: храним счётчики по минутам и считаем взвешенную сумму. Это компромисс между точностью и расходом памяти.
class SlidingWindow(private val limit: Int, private val windowSizeMs: Long) {
private val timestamps = ArrayDeque<Long>()
@Synchronized
fun tryAcquire(): Boolean {
val now = System.currentTimeMillis()
val cutoff = now - windowSizeMs
while (timestamps.isNotEmpty() && timestamps.first() < cutoff) {
timestamps.removeFirst()
}
if (timestamps.size < limit) {
timestamps.addLast(now)
return true
}
return false
}
}Точно, но дороже по памяти: храним каждый timestamp.
На больших объёмах используют counter-based sliding window: храним счётчики по слайсам времени и складываем взвешенно. Меньше памяти, чуть менее точно.
Подходит когда: нужна гладкая картина без эффекта границ fixed window, и точность важна.
Где выполнять rate limiting
Технически можно ставить на разных уровнях.
В коде сервиса
Простой in-memory rate limiter в каждом инстансе. Подходит, если у вас один инстанс или вы готовы к тому, что лимит будет per-instance.
Минус — при горизонтальном масштабировании клиент с лимитом 100 RPS может на самом деле получить 100×N RPS, где N — количество инстансов. Не годится для глобальных лимитов.
В API gateway
Kong, Tyk, NGINX, Spring Cloud Gateway — у всех есть встроенный rate limiting с разными алгоритмами. Это самый частый вариант.
Лимиты применяются глобально (gateway знает обо всех инстансах сервиса). Конфигурация декларативная, не размазывается по коду.
Distributed rate limiter
Когда несколько инстансов сервиса должны разделять один глобальный лимит, нужно общее хранилище. Чаще всего Redis с Lua-скриптом или специализированный сервис (например, Envoy ratelimit).
-- token-bucket.lua: атомарная операция в Redis
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local data = redis.call('HMGET', key, 'tokens', 'last_refill')
local tokens = tonumber(data[1]) or capacity
local last_refill = tonumber(data[2]) or now
local elapsed = math.max(0, now - last_refill)
tokens = math.min(capacity, tokens + elapsed * refill_rate / 1000)
if tokens >= 1 then
tokens = tokens - 1
redis.call('HMSET', key, 'tokens', tokens, 'last_refill', now)
redis.call('EXPIRE', key, 60)
return 1
else
redis.call('HMSET', key, 'tokens', tokens, 'last_refill', now)
redis.call('EXPIRE', key, 60)
return 0
endLua-скрипт делает refill и acquire атомарно. Без атомарности два инстанса могут одновременно прочитать «у нас 1 токен», оба потратить — счёт уйдёт в минус.
Ключи и гранулярность
По чему лимитировать — отдельный вопрос.
По IP. Базовая защита от примитивного абьюза. Минус — клиенты за NAT (мобильные операторы, корпоративные сети) разделяют один IP. Один абьюзер ломает доступ многим.
По API-ключу. Для API с регистрацией клиентов. Каждый клиент имеет свой лимит, не зависит от IP.
По user_id. Внутри приложения с пользователями. Каждый юзер имеет свою квоту, независимо от устройства/IP.
По endpoint + user_id. Разные ручки имеют разные лимиты для одного юзера. POST /payments — 10 в минуту, GET /products — 1000.
Per-tenant. В мульти-тенантной системе — лимит на тенанта, не на пользователя. Защищает от того, что один тенант съест ресурсы за всех.
В реальной системе обычно несколько уровней одновременно: per-IP для базовой защиты, per-user для бизнес-лимитов, per-tenant для fairness.
Что отвечать клиенту
Стандартный HTTP 429 Too Many Requests с заголовками:
HTTP/1.1 429 Too Many Requests
Retry-After: 30
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1710501330
Content-Type: application/json
{"error": "rate_limit_exceeded", "retry_after": 30}Retry-After — обязательно. Без него клиент не знает, через сколько повторять, и обычно ретраит сразу. Это превращает rate limiting в «retry storm генератор».
X-RateLimit-* — необязательно, но полезно. Клиент видит свою текущую квоту и может управлять нагрузкой proactively.
Подводные камни
Несколько вещей, которые я ловил.
Rate limiter без atomicity. Два инстанса параллельно делают check-and-decrement в Redis без транзакции. Лимит легко превышается. Атомарность через Lua или MULTI/EXEC обязательна.
Rate limiting на хелсчеки. Внутренние хелсчеки идут от monitoring-системы и попадают под лимит. После всплеска нагрузки monitoring видит «сервис не отвечает», хотя он просто отказывает по rate limit.
Лимиты per-instance под балансером. Каждый инстанс имеет свой лимит 100 RPS, балансер раскидывает запросы. Реальный лимит — N×100. При autoscaling этот «лимит» становится бессмысленным.
Игнорирование клиентом Retry-After. Сервер возвращает 429 с Retry-After=30, клиент сразу повторяет. Решение — убедить команду клиента уважать заголовок, либо ставить более жёсткие меры (временный бан IP).
Cache header'ы. CDN или прокси кеширует 429-ответ, отдаёт его клиентам, которые на самом деле не превысили лимит. Cache-Control: no-store на 429 обязателен.
Drift времени. Distributed rate limiter с разными часами на нодах работает плохо. NTP-синхронизация обязательна, или используйте часы Redis (TIME команда).
Что запомнить
Token bucket — дефолт для большинства сценариев: гибкий, поддерживает burst, прост в реализации. Leaky bucket — когда нужна равномерная нагрузка на downstream. Sliding window — когда важна точность без эффекта границ.
Уровень: API gateway для большинства, distributed rate limiter в Redis — когда нужны глобальные лимиты на нескольких инстансах. In-memory только для одиночных деплоев.
Гранулярность — по контексту: IP, API key, user, tenant. Часто — несколько уровней одновременно.
Главное — не «забыть про Retry-After», помнить про атомарность в distributed-режиме и тестировать сценарий «превысил лимит» в нагрузочном профиле. Rate limiting без тестов под нагрузкой работает на 80% — оставшиеся 20% обнаруживаются на проде в самый неудобный момент.