Модуль: System Design · Уровень: Senior

TL;DR#

Rate Limiter ограничивает число запросов от клиента (по ключу: user_id, API-key, IP) за единицу времени. Базовый ответ при превышении — HTTP 429 Too Many Requests с Retry-After. Ключевой выбор — алгоритм (точность vs память) и место размещения (gateway/middleware/sidecar). В распределённой системе состояние обычно держат в Redis с атомарными операциями через Lua-скрипты; для снижения нагрузки на Redis применяют гибрид local + global (локальный токен-бакет на ноде + периодическая синхронизация).

Главные trade-offs:

• Точность ↔ память: sliding window log (точный, дорогой по памяти) vs sliding window counter (аппроксимация, O(1) памяти).
• Гладкость ↔ всплески: leaky bucket выравнивает трафик; token bucket допускает контролируемые всплески (burst).
• Согласованность ↔ латентность: строгий глобальный лимит через Redis (сетевой hop на каждый запрос) vs eventual consistency при локальных счётчиках.

Требования#

Functional#

• Ограничить запросы по конфигурируемому правилу: N запросов / окно T для ключа.
• Поддержка нескольких размерностей ключа: per-user, per-API-key, per-IP, per-endpoint, глобально.
• Несколько уровней лимитов одновременно (например, 10 req/s И 1000 req/day).
• При превышении — отклонить с 429, вернуть Retry-After и X-RateLimit-* заголовки.
• Поддержка burst (кратковременных всплесков) — настраиваемо.
• Динамическое обновление правил без рестарта (hot reload).
• Разные тарифы (free/pro/enterprise) — лимит зависит от плана клиента.

Non-functional#

• Низкая латентность: rate limiter добавляет < 1–2 ms к p99 запроса.
• Высокая доступность: отказ rate limiter не должен ронять сервис. Политика fail-open (пропускать при недоступности backend) или fail-closed (блокировать) — осознанный выбор.
• Точность: не выпускать существенно больше лимита (приемлемая погрешность зависит от алгоритма).
• Масштабируемость: десятки/сотни тысяч RPS, миллионы уникальных ключей.
• Эффективность по памяти: O(1) на ключ предпочтительно.
• Распределённость: согласованный лимит между N инстансами сервиса.

Оценки нагрузки#

Допустим: API-сервис, 100 000 RPS, 10 млн уникальных активных клиентов в сутки, окно лимита 1 минута.

QPS на backend счётчиков (Redis):

• При проверке на каждый запрос — 100k операций/с к Redis (INCR/EVAL). Один Redis-инстанс держит ~100k–200k простых операций/с — мы на грани, нужен шардинг/кластер или local cache.

Память на ключ по алгоритмам:

Вывод по цифрам: log-подход не масштабируется на миллионы ключей с высокими лимитами; counter-подходы дают O(1) и реалистичны. Реальный оверхед Redis-ключа существенен (минимум ~50–90 B на маленький ключ), поэтому считаем именно его, а не голый payload.

Уникальные клиенты: активных одновременно (за минуту) обычно гораздо меньше суточных — например 1–2M. Память считаем по пику активных ключей с TTL = окно (мёртвые ключи сами истекают).

Архитектура#

                          ┌──────────────────────────┐
                          │     Config / Rules store  │
                          │  (plan limits, hot reload)│
                          └───────────┬──────────────┘
                                      │
  Client ──HTTP──> ┌─────────────────▼─────────────────┐
                   │            API Gateway             │
                   │   ┌───────────────────────────┐    │
                   │   │   Rate Limiter middleware  │    │
                   │   │  1) build key (user/ip/ep) │    │
                   │   │  2) check local bucket ────┼────┼──> local in-memory
                   │   │  3) (sync) check Redis ────┼────┼──┐  token bucket
                   │   └───────────────────────────┘    │  │
                   └────────┬───────────────▲───────────┘  │
                            │ allow         │ 429 +         │
                            ▼               │ Retry-After   ▼
                     ┌────────────┐         │        ┌──────────────┐
                     │  Upstream  │         └────────│ Redis Cluster│
                     │  services  │   atomic EVAL    │ (sharded by  │
                     └────────────┘   (Lua script)   │     key)     │
                                                      └──────────────┘

Где размещать rate limiter#

Практика senior-уровня: первичный лимит на gateway/edge (грубый, защита от DDoS/абуза) + точный бизнес-лимит в middleware/RLS (per-plan, per-endpoint). Глобальное состояние — в Redis, локальный кэш — на каждой ноде.

Ключевые решения и trade-offs#

Token Bucket#

Бакет вместимостью capacity токенов пополняется со скоростью refillRate токенов/сек. Каждый запрос забирает 1 (или N) токенов; нет токена — отказ.

• Плюсы: допускает контролируемые всплески (до capacity), O(1) памяти (2 числа на ключ), интуитивно, легко выразить “burst + sustained rate”.
• Минусы: всплеск может пройти сразу до capacity (если нужна строгая гладкость — не подходит).
• Точность/память: точный по среднему rate, O(1).

Leaky Bucket#

Очередь (или счётчик “уровня воды”) фиксированной ёмкости, “вытекающая” с постоянной скоростью. Запросы добавляются в очередь; переполнение — отказ. По сути queue-as-buffer + постоянный output rate.

• Плюсы: выравнивает исходящий трафик до строго постоянной скорости (хорошо для защиты медленного downstream).
• Минусы: всплески не пропускает (запросы ждут или отбрасываются), добавляет латентность при буферизации, очередь = память.
• Token vs leaky: token bucket разрешает burst, leaky — сглаживает. Token bucket чаще выбирают для API.

Fixed Window Counter#

Счётчик на окно [t0, t0+T). INCR на запрос, сброс в начале нового окна.

• Плюсы: тривиально, O(1), 1 счётчик + TTL.
• Минус (всплеск на границе): при лимите 100/мин клиент может сделать 100 запросов в 00:59 и ещё 100 в 01:00 — 200 запросов за 2 секунды на стыке окон. Эффективно до 2× лимита локально.

Sliding Window Log#

Хранит timestamp каждого запроса (в Redis — ZSET). При проверке удаляет записи старше now - T, считает оставшиеся, сравнивает с лимитом.

• Плюсы: абсолютно точный, нет проблемы границы.
• Минусы: память O(N) — по timestamp на каждый запрос в окне (при высоких лимитах — дорого, см. таблицу), ZSET-операции тяжелее.

Sliding Window Counter#

Аппроксимация: хранит счётчики текущего и предыдущего окна, взвешивает предыдущее по доле перекрытия. estimate = curr + prev * (1 - elapsed_in_curr / T).

• Плюсы: O(1) памяти (2 счётчика), сглаживает границу гораздо лучше fixed window, дёшево.
• Минусы: аппроксимация — предполагает равномерное распределение запросов в предыдущем окне; погрешность обычно < 1%, но при неравномерном трафике может слегка пере-/недопускать.

Практический выбор: token bucket (если нужен burst) или sliding window counter (если нужна гладкость без затрат log). Это наиболее частые ответы на senior-собеседовании.

Distributed: Redis, атомарность, гонки#

Проблема: с несколькими инстансами сервиса наивный GET → проверка → SET создаёт race condition — два инстанса читают счётчик 99, оба разрешают, лимит превышен.

Решения:

• INCR атомарен, но “проверить-и-откатить” из нескольких команд — нет.
• Lua-скрипт в Redis выполняется атомарно (single-threaded, скрипт = одна транзакция без вытеснения). Вся логика «прочитать-вычислить-записать-вернуть решение» — внутри EVAL. Это канонический способ.
• WATCH/MULTI/EXEC (optimistic) возможен, но Lua проще и быстрее (один round-trip).

Синхронизация между нодами: при чистом Redis-подходе ноды stateless, состояние в Redis — согласованность строгая (с точностью до атомарности скрипта). При гибриде — eventual (см. ниже).

HTTP-семантика#

При отказе:

• Статус 429 Too Many Requests.
• Retry-After: <секунды> — когда можно повторить.
• X-RateLimit-Limit: 100 — лимит.
• X-RateLimit-Remaining: 0 — остаток.
• X-RateLimit-Reset: <unix-ts или секунды> — когда окно сбросится.

(Стандартизируемый вариант — заголовки RateLimit / RateLimit-Policy из черновика IETF, но X-RateLimit-* де-факто распространены.)

Go-реализация#

Token Bucket (in-memory, потокобезопасный)#

package ratelimit

import (
	"sync"
	"time"
)

// TokenBucket — потокобезопасный токен-бакет с ленивым (lazy) пополнением.
type TokenBucket struct {
	mu         sync.Mutex
	capacity   float64   // максимум токенов (burst)
	refillRate float64   // токенов в секунду (sustained rate)
	tokens     float64   // текущее число токенов
	lastRefill time.Time
}

func NewTokenBucket(capacity, refillRate float64) *TokenBucket {
	return &TokenBucket{
		capacity:   capacity,
		refillRate: refillRate,
		tokens:     capacity, // стартуем заполненными
		lastRefill: time.Now(),
	}
}

// Allow пытается списать n токенов. Возвращает (разрешено, сколько ждать до следующей попытки).
func (tb *TokenBucket) Allow(n float64) (bool, time.Duration) {
	tb.mu.Lock()
	defer tb.mu.Unlock()

	now := time.Now()
	// Ленивое пополнение: считаем токены по прошедшему времени, без фонового тикера.
	elapsed := now.Sub(tb.lastRefill).Seconds()
	tb.tokens = min(tb.capacity, tb.tokens+elapsed*tb.refillRate)
	tb.lastRefill = now

	if tb.tokens >= n {
		tb.tokens -= n
		return true, 0
	}
	// Сколько ждать, пока накопится недостающее.
	deficit := n - tb.tokens
	wait := time.Duration(deficit / tb.refillRate * float64(time.Second))
	return false, wait
}

func min(a, b float64) float64 {
	if a < b {
		return a
	}
	return b
}

Менеджер бакетов по ключу с очисткой простаивающих (чтобы не течь по памяти):

type Limiter struct {
	mu       sync.Mutex
	buckets  map[string]*bucketEntry
	cap, rate float64
	ttl      time.Duration
}

type bucketEntry struct {
	tb       *TokenBucket
	lastSeen time.Time
}

func NewLimiter(capacity, rate float64, ttl time.Duration) *Limiter {
	l := &Limiter{
		buckets: make(map[string]*bucketEntry),
		cap:     capacity, rate: rate, ttl: ttl,
	}
	go l.gc()
	return l
}

func (l *Limiter) Allow(key string) (bool, time.Duration) {
	l.mu.Lock()
	e, ok := l.buckets[key]
	if !ok {
		e = &bucketEntry{tb: NewTokenBucket(l.cap, l.rate)}
		l.buckets[key] = e
	}
	e.lastSeen = time.Now()
	l.mu.Unlock()
	return e.tb.Allow(1)
}

func (l *Limiter) gc() {
	t := time.NewTicker(time.Minute)
	for range t.C {
		cutoff := time.Now().Add(-l.ttl)
		l.mu.Lock()
		for k, e := range l.buckets {
			if e.lastSeen.Before(cutoff) {
				delete(l.buckets, k)
			}
		}
		l.mu.Unlock()
	}
}

HTTP middleware с корректными заголовками:

func RateLimitMiddleware(l *Limiter, limit int, next http.Handler) http.Handler {
	return http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
		key := clientKey(r) // например, из API-key или r.RemoteAddr
		ok, retry := l.Allow(key)
		w.Header().Set("X-RateLimit-Limit", strconv.Itoa(limit))
		if !ok {
			secs := int(retry.Seconds()) + 1
			w.Header().Set("X-RateLimit-Remaining", "0")
			w.Header().Set("Retry-After", strconv.Itoa(secs))
			w.Header().Set("X-RateLimit-Reset", strconv.Itoa(secs))
			http.Error(w, "rate limit exceeded", http.StatusTooManyRequests)
			return
		}
		next.ServeHTTP(w, r)
	})
}

Distributed: Sliding Window Counter на Redis + Lua#

Атомарный Lua-скрипт: считает аппроксимацию по текущему и предыдущему окну, инкрементит текущее при разрешении.

// KEYS[1] = базовый ключ (например "rl:user:42")
// ARGV[1] = limit, ARGV[2] = window_seconds, ARGV[3] = now_ms
const slidingWindowLua = `
local key      = KEYS[1]
local limit    = tonumber(ARGV[1])
local window   = tonumber(ARGV[2]) * 1000   -- в мс
local now      = tonumber(ARGV[3])

local curr_win = math.floor(now / window)
local prev_win = curr_win - 1
local curr_key = key .. ":" .. curr_win
local prev_key = key .. ":" .. prev_win

local curr = tonumber(redis.call("GET", curr_key) or "0")
local prev = tonumber(redis.call("GET", prev_key) or "0")

-- доля предыдущего окна, попадающая в скользящее окно
local elapsed = (now % window) / window
local weighted = prev * (1 - elapsed) + curr

if weighted >= limit then
  -- сколько примерно ждать до освобождения слота
  local reset = window - (now % window)
  return {0, math.floor(reset)}   -- отказ + retry_after_ms
end

-- разрешаем: инкремент текущего окна, TTL = 2 окна (нужно prev на стыке)
redis.call("INCR", curr_key)
redis.call("PEXPIRE", curr_key, window * 2)
local remaining = math.floor(limit - weighted - 1)
return {1, remaining}
`

Использование из Go (github.com/redis/go-redis/v9):

type RedisLimiter struct {
	rdb    *redis.Client
	script *redis.Script
	limit  int
	window time.Duration
}

func NewRedisLimiter(rdb *redis.Client, limit int, window time.Duration) *RedisLimiter {
	return &RedisLimiter{
		rdb:    rdb,
		script: redis.NewScript(slidingWindowLua), // использует EVALSHA с фоллбэком на EVAL
		limit:  limit,
		window: window,
	}
}

func (rl *RedisLimiter) Allow(ctx context.Context, key string) (bool, time.Duration, error) {
	now := time.Now().UnixMilli()
	res, err := rl.script.Run(ctx, rl.rdb,
		[]string{"rl:" + key},
		rl.limit, int(rl.window.Seconds()), now,
	).Int64Slice()
	if err != nil {
		// Политика при недоступности Redis: fail-open (разрешить) либо fail-closed.
		return true, 0, err // здесь fail-open
	}
	allowed := res[0] == 1
	retry := time.Duration(res[1]) * time.Millisecond
	return allowed, retry, nil
}

Замечания по реализации:

• redis.NewScript(...).Run сначала пытается EVALSHA (скрипт закэширован на сервере), при NOSCRIPT — EVAL. Меньше трафика.
• TTL = 2 × window, потому что на стыке нужен счётчик предыдущего окна.
• В Redis Cluster ключи одного лимита (curr_key, prev_key) должны попадать в один слот — используйте hash tag: rl:{user:42}:..., иначе CROSSSLOT ошибка для multi-key операций.

Масштабирование и узкие места#

• Redis — главный боттлнек: каждый запрос = round-trip + EVAL. При 100k RPS один инстанс перегружен.
  • Шардинг по ключу (Redis Cluster, hash tag для co-location ключей одного лимита).
  • Read replicas не помогают — операции пишущие; масштабируем шардами, не репликами.
  • Pipeline/батчинг при множественных лимитах на запрос.
• Local + global hybrid: каждая нода держит локальный token bucket на долю глобального лимита; периодически (например, раз в 1–10 с) синхронизирует фактический расход с Redis и перераспределяет квоту. Снижает round-trips на порядок ценой точности на коротких интервалах.
  • Простейший вариант: глобальный лимит L, N нод → каждой L/N локально. Минус: неравномерная нагрузка между нодами недоиспользует общий лимит.
  • Умный вариант: ноды отчитываются о расходе, координатор/Redis перераспределяет неиспользованную квоту.
• Eventual consistency лимитов: при гибриде глобальный лимит соблюдается приблизительно — на коротком окне возможен перерасход до (число нод × локальный буфер). Для биллинга/жёстких квот это неприемлемо → строгий Redis-путь; для защиты от абуза — допустимо.
• Latency / availability: вынос Redis в тот же AZ, таймаут на EVAL (например 5–10 ms), circuit breaker. Fail-open vs fail-closed — продуктовое решение: для публичного API часто fail-open (доступность важнее), для защиты дорогого ресурса — fail-closed.
• Hot keys: один очень активный ключ (например, шумный клиент) бьёт в один шард → горячий слот. Митигация: локальный pre-throttle на ноде до обращения к Redis.
• Clock skew: sliding window и token bucket зависят от времени. Для Redis-варианта используйте серверное время Redis (TIME) вместо времени клиента, чтобы избежать рассинхрона часов между нодами.

Вопросы на собеседовании#

В: Чем token bucket отличается от leaky bucket и когда выбрать каждый? О: Token bucket пополняется токенами и разрешает burst до capacity — хорош для API, где допустимы всплески при соблюдении среднего rate. Leaky bucket выпускает запросы с постоянной скоростью (выравнивает трафик), запросы буферизуются/отбрасываются — хорош для защиты медленного downstream от всплесков. Для большинства публичных API выбирают token bucket из-за burst-дружелюбности.

В: В чём проблема fixed window counter и как её решает sliding window? О: На стыке окон клиент может отправить полный лимит в конце одного окна и сразу полный в начале следующего — до 2× лимита за короткий промежуток. Sliding window log решает точно (хранит timestamps), sliding window counter — аппроксимацией через взвешивание предыдущего окна, давая O(1) памяти и приемлемую погрешность (<1%).

В: Почему именно Lua-скрипт, а не INCR + проверка в коде? О: Между чтением счётчика и записью в распределённой системе возникает race condition: несколько инстансов прочитают значение ниже лимита и все разрешат запрос. Redis выполняет Lua-скрипт атомарно (single-threaded, без вытеснения), поэтому вся логика «прочитать-вычислить-решить-записать» выполняется как единая неделимая операция в один round-trip.

В: Как считать память и выдержит ли один Redis миллионы ключей? О: Для counter/token-bucket — O(1) на ключ, но с учётом оверхеда Redis-ключа реально ~60–90 B на маленький ключ. 10M ключей ≈ 0.6–0.9 GB. Sliding window log хранит timestamp на запрос — не масштабируется при высоких лимитах. Активных одновременно ключей меньше суточных, а TTL = окно сам чистит мёртвые ключи.

В: Что произойдёт, если Redis недоступен? Какую политику выбрать? О: Это выбор fail-open (пропускать запросы — доступность важнее, риск перегрузки) vs fail-closed (блокировать — защита важнее, риск отказа сервиса). Для публичного API часто fail-open с локальным fallback-лимитом и circuit breaker. Нужно явно проговорить, что rate limiter не должен становиться SPOF.

В: Как масштабировать, когда один Redis не тянет QPS? О: Шардинг по ключу (Redis Cluster), с hash tag для co-location ключей одного лимита в один слот (иначе CROSSSLOT). Реплики не помогают — операции пишущие. Дополнительно — гибрид local+global: локальный токен-бакет на ноде снижает round-trips на порядок ценой точности.

В: Как работает local+global hybrid и какой компромисс по точности? О: Каждая нода держит локальный бакет на долю глобального лимита и периодически синхронизирует расход с центральным стором. Это сокращает обращения к Redis, но даёт eventual consistency: на коротком интервале возможен перерасход до суммы локальных буферов всех нод. Подходит для anti-abuse, не подходит для биллинговых квот.

В: Какие HTTP-заголовки вернуть при превышении и почему важен Retry-After? О: Статус 429, Retry-After (когда повторить — даёт клиенту корректную backoff-стратегию вместо хаотичных ретраев), X-RateLimit-Limit/Remaining/Reset для прозрачности. Без Retry-After клиенты ретраят агрессивно и усугубляют перегрузку.

В: Где разместить rate limiter — gateway, middleware или sidecar? О: Часто комбинация: грубый защитный лимит на edge/gateway (до бизнес-логики, защита от DDoS), точный per-plan/per-endpoint лимит в middleware или sidecar (RLS), где доступен контекст приложения. Client-side — только как вежливость, ему нельзя доверять.

На что копают на senior+#

• Атомарность в распределённой среде: понимает ли кандидат, почему GET+SET ломается и как именно Lua/EVALSHA это решает; что WATCH/MULTI — альтернатива, но дороже.
• Clock skew и источник времени: использование серверного времени Redis (TIME) вместо клиентского, чтобы лимиты не «плыли» при рассинхроне часов между нодами.
• Redis Cluster нюансы: hash tags для co-location, CROSSSLOT при multi-key Lua, почему реплики не масштабируют запись.
• Граница точность/память/латентность: умеет ли осознанно выбрать алгоритм под требования, а не назвать один «правильный».
• Fail-open vs fail-closed как продуктовое, а не техническое решение; rate limiter не должен быть SPOF; circuit breaker и таймауты на backend.
• Hot key / hot shard: один шумный клиент бьёт в один слот; pre-throttle на ноде.
• Eventual consistency границ лимита: честная оценка перерасхода при гибриде и когда это недопустимо (биллинг).
• Утечки памяти: GC простаивающих бакетов in-memory, TTL для Redis-ключей; что будет с памятью при миллионах редких ключей.
• Несколько лимитов сразу (per-second + per-day): как скомпоновать атомарно и эффективно (пайплайн, один Lua на несколько окон).
• Идемпотентность и точность списания: списывать токен до или после обработки; что делать при ошибке upstream (возврат токена?).