Rate limiting: fixed window, token bucket и sliding window

Что происходит при расхождении: инстанс с часами, убежавшими вперёд, считает elapsed больше реального и доливает лишние токены; инстанс с отстающими часами записывает ts в прошлое, и следующий запрос доливает ещё раз за тот же интервал. Лимит начинает зависеть от того, на какой машине оказался запрос - и воспроизвести это в тестах почти невозможно, потому что локально часы одни.

redis.call('TIME') убирает допущение: часы одни на всех, потому что это часы Redis. Цена - команда TIME недетерминирована, поэтому скрипт нельзя реплицировать построчно; Redis 3.2+ по умолчанию репликует эффекты скрипта, а не сам скрипт, так что на поддерживаемых версиях это работает без оговорок.

Если время всё же приходит из приложения (например, вы вызываете 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);

В phpredis эквивалент - $redis->eval($script, [$expected, $newValue, 'key'], 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\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()) {
            $headers['Retry-After'] = (string) $limit->getRetryAfter()->getTimestamp();

            return new Response('rate limit exceeded', Response::HTTP_TOO_MANY_REQUESTS, $headers);
        }

        return new Response('ok', Response::HTTP_OK, $headers);
    }
}

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 тест на конкурентность должен падать, это и есть смысл упражнения.