System Design
Rate Limiting & Throttling
Цели урока
- Понять зачем нужен Rate Limiting и его отличие от Throttling
- Изучить алгоритм Token Bucket и его burst-friendly поведение
- Разобраться в Leaky Bucket для сглаживания трафика
- Освоить Sliding Window для точного подсчёта
- Научиться реализовывать Distributed Rate Limiting с Redis
Предварительные знания
- Предыдущие уроки System Design
- Базовое понимание Redis
Rate Limiting - обязательный компонент любого production API. Без него один клиент может положить весь сервис. На интервью часто спрашивают: 'Как бы вы защитили API?' - и ожидают знания конкретных алгоритмов.
- Используется в production системах
Зачем ограничивать запросы?
**Rate Limiting** - контроль количества запросов, которые клиент может сделать за единицу времени. Это фундаментальный механизм защиты любого API.
Без rate limiting один злонамеренный (или баговый) клиент может положить весь сервис, отправляя миллионы запросов.
**Где применяется Rate Limiting:**
**Rate Limiting vs Throttling:**
При возврате 429 всегда включай заголовок Retry-After с количеством секунд до сброса лимита. Это позволяет клиентам корректно обрабатывать ограничения.
Какой HTTP статус возвращается при превышении rate limit?
429 Too Many Requests - стандартный статус для rate limiting. 403 - для authorization ошибок, 503 - для временной недоступности сервиса.
Token Bucket
**Token Bucket** - самый популярный алгоритм rate limiting. Используется в AWS API Gateway, Stripe, NGINX.
**Идея:** есть ведро с токенами. Каждый запрос забирает один токен. Токены добавляются с фиксированной скоростью. Если токенов нет - запрос отклоняется.
**Реализация на Python:**
**Преимущества Token Bucket:**
- **Burst-friendly** - позволяет короткие всплески активности
- **Простота** - легко реализовать и понять
- **Memory efficient** - хранит только 2 числа (tokens, timestamp)
- **Гибкость** - настраиваемый burst и sustained rate
Token Bucket идеален когда нужно разрешить burst (всплески), но ограничить средний rate. Например, пользователь открывает страницу - 10 API запросов сразу, потом тишина.
Token Bucket с capacity=100 и rate=10/sec. Сколько запросов можно сделать за первую секунду?
В начале bucket полный (100 токенов), поэтому можно сделать burst из 100 запросов мгновенно. После этого - только 10/sec по мере refill.
Leaky Bucket
**Leaky Bucket** - запросы «вытекают» из ведра с постоянной скоростью. Сглаживает трафик до ровного потока.
В отличие от Token Bucket, здесь не burst, а queue - запросы накапливаются и обрабатываются равномерно.
**Token Bucket vs Leaky Bucket:**
**Когда использовать Leaky Bucket:**
- **Network traffic shaping** - ровный поток пакетов
- **Защита backend** - не передавать burst на слабый сервис
- **Video streaming** - равномерная отдача битрейта
- **Message queues** - ровная скорость потребления
Leaky Bucket добавляет latency! Запросы ждут в очереди. Для user-facing API обычно лучше Token Bucket с быстрым reject.
Главное отличие Leaky Bucket от Token Bucket?
Leaky Bucket превращает любой входящий трафик в ровный поток. Token Bucket разрешает burst (всплески). Leaky использует больше памяти (очередь) и может добавлять latency.
Sliding Window
**Sliding Window** - подсчитывает запросы в скользящем временном окне. Более точный, чем Fixed Window, но сложнее в реализации.
**Проблема Fixed Window:**
**Sliding Window Log:**
Храним timestamp каждого запроса. При новом запросе удаляем старые (за пределами окна) и считаем оставшиеся.
**Sliding Window Counter (компромисс):**
Комбинирует Fixed Window с весовым коэффициентом. Меньше памяти, чем Log, точнее, чем Fixed.
**Сравнение алгоритмов:**
Sliding Window Counter использует 2 счётчика. Зачем нужен счётчик предыдущего окна?
Счётчик предыдущего окна используется для weighted расчёта: часть прошлого окна ещё попадает в текущее sliding window. Это решает проблему burst на границе Fixed Window.
Distributed Rate Limiting
В реальных системах rate limiting должен работать **распределённо** - на нескольких серверах, которые должны "видеть" общий счётчик.
**Решение 1: Centralized Counter (Redis)**
**Решение 2: Sticky Sessions**
**Решение 3: Token Bucket с синхронизацией**
**Rate Limit Headers:**
Для большинства случаев Redis + Sliding Window Counter - оптимальный выбор. O(1) memory, O(1) operations, высокая точность, простая реализация.
Почему для distributed rate limiting часто используют Redis?
Redis идеален для rate limiting: атомарный INCR без race conditions, EXPIRE для автоматического сброса окна, sub-millisecond latency, простой API.
Ключевые идеи
- Token Bucket: разрешает burst, используется в API Gateway, Stripe
- Leaky Bucket: сглаживает трафик до ровного потока
- Fixed Window: простой но неточный на границах
- Sliding Window Counter: компромисс - O(1) memory и высокая точность
- Для distributed: Redis + INCR + EXPIRE
Что дальше
Следующий урок: Consistent Hashing - как распределять данные между серверами так, чтобы добавление/удаление сервера минимально затрагивало существующее распределение.
- System Design — продолжение курса