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 # токенов/сек
Визуализация алгоритма
Архитектура системы
Связанный кейс
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 -- отклонено
endRace 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.
- 4Redis + Lua: Атомарные операции решают race conditions.
- 5Fail-open vs Fail-close: Что делать при отказе rate limiter?
