System Design Space

    Глава 22

    Обновлено: 15 февраля 2026 г. в 14:20

    Rate Limiter

    Прогресс части0/21

    Классическая задача: Token Bucket, Sliding Window, Redis + Lua scripts, distributed rate limiting.

    Rate Limiter — одна из самых популярных задач на System Design интервью. Она присутствует в книгах Alex Xu ("System Design Interview") и Zhiyong Tan ("Acing the System Design Interview") как базовый пример проектирования распределённой системы с жёсткими требованиями к производительности.

    Глава 4

    Alex Xu: Rate Limiter

    Детальный разбор алгоритмов и архитектуры в книге

    Читать обзор

    Зачем нужен Rate Limiter

    Проблемы без Rate Limiting

    • DDoS атаки — перегрузка сервиса вредоносным трафиком
    • Каскадные отказы — один клиент убивает весь сервис
    • Перерасход ресурсов — бесконтрольное потребление API
    • Неравномерная нагрузка — "шумные соседи" мешают другим

    Преимущества Rate Limiting

    • Защита сервисов — предотвращение перегрузки
    • Справедливое распределение — квоты для каждого клиента
    • Экономия денег — контроль использования платных API
    • Предсказуемость — стабильная производительность

    Типичные требования

    Функциональные

    • FR1
      Ограничение запросов по IP, user ID или API key
    • FR2
      Настраиваемые лимиты для разных эндпоинтов
    • FR3
      Информативный ответ при превышении лимита (429)
    • FR4
      Поддержка distributed environment

    Нефункциональные

    • NFR1
      Низкая латентность — <1ms overhead на запрос
    • NFR2
      Высокая доступность — сбой лимитера ≠ сбой сервиса
    • NFR3
      Точность лимитов (допустимо ±5% в distributed)
    • NFR4
      Горизонтальное масштабирование

    Алгоритмы Rate Limiting

    Существует несколько классических алгоритмов, каждый с своими trade-offs:

    Интерактивная визуализация

    1. Token Bucket

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

    Преимущества

    • Простая реализация
    • Позволяет burst трафик
    • Memory efficient (2 числа на пользователя)

    Недостатки

    • Сложно подобрать bucket size
    • Race conditions в distributed

    # Параметры:

    bucket_size = 10 # макс. токенов

    refill_rate = 2 # токенов/сек

    Визуализация алгоритма

    Токены:
    5.0 / 5
    Пополнение: 1 токен/сек
    t = 0.0s
    История запросов:
    Нажмите "Старт" и отправляйте запросы

    Архитектура системы

    Связанный кейс

    API Gateway

    Полный разбор API Gateway: routing, security, BFF pattern и сравнение технологий.

    Читать кейс

    Где разместить Rate Limiter?

    Client-side

    Легко обойти, не надёжно. Используется только как оптимизация.

    API Gateway

    Идеальное место — централизованно, до сервисов. AWS API Gateway, Kong, Envoy.

    Middleware

    В каждом сервисе — гибко, но дублирование и сложность синхронизации.

    Zhiyong Tan

    Acing SDI: Rate Limiter

    Сравнение подходов к размещению rate limiter

    Читать обзор

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

    Redis — стандартный выбор для Rate Limiter благодаря in-memory скорости и атомарным операциям.

    Sliding Window Counter на Redis

    -- Lua script для атомарности
    local key = KEYS[1]
    local window = tonumber(ARGV[1])  -- размер окна в секундах
    local limit = tonumber(ARGV[2])   -- лимит запросов
    local now = tonumber(ARGV[3])     -- текущий timestamp
    
    -- Удаляем старые записи
    redis.call('ZREMRANGEBYSCORE', key, 0, now - window)
    
    -- Считаем текущие запросы
    local count = redis.call('ZCARD', key)
    
    if count < limit then
        -- Добавляем новый запрос
        redis.call('ZADD', key, now, now .. '-' .. math.random())
        redis.call('EXPIRE', key, window)
        return 1  -- разрешено
    else
        return 0  -- отклонено
    end

    Race Condition Protection

    Проблема: Concurrent запросы читают одинаковый count.

    Решение: Lua scripts выполняются атомарно в Redis.

    Альтернатива: Redis MULTI/EXEC или Redlock для distributed locking.

    Synchronization

    Centralized: Один Redis cluster для всех инстансов.

    Eventual consistency: Локальные счётчики + периодическая синхронизация.

    Trade-off: Точность vs Latency.

    HTTP Response Headers

    # При успешном запросе:

    X-RateLimit-Limit: 100

    X-RateLimit-Remaining: 42

    X-RateLimit-Reset: 1640995200

    # При превышении лимита:

    HTTP/1.1 429 Too Many Requests

    Retry-After: 30

    Deep Dive: Multi-tier Rate Limiting

    В реальных системах применяют несколько уровней лимитов:

    По уровням

    • Global: 10M req/day на весь сервис
    • Per-user: 1000 req/hour на пользователя
    • Per-endpoint: 100 req/min на /api/search
    • Per-IP: защита от DDoS с одного IP

    Graceful Degradation

    • Soft limit: Предупреждение в headers
    • Hard limit: 429 + Retry-After
    • Redis down: Fail-open (пропускаем) или fail-close?
    • Monitoring: Alert на аномалии трафика

    Ключевые выводы для интервью

    • 1
      Начните с требований: Какой трафик? Допустима ли неточность? Distributed?
    • 2
      Выберите алгоритм: Token Bucket для burst, Sliding Window Counter для точности.
    • 3
      Обсудите trade-offs: Memory vs Accuracy, Latency vs Consistency.
    • 4
      Redis + Lua: Атомарные операции решают race conditions.
    • 5
      Fail-open vs Fail-close: Что делать при отказе rate limiter?