Rate limiting: fixed window, token bucket и sliding window
Блокировка из прошлого урока отвечает на вопрос «кто сейчас работает». Rate limiting отвечает на другой: «сколько раз за интервал можно». Механика похожая - атомарные операции в Redis, - а вот ошибки другие, и цена ошибки выше: неверно посчитанный лимит либо пропускает вдвое больше запросов, либо блокирует живых пользователей.
Разберём три алгоритма по возрастанию точности и стоимости.
Rate limiting: подходы
Fixed Window
// Номер окна в самом ключе, поэтому старые ключи не мешают: они просто
// перестают использоваться и умирают по TTL.
key := fmt.Sprintf("ratelimit:%s:%d", userID, time.Now().Unix()/60)
count, err := rdb.Incr(ctx, key).Result()
if err != nil {
// Политика при недоступности Redis - решение, а не деталь: см. ниже.
return fmt.Errorf("rate limit check: %w", err)
}
if count == 1 {
// TTL ставится один раз, при создании ключа окна. Вызывать EXPIRE
// на каждом запросе смысла нет: ключ уже живёт ровно до конца окна.
if err := rdb.Expire(ctx, key, time.Minute).Err(); err != nil {
return fmt.Errorf("set window ttl: %w", err)
}
}
if count > 60 { /* 429 Too Many Requests */ }
<?php
declare(strict_types=1);
$window = (int) floor(time() / 60);
$key = sprintf('ratelimit:%s:%d', $userId, $window);
$count = $redis->incr($key);
if ($count === 1) {
$redis->expire($key, 60);
}
if ($count > 60) {
throw new TooManyRequestsException();
}
import time
from datetime import timedelta
import redis
class RateLimitUnavailable(Exception):
pass
# Номер окна в самом ключе, поэтому старые ключи не мешают: они просто
# перестают использоваться и умирают по TTL.
key = f"ratelimit:{user_id}:{int(time.time()) // 60}"
try:
count = rdb.incr(key)
if count == 1:
# TTL ставится один раз, при создании ключа окна. Вызывать EXPIRE
# на каждом запросе смысла нет: ключ уже живёт ровно до конца окна.
rdb.expire(key, timedelta(minutes=1))
except redis.RedisError as e:
# Политика при недоступности Redis - решение, а не деталь: см. ниже.
raise RateLimitUnavailable("rate limit check") from e
if count > 60:
... # 429 Too Many Requests
Простой: счётчик в окне (минута). Проблема: на границе окон можно получить 2x лимит (последние 30 секунд предыдущего + первые 30 нового).
⚠️ Что делать, когда Redis недоступен - выбор, а не мелочь
В первой версии этого урока здесь стояло
count, _ := rdb.Incr(...).Result(). Ошибка проглатывалась,countоставался нулём, условиеcount > 60не срабатывало - то есть при падении Redis лимитер молча пропускал весь трафик. Это работающая политика (fail-open), но она была выбрана не решением, а знаком подчёркивания.Политики две, и обе законные:
Политика Поведение при сбое Redis Когда уместна fail-openпропускать запросы лимитер защищает от случайных всплесков, доступность сервиса важнее fail-closedотвечать 503 лимит защищает дорогой ресурс (SMS, платёжный шлюз, внешний API с квотой) Проглатывать ошибку нельзя ни при какой из них:
fail-openбез лога - это отключённая защита, о которой никто не узнает. Здесь ошибка возвращается вызывающему, и политику выбирает он - осознанно и в одном месте.
Обе реализации ставят TTL один раз, при создании ключа окна. Раньше
Go-версия вызывала EXPIRE на каждом запросе, а PHP - только после первого
INCR; на поведение это не влияло (номер окна в ключе), но лишний сетевой
вызов на каждый запрос был, и два языка в одном уроке учили разному.
Sliding Window через Sorted Set
// slidingWindowScript - проверка и запись одним атомарным шагом.
//
// KEYS[1] - sorted set окна, KEYS[2] - счётчик для уникальных member.
// Оба ключа в одном хеш-теге, чтобы жить в одном слоте Redis Cluster.
// ARGV[1] - размер окна в миллисекундах, ARGV[2] - лимит.
var slidingWindowScript = redis.NewScript(`
local now_pair = redis.call('TIME')
local now = now_pair[1] * 1000 + math.floor(now_pair[2] / 1000)
local window = tonumber(ARGV[1])
local limit = tonumber(ARGV[2])
redis.call('ZREMRANGEBYSCORE', KEYS[1], 0, now - window)
-- Лимит проверяется ДО записи. Иначе отклонённые запросы тоже попадали бы
-- в окно и продлевали блокировку: клиент, который долбит в закрытую дверь,
-- никогда бы не дождался разблокировки.
if redis.call('ZCARD', KEYS[1]) >= limit then
return 0
end
-- Уникальный member. Только timestamp не годится: два запроса в одну
-- миллисекунду дали бы одинаковый member, и ZADD посчитал бы их за один.
local seq = redis.call('INCR', KEYS[2])
redis.call('ZADD', KEYS[1], now, now .. '-' .. seq)
redis.call('PEXPIRE', KEYS[1], window)
redis.call('PEXPIRE', KEYS[2], window)
return 1
`)
func IsAllowed(ctx context.Context, rdb *redis.Client, key string, limit int, window time.Duration) (bool, error) {
keys := []string{"rl:{" + key + "}:z", "rl:{" + key + "}:seq"}
allowed, err := slidingWindowScript.Run(ctx, rdb, keys,
window.Milliseconds(), limit).Int()
if err != nil {
// Ошибку возвращаем, а не проглатываем: политику при недоступности
// Redis выбирает вызывающий - см. раздел ниже.
return false, err
}
return allowed == 1, nil
}
<?php
declare(strict_types=1);
final readonly class SlidingWindowRateLimiter
{
public function __construct(
private Predis\Client $redis,
private int $limit,
private int $windowSeconds,
) {}
public function isAllowed(string $key): bool
{
$windowMs = $this->windowSeconds * 1000;
// Тот же скрипт, что в Go-версии: проверка и запись атомарны,
// время берётся из Redis, member уникален.
$script = <<<'LUA'
local now_pair = redis.call('TIME')
local now = now_pair[1] * 1000 + math.floor(now_pair[2] / 1000)
local window = tonumber(ARGV[1])
local limit = tonumber(ARGV[2])
redis.call('ZREMRANGEBYSCORE', KEYS[1], 0, now - window)
if redis.call('ZCARD', KEYS[1]) >= limit then
return 0
end
local seq = redis.call('INCR', KEYS[2])
redis.call('ZADD', KEYS[1], now, now .. '-' .. seq)
redis.call('PEXPIRE', KEYS[1], window)
redis.call('PEXPIRE', KEYS[2], window)
return 1
LUA;
$allowed = (int) $this->redis->eval(
$script, 2,
sprintf('rl:{%s}:z', $key), sprintf('rl:{%s}:seq', $key),
(string) $windowMs, (string) $this->limit,
);
return $allowed === 1;
}
}
from datetime import timedelta
import redis
# SLIDING_WINDOW_SCRIPT - проверка и запись одним атомарным шагом.
#
# KEYS[1] - sorted set окна, KEYS[2] - счётчик для уникальных member.
# Оба ключа в одном хеш-теге, чтобы жить в одном слоте Redis Cluster.
# ARGV[1] - размер окна в миллисекундах, ARGV[2] - лимит.
SLIDING_WINDOW_SCRIPT = """
local now_pair = redis.call('TIME')
local now = now_pair[1] * 1000 + math.floor(now_pair[2] / 1000)
local window = tonumber(ARGV[1])
local limit = tonumber(ARGV[2])
redis.call('ZREMRANGEBYSCORE', KEYS[1], 0, now - window)
-- Лимит проверяется ДО записи. Иначе отклонённые запросы тоже попадали бы
-- в окно и продлевали блокировку: клиент, который долбит в закрытую дверь,
-- никогда бы не дождался разблокировки.
if redis.call('ZCARD', KEYS[1]) >= limit then
return 0
end
-- Уникальный member. Только timestamp не годится: два запроса в одну
-- миллисекунду дали бы одинаковый member, и ZADD посчитал бы их за один.
local seq = redis.call('INCR', KEYS[2])
redis.call('ZADD', KEYS[1], now, now .. '-' .. seq)
redis.call('PEXPIRE', KEYS[1], window)
redis.call('PEXPIRE', KEYS[2], window)
return 1
"""
class SlidingWindowRateLimiter:
def __init__(self, rdb: redis.Redis) -> None:
# register_script: SCRIPT LOAD один раз, дальше EVALSHA
self._script = rdb.register_script(SLIDING_WINDOW_SCRIPT)
def is_allowed(self, key: str, limit: int, window: timedelta) -> bool:
keys = [f"rl:{{{key}}}:z", f"rl:{{{key}}}:seq"]
# Ошибки Redis (ConnectionError, TimeoutError) здесь не ловим:
# политику при недоступности Redis выбирает вызывающий - см. раздел ниже.
allowed = self._script(keys=keys, args=[int(window.total_seconds() * 1000), limit])
return allowed == 1
В продакшене - symfony/rate-limiter с sliding_window policy и RedisStorage: даёт тот же sliding window + готовые X-RateLimit-* headers и обёртки для HTTP-firewall:
# config/packages/rate_limiter.yaml
framework:
rate_limiter:
api:
policy: 'sliding_window'
limit: 60
interval: '1 minute'
storage_service: 'limiter.storage.redis'
Точное окно: «не более N запросов за последние M секунд». Дороже по памяти (хранит timestamp каждого запроса), но даёт ровный rate без burst на границах.
Скрипт выполняется как одна операция, и это здесь не оптимизация, а условие корректности.
⚠️ Pipeline не даёт атомарности - и первая версия этого урока на этом ошибалась
Раньше здесь стояли те же четыре команды через
Pipeline, и объяснялись они экономией сетевых round-trip-ов. Экономия настоящая, но алгоритм при этом неверен: pipeline лишь склеивает отправку, он не мешает другому клиенту выполнить свои команды между нашими.Как это ломается: два запроса при лимите 10 и девяти записях в окне. Оба делают
ZADD, оба потом видятZCARD= 11 - или оба видят 10, если ихZCARDуспел пройти до чужогоZADD. Во втором случае лимит превышен, и никакая проверка возвращённого значения этого не исправит: решение принималось по состоянию, которое к моменту записи уже изменилось. Это классический check-then-act, и лечится он не проверкой, а тем, что проверка и запись становятся одной операцией.Второй дефект той версии - member из одного timestamp:
Member: fmt.Sprintf("%d", now). Sorted set хранит уникальные member, поэтому два запроса в одну миллисекунду давали один и тот же member, и второйZADDне добавлял элемент, а перезаписывал score существующего. Окно недосчитывало запросы ровно в тот момент, когда их больше всего. Здесь member -now-seq, гдеseqинкрементируется в том же скрипте.Третья деталь, которую видно только в атомарной версии: лимит проверяется до записи. В pipeline-версии запись шла всегда, и отклонённые запросы тоже попадали в окно - клиент, продолжающий стучаться, сам себе продлевал блокировку бесконечно.
Pipeline и
MULTI/EXECразобраны в уроке про go-redis, Lua-скрипты - ниже в этом уроке (раздел «Lua scripts»). Для алгоритмов вида «прочитать, решить, записать» годится только Lua: pipeline не атомарен, а внутриMULTI/EXECнельзя принять решение по результату чтения.
Время берётся из redis.call('TIME'), то есть по часам самого Redis.
Если передавать now из приложения, окно поедет на столько, на сколько
разошлись часы инстансов: при десяти воркерах с рассинхроном в секунду
лимит «100 в минуту» превращается в «100 в интервале, границы которого
каждый считает по-своему». Одни часы вместо N - это ещё и причина, по которой
TIME внутри скрипта предпочтительнее ARGV.
Token Bucket
Bucket с ёмкостью N токенов, пополняется с rate R/sec. Каждый запрос забирает токен. Burst разрешён до ёмкости bucket.
-- Lua script для атомарного refill+consume
local key = KEYS[1]
local rate = tonumber(ARGV[1])
local capacity = tonumber(ARGV[2])
-- Время - по часам Redis, а не из приложения: см. врезку под скриптом.
local now_pair = redis.call('TIME')
local now = now_pair[1] * 1000 + math.floor(now_pair[2] / 1000)
local requested = tonumber(ARGV[3])
local data = redis.call("HMGET", key, "tokens", "ts")
local tokens = tonumber(data[1]) or capacity
local ts = tonumber(data[2]) or now
local elapsed = (now - ts) / 1000.0
tokens = math.min(capacity, tokens + elapsed * rate)
if tokens < requested then
return 0
end
tokens = tokens - requested
redis.call("HMSET", key, "tokens", tokens, "ts", now)
redis.call("EXPIRE", key, math.ceil(capacity / rate))
return 1
⚠️ Чьи часы считают refill
В первой версии скрипт получал
nowиз приложения (ARGV[3]), и это тихое допущение: у всех инстансов приложения одинаковое время. На одной машине так и есть, на десяти - нет.Что происходит при расхождении: инстанс с часами, убежавшими вперёд, считает
elapsedбольше реального и доливает лишние токены; инстанс с отстающими часами записываетtsв прошлое, и следующий запрос доливает ещё раз за тот же интервал. Лимит начинает зависеть от того, на какой машине оказался запрос - и воспроизвести это в тестах почти невозможно, потому что локально часы одни.
redis.call('TIME')убирает допущение: часы одни на всех, потому что это часы Redis. Цена - командаTIMEнедетерминирована, поэтому скрипт нельзя реплицировать построчно. Redis 5.0+ по умолчанию реплицирует эффекты скрипта, а не сам скрипт (в Redis 7 другого режима уже нет), так что на поддерживаемых версиях это работает без оговорок. В Redis 3.2-4.x нужно было явно вызватьredis.replicate_commands().Если время всё же приходит из приложения (например, вы вызываете
EVALиз библиотеки, которая так устроена), допущение надо назвать в коде - и синхронизировать часы через NTP, помня, что NTP уменьшает расхождение, а не устраняет его.
Token bucket любим за burst-friendliness: позволяет быстрые всплески активности при долгосрочном среднем под лимитом.
<?php
declare(strict_types=1);
final readonly class TokenBucketLimiter
{
public function __construct(
private Predis\Client $redis,
private float $rate, // токенов/сек
private int $capacity, // макс. ёмкость bucket
) {}
public function consume(string $key, int $requested = 1): bool
{
$script = <<<'LUA'
local key = KEYS[1]
local rate = tonumber(ARGV[1])
local capacity = tonumber(ARGV[2])
local now_pair = redis.call('TIME')
local now = now_pair[1] * 1000 + math.floor(now_pair[2] / 1000)
local requested = tonumber(ARGV[3])
local data = redis.call("HMGET", key, "tokens", "ts")
local tokens = tonumber(data[1]) or capacity
local ts = tonumber(data[2]) or now
local elapsed = (now - ts) / 1000.0
tokens = math.min(capacity, tokens + elapsed * rate)
if tokens < requested then
return 0
end
tokens = tokens - requested
redis.call("HMSET", key, "tokens", tokens, "ts", now)
redis.call("EXPIRE", key, math.ceil(capacity / rate))
return 1
LUA;
// now не передаётся: скрипт берёт время из Redis.
$result = (int) $this->redis->eval(
$script, 1, $key,
(string) $this->rate, (string) $this->capacity, (string) $requested,
);
return $result === 1;
}
}
В Symfony готовый token bucket - symfony/rate-limiter с policy: token_bucket. Симметрично sliding window, только в YAML меняется один параметр.
Lua scripts: атомарность нескольких команд
Lua-скрипт в Redis выполняется атомарно - никаких других команд между его шагами. Используется когда:
- Нужна condition + action атомарно (compare-and-swap)
- Нужно много операций без сетевых RTT
- Нужна транзакция со сложной логикой
script := redis.NewScript(`
local current = redis.call("GET", KEYS[1])
if current == ARGV[1] then
return redis.call("SET", KEYS[1], ARGV[2])
end
return nil
`)
// CAS: установить новое значение только если текущее = expected
result, err := script.Run(ctx, rdb, []string{"key"}, expected, newValue).Result()
<?php
declare(strict_types=1);
$script = <<<'LUA'
local current = redis.call("GET", KEYS[1])
if current == ARGV[1] then
return redis.call("SET", KEYS[1], ARGV[2])
end
return nil
LUA;
// CAS: установить новое значение только если текущее = expected
// В predis: eval($script, numKeys, ...keysAndArgs)
$result = $redis->eval($script, 1, 'key', $expected, $newValue);
script = rdb.register_script("""
local current = redis.call("GET", KEYS[1])
if current == ARGV[1] then
return redis.call("SET", KEYS[1], ARGV[2])
end
return nil
""")
# CAS: установить новое значение только если текущее = expected
result = script(keys=["key"], args=[expected, new_value])
register_script возвращает вызываемый объект - аналог redis.NewScript в go-redis: при первом вызове SCRIPT LOAD, дальше EVALSHA, а на NOSCRIPT после рестарта Redis он сам откатывается на EVAL. Для разового вызова есть и прямой rdb.eval(script, 1, "key", expected, new_value).
В phpredis эквивалент - $redis->eval($script, ['key', $expected, $newValue], 1) (в одном массиве сначала ключи, затем аргументы; последний параметр - число ключей). Для повторного запуска скрипта можно использовать evalsha() после script load - Redis закеширует bytecode по SHA1.
Возврат limits клиенту
REST best practice - заголовки X-RateLimit-*:
w.Header().Set("X-RateLimit-Limit", "60")
w.Header().Set("X-RateLimit-Remaining", "47")
w.Header().Set("X-RateLimit-Reset", strconv.FormatInt(resetTime, 10))
if !allowed {
w.Header().Set("Retry-After", "30")
http.Error(w, "rate limit exceeded", http.StatusTooManyRequests)
}
<?php
declare(strict_types=1);
use Symfony\Component\HttpFoundation\Request;
use Symfony\Component\HttpFoundation\Response;
use Symfony\Component\RateLimiter\RateLimiterFactory;
final readonly class RateLimitController
{
public function __construct(private RateLimiterFactory $apiLimiter) {}
public function __invoke(Request $request): Response
{
$limit = $this->apiLimiter->create($request->getClientIp())->consume(1);
$headers = [
'X-RateLimit-Limit' => (string) $limit->getLimit(),
'X-RateLimit-Remaining' => (string) $limit->getRemainingTokens(),
'X-RateLimit-Reset' => (string) $limit->getRetryAfter()->getTimestamp(),
];
if (!$limit->isAccepted()) {
// Retry-After по RFC 9110 - число секунд задержки (или HTTP-дата), не unix timestamp
$headers['Retry-After'] = (string) max(0, $limit->getRetryAfter()->getTimestamp() - time());
return new Response('rate limit exceeded', Response::HTTP_TOO_MANY_REQUESTS, $headers);
}
return new Response('ok', Response::HTTP_OK, $headers);
}
}
from http import HTTPStatus
# WSGI-приложение без фреймворка; в FastAPI это Response(headers=...),
# в Django - HttpResponse с response["X-RateLimit-Limit"] = "60"
def app(environ, start_response):
headers = [
("X-RateLimit-Limit", "60"),
("X-RateLimit-Remaining", "47"),
("X-RateLimit-Reset", str(reset_time)),
]
if not allowed:
headers.append(("Retry-After", "30"))
status = HTTPStatus.TOO_MANY_REQUESTS
start_response(f"{status.value} {status.phrase}", headers)
return [b"rate limit exceeded"]
status = HTTPStatus.OK
start_response(f"{status.value} {status.phrase}", headers)
return [b"ok"]
Готовые X-RateLimit-* заголовки отдают slowapi (FastAPI/Starlette) и django-ratelimit; оба умеют Redis-хранилище. Как и в Symfony, руками их считать не стоит - только понимать, что внутри.
symfony/rate-limiter отдаёт RateLimit объект - оттуда уже готовые getLimit(), getRemainingTokens(), getRetryAfter(). Не считай заголовки руками.
Это позволяет клиенту корректно бэкоффиться и не плодить retry-storm.
Типичные ошибки
- Rate limit per-IP без X-Forwarded-For - за CDN/прокси все запросы идут с одного IP балансера, лимит срабатывает на всех пользователей. Бери
X-Forwarded-For/CF-Connecting-IP(с валидацией доверенного прокси), неRemoteAddr. - Любой лимитер, где решение и запись - разные команды - между ними race: два запроса увидят одинаковый бюджет и оба пройдут. Это касается и token bucket из
GET/DECR/EXPIRE, и sliding window из четырёх команд в pipeline (pipeline не атомарен - см. врезку выше). Проверка и запись должны быть одной операцией: Lua-скрипт либо, для простого счётчика,INCRс проверкой возвращённого значения - он атомарен сам по себе. - Проглоченная ошибка Redis -
count, _ := rdb.Incr(...)превращает падение Redis в бесшумное отключение лимитера. Выбериfail-openилиfail-closedявно и залогируй сбой. nowиз приложения в Lua-скрипте - при нескольких инстансах refill считается по разным часам. Бериredis.call('TIME').- Только timestamp как member sorted set - два запроса в одну миллисекунду дают один member, и окно недосчитывает запросы. Добавляй счётчик или другой уникальный суффикс.
Retry-Afterзабыт в 429-ответе - клиенты не знают, когда повторять, отвечают через 100ms и наматывают retry-storm. Всегда возвращайRetry-After: <seconds>+X-RateLimit-Reset: <unix>.
Мини-практика
Реализуй HTTP middleware для rate limiting: 60 запросов в минуту на IP через
sliding window. Возвращай X-RateLimit-Remaining и Retry-After. Покрой
тестами с симуляцией параллельных запросов - без атомарности через Lua тест
на конкурентность должен падать, это и есть смысл упражнения.