System Design Space
Граф знанийНастройки

Обновлено: 25 марта 2026 г. в 04:52

Rate Limiter

medium

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

Rate limiter кажется задачей про счетчик, но на деле это задача про справедливость под burst-нагрузкой, распределенное состояние и поведение системы в момент отказа самого лимитера.

Кейс помогает разложить по полочкам token bucket, leaky bucket и sliding window, выбор точки применения, хранение ключей лимитов и fail-open vs fail-close policy.

В интервью и design review он хорошо вскрывает качество инженерного мышления вокруг abuse prevention, критического пути и цены неверного default.

Control Plane

Фокус на governance-политиках, лимитах, маршрутизации и стабильности edge-поведения.

Data Path

Нужно держать предсказуемую latency и throughput при росте трафика и burst-нагрузке.

Failure Modes

Покрывайте fail-open/fail-close, деградацию и безопасный fallback при частичных отказах.

Ops Ready

Показывайте мониторинг saturation, retry storm и operational guardrails.

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?

Для дополнительной практики и сравнения реализаций полезно посмотреть System Design Primer: Rate Limiter и Cloudflare Rate Limiting Rules.

Связанные главы

  • System Design Primer (short summary) - даёт базовые шаблоны для постановки требований и оценки ограничений в rate limiting задачах.
  • System Design Interview - Alex Xu - содержит классический интервью-разбор rate limiter с акцентом на алгоритмы и trade-offs.
  • Acing the System Design Interview - дополняет тему практическими вариантами размещения лимитера в distributed-среде.
  • API Gateway - показывает главный production-контур, где rate limiting обычно реализуют централизованно.
  • API Security Patterns - связывает rate limiting с более широкой защитой API: auth, abuse control и policy enforcement.
  • Caching Strategies - помогает выбирать storage/cache-подход для счётчиков лимитов и снижения latency оверхеда.
  • Resilience Patterns - расширяет тему fail-open/fail-close и деградации лимитера без каскадных сбоев сервиса.
  • Notification System - показывает практический кейс, где multi-tier лимиты ограничивают burst и защищают downstream.
  • Web Crawler - демонстрирует необходимость лимитов для вежливого и контролируемого доступа к внешним источникам.
  • Payment System - даёт high-stakes контекст, где rate limiting помогает защищать критичные финансовые операции.

Чтобы отмечать прохождение, включи трекинг в Настройки