HardПрактика17 min

Rate limiter: реализации

5 алгоритмов: token bucket, leaky bucket, fixed window, sliding window log, sliding window counter. Redis Lua для атомарности

SysdesignDesign patterns

Зачем нужен

Ограничение частоты запросов защищает от:

  • Abuse / DDoS атак
  • Bug в клиенте (retry-шторм)
  • Перегрузки ограниченных ресурсов (БД, внешние API)
  • Нарушения квот тарифных планов

Overview rate limiter как case study есть в 03.case-studies/3.rate-limiter.md. Здесь -- детальная реализация 5 алгоритмов с кодом и трейдоффами.

Обзор алгоритмов

Алгоритм Burst Smooth Memory Точность
Fixed window ❌ (2x на границе) ❌ O(1) Низкая
Sliding window log ✅ ✅ O(N) Идеальная
Sliding window counter ✅ ✅ O(1) Средняя
Token bucket ✅ ✅ O(1) Хорошая
Leaky bucket ❌ ✅ (queue) O(N) Идеальная (shaping)

Схема limit = 10 req/sec

Каждый пример ниже использует: userID = U123, лимит 10 rps.

1. Fixed Window

Разбиваем время на окна фиксированной длины (1 сек), считаем запросы в каждом.

Time: 0.0 --------- 1.0 --------- 2.0
     |<- window 0 ->|<- window 1 ->|
     counter=7       counter=0

Плюсы

  • Память O(1): один счётчик на ключ
  • Простейшая реализация
  • Атомарный INCR в Redis

Минусы

  • Граничный эффект: 10 запросов в 0.99 сек + 10 в 1.01 сек = 20 запросов за ~20 мс. Реальный burst в 2x.
  • Неравномерное распределение

Реализация

<?php

declare(strict_types=1);

namespace App\RateLimit;

final readonly class FixedWindow
{
    public function __construct(
        private \Redis $redis,
        private int $limit,
        private int $windowSec = 1,
    ) {}

    public function allow(string $userId): bool
    {
        $window = (int) (time() / $this->windowSec);
        $key = "rl:fw:$userId:$window";

        $count = $this->redis->incr($key);

        if ($count === 1) {
            // Set TTL only on first increment (2x window to be safe)
            $this->redis->expire($key, $this->windowSec * 2);
        }

        return $count <= $this->limit;
    }
}
## 2. Sliding Window Log

Храним timestamps всех запросов, на каждый новый -- считаем сколько попало в окно [now - window, now].

Requests: [t1, t2, t3, t4, t5, t6]
Now: t6. Window: [t6-1.0, t6]
Count in window: 4 (t3..t6)

Плюсы

  • Идеально точный -- считает реальное число запросов в любом скользящем окне
  • Без граничных эффектов

Минусы

  • O(N) память -- timestamp каждого запроса
  • При высокой нагрузке ключ раздувается

Реализация

<?php

declare(strict_types=1);

namespace App\RateLimit;

final readonly class SlidingWindowLog
{
    public function __construct(
        private \Redis $redis,
        private int $limit,
        private int $windowMs = 1000,
    ) {}

    /**
     * Lua script ensures atomic check-and-insert under contention.
     */
    public function allow(string $userId): bool
    {
        $key = "rl:swl:$userId";
        $nowMs = (int) (microtime(true) * 1000);
        $cutoff = $nowMs - $this->windowMs;

        $lua = <<<'LUA'
            local key = KEYS[1]
            local now = tonumber(ARGV[1])
            local cutoff = tonumber(ARGV[2])
            local limit = tonumber(ARGV[3])
            local ttl = tonumber(ARGV[4])

            -- Remove entries older than cutoff
            redis.call('ZREMRANGEBYSCORE', key, 0, cutoff)

            local count = redis.call('ZCARD', key)
            if count >= limit then
                return 0
            end

            -- Use now as both score and member (member must be unique)
            redis.call('ZADD', key, now, now .. ':' .. math.random(1000000))
            redis.call('PEXPIRE', key, ttl)
            return 1
        LUA;

        $allowed = $this->redis->eval(
            $lua,
            [$key, $nowMs, $cutoff, $this->limit, $this->windowMs * 2],
            1,
        );

        return (bool) $allowed;
    }
}
## 3. Sliding Window Counter

Компромисс: fixed window + взвешенная доля предыдущего окна.

count = curr_window_count + prev_window_count * (1 - elapsed_in_curr / window_size)

Example: window=1s, current=300ms in, prev=8, curr=3
  count = 3 + 8 * (1 - 0.3) = 3 + 5.6 = 8.6

Плюсы

  • O(1) память
  • Сглаживает граничный эффект fixed window
  • Приемлемая точность (~0.003% ошибки на реальных нагрузках)

Минусы

  • Не идеально точный
  • Предполагает равномерное распределение в предыдущем окне

Реализация

<?php

declare(strict_types=1);

namespace App\RateLimit;

final readonly class SlidingWindowCounter
{
    public function __construct(
        private \Redis $redis,
        private int $limit,
        private int $windowMs = 1000,
    ) {}

    public function allow(string $userId): bool
    {
        $nowMs = (int) (microtime(true) * 1000);
        $curr = intdiv($nowMs, $this->windowMs);
        $prev = $curr - 1;
        $elapsedInCurr = $nowMs % $this->windowMs;
        $prevWeight = 1 - ($elapsedInCurr / $this->windowMs);

        $lua = <<<'LUA'
            local currKey = KEYS[1]
            local prevKey = KEYS[2]
            local limit = tonumber(ARGV[1])
            local weight = tonumber(ARGV[2])
            local ttl = tonumber(ARGV[3])

            local currCount = tonumber(redis.call('GET', currKey)) or 0
            local prevCount = tonumber(redis.call('GET', prevKey)) or 0
            local estimated = currCount + prevCount * weight

            if estimated >= limit then
                return 0
            end

            redis.call('INCR', currKey)
            redis.call('PEXPIRE', currKey, ttl)
            return 1
        LUA;

        $res = $this->redis->eval(
            $lua,
            [
                "rl:swc:$userId:$curr",
                "rl:swc:$userId:$prev",
                $this->limit,
                $prevWeight,
                $this->windowMs * 2,
            ],
            2,
        );

        return (bool) $res;
    }
}
## 4. Token Bucket

В бакете лежат токены. Каждый запрос забирает 1 токен. Токены пополняются с постоянной скоростью.

Capacity: 10, Rate: 10/sec, Current tokens: 7
  Request arrives at t+0.0 -> take 1, tokens=6
  Request arrives at t+0.1 -> refill +1, take 1, tokens=6
  ...
  Burst: 10 requests in 10ms -> tokens=0, next 1 sec reject

Плюсы

  • Поддерживает burst: при пустом трафике накопились токены, можно их "потратить"
  • O(1) память
  • Популярный выбор (AWS, Stripe используют token bucket)

Минусы

  • Burst может быть нежелателен для downstream
  • Редукция: last_refill_time нужен, значит lua

Формула refill

tokens_to_add = (now - last_refill) * rate_per_sec
new_tokens = min(capacity, old_tokens + tokens_to_add)

Реализация

<?php

declare(strict_types=1);

namespace App\RateLimit;

final readonly class TokenBucket
{
    /**
     * @param int   $capacity Maximum tokens (burst size)
     * @param float $ratePerSec Refill rate
     */
    public function __construct(
        private \Redis $redis,
        private int $capacity,
        private float $ratePerSec,
    ) {}

    public function allow(string $userId, int $cost = 1): bool
    {
        $key = "rl:tb:$userId";
        $now = microtime(true);

        // HSET with {tokens, last_refill}
        $lua = <<<'LUA'
            local key = KEYS[1]
            local capacity = tonumber(ARGV[1])
            local rate = tonumber(ARGV[2])
            local now = tonumber(ARGV[3])
            local cost = tonumber(ARGV[4])
            local ttl = tonumber(ARGV[5])

            local data = redis.call('HMGET', key, 'tokens', 'ts')
            local tokens = tonumber(data[1])
            local ts = tonumber(data[2])

            if tokens == nil then
                tokens = capacity
                ts = now
            end

            -- Refill based on elapsed time
            local elapsed = math.max(0, now - ts)
            tokens = math.min(capacity, tokens + elapsed * rate)

            if tokens < cost then
                redis.call('HMSET', key, 'tokens', tokens, 'ts', now)
                redis.call('EXPIRE', key, ttl)
                return 0
            end

            tokens = tokens - cost
            redis.call('HMSET', key, 'tokens', tokens, 'ts', now)
            redis.call('EXPIRE', key, ttl)
            return 1
        LUA;

        $res = $this->redis->eval(
            $lua,
            [$key, $this->capacity, $this->ratePerSec, $now, $cost, 3600],
            1,
        );

        return (bool) $res;
    }
}
## 5. Leaky Bucket

Запросы попадают в очередь (bucket). Worker обрабатывает с постоянной скоростью (leak). Переполненная очередь -- reject.

Arrivals: [r1, r2, r3, r4, r5]  (burst)
Bucket:   [ r1 ][ r2 ][ r3 ]    (max size 3, r4/r5 rejected)
Leak rate: 1/sec
At t+1s:  [ r2 ][ r3 ]          (r1 processed)

Отличие от token bucket: не допускает burst -- все запросы выходят с постоянной скоростью. Это traffic shaping.

Реализация на ZSET

<?php

declare(strict_types=1);

namespace App\RateLimit;

/**
 * Leaky bucket as a token-bucket variant where tokens do not exceed a rate.
 * We track virtual "drain time" per user.
 */
final readonly class LeakyBucket
{
    public function __construct(
        private \Redis $redis,
        private int $capacity,
        private float $leakPerSec,
    ) {}

    public function allow(string $userId): bool
    {
        $key = "rl:lb:$userId";
        $now = microtime(true);
        $leakInterval = 1.0 / $this->leakPerSec;

        $lua = <<<'LUA'
            local key = KEYS[1]
            local now = tonumber(ARGV[1])
            local interval = tonumber(ARGV[2])
            local capacity = tonumber(ARGV[3])
            local ttl = tonumber(ARGV[4])

            local last = tonumber(redis.call('HGET', key, 'last_drain')) or now
            local level = tonumber(redis.call('HGET', key, 'level')) or 0

            -- Drain: items leaked since last check
            local drained = math.floor((now - last) / interval)
            level = math.max(0, level - drained)
            -- Advance last_drain by the exact amount we drained
            last = last + drained * interval

            if level >= capacity then
                redis.call('HMSET', key, 'level', level, 'last_drain', last)
                redis.call('EXPIRE', key, ttl)
                return 0
            end

            level = level + 1
            redis.call('HMSET', key, 'level', level, 'last_drain', last)
            redis.call('EXPIRE', key, ttl)
            return 1
        LUA;

        $res = $this->redis->eval(
            $lua,
            [$key, $now, $leakInterval, $this->capacity, 3600],
            1,
        );

        return (bool) $res;
    }
}
## Выбор алгоритма
Случай Рекомендация
Public API с честной квотой Sliding Window Counter (баланс точности и ресурсов)
Бизнес допускает burst Token Bucket
Downstream не любит burst Leaky Bucket (shaping)
Audit / compliance Sliding Window Log (точный)
In-memory, низкая нагрузка Token Bucket (golang.org/x/time/rate)

Distributed vs local

Local (in-process): golang.org/x/time/rate, per-instance state. Плюс: 0 latency. Минус: N instance = N × limit.

Distributed (Redis): все примеры выше. Плюс: глобальный лимит. Минус: +2-5 ms latency, Redis SPOF.

Hybrid: локальный лимит как "sanity check" + distributed для точности. Local лимит можно поставить выше (например 2x), distributed -- строгий.

Ключи для rate limit

Что использовать как ключ:

  • IP -- легкий, но IP shared за NAT; клиент легко меняет
  • User ID -- честно, но требует auth
  • API key -- для машинных клиентов
  • (user, endpoint) -- точечные лимиты
  • (tenant, user, endpoint) -- для multi-tenant SaaS

Обычно комбинируют несколько: IP-wide глобальный + user-specific + endpoint-specific.

Коммуникация с клиентом

Стандартные HTTP headers:

HTTP/1.1 429 Too Many Requests
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1700000061      # unix ts when limit resets
Retry-After: 30

Клиент смотрит на Retry-After и ждёт.

Redis cluster considerations

  • Rate limit ключ должен быть на одной shard -- используйте hash tag: rl:{user123}:fw
  • Lua script выполняется на одной ноде -- ключи должны быть на ней же
  • При Redis failover state может потеряться -- лимит "сбросится"

Fail open vs fail closed

Redis упал, limiter вернул ошибку. Что делать?

  • Fail open (пропустить): доступность важнее. Риск: при Redis down кто-то добьёт downstream.
  • Fail closed (отклонить): безопасность. Риск: Redis моргнёт -- все пользователи получат 429.

Обычно -- fail open для public API + локальный fallback на in-memory лимит.

Pitfalls

  • Lua script: не atomic между ключами разных shard'ов. Hash tag обязателен.
  • Время не синхронизировано между app и Redis -- token bucket refill может быть неправильным. Передавайте now с клиента, а не TIME Redis.
  • Счётчик вечно растёт -- забыли EXPIRE. Проверяйте TTL.
  • "Холодный" клиент бьёт в закэшированный лимит и попадает в 429 -- но квота "свежая". Race между incr и expire.
  • Per-request cost > 1 -- некоторые endpoint "дороже". Учитывайте cost в token bucket.
  • Forgot rate per-endpoint -- один endpoint DoS'ит сервис. Add endpoint-specific limits.

Выводы

  • 5 алгоритмов, все работают, выбор зависит от требований
  • Token bucket -- золотая середина, допускает burst
  • Sliding window counter -- лучший компромисс точности и ресурсов
  • Leaky bucket -- когда downstream не переносит burst
  • Всегда Lua script для атомарности в Redis
  • Hash tag в ключах для Redis cluster
  • Headers X-RateLimit-* + Retry-After в ответе 429
  • Fail-open по умолчанию, локальный fallback для отказоустойчивости

Связанные темы

Генераторы уникальных ID

Связанная тема

Распределённые локи

Связанная тема