MidКейс27 min

Rate Limiter

Проектирование Rate Limiter: алгоритмы Token Bucket, Leaky Bucket, Fixed/Sliding Window с реализацией на PHP и Redis

SysdesignCase studies

Rate Limiter -- компонент, ограничивающий количество запросов клиента за единицу времени. Защита от DDoS, злоупотреблений API и обеспечение справедливого использования ресурсов.

Шаг 1: Требования

Функциональные требования

  1. Ограничение запросов по разным ключам (IP, user_id, API key)
  2. Поддержка разных правил (100 req/min, 1000 req/hour)
  3. Возврат HTTP 429 (Too Many Requests) при превышении лимита
  4. Заголовки ответа: X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset
  5. Конфигурация правил без перезапуска сервиса

Нефункциональные требования

  1. Минимальная latency (< 1ms для проверки)
  2. Distributed: работает на кластере серверов
  3. Точность: допустимо отклонение ~1%
  4. Fault-tolerant: при падении rate limiter -- пропускать запросы (fail-open)

Шаг 2: Оценка нагрузки

Метрика Значение
API requests ~500K QPS
Уникальных клиентов ~10M
Правил rate limit ~50
Размер состояния на клиента ~100 bytes
Общее состояние в памяти ~1 GB

Шаг 3: High-Level архитектура

┌──────────┐     ┌───────────────┐     ┌─────────────────────────┐
│  Client  │────>│  Load         │────>│  API Gateway / Nginx    │
│          │     │  Balancer     │     │  (Rate Limit Check)     │
└──────────┘     └───────────────┘     └────────────┬────────────┘
                                                    │
                                           ┌────────▼────────┐
                                           │  Rate Limiter   │
                                           │  Service        │
                                           └────────┬────────┘
                                                    │
                                           ┌────────▼────────┐
                                           │  Redis Cluster  │
                                           │  (State Store)  │
                                           └─────────────────┘
                                                    │
                                           ┌────────▼────────┐
                                           │  Rules Config   │
                                           │  (DB / File)    │
                                           └─────────────────┘

Шаг 4: Алгоритмы Rate Limiting

4.1 Token Bucket

Наиболее распространённый алгоритм. Токены добавляются с фиксированной скоростью. Каждый запрос забирает один токен.

<?php

declare(strict_types=1);

final class TokenBucketLimiter
{
    public function __construct(
        private readonly \Redis $redis,
    ) {}

    /**
     * @param string $key       Unique client identifier
     * @param int    $capacity  Max tokens (burst size)
     * @param float  $rate      Tokens added per second
     * @return array{allowed: bool, remaining: int, retryAfter: float}
     */
    public function allow(string $key, int $capacity, float $rate): array
    {
        $now = microtime(true);
        $redisKey = "token_bucket:{$key}";

        // Lua script for atomicity
        $script = <<<'LUA'
            local key = KEYS[1]
            local capacity = tonumber(ARGV[1])
            local rate = tonumber(ARGV[2])
            local now = tonumber(ARGV[3])

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

            -- Initialize if first request
            if tokens == nil then
                tokens = capacity
                lastRefill = now
            end

            -- Add tokens based on elapsed time
            local elapsed = now - lastRefill
            local newTokens = elapsed * rate
            tokens = math.min(capacity, tokens + newTokens)
            lastRefill = now

            -- Try to consume one token
            local allowed = 0
            if tokens >= 1 then
                tokens = tokens - 1
                allowed = 1
            end

            -- Save state
            redis.call('HMSET', key, 'tokens', tokens, 'last_refill', lastRefill)
            redis.call('EXPIRE', key, math.ceil(capacity / rate) + 1)

            -- Calculate retry-after if not allowed
            local retryAfter = 0
            if allowed == 0 then
                retryAfter = (1 - tokens) / rate
            end

            return {allowed, math.floor(tokens), tostring(retryAfter)}
        LUA;

        $result = $this->redis->eval($script, [$redisKey, $capacity, $rate, $now], 1);

        return [
            'allowed' => (bool) $result[0],
            'remaining' => (int) $result[1],
            'retryAfter' => (float) $result[2],
        ];
    }
}
**Плюсы:** допускает burst, гибкий, интуитивный. **Минусы:** нужно хранить состояние для каждого клиента.

4.2 Leaky Bucket

Запросы обрабатываются с постоянной скоростью, лишние отбрасываются.

<?php

declare(strict_types=1);

final class LeakyBucketLimiter
{
    public function __construct(
        private readonly \Redis $redis,
    ) {}

    /**
     * @param string $key      Unique client identifier
     * @param int    $capacity Queue size (max waiting requests)
     * @param float  $leakRate Requests processed per second
     */
    public function allow(string $key, int $capacity, float $leakRate): array
    {
        $now = microtime(true);
        $redisKey = "leaky_bucket:{$key}";

        $script = <<<'LUA'
            local key = KEYS[1]
            local capacity = tonumber(ARGV[1])
            local leakRate = tonumber(ARGV[2])
            local now = tonumber(ARGV[3])

            local data = redis.call('HMGET', key, 'water', 'last_leak')
            local water = tonumber(data[1]) or 0
            local lastLeak = tonumber(data[2]) or now

            -- Leak water based on time passed
            local elapsed = now - lastLeak
            local leaked = elapsed * leakRate
            water = math.max(0, water - leaked)
            lastLeak = now

            local allowed = 0
            if water < capacity then
                water = water + 1
                allowed = 1
            end

            redis.call('HMSET', key, 'water', water, 'last_leak', lastLeak)
            redis.call('EXPIRE', key, math.ceil(capacity / leakRate) + 1)

            return {allowed, capacity - math.floor(water)}
        LUA;

        $result = $this->redis->eval($script, [$redisKey, $capacity, $leakRate, $now], 1);

        return [
            'allowed' => (bool) $result[0],
            'remaining' => (int) $result[1],
        ];
    }
}
**Плюсы:** стабильный output rate. **Минусы:** burst трафик теряется, не подходит для API.

4.3 Fixed Window Counter

Простейший алгоритм: счётчик на фиксированный интервал.

<?php

declare(strict_types=1);

final class FixedWindowLimiter
{
    public function __construct(
        private readonly \Redis $redis,
    ) {}

    /**
     * @param string $key        Unique client identifier
     * @param int    $limit      Max requests per window
     * @param int    $windowSec  Window size in seconds
     */
    public function allow(string $key, int $limit, int $windowSec): array
    {
        $window = (int) (time() / $windowSec);
        $redisKey = "fixed_window:{$key}:{$window}";

        $script = <<<'LUA'
            local key = KEYS[1]
            local limit = tonumber(ARGV[1])
            local windowSec = tonumber(ARGV[2])

            local current = tonumber(redis.call('GET', key) or '0')

            if current < limit then
                redis.call('INCR', key)
                redis.call('EXPIRE', key, windowSec)
                return {1, limit - current - 1}
            else
                return {0, 0}
            end
        LUA;

        $result = $this->redis->eval($script, [$redisKey, $limit, $windowSec], 1);

        return [
            'allowed' => (bool) $result[0],
            'remaining' => (int) $result[1],
            'resetAt' => ($window + 1) * $windowSec,
        ];
    }
}
**Плюсы:** простой, мало памяти. **Минусы:** edge case на границе окна (можно получить 2x трафика).

4.4 Sliding Window Log

Точный, но ресурсоёмкий: хранит timestamp каждого запроса.

<?php

declare(strict_types=1);

final class SlidingWindowLogLimiter
{
    public function __construct(
        private readonly \Redis $redis,
    ) {}

    public function allow(string $key, int $limit, int $windowSec): array
    {
        $now = microtime(true);
        $redisKey = "sliding_log:{$key}";
        $windowStart = $now - $windowSec;

        $script = <<<'LUA'
            local key = KEYS[1]
            local limit = tonumber(ARGV[1])
            local now = tonumber(ARGV[2])
            local windowStart = tonumber(ARGV[3])
            local windowSec = tonumber(ARGV[4])

            -- Remove expired entries
            redis.call('ZREMRANGEBYSCORE', key, '-inf', windowStart)

            -- Count current requests in window
            local count = redis.call('ZCARD', key)

            if count < limit then
                -- Add current request
                redis.call('ZADD', key, now, now .. ':' .. math.random(1000000))
                redis.call('EXPIRE', key, windowSec)
                return {1, limit - count - 1}
            else
                redis.call('EXPIRE', key, windowSec)
                return {0, 0}
            end
        LUA;

        $result = $this->redis->eval(
            $script,
            [$redisKey, $limit, $now, $windowStart, $windowSec],
            1,
        );

        return [
            'allowed' => (bool) $result[0],
            'remaining' => (int) $result[1],
        ];
    }
}
### 4.5 Sliding Window Counter (гибридный)

Комбинация Fixed Window и Sliding Window. Оптимальный баланс точности и ресурсов.

<?php

declare(strict_types=1);

final class SlidingWindowCounterLimiter
{
    public function __construct(
        private readonly \Redis $redis,
    ) {}

    public function allow(string $key, int $limit, int $windowSec): array
    {
        $now = time();
        $currentWindow = (int) ($now / $windowSec);
        $previousWindow = $currentWindow - 1;

        $currentKey = "swc:{$key}:{$currentWindow}";
        $previousKey = "swc:{$key}:{$previousWindow}";

        $script = <<<'LUA'
            local currentKey = KEYS[1]
            local previousKey = KEYS[2]
            local limit = tonumber(ARGV[1])
            local windowSec = tonumber(ARGV[2])
            local elapsedRatio = tonumber(ARGV[3])

            local currentCount = tonumber(redis.call('GET', currentKey) or '0')
            local previousCount = tonumber(redis.call('GET', previousKey) or '0')

            -- Weighted count: previous window * remaining ratio + current count
            local remainingRatio = 1 - elapsedRatio
            local estimatedCount = math.floor(previousCount * remainingRatio) + currentCount

            if estimatedCount < limit then
                redis.call('INCR', currentKey)
                redis.call('EXPIRE', currentKey, windowSec * 2)
                return {1, limit - estimatedCount - 1}
            else
                return {0, 0}
            end
        LUA;

        $elapsedInCurrentWindow = $now % $windowSec;
        $elapsedRatio = $elapsedInCurrentWindow / $windowSec;

        $result = $this->redis->eval(
            $script,
            [$currentKey, $previousKey, $limit, $windowSec, $elapsedRatio],
            2,
        );

        return [
            'allowed' => (bool) $result[0],
            'remaining' => (int) $result[1],
            'resetAt' => ($currentWindow + 1) * $windowSec,
        ];
    }
}
## Сравнение алгоритмов
Алгоритм Память Точность Burst Сложность
Token Bucket O(1) Высокая Да Средняя
Leaky Bucket O(1) Высокая Нет Средняя
Fixed Window O(1) Низкая (edge) Да (2x) Низкая
Sliding Log O(N) Идеальная Нет Высокая
Sliding Counter O(1) Высокая Частично Средняя

Шаг 5: Middleware приложения

<?php

declare(strict_types=1);

final class RateLimitMiddleware
{
    public function __construct(
        private readonly TokenBucketLimiter $limiter,
        private readonly RateLimitConfig $config,
    ) {}

    public function handle(Request $request, callable $next): Response
    {
        $key = $this->resolveKey($request);
        $rule = $this->config->getRuleForPath($request->getPathInfo());

        $result = $this->limiter->allow($key, $rule->capacity, $rule->rate);

        if (!$result['allowed']) {
            return new Response(
                json_encode(['error' => 'Rate limit exceeded']),
                429,
                [
                    'Content-Type' => 'application/json',
                    'X-RateLimit-Limit' => (string) $rule->capacity,
                    'X-RateLimit-Remaining' => '0',
                    'X-RateLimit-Reset' => (string) ($result['resetAt'] ?? time() + 60),
                    'Retry-After' => (string) ceil($result['retryAfter']),
                ],
            );
        }

        $response = $next($request);

        // Add rate limit headers to successful responses
        return $response->withHeaders([
            'X-RateLimit-Limit' => (string) $rule->capacity,
            'X-RateLimit-Remaining' => (string) $result['remaining'],
            'X-RateLimit-Reset' => (string) ($result['resetAt'] ?? time() + 60),
        ]);
    }

    private function resolveKey(Request $request): string
    {
        // Priority: API Key > User ID > IP
        if ($apiKey = $request->headers->get('X-API-Key')) {
            return "api_key:{$apiKey}";
        }

        if ($userId = $request->attributes->get('user_id')) {
            return "user:{$userId}";
        }

        return "ip:{$request->getClientIp()}";
    }
}

final readonly class RateLimitRule
{
    public function __construct(
        public int $capacity,    // Max requests (burst)
        public float $rate,      // Refill rate per second
        public string $keyType,  // ip, user, api_key
    ) {}
}

final class RateLimitConfig
{
    /** @var array<string, RateLimitRule> */
    private array $rules = [];

    public function addRule(string $pathPattern, RateLimitRule $rule): void
    {
        $this->rules[$pathPattern] = $rule;
    }

    public function getRuleForPath(string $path): RateLimitRule
    {
        foreach ($this->rules as $pattern => $rule) {
            if (preg_match($pattern, $path)) {
                return $rule;
            }
        }

        // Default rule
        return new RateLimitRule(
            capacity: 100,
            rate: 10.0,
            keyType: 'ip',
        );
    }
}
## Шаг 6: Distributed Rate Limiting

Проблема: несколько серверов

Client -> LB -> Server 1 (limit: 50 of 100) -> Redis
          └──-> Server 2 (limit: 50 of 100) -> Redis (same key!)

Redis решает проблему: все серверы используют один Redis для состояния.

Race conditions

Lua-скрипты в Redis атомарны -- нет race conditions. Это главная причина использования Lua, а не отдельных GET/SET.

Синхронизация при Redis Cluster

<?php

declare(strict_types=1);

final class DistributedRateLimiter
{
    /** @var \Redis[] */
    private array $redisNodes;

    public function __construct(array $redisNodes)
    {
        $this->redisNodes = $redisNodes;
    }

    /**
     * Use consistent hashing to route to the correct Redis node
     */
    public function allow(string $key, int $limit, int $windowSec): array
    {
        $node = $this->getNodeForKey($key);

        return $this->checkLimit($node, $key, $limit, $windowSec);
    }

    private function getNodeForKey(string $key): \Redis
    {
        $hash = crc32($key);
        $index = $hash % count($this->redisNodes);

        return $this->redisNodes[$index];
    }

    private function checkLimit(\Redis $redis, string $key, int $limit, int $windowSec): array
    {
        // Same Lua script as before, executed on the specific node
        // ...
        return ['allowed' => true, 'remaining' => $limit];
    }
}
## Возможные вопросы интервьюера

  1. Как обрабатывать ситуацию, когда Redis недоступен?

    • Fail-open: пропускаем все запросы (лучше доступность)
    • Fail-closed: блокируем все (лучше безопасность)
    • Local fallback: in-memory rate limiter на каждом сервере

  2. Как реализовать разные лимиты для разных тарифов?

    • Конфигурация правил в базе данных
    • Ключ кэша включает tier: rate_limit:{user_id}:{tier}

  3. Как избежать hot key в Redis?

    • Шардирование по ключам
    • Local cache для часто проверяемых клиентов
    • Pipelining для batch проверок

  4. Rate limiting на уровне API Gateway vs Application?

    • Gateway: грубая защита (IP-based), DDoS
    • Application: точная (user-based), бизнес-правила

  5. Как тестировать rate limiter?

    • Unit-тесты с mock Redis
    • Integration-тесты с реальным Redis
    • Load testing для проверки точности при высоком QPS

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

Геолокация и Proximity

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

Google Calendar

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

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

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