Открытое собеседование по System Design

2 апреля 2024 г. · 43 мин. чтения

Сегодня мы разберем реальное собеседование по системному дизайну, в ходе которого интервьюер и кандидат совместно проектируют сервис-ограничитель трафика (rate limiter) — от формулирования требований и выбора алгоритма до приземления на конкретные технологии и обсуждения масштабируемости. Это демонстрация того, как выглядит живой процесс проектирования в условиях собеседования: уточняющие вопросы, компромиссы, анализ плюсов и минусов разных подходов — всё с мгновенной обратной связью и комментариями от обоих участников.

Вопрос 1. Для каких специалистов обычно проводят собеседования по системному дизайну и какую пользу они приносят разработчикам разного уровня?

Таймкод: 00:00:05

Ответ собеседника: Правильный. Собеседования по системному дизайну в основном проводят для мидлов и сеньоров, но они также полезны и джуниорам. Они помогают расширить кругозор, понять как строится архитектура различных систем, изучить практики применимые в разных задачах. Системный дизайн хорош тем, что состоит из блоков, которые можно комбинировать при решении различных задач. Это помогает понять каких знаний не хватает для получения оффера, а на практике мы применяем именно эти решения. Системный дизайн позволяет увидеть ход мыслей человека, какие решения он выбирает и почему.

Правильный ответ:

Собеседования по системному дизайну (System Design Interview) проводятся для разработчиков разного уровня, но глубина и фокус вопросов существенно различаются.

Для кого проводят:

Middle-разработчики (2–5 лет опыта) — основная целевая аудитория. Ожидается умение спроектировать систему средней сложности: выбрать подходящую архитектуру, обосновать выбор базы данных, описать API, рассмотреть базовые компромиссы (consistency vs. availability, latency vs. throughput).
Senior-разработчики (5+ лет опыта) — углублённый системный дизайн с акцентом на масштабирование, отказоустойчивость, распределённые системы, capacity planning, trade-offs на уровне enterprise. Ожидается способность вести диалог, задавать уточняющие вопросы, итеративно улучшать дизайн.
Staff/Principal-разработчики — проектирование систем организационного масштаба, cross-team взаимодействие, техническая стратегия, долгосрочная эволюция архитектуры.
Junior-разработчики — системный дизайн проводится реже, но некоторые компании включают упрощённые вопросы (например, «спроектируй URL-shortener»), чтобы оценить потенциал и базовое понимание архитектурных концепций.

Польза для разработчиков разного уровня:

Для джуниоров — даже подготовка к системному дизайну даёт огромную пользу: понимание того, как компоненты системы взаимодействуют между собой, что такое кэширование, балансировка нагрузки, репликация. Это формирует целостную картину, которая ускоряет профессиональный рост.

Для мидлов — системный дизайн помогает перейти от «писать код по ТЗ» к «понимать, почему система устроена так». Это критический переход: умение видеть систему целиком, оценивать последствия архитектурных решений, обосновывать выбор технологий.

Для сеньоров и выше — системный дизайн становится ежедневной практикой. Собеседование проверяет способность принимать решения в условиях неопределённости, работать с противоречивыми требованиями и коммуницировать сложные технические идеи.

Ключевые навыки, которые проверяет системный дизайн:

Умение декомпозировать сложную задачу на компоненты
Понимание CAP-теоремы, моделей консистентности, паттернов распределённых систем
Способность оценивать объёмы данных, QPS, требования к хранилищу (back-of-the-envelope estimation)
Навык ведения структурированного диалога с интервьюером
Умение делать обоснованные компромиссы, а не искать «единственно правильный ответ»

Системный дизайн — это не про запоминание готовых решений, а про развитие инженерного мышления и способности рассуждать о сложных системах.

Вопрос 2. Какой тип трафика нужно ограничивать при проектировании ограничителя трафика для защиты сервисов от DDoS и снижения нагрузки?

Таймкод: 00:08:57

Ответ собеседника: Правильный. Ограничение трафика нужно на серверном уровне, то есть для межсерверного взаимодействия, чтобы защитить сервисы от слишком большого количества запросов. В ходе уточнения было определено, что в первую очередь нужно ограничивать клиентский трафик.

Правильный ответ:

В реальных системах ограничение трафика (rate limiting) применяется на нескольких уровнях, и выбор зависит от архитектуры и характера угроз.

Основные типы трафика для ограничения:

А. Клиентский трафик (North-South) — это запросы от внешних пользователей и клиентов к API. Это первая линия защиты от DDoS и злоупотреблений. Ограничивается по IP-адресу, API-ключу, пользовательской сессии или токену.

Б. Межсервисный трафик (East-West) — запросы между внутренними сервисами. Ограничение необходимо для предотвращения каскадных сбоев: если один сервис начинает генерировать аномально много запросов (например, из-за бага или retry-шторма), это не должно положить всю систему.

В. Исходящий трафик — ограничение запросов от ваших сервисов к внешним зависимостям (сторонние API, базы данных). Это защищает от случайного сжигания квот и денег.

Приоритет при проектировании:

В первую очередь ограничивается клиентский трафик, так как именно он является основным вектором DDoS-атак и злоупотреблений. Затем — месервисный для обеспечения resilience. Исходящий трафик обычно контролируется на уровне circuit breaker и bulkhead паттернов.

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

Edge/Proxy уровень (Nginx, Envoy, CDN) — для клиентского трафик до попадания в приложение
API Gateway — централизованное ограничение на входе в систему
Уровень сервиса — библиотеки вроде golang.org/x/time/rate для локального ограничения
Распределённый уровень — Redis-based rate limiter для согласованного ограничения между инстансами

Пример реализации на Go с использованием токен-бакета:

package ratelimiter

import (
    "sync"
    "time"
)

type TokenBucket struct {
    rate       float64    // токенов в секунду
    capacity   float64    // максимальный размер бакета
    tokens     float64    // текущее количество токенов
    lastRefill time.Time  // последнее пополнение
    mu         sync.Mutex
}

func NewTokenBucket(rate, capacity float64) *TokenBucket {
    return &TokenBucket{
        rate:       rate,
        capacity:   capacity,
        tokens:     capacity,
        lastRefill: time.Now(),
    }
}

func (tb *TokenBucket) Allow() bool {
    tb.mu.Lock()
    defer tb.mu.Unlock()

    now := time.Now()
    elapsed := now.Sub(tb.lastRefill).Seconds()
    tb.tokens += elapsed * tb.rate
    if tb.tokens > tb.capacity {
        tb.tokens = tb.capacity
    }
    tb.lastRefill = now

    if tb.tokens >= 1 {
        tb.tokens--
        return true
    }
    return false
}

// Распределённый rate limiter на Redis
func RedisRateLimiter(key string, maxRequests int, window time.Duration) (bool, error) {
    // Используем Redis INCR с TTL для скользящего окна
    // или Redis Cell модуль для более точного алгоритма
    // CL.THROTTLE key max_burst count_per_period period [quantity]
    return true, nil
}

Ключевые алгоритмы rate limiting:

Token Bucket — позволяет кратковременные burst'и при сохранении среднего рейта
Leaky Bucket — строго гладкий выходной поток
Fixed Window Counter — простой, но имеет проблему на границах окон
Sliding Window Log — точный, но требует памяти на каждый запрос
Sliding Window Counter — компромисс между точностью и памятью

Вопрос 3. По какому признаку идентифицировать клиентов для ограничения трафика и какую нагрузку система должна выдерживать?

Таймкод: 00:10:26

Ответ собеседника: Неполный. Кандидат хотел бы иметь гибкий подход, но для начала предложил использовать IP-адреса в качестве признака для ограничения трафика с возможностью расширения. Система должна выдерживать примерно 1 миллион активных пользователей в день с устойчивостью к пиковым нагрузкам и DDoS-атакам.

Правильный ответ:

Идентификация клиентов для rate limiting:

Использовать только IP-адрес — это необходимый, но недостаточный подход. В реальных системах применяется многоуровневая идентификация.

Уровни идентификации:

А. IP-адрес — базовый уровень, но имеет ограничения: NAT заставляет множество пользователей иметь один IP, ботнеты могут использовать миллионы IP-адресов. Подходит для грубого ограничения на edge-уровне.

Б. API-ключ / Client ID — для аутентифицированных API-клиентов. Позволяет устанавливать разные лимиты для разных тарифных планов (free tier — 100 req/min, enterprise — 10000 req/min).

В. User ID — для аутентифицированных пользователей. Ограничение на уровне аккаунта предотвращает злоупотребления даже при смене IP.

Г. Комбинированный подход (recommended) — совместное использование нескольких признаков:

type RateLimitKey struct {
    IP        string
    UserID    string
    APIKey    string
    Endpoint  string
}

func (rl *RateLimiter) CheckLimit(key RateLimitKey) (bool, error) {
    // Иерархия проверок: сначала наиболее специфичный ключ
    if key.UserID != "" {
        return rl.check("user:"+key.UserID, userLimit)
    }
    if key.APIKey != "" {
        return rl.check("apikey:"+key.APIKey, apiKeyLimit)
    }
    return rl.check("ip:"+key.IP, ipLimit)
}

Дополнительные техники идентификации:

Fingerprinting — комбинация User-Agent, Accept-Language, TLS fingerprint для выботы клиентов за NAT
Behavioral analysis — анализ паттернов запросов (скорость, последовательность endpoint'ов) для выботы ботов
CAPTCHA challenge — при превышении порога перенаправление на верификацию

Оценка нагрузки для 1 млн DAU:

Для оценки нужно рассчитать реалистичные цифры:

1,000,000 DAU
× 10 запросов в день на пользователя (среднее)
= 10,000,000 запросов/день
÷ 86,400 секунд
≈ 116 RPS среднее

Пиковый коэффициент (обычно 3-10x):
116 × 5 = 580 RPS пик

При DDoS-атаке (100-1000x):
116 × 500 = 58,000 RPS атака

Архитектурные требования к системе:

Нормальный режим: 500-1000 RPS с запасом в 3x → система должна выдерживать ~3000 RPS
Защита от DDoS: способность обнаруживать и фильтровать 50,000+ RPS на уровне edge без влияния на легитимный трафик
Задержка: p99 < 100ms для rate limiting check (иначе сам лимитер становится bottleneck)
Память: для хранения состояния 1 млн активных ключей нужно ~100-500 MB Redis

Capacity planning пример:

type CapacityPlan struct {
    DAU            int     // 1,000,000
    RequestsPerDay int     // 10 per user
    PeakMultiplier float64 // 5x
    DDoSMultiplier float64 // 500x for attack scenario
    
    func (c *CapacityPlan) NormalRPS() float64 {
        return float64(c.DAU*c.RequestsPerDay) / 86400.0
    }
    
    func (c *CapacityPlan) PeakRPS() float64 {
        return c.NormalRPS() * c.PeakMultiplier
    }
    
    func (c *CapacityPlan) TargetCapacity() float64 {
        // Целевая пропускная способность с запасом 3x от пика
        return c.PeakRPS() * 3
    }
}

Рекомендуемые лимиты по уровням:

Уровень	Лимит	Обоснование
IP	100 req/min	Защита от одиночных источников
User	1000 req/min	Разумный лимит для человека
API Key (free)	6000 req/hour	Тарифный план
API Key (enterprise)	100000 req/hour	Премиум клиенты

Вопрос 4. Какой архитектуре должна соответствовать система ограничения трафика, какие требования к латентности, отказоустойчивости и поведению при отклонении запросов?

Таймкод: 00:11:54

Ответ собеседника: Правильный. Система будет распределённой. Латентность ограничителя должна быть низкой, чтобы не влиять на основные запросы. Также система должна быть толерантна к сбоям ограничителя — при его отказе вся система должна продолжать работу. В случае отклонения запроса пользователю давать пояснение.

Правильный ответ:

Распределённая архитектура — единственный правильный выбор для rate limiting в production-системе. Монолитный подход не масштабируется и создаёт single point of failure.

Архитектурные решения:

А. Распределённая архитектура с несколькими уровнями:

Client → CDN/Edge (L1) → API Gateway (L2) → Service Rate Limiter (L3)

Каждый уровень обеспечивает свою гранулярность защиты. Edge — грубая фильтрация DDoS, Gateway — централизованное ограничение, сервисный уровень — точечное ограничение критичных endpoint'ов.

Б. Требования к латентности:

Rate limiting check должен добавлять не более 1-5ms к каждому запросу
p99 latency для rate limiter < 5ms
Использование in-memory кэша для "горячих" ключей без обращения к Redis каждый раз
Асинхронное обновление счётчиков для не-критичных проверок

В. Отказоустойчивость — fail-open vs fail-close:

Это критическое архитектурное решение. Для rate limiter почти всегда выбирается fail-open (при недоступности лимитера — пропускать трафик):

func (rl *RateLimiter) Allow(ctx context.Context, key string) (bool, error) {
    allowed, err := rl.redisClient.Get(ctx, key).Result()
    if err != nil {
        if errors.Is(err, redis.ErrClosed) || errors.Is(err, context.DeadlineExceeded) {
            // Redis недоступен — пропускаем запрос (fail-open)
            // Логируем инцидент для мониторинга
            rl.metrics.Inc("rate_limiter.redis_unavailable")
            return true, nil
        }
        return false, err
    }
    return allowed == "allowed", nil
}

Обоснование fail-open: лучше временно пропустить лишний трафик, чем отказать всем легитимным пользователям. Другие уровни защиты (circuit breaker, bulkhead) справятся с нагрузкой.

Г. Поведение при отклонении запроса:

type RateLimitResponse struct {
    Allowed       bool
    RetryAfter    time.Duration
    Limit         int
    Remaining     int
    ResetTime     time.Time
}

func (rl *RateLimiter) HandleExceeded(w http.ResponseWriter, resp RateLimitResponse) {
    // Устанавливаем стандартные заголовки RFC 6585
    w.Header().Set("X-RateLimit-Limit", strconv.Itoa(resp.Limit))
    w.Header().Set("X-RateLimit-Remaining", "0")
    w.Header().Set("X-RateLimit-Reset", strconv.FormatInt(resp.ResetTime.Unix(), 10))
    w.Header().Set("Retry-After", strconv.Itoa(int(resp.RetryAfter.Seconds())))
    
    w.WriteHeader(http.StatusTooManyRequests) // 429
    
    json.NewEncoder(w).Encode(map[string]interface{}{
        "error":       "rate_limit_exceeded",
        "message":     "Too many requests. Please retry after " + resp.RetryAfter.String(),
        "retry_after": resp.RetryAfter.Seconds(),
    })
}

Стандартные HTTP-заголовки для rate limiting:

X-RateLimit-Limit — максимальное количество запросов в окне
X-RateLimit-Remaining — оставшиеся запросы
X-RateLimit-Reset — время сброса окна (Unix timestamp)
Retry-After — через сколько секунд повторить запрос

Дополнительные требования:

Консистентность: eventual consistency допустима для rate limiting; небольшое превышение лимита (5-10%) — приемлемая цена за производительность
Мониторинг: алерты при высоком проценте rate-limited запросов (>10% от общего трафика может указывать на неправильные лимиты)
Graceful degradation: при перегрузке Redis переключаться на local in-memory rate limiting с менее точными, но всё ещё работающими лимитами

Вопрос 5. Нужно ли масштабирование по регионам и стоит ли использовать готовые решения вместо собственной разработки?

Таймкод: 00:14:59

Ответ собеседника: Правильный. Масштабирование по регионам пока не требуется. Кандидат предложил рассмотреть готовые решения, такие как Cloudflare или Yandex Cloud, которые предоставляют аналогичный функционал. Это может быть дешевле, проще и быстрее, чем разрабатывать собственное решение. Кандидат также отметил важность обсуждения с бизнесом плюсов и минусов каждого подхода.

Правильный ответ:

Региональное масштабирование:

Для системы с 1 млн DAU одном региона обычно достаточно, но нужно заложить архитектуру для будущего расширения.

Когда нужно региональное масштабирование:

Пользователи географически распределены (EU, US, Asia) и latency критичен
Требования к data residency (GDPR, локальные законы)
Более 10 млн DAU с высоким RPS

Архитектура для будущей региональности:

// Дизайн с учётом будущего регионального масштабирования
type RegionalRateLimiter struct {
    local  *LocalRateLimiter   // In-memory для текущего инстанса
    redis  *redis.Client       // Локальный Redis (per-region)
    global *redis.Client       // Глобальный Redis для cross-region синхронизации (опционально)
}

func (r *RegionalRateLimiter) Allow(userID string) bool {
    // Сначала проверяем локально (быстро)
    if !r.local.Allow(userID) {
        return false
    }
    
    // Затем проверяем в региональном Redis
    return r.redis.Allow(userID)
}

Готовые решения vs собственная разработка:

Это классический вопрос build vs buy, и ответ зависит от контекста.

Готрешения (Cloudflare, AWS WAF, Yandex Cloud):

Плюсы	Минусы
Развёртывание за часы	Ограниченная кастомизация
Защита от DDoS из коробки	Зависимость от вендора
Глобальная CDN-сеть	Стоимость растёт с трафиком
Не нужна поддержка	Vendor lock-in
Обновления безопасности	Меньше контроля над логикой

Собственная разработка:

Плюсы	Минусы
Полный контроль над логикой	Нужна команда для поддержки
Кастомные бизнес-правила	Время разработки (2-6 месяцев)
Нет vendor lock-in	Нужно самому бороться с DDoS
Оптимизация под свои нужды	Операционные расходы

Рекомендация для большинства компаний:

Использовать гибридный подход:

Edge-защита (L1): Cloudflare/AWS Shield — для фильтрации DDoS до попадания в вашу инфраструктуру
Application-level rate limiting (L2): собственная разработка — для бизнес-логики (разные лимиты для разных тарифов, пользователей, endpoint'ов)

Обоснование для бизнеса:

Стоимость Cloudflare Pro: ~$20/мес + $0.10/GB
Стоимость собственной разработки: 2 инженера × 3 месяца + $500/мес инфраструктура

Для 1 млн DAU: Cloudflare дешевле в первые 2-3 года
Для 10+ млн DAU: собственное решение может быть выгоднее

Критерии выбора в пользу собственной разработки:

Уникальные бизнес-требования к rate limiting
Нужна интеграция с внутренними системами (billing, analytics)
Достаточная инженерная команда
Долгосрочная стратегия экономии на масштабе

Вопрос 6. Как выглядит верхнеуровневая архитектура системы ограничения трафика и где оптимально разместить ограничитель?

Таймкод: 00:16:32

Ответ собеседника: Правильный. Кандидат предложил разместить ограничитель между клиентом и бэкендом, совместив его с сервисом авторизации. Размещение на стороне клиента небезопасно из-за возможности подделки, а размещение на каждом микросервисе приведёт к неконсистентному состоянию. Оптимальным решением является размещение рядом с авторизацией, где можно проверять токены и ограничивать трафик. В итоге было решено вынести лимитер в отдельный сервис, чтобы не нарушать принцип единственной ответственности.

Правильный ответ:

Верхнеуровневая архитектура:

Оптимальная архитектура — многоуровневая с чётким разделением ответственности:

┌─────────────────────────────────────────────────────────────────┐
│                        CDN / Edge (Cloudflare)                  │
│                    DDoS Protection, WAF Rules                   │
└─────────────────────────────┬───────────────────────────────────┘
                              │
┌─────────────────────────────▼───────────────────────────────────┐
│                         API Gateway                              │
│            Rate Limiter Service (централизованный)               │
│     ┌─────────────┬──────────────────┬──────────────────┐       │
│     │  IP-based   │  User-based      │  API Key-based   │       │
│     │  limiting   │  limiting        │  limiting        │       │
│     └─────────────┴──────────────────┴──────────────────┘       │
└─────────────────────────────┬───────────────────────────────────┘
                              │
┌─────────────────────────────▼───────────────────────────────────┐
│                      Backend Services                            │
│   ┌──────────┐  ┌──────────┐  ┌──────────┐  ┌──────────┐      │
│   │  Auth    │  │  Order   │  │  Payment │  │  User    │      │
│   │ Service  │  │ Service  │  │ Service  │  │ Service  │      │
│   └──────────┘  └──────────┘  └──────────┘  └──────────┘      │
│        (локальные rate limiters для критичных endpoint'ов)      │
└─────────────────────────────────────────────────────────────────┘

Размещение rate limiter — варианты:

А. На стороне клиента — не подходит для защиты, так как клиентский код легко подделать. Может использоваться только как UX-оптимизация (показать пользователю сообщение до отправки запроса).

Б. В каждом микросервисе — обеспечивает точечную защиту, но создаёт проблемы: неконсистентное состояние между инстансами, дублирование логики, сложность управления лимитами.

В. API Gateway / отдельный сервис (рекомендуется) — централизованное управление, единая точка принятия решений, интеграция с Redis для распределённого состояния.

Реализация отдельного rate limiter сервиса на Go:

package main

import (
    "context"
    "encoding/json"
    "net/http"
    "time"

    "github.com/go-redis/redis/v8"
    "golang.org/x/time/rate"
)

type RateLimiterService struct {
    redisClient *redis.Client
    limiters    map[string]*rate.Limiter // локальный кэш для "горячих" ключей
}

type RateLimitRequest struct {
    Key       string `json:"key"`        // user_id, api_key, or ip
    LimitType string `json:"limit_type"` // "user", "api_key", "ip"
}

type RateLimitResponse struct {
    Allowed    bool      `json:"allowed"`
    Limit      int       `json:"limit"`
    Remaining  int       `json:"remaining"`
    ResetAt    time.Time `json:"reset_at"`
    RetryAfter int       `json:"retry_after_seconds,omitempty"`
}

func (s *RateLimiterService) CheckLimit(ctx context.Context, req RateLimitRequest) (*RateLimitResponse, error) {
    limit := s.getLimitForType(req.LimitType)
    window := time.Minute

    // Используем Redis для атомарного инкремента
    pipe := s.redisClient.Pipeline()
    incr := pipe.Incr(ctx, "ratelimit:"+req.Key)
    pipe.Expire(ctx, "ratelimit:"+req.Key, window)
    _, err := pipe.Exec(ctx)
    if err != nil {
        // Fail-open: при ошибке Redis пропускаем запрос
        return &RateLimitResponse{Allowed: true}, nil
    }

    current := incr.Val()
    remaining := int(limit) - int(current)
    if remaining < 0 {
        remaining = 0
    }

    return &RateLimitResponse{
        Allowed:   current <= limit,
        Limit:     limit,
        Remaining: remaining,
        ResetAt:   time.Now().Add(window),
    }, nil
}

func (s *RateLimiterService) getLimitForType(limitType string) int64 {
    switch limitType {
    case "user":
        return 1000 // запросов в минуту
    case "api_key":
        return 10000
    case "ip":
        return 100
    default:
        return 100
    }
}

// HTTP handler для интеграции с API Gateway
func (s *RateLimiterService) ServeHTTP(w http.ResponseWriter, r *http.Request) {
    var req RateLimitRequest
    if err := json.NewDecoder(r.Body).Decode(&req); err != nil {
        http.Error(w, "bad request", http.StatusBadRequest)
        return
    }

    resp, err := s.CheckLimit(r.Context(), req)
    if err != nil {
        http.Error(w, "internal error", http.StatusInternalServerError)
        return
    }

    if !resp.Allowed {
        w.Header().Set("Retry-After", string(rune(resp.RetryAfter)))
        w.WriteHeader(http.StatusTooManyRequests)
    }

    json.NewEncoder(w).Encode(resp)
}

Конфигурация лимитов:

rate_limits:
  ip:
    requests: 100
    window: 1m
  user:
    requests: 1000
    window: 1m
  api_key_free:
    requests: 6000
    window: 1h
  api_key_enterprise:
    requests: 100000
    window: 1h
  # Отдельные лимиты для критичных endpoint'ов
  endpoints:
    /api/v1/login:
      requests: 5
      window: 1m
    /api/v1/password-reset:
      requests: 3
      window: 1h

Ключевые принципы размещения:

Единая точка входа — rate limiter размещается как можно ближе к входу в систему
Близость к авторизации — позволяет использовать уже идентифицированного пользователя
Отдельный сервис — соблюдение SRP, возможность масштабирования независимо
Fail-open — при недоступности rate limiter'а система продолжает работать

Вопрос 7. Какие алгоритмы ограничения трафика существуют и какой лучше выбрать для данной задачи?

Таймкод: 00:22:26

Ответ собеседника: Правильный. Кандидат рассмотрел три алгоритма: Leaky Bucket — очередь с фиксированной скоростью обработки, хорош для фиксированной нагрузки, но плохо справляется с пиками; Token Bucket — фиксированный бакет, который очищается по интервалу, проще в реализации, устойчив к пикам; Sliding Window Log — хранит таймстампы каждого запроса, точнее, но требует больше памяти. Кандидат выбрал Token Bucket как оптимальный вариант по соотношению простоты, скорости работы и устойчивости к пикам.

Правильный ответ:

Основные алгоритмы rate limiting:

1. Fixed Window Counter

Простейший алгоритм: счётчик сбрасывается в начале каждого временного окна.

type FixedWindow struct {
    limit    int
    window   time.Duration
    counters map[string]*windowCounter
}

type windowCounter struct {
    count     int
    windowStart time.Time
}

func (fw *FixedWindow) Allow(key string) bool {
    now := time.Now()
    wc, exists := fw.counters[key]
    
    if !exists || now.Sub(wc.windowStart) >= fw.window {
        fw.counters[key] = &windowCounter{count: 1, windowStart: now}
        return true
    }
    
    if wc.count < fw.limit {
        wc.count++
        return true
    }
    return false
}

Проблема: на границе окон может пропустить до 2x запросов. При лимите 100 req/min и 100 запросах в конце первой минуты + 100 в начале второй = 200 запросов за 2 минуты.

2. Sliding Window Log

Хранит timestamp каждого запроса, проверяет количество запросов в скользящем окне.

type SlidingWindowLog struct {
    limit  int
    window time.Duration
    logs   map[string][]time.Time
}

func (sw *SlidingWindowLog) Allow(key string) bool {
    now := time.Now()
    cutoff := now.Add(-sw.window)
    
    // Очищаем старые записи
    var valid []time.Time
    for _, t := range sw.logs[key] {
        if t.After(cutoff) {
            valid = append(valid, t)
        }
    }
    
    if len(valid) < sw.limit {
        sw.logs[key] = append(valid, now)
        return true
    }
    
    sw.logs[key] = valid
    return false
}

Плюсы: точный. Минусы: O(n) памяти на ключ, где n — количество запросов в окне.

3. Sliding Window Counter

Компромисс между Fixed Window и Sliding Window Log. Использует взвешенное количество запросов из текущего и предыдущего окон.

type SlidingWindowCounter struct {
    limit  int
    window time.Duration
}

func (sw *SlidingWindowCounter) Allow(ctx context.Context, redis *redis.Client, key string) (bool, error) {
    now := time.Now()
    currentWindow := now.Unix() / int64(sw.window.Seconds())
    previousWindow := currentWindow - 1
    
    pipe := redis.Pipeline()
    currentCount := pipe.Get(ctx, fmt.Sprintf("%s:%d", key, currentWindow))
    previousCount := pipe.Get(ctx, fmt.Sprintf("%s:%d", key, previousWindow))
    pipe.Exec(ctx)
    
    curr, _ := currentCount.Int64()
    prev, _ := previousCount.Int64()
    
    // Взвешенный расчёт
    windowProgress := float64(now.Unix()%int64(sw.window.Seconds())) / float64(sw.window.Seconds())
    estimatedCount := float64(prev)*(1-windowProgress) + float64(curr)
    
    return int(estimatedCount) < sw.limit, nil
}

4. Token Bucket

Токены добавляются с фиксированной скоростью. Запрос потребляет токен. Пустой бакет — запрос отклоняется.

type TokenBucket struct {
    rate       float64       // токенов в секунду
    capacity   float64       // максимальный размер бакета
    tokens     float64       // текущее количество токенов
    lastRefill time.Time     // последнее пополнение
    mu         sync.Mutex
}

func NewTokenBucket(rate, capacity float64) *TokenBucket {
    return &TokenBucket{
        rate:       rate,
        capacity:   capacity,
        tokens:     capacity,
        lastRefill: time.Now(),
    }
}

func (tb *TokenBucket) Allow() bool {
    tb.mu.Lock()
    defer tb.mu.Unlock()
    
    now := time.Now()
    elapsed := now.Sub(tb.lastRefill).Seconds()
    tb.tokens += elapsed * tb.rate
    if tb.tokens > tb.capacity {
        tb.tokens = tb.capacity
    }
    tb.lastRefill = now
    
    if tb.tokens >= 1 {
        tb.tokens--
        return true
    }
    return false
}

Плюсы: допускает burst'и до размера бакета, постоянная скорость в долгосрочной перспективе. Минусы: требует синхронизации в распределённой среде.

5. Leaky Bucket

Запросы обрабатываются с фиксированной скоростью, избыток переполняет бакет.

type LeakyBucket struct {
    rate      float64
    capacity  float64
    water     float64
    lastLeak  time.Time
    mu        sync.Mutex
}

func (lb *LeakyBucket) Allow() bool {
    lb.mu.Lock()
    defer lb.mu.Unlock()
    
    now := time.Now()
    elapsed := now.Sub(lb.lastLeak).Seconds()
    lb.water -= elapsed * lb.rate
    if lb.water < 0 {
        lb.water = 0
    }
    lb.lastLeak = now
    
    if lb.water < lb.capacity {
        lb.water++
        return true
    }
    return false
}

Плюсы: стабильная выходная скорость. Минусы: не допускает burst'и, плохо для пользовательских API.

Сравнительная таблица:

Алгоритм	Точность	Память	Burst	Сложность
Fixed Window	Низкая	O(1)	Да	Простой
Sliding Window Log	Высокая	O(n)	Да	Средний
Sliding Window Counter	Средняя	O(1)	Да	Средний
Token Bucket	Средняя	O(1)	Да	Простой
Leaky Bucket	Высокая	O(1)	Нет	Простой

Рекомендация для задачи:

Для API rate limiting с 1 млн DAU оптимальный выбор — Sliding Window Counter на Redis или Token Bucket.

Sliding Window Counter предпочтительнее, потому что:

Не имеет проблемы границ окон Fixed Window
Требует O(1) памяти против O(n) у Sliding Window Log
Легко реализуется атомарно через Redis Lua-скрипты

-- Redis Lua script для атомарного rate limiting
local key = KEYS[1]
local limit = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local now = tonumber(ARGV[3])

local clearBefore = now - window
redis.call('ZREMRANGEBYSCORE', key, 0, clearBefore)
local current = redis.call('ZCARD', key)

if current < limit then
    redis.call('ZADD', key, now, now)
    redis.call('PEXPIRE', key, window)
    return 1
else
    return 0
end

Вопрос 8. Какие технологии использовать для хранения данных ограничителя в распределённой системе и как организовать масштабирование?

Таймкод: 00:33:46

Ответ собеседника: Правильный. Кандидат предложил использовать Redis для хранения данных ограничителя, так как он работает в памяти (in-memory) и обеспечивает высокую скорость. Реляционные базы данных не подходят из-за работы с жёстким диском. Для масштабирования предложил использовать единую точку синхронизации (Redis) для нескольких инстансов рейт-лимитера, что обеспечивает отказоустойчивость. Для деплоя предложил стратегию постепенного перекатывания на новую версию с одной репликой.

Правильный ответ:

Выбор хранилища:

Redis — стандарт де-факто для distributed rate limiting, и вот почему:

Почему Redis:

Sub-millisecond latency — критично, так как rate limiter должен добавлять <5ms к каждому запросу
Атомарные операции — INCR, EVAL (Lua scripts) обеспечивают консистентность без блокировок
Встроенный TTL — автоматическая очистка устаревших ключей
Кластерный режим — горизонтальное масштабирование через Redis Cluster
Поддержка сложных структур — Sorted Sets для sliding window, HyperLogLog для cardinality estimation

Почему не реляционные БД:

Disk I/O добавляет 10-100ms latency — неприемлемо для rate limiting
Нет встроенного TTL для автоматической очистки
Сложнее обеспечить атомарность без транзакций

Почему не in-memory только:

При перезапуске инстанса данные теряются
Нет консистентности между инстансами rate limiter'а

Архитектура хранения:

type RedisRateLimiter struct {
    client     *redis.Client
    limit      int
    window     time.Duration
}

// Lua script для атомарного sliding window rate limiting
const rateLimitScript = `
local key = KEYS[1]
local limit = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local now = tonumber(ARGV[3])

-- Удаляем записи старше окна
redis.call('ZREMRANGEBYSCORE', key, '-inf', now - window)

-- Считаем текущее количество
local current = redis.call('ZCARD', key)

if current < limit then
    -- Добавляем текущий запрос
    redis.call('ZADD', key, now, now .. ':' .. math.random())
    -- Устанавливаем TTL на ключ
    redis.call('PEXPIRE', key, window * 2)
    return {1, limit - current - 1}  -- allowed, remaining
else
    -- Возвращаем время до истечения самого старого запроса
    local oldest = redis.call('ZRANGE', key, 0, 0, 'WITHSCORES')
    local retryAfter = (oldest[2] + window - now) / 1000
    return {0, 0, retryAfter}  -- denied, remaining, retry_after
end
`

func (rl *RedisRateLimiter) Allow(ctx context.Context, key string) (*RateLimitResult, error) {
    now := time.Now().UnixNano() / 1e6 // milliseconds
    
    result, err := rl.client.Eval(ctx, rateLimitScript, []string{key}, 
        rl.limit, 
        rl.window.Milliseconds(),
        now,
    ).Result()
    
    if err != nil {
        // Fail-open при ошибке Redis
        return &RateLimitResult{Allowed: true}, nil
    }
    
    values := result.([]interface{})
    allowed := values[0].(int64) == 1
    
    return &RateLimitResult{
        Allowed:   allowed,
        Remaining: int(values[1].(int64)),
    }, nil
}

Масштабирование Redis:

А. Redis Sentinel — для high availability с автоматическим failover:

┌─────────────┐     ┌─────────────┐     ┌─────────────┐
│  Master     │────▶│  Replica 1  │     │  Replica 2  │
│  (writes)   │     │  (reads)    │     │  (reads)    │
└─────────────┘     └─────────────┘     └─────────────┘
       │
   Sentinel (мониторинг и failover)

Б. Redis Cluster — для горизонтального масштабирования:

// Используем консистентное хеширование для распределения ключей
func (rl *RedisRateLimiter) getShardKey(userID string) string {
    // Все ключи одного пользователя должны попадать на один шард
    // Используем hash tag для этого
    return fmt.Sprintf("ratelimit:{%s}", userID)
}

В. Локальный кэш + Redis — для снижения нагрузки на Redis:

type HybridRateLimiter struct {
    localCache *lru.Cache // локальный LRU кэш для "горячих" ключей
    redis      *redis.Client
    limit      int
    window     time.Duration
}

func (h *HybridRateLimiter) Allow(ctx context.Context, key string) bool {
    // Сначала проверяем локальный кэш
    if val, ok := h.localCache.Get(key); ok {
        count := val.(int)
        if count >= h.limit {
            return false
        }
    }
    
    // Затем проверяем Redis
    allowed := h.redisAllow(ctx, key)
    
    // Обновляем локальный кэш
    if allowed {
        h.localCache.Add(key, h.getCurrentCount(key)+1)
    }
    
    return allowed
}

Стратегия деплоя:

# Kubernetes deployment для rate limiter
apiVersion: apps/v1
kind: Deployment
metadata:
  name: rate-limiter
spec:
  replicas: 3
  strategy:
    type: RollingUpdate
    rollingUpdate:
      maxSurge: 1
      maxUnavailable: 0
  template:
    spec:
      containers:
      - name: rate-limiter
        image: rate-limiter:latest
        resources:
          requests:
            memory: "256Mi"
            cpu: "250m"
          limits:
            memory: "512Mi"
            cpu: "500m"
        readinessProbe:
          httpGet:
            path: /health
            port: 8080
          initialDelaySeconds: 5
          periodSeconds: 10

Мониторинг и метрики:

type RateLimiterMetrics struct {
    allowedTotal      prometheus.Counter
    deniedTotal       prometheus.Counter
    redisLatency      prometheus.Histogram
    redisErrors       prometheus.Counter
    activeKeys        prometheus.Gauge
}

func (m *RateLimiterMetrics) RecordCheck(allowed bool, latency time.Duration) {
    if allowed {
        m.allowedTotal.Inc()
    } else {
        m.deniedTotal.Inc()
    }
    m.redisLatency.Observe(latency.Seconds())
}

Оценка ресурсов для 1 млн DAU:

Redis память: ~500MB для хранения активных ключей (1M ключей × ~500 bytes)
Redis CPU: ~2-4 CPU cores при 1000 RPS
Rate limiter instances: 3-5 реплик для отказоустойчивости
Сеть: ~10 Mbps между rate limiter и Redis

Вопрос 9. Как пояснять клиенту причину отклонения запроса и какие HTTP-коды и заголовки использовать?

Таймкод: 00:36:17

Ответ собеседника: Правильный. Кандидат предложил использовать HTTP-код 429 (Too Many Requests) для пояснения клиенту причины отклонения запроса. Также предложил использовать заголовки для информирования клиента о оставшемся лимите и времени до возможности повторного запроса. Для успешных ответов можно возвращать заголовки с информацией о текущем лимите.

Правильный ответ:

HTTP-коды для rate limiting:

Основной код: 429 Too Many Requests (RFC 6585)

Это стандартный код для указания на превышение rate limit. Клиент должен понять, что нужно подождать перед повторным запросом.

Дополнительные коды:

401 Unauthorized — если rate limit превышен из-за невалидного токена (не раскрываем детали атакующему)
403 Forbidden — если клиент заблокирован на уровне WAF/защиты
503 Service Unavailable — при DDoS-атаке, когда система перегружена (без уточнения причины)

Обязательные заголовки (RFC 6585 + де-факто стандарты):

package ratelimit

import (
    "encoding/json"
    "net/http"
    "strconv"
    "time"
)

type RateLimitInfo struct {
    Limit      int       `json:"limit"`
    Remaining  int       `json:"remaining"`
    ResetAt    time.Time `json:"reset_at"`
    RetryAfter int       `json:"retry_after_seconds"`
    Window     string    `json:"window"`
}

func SetRateLimitHeaders(w http.ResponseWriter, info RateLimitInfo) {
    // Стандартные заголовки (Twitter/GitHub/Stripe конвенция)
    w.Header().Set("X-RateLimit-Limit", strconv.Itoa(info.Limit))
    w.Header().Set("X-RateLimit-Remaining", strconv.Itoa(info.Remaining))
    w.Header().Set("X-RateLimit-Reset", strconv.FormatInt(info.ResetAt.Unix(), 10))
    
    // RFC 6585 заголовок
    if info.RetryAfter > 0 {
        w.Header().Set("Retry-After", strconv.Itoa(info.RetryAfter))
    }
    
    // Дополнительные заголовки для информативности
    w.Header().Set("X-RateLimit-Window", info.Window)
}

func WriteRateLimitExceeded(w http.ResponseWriter, info RateLimitInfo) {
    SetRateLimitHeaders(w, info)
    w.Header().Set("Content-Type", "application/json")
    w.WriteHeader(http.StatusTooManyRequests)
    
    response := map[string]interface{}{
        "error": map[string]interface{}{
            "code":    "rate_limit_exceeded",
            "message": "API rate limit exceeded. Please retry after " + 
                       strconv.Itoa(info.RetryAfter) + " seconds.",
            "details": map[string]interface{}{
                "limit":          info.Limit,
                "remaining":      0,
                "reset_at":       info.ResetAt.Format(time.RFC3339),
                "retry_after":    info.RetryAfter,
                "documentation":  "https://api.example.com/docs/rate-limiting",
            },
        },
    }
    
    json.NewEncoder(w).Encode(response)
}

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

HTTP/1.1 429 Too Many Requests
X-RateLimit-Limit: 1000
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1699900000
X-RateLimit-Window: 60s
Retry-After: 45
Content-Type: application/json

{
    "error": {
        "code": "rate_limit_exceeded",
        "message": "API rate limit exceeded. Please retry after 45 seconds.",
        "details": {
            "limit": 1000,
            "remaining": 0,
            "reset_at": "2024-01-15T10:30:00Z",
            "retry_after": 45,
            "documentation": "https://api.example.com/docs/rate-limiting"
        }
    }
}

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

HTTP/1.1 200 OK
X-RateLimit-Limit: 1000
X-RateLimit-Remaining: 847
X-RateLimit-Reset: 1699900000
X-RateLimit-Window: 60s
Content-Type: application/json

{
    "data": { ... }
}

Middleware для Go:

type RateLimitMiddleware struct {
    limiter *RateLimiterService
}

func (m *RateLimitMiddleware) Handler(next http.Handler) http.Handler {
    return http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
        // Определяем ключ для rate limiting
        key := extractKey(r)
        limitType := extractLimitType(r)
        
        result, err := m.limiter.CheckLimit(r.Context(), key, limitType)
        if err != nil {
            // При ошибке — пропускаем (fail-open)
            next.ServeHTTP(w, r)
            return
        }
        
        // Устанавливаем заголовки для всех ответов
        info := RateLimitInfo{
            Limit:     result.Limit,
            Remaining: result.Remaining,
            ResetAt:   result.ResetAt,
            Window:    "60s",
        }
        SetRateLimitHeaders(w, info)
        
        if !result.Allowed {
            info.RetryAfter = int(time.Until(result.ResetAt).Seconds())
            WriteRateLimitExceeded(w, info)
            return
        }
        
        next.ServeHTTP(w, r)
    })
}

func extractKey(r *http.Request) string {
    // Приоритет: UserID > API Key > IP
    if userID := r.Header.Get("X-User-ID"); userID != "" {
        return "user:" + userID
    }
    if apiKey := r.Header.Get("X-API-Key"); apiKey != "" {
        return "apikey:" + apiKey
    }
    return "ip:" + r.RemoteAddr
}

Рекомендации по информированию клиентов:

Всегда включайте заголовки — даже в успешных ответах, чтобы клиент мог отслеживать свой лимит
Retry-After в секундах — точнее, чем в виде даты, проще для клиентов
Документация — ссылка на страницу с описанием лимитов и политики
Graceful degradation — при приближении к лимиту (remaining < 10%) можно добавлять предупреждение в ответ

Алерты для мониторинга:

// Отслеживаем процент rate-limited запросов
func (m *Metrics) CheckRateLimitHealth() {
    total := m.allowedTotal.Get() + m.deniedTotal.Get()
    if total > 0 {
        deniedRate := m.deniedTotal.Get() / total
        if deniedRate > 0.1 { // Более 10% запросов отклоняется
            alert("High rate limit denial rate: " + strconv.FormatFloat(deniedRate, 'f', 2, 64))
        }
    }
}

Вопрос 10. Как организовать структуру хранения данных в Redis и избежать гонки данных при реализации rate limiting?

Таймкод: 00:38:11

Ответ собеседника: Правильный. Кандидат предложил использовать хэш от IP-адреса в качестве ключа в Redis. IP-адрес можно кодировать по основанию 256 для получения уникального ключа. Для избежания гонки данных предложил использовать модель SET NX (set if not exists) вместо GET-SET, что позволяет сначала установить значение, а потом проверить, укладывается ли запрос в лимит. Это предотвращает ситуацию когда два одновременных запроса проходят проверку, хотя должен пройти только один.

Правильный ответ:

Структура ключей в Redis:

Правильная организация ключей критична для производительности и управляемости.

Иерархия ключей:

ratelimit:{type}:{identifier}:{window}

Примеры:
ratelimit:ip:192.168.1.1:60        # IP-based, 60-секундное окно
ratelimit:user:12345:60            # User-based, 60-секундное окно
ratelimit:apikey:abc123:3600       # API key, часовое окно
ratelimit:endpoint:/api/login:60   # Endpoint-specific limit

Реализация с использованием Redis Hash:

package ratelimit

import (
    "context"
    "fmt"
    "time"

    "github.com/go-redis/redis/v8"
)

type RedisStore struct {
    client *redis.Client
    prefix string
}

func NewRedisStore(client *redis.Client) *RedisStore {
    return &RedisStore{
        client: client,
        prefix: "ratelimit",
    }
}

// Генерация ключа с учётом временного окна
func (rs *RedisStore) makeKey(limitType, identifier string, window time.Duration) string {
    // Округляем до начала текущего окна для фиксированного окна
    windowSeconds := int(window.Seconds())
    now := time.Now().Unix()
    windowStart := now - (now % int64(windowSeconds))
    
    return fmt.Sprintf("%s:%s:%s:%d", rs.prefix, limitType, identifier, windowStart)
}

// Для sliding window используем Sorted Set
func (rs *RedisStore) slidingWindowKey(limitType, identifier string) string {
    return fmt.Sprintf("%s:%s:%s:log", rs.prefix, limitType, identifier)
}

Проблема гонки данных и решения:

Классическая проблема: два параллельных запроса читают счётчик = 99 при лимите 100, оба инкрементируют до 100, оба проходят. Результат: 101 запрос при лимите 100.

Решение 1: Lua-скрипты (атомарность на стороне Redis)

// Атомарный INCR с проверкой лимита через Lua
const incrWithLimitScript = `
local key = KEYS[1]
local limit = tonumber(ARGV[1])
local ttl = tonumber(ARGV[2])

local current = redis.call('INCR', key)
if current == 1 then
    -- Первый запрос в окне, устанавливаем TTL
    redis.call('EXPIRE', key, ttl)
end

if current > limit then
    return 0  -- превышен лимит
end
return 1  -- разрешено
`

func (rs *RedisStore) IncrWithLimit(ctx context.Context, key string, limit int, window time.Duration) (bool, error) {
    result, err := rs.client.Eval(ctx, incrWithLimitScript, []string{key}, 
        limit, 
        int(window.Seconds()),
    ).Int64()
    
    if err != nil {
        return false, err
    }
    return result == 1, nil
}

Решение 2: Redis Transactions (MULTI/EXEC)

func (rs *RedisStore) TransactionalCheck(ctx context.Context, key string, limit int) (bool, error) {
    // Используем WATCH для оптимистичной блокировки
    err := rs.client.Watch(ctx, func(tx *redis.Tx) error {
        current, err := tx.Get(ctx, key).Int64()
        if err != nil && err != redis.Nil {
            return err
        }
        
        if current >= int64(limit) {
            return fmt.Errorf("rate limit exceeded")
        }
        
        // Атомарный инкремент
        _, err = tx.TxPipelined(ctx, func(pipe redis.Pipeliner) error {
            pipe.Incr(ctx, key)
            pipe.Expire(ctx, key, time.Minute)
            return nil
        })
        return err
    }, key)
    
    if err != nil {
        if err.Error() == "rate limit exceeded" {
            return false, nil
        }
        return false, err
    }
    return true, nil
}

Решение 3: SET NX с атомарным инкрементом

// Используем SET NX для инициализации + INCR для подсчёта
const setNxIncrScript = `
local key = KEYS[1]
local limit = tonumber(ARGV[1])
local ttl = tonumber(ARGV[2])

-- Пытаемся установить начальное значение
local setResult = redis.call('SET', key, 0, 'NX', 'EX', ttl)
if setResult then
    -- Ключ был создан, первый запрос
    redis.call('INCR', key)
    return 1
end

-- Ключ уже существует, инкрементим
local current = redis.call('INCR', key)
if current > limit then
    return 0
end
return 1
`

Реализация Sliding Window Log с Sorted Sets:

const slidingWindowScript = `
local key = KEYS[1]
local now = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local limit = tonumber(ARGV[3])
local member = ARGV[4]

-- Удаляем старые записи
redis.call('ZREMRANGEBYSCORE', key, '-inf', now - window)

-- Проверяем количество запросов в окне
local current = redis.call('ZCARD', key)

if current < limit then
    -- Добавляем текущий запрос
    redis.call('ZADD', key, now, member)
    -- Устанавливаем TTL
    redis.call('PEXPIRE', key, window * 2)
    return {1, limit - current - 1}
else
    -- Возвращаем время до истечения самого старого запроса
    local oldest = redis.call('ZRANGE', key, 0, 0, 'WITHSCORES')
    local retryAfter = math.ceil((oldest[2] + window - now) / 1000)
    return {0, 0, retryAfter}
end
`

func (rs *RedisStore) SlidingWindowAllow(ctx context.Context, limitType, identifier string, limit int, window time.Duration) (bool, int, error) {
    key := rs.slidingWindowKey(limitType, identifier)
    now := time.Now().UnixNano() / 1e6 // milliseconds
    member := fmt.Sprintf("%d:%s", now, uuid.New().String())
    
    result, err := rs.client.Eval(ctx, slidingWindowScript, []string{key},
        now,
        window.Milliseconds(),
        limit,
        member,
    ).Result()
    
    if err != nil {
        return false, 0, err
    }
    
    values := result.([]interface{})
    allowed := values[0].(int64) == 1
    remaining := int(values[1].(int64))
    
    return allowed, remaining, nil
}

Сравнение подходов к предотвращению гонки:

Подход	Атомарность	Производительность	Сложность
Lua-скрипты	Да	Высокая	Средняя
WATCH/MULTI	Да	Средняя (retry при конфликте)	Средняя
SET NX + INCR	Да	Высокая	Низкая
GET + INCR	Нет	Высокая	Низкая

Рекомендация: Использовать Lua-скрипты для атомарных операций — это самый надёжный и производительный подход. Redis выполняет Lua-скрипт атомарно, без возможности интерлейва других команд.

Дополнительные оптимизации:

// Pipeline для batch проверок (когда нужно проверить несколько лимитов одновременно)
func (rs *RedisStore) BatchCheck(ctx context.Context, checks []RateLimitCheck) ([]bool, error) {
    pipe := rs.client.Pipeline()
    cmds := make([]*redis.Cmd, len(checks))
    
    for i, check := range checks {
        key := rs.makeKey(check.Type, check.Identifier, check.Window)
        cmds[i] = pipe.Eval(ctx, incrWithLimitScript, []string{key}, check.Limit, int(check.Window.Seconds()))
    }
    
    _, err := pipe.Exec(ctx)
    if err != nil {
        return nil, err
    }
    
    results := make([]bool, len(checks))
    for i, cmd := range cmds {
        val, _ := cmd.Int64()
        results[i] = val == 1
    }
    
    return results, nil
}

Вопрос 11. Как организовать структуру хранения данных в Redis и избежать гонки данных при реализации Token Bucket?

Таймкод: 00:38:11

Правильный ответ:

Этот вопрос уже был подробно рассмотрен в предыдущем ответе. Вот краткое резюме ключевых моментов:

Структура ключей:

ratelimit:{type}:{identifier}:{window}

Примеры: ratelimit:ip:192.168.1.1:60, ratelimit:user:12345:60

Предотвращение гонки данных:

Основные подходы в порядке предпочтительности:

Lua-скрипты — атомарное выполнение на стороне Redis, самый надёжный подход
Redis Transactions (WATCH/MULTI) — оптимистичная блокировка с retry при конфликте
SET NX + INCR — простой и эффективный подход для fixed window

Пример Lua-скрипта для Token Bucket:

local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refillRate = tonumber(ARGV[2])  -- tokens per second
local now = tonumber(ARGV[3])
local requested = tonumber(ARGV[4])

local bucket = redis.call('HMGET', key, 'tokens', 'last_refill')
local tokens = tonumber(bucket[1]) or capacity
local last_refill = tonumber(bucket[2]) or now

-- Пополняем токены
local elapsed = math.max(0, now - last_refill)
local new_tokens = math.min(capacity, tokens + elapsed * refillRate)

if new_tokens >= requested then
    new_tokens = new_tokens - requested
    redis.call('HMSET', key, 'tokens', new_tokens, 'last_refill', now)
    redis.call('EXPIRE', key, math.ceil(capacity / refillRate) * 2)
    return 1
else
    redis.call('HMSET', key, 'tokens', new_tokens, 'last_refill', now)
    return 0
end

Для детального разбора с примерами кода на Go и Redis — см. предыдущий ответ.

Вопрос 12. Какие метрики и мониторинг нужно настроить для системы ограничения трафика?

Таймкод: 00:45:31

Ответ собеседника: Правильный. Кандидат предложил настроить логирование и трейсинг запросов с определённым сэмплированием, бизнес-метрики (процент прошедшего и отклонённого трафика, RPS на каждую ручку), метрики производительности (время проверки лимита), стандартные метрики жизненного цикла приложения. Также упомянул возможность использования Circuit Breaker для защиты бэкенда при отказе лимитера.

Правильный ответ:

Категории метрик для rate limiting системы:

А. Бизнес-метрики (что происходит с трафиком):

type RateLimitMetrics struct {
    // Основные счётчики
    allowedTotal    prometheus.CounterVec // по типу лимита, endpoint
    deniedTotal     prometheus.CounterVec // по типу лимита, endpoint
    
    // Производительность
    checkLatency    prometheus.Histogram  // время проверки лимита
    redisLatency    prometheus.Histogram  // время обращения к Redis
    
    // Состояние системы
    activeKeys      prometheus.Gauge      // количество активных ключей в Redis
    redisErrors     prometheus.Counter    // ошибки Redis
    circuitBreaker  prometheus.Gauge      // состояние circuit breaker
}

func NewMetrics() *RateLimitMetrics {
    return &RateLimitMetrics{
        allowedTotal: *prometheus.NewCounterVec(prometheus.CounterOpts{
            Name: "rate_limit_allowed_total",
            Help: "Total number of allowed requests",
        }, []string{"limit_type", "endpoint"}),
        
        deniedTotal: *prometheus.NewCounterVec(prometheus.CounterOpts{
            Name: "rate_limit_denied_total",
            Help: "Total number of denied requests",
        }, []string{"limit_type", "endpoint"}),
        
        checkLatency: prometheus.NewHistogram(prometheus.HistogramOpts{
            Name:    "rate_limit_check_duration_seconds",
            Help:    "Duration of rate limit check",
            Buckets: prometheus.ExponentialBuckets(0.0001, 2, 15), // 0.1ms to ~3s
        }),
        
        redisLatency: prometheus.NewHistogram(prometheus.HistogramOpts{
            Name:    "rate_limit_redis_duration_seconds",
            Help:    "Duration of Redis operations",
            Buckets: prometheus.ExponentialBuckets(0.0001, 2, 10),
        }),
    }
}

Б. Метрики для алертинга:

# Prometheus alerting rules
groups:
  - name: rate_limit_alerts
    rules:
      # Высокий процент отклонённых запросов
      - alert: HighRateLimitDenialRate
        expr: |
          rate(rate_limit_denied_total[5m]) / 
          (rate(rate_limit_allowed_total[5m]) + rate(rateLimit_denied_total[5m])) > 0.1
        for: 5m
        labels:
          severity: warning
        annotations:
          summary: "High rate limit denial rate (>10%)"
          
      # Rate limiter стал медленным
      - alert: RateLimiterSlow
        expr: histogram_quantile(0.99, rate(rate_limit_check_duration_seconds_bucket[5m])) > 0.01
        for: 2m
        labels:
          severity: critical
        annotations:
          summary: "Rate limiter p99 latency > 10ms"
          
      # Redis недоступен
      - alert: RateLimiterRedisDown
        expr: rate(rate_limit_redis_errors_total[5m]) > 0
        for: 1m
        labels:
          severity: critical
        annotations:
          summary: "Rate limiter Redis errors detected"

В. Структурированное логирование:

func (rl *RateLimiter) CheckWithLogging(ctx context.Context, key string) (bool, error) {
    start := time.Now()
    allowed, err := rl.Check(ctx, key)
    duration := time.Since(start)
    
    log.Info().
        Str("key", key).
        Bool("allowed", allowed).
        Dur("duration_ms", duration).
        Err(err).
        Msg("rate_limit_check")
    
    // Логируем подозрительную активность
    if !allowed {
        log.Warn().
            Str("key", key).
            Str("reason", "rate_limit_exceeded").
            Msg("request_denied")
    }
    
    return allowed, err
}

Г. Ключевые метрики для дашборда:

Метрика	Описание	Пороговое значение
Allowed rate	RPS разрешённых запросов	Базовая линия
Denied rate	RPS отклонённых запросов	< 10% от общего
Denial percentage	Процент отклонённых	< 10% warning, > 25% critical
Check latency p99	Время проверки	< 5ms
Redis latency p99	Время Redis	< 2ms
Active keys	Количество ключей	Мониторинг роста
Redis errors	Ошибки Redis	0

Д. Трейсинг с OpenTelemetry:

func (rl *RateLimiter) CheckWithTracing(ctx context.Context, key string) (bool, error) {
    ctx, span := tracer.Start(ctx, "rate_limiter.check",
        trace.WithAttributes(
            attribute.String("rate_limit.key", key),
            attribute.String("rate_limit.type", "user"),
        ),
    )
    defer span.End()
    
    allowed, err := rl.Check(ctx, key)
    
    span.SetAttributes(
        attribute.Bool("rate_limit.allowed", allowed),
        attribute.Int64("rate_limit.duration_us", time.Since(start).Microseconds()),
    )
    
    if err != nil {
        span.RecordError(err)
    }
    
    return allowed, err
}

Е. Circuit Breaker для защиты:

import "github.com/sony/gobreaker"

var cb = gobreaker.NewCircuitBreaker(gobreaker.Settings{
    Name:        "redis-rate-limiter",
    MaxRequests: 100,
    Interval:    10 * time.Second,
    Timeout:     5 * time.Second,
    ReadyToTrip: func(counts gobreaker.Counts) bool {
        failureRatio := float64(counts.TotalFailures) / float64(counts.Requests)
        return counts.Requests >= 10 && failureRatio >= 0.5
    },
})

func (rl *RateLimiter) CheckWithCircuitBreaker(ctx context.Context, key string) (bool, error) {
    result, err := cb.Execute(func() (interface{}, error) {
        return rl.redisCheck(ctx, key)
    })
    
    if err != nil {
        // Circuit breaker открыт или ошибка Redis
        // Fail-open: пропускаем запрос
        return true, nil
    }
    
    return result.(bool), nil
}

Вопрос 13. Чем Token Bucket отличается от Sliding Window Log и в чём выигрыш по памяти и производительности?

Таймкод: 00:59:01

Ответ собеседника: Правильный. Token Bucket — это простой счётчик по ключу, который занимает фиксированный объём памяти и работает быстро (O(1) для инкремента). Sliding Window Log хранит таймстампы каждого запроса в отсортированном множестве (Sorted Set), что требует больше памяти и сложнее в реализации. Для Sliding Window Log в Redis нужно использовать транзакционные пайплайны с оптимистичными блокировками, что добавляет сложности и может снижать производительность при высокой нагрузке.

Правильный ответ:

Детальное сравнение Token Bucket и Sliding Window Log:

Token Bucket:

Хранит только текущее состояние: количество токенов и время последнего пополнения.

type TokenBucketState struct {
    Tokens     float64   `json:"tokens"`      // 8 bytes
    LastRefill time.Time `json:"last_refill"` // 8 bytes
}
// Итого: ~16 bytes на ключ + overhead Redis

Операции:

INCR/DECR или HMGET/HMSET — O(1)
Одна операция Redis на проверку
Атомарность через Lua-скрипт

Sliding Window Log:

Хранит timestamp каждого запроса в окне.

// Для лимита 1000 req/min при полной нагрузке:
// 1000 timestamps × 8 bytes = 8000 bytes на ключ
// При 1M активных пользователей: 8GB только для rate limiting

Операции:

ZREMRANGEBYSCORE — O(log(N) + M), где M — количество удаляемых элементов
ZCARD — O(1)
ZADD — O(log(N))
Итого: O(log(N)) на проверку

Сравнительная таблица:

Характеристика	Token Bucket	Sliding Window Log
Память на ключ	O(1) ~16 bytes	O(n) ~8n bytes (n = запросы в окне)
Время проверки	O(1)	O(log n)
Точность	Средняя (burst до capacity)	Высокая (точный подсчёт)
Сложность реализации	Низкая	Средняя
Redis операции	1-2 команды	3-4 команды в транзакции
Подходит для	API rate limiting, высокие лимиты	Точное ограничение, низкие лимиты

Пример расчёта памяти:

1,000,000 активных пользователей
Лимит: 1000 req/min

Token Bucket:
  1M × 16 bytes = 16 MB

Sliding Window Log (при 50% заполнении):
  1M × 500 × 8 bytes = 4 GB

Sliding Window Log (при 100% заполнении):
  1M × 1000 × 8 bytes = 8 GB

Когда выбирать каждый алгоритм:

Token Bucket подходит для:

API rate limiting с высокими лимитами (1000+ req/min)
Систем с большим количеством активных ключей
Случаев, где burst-поведение допустимо
Ограниченных ресурсов Redis

Sliding Window Log подходит для:

Точного ограничения (платёжные операции, критичные endpoint'ы)
Низких лимитов (5-100 req/min)
Систем, где важна точность, а не экономия памяти
Аудита и отчётности (можно восстановить историю запросов)

Гибридный подход (рекомендуция):

type HybridRateLimiter struct {
    // Для большинства ключей — Token Bucket (экономия памяти)
    tokenBucket *TokenBucketLimiter
    
    // Для критичных endpoint'ов — Sliding Window Log (точность)
    slidingWindow *SlidingWindowLimiter
}

func (h *HybridRateLimiter) Allow(ctx context.Context, key string, endpoint string) bool {
    // Критичные endpoint'ы проверяем точно
    if isCriticalEndpoint(endpoint) {
        return h.slidingWindow.Allow(ctx, key)
    }
    
    // Остальные — через Token Bucket
    return h.tokenBucket.Allow(ctx, key)
}

Вывод: Для большинства случаев rate limiting в production Token Bucket — оптимальный выбор по соотношению памяти, производительности и сложности. Sliding Window Log стоит использовать только для критичных endpoint'ов с низкими лимитами, где точность важнее ресурсов.

Вопрос 14. Как обеспечить отказоустойчивость системы при падении сервиса ограничителя трафика?

Таймкод: 01:01:06

Ответ собеседника: Правильный. В требованиях было оговорено, что при недоступности ограничителя система должна продолжать работу. Запросы должны проходить на сервис через балансировщик, который находится до лимитера. Если лимитер недоступен, запросы просто идут на бэкенд без ограничений, что обеспечивает отказоустойчивость системы.

Правильный ответ:

Отказоустойчивость rate limiting системы — критический аспект архитектуры.

Принцип fail-open vs fail-close:

Для rate limiter почти всегда выбирается fail-open (при отказе — пропускать трафик). Обоснование: лучше временно пропустить лишний трафик, чем отказать всем легитимным пользователям.

Уровни отказоустойчивости:

А. Отказ отдельного инстанса rate limiter:

// Kubernetes обеспечивает автоматический рестарт
spec:
  replicas: 3
  strategy:
    type: RollingUpdate
    rollingUpdate:
      maxUnavailable: 0  # Никогда не уменьшаем количество реплик

При падении одного инстанса оставшиеся 2 продолжают обслуживать запросы. Load balancer автоматически убирает недоступный инстанс из пула.

Б. Отказ Redis (основное хранилище):

func (rl *RateLimiter) CheckWithFailover(ctx context.Context, key string) (bool, error) {
    // Пробуем основной Redis
    result, err := rl.redisCheck(ctx, key)
    if err == nil {
        return result, nil
    }
    
    // Redis недоступен — переключаемся на локальный rate limiter
    rl.metrics.Inc("rate_limiter.redis_failover")
    return rl.localLimiter.Allow(key), nil
}

// Локальный fallback rate limiter (менее точный, но работает без Redis)
type LocalRateLimiter struct {
    limiters *lru.Cache // LRU кэш для горячих ключей
    limit    int
    window   time.Duration
}

В. Полный отказ rate limiter сервиса:

// API Gateway конфигурация (Envoy/Nginx)
// При недоступности rate limiter — пропускаем запросы

# Envoy rate limit service configuration
rate_limit_service:
  grpc_service:
    envoy_grpc:
      cluster_name: rate_limiter
  timeout: 100ms  # Таймаут на проверку
  # При таймауте или ошибке — пропускаем (fail-open)
  failure_mode_deny: false

Г. Circuit Breaker для защиты бэкенда:

import "github.com/sony/gobreaker"

var cb = gobreaker.NewCircuitBreaker(gobreaker.Settings{
    Name:        "rate-limiter-to-backend",
    MaxRequests: 100,
    Interval:    10 * time.Second,
    Timeout:     5 * time.Second,
    ReadyToTrip: func(counts gobreaker.Counts) bool {
        failureRatio := float64(counts.TotalFailures) / float64(counts.Requests)
        return counts.Requests >= 10 && failureRatio >= 0.5
    },
    OnStateChange: func(name string, from gobreaker.State, to gobreaker.State) {
        log.Warn().
            Str("name", name).
            Str("from", from.String()).
            Str("to", to.String()).
            Msg("circuit_breaker_state_change")
    },
})

Д. Graceful degradation стратегия:

type DegradationLevel int

const (
    LevelNormal DegradationLevel = iota      # Полная функциональность
    LevelRedisDown                           # Redis недоступен, локальный rate limiter
    LevelRateLimiterDown                     # Rate limiter недоступен, пропускаем всё
    LevelEmergency                           # Только критичные endpoint'ы
)

func (rl *RateLimiter) CheckWithDegradation(ctx context.Context, key string) (bool, error) {
    switch rl.currentLevel {
    case LevelNormal:
        return rl.normalCheck(ctx, key)
    case LevelRedisDown:
        return rl.localCheck(key)
    case LevelRateLimiterDown:
        return true, nil // Пропускаем всё
    case LevelEmergency:
        return rl.emergencyCheck(key)
    }
    return true, nil
}

Архитектура для отказоустойчивости:

                    ┌─────────────────────────────────┐
                    │         Load Balancer            │
                    └─────────────┬───────────────────┘
                                  │
              ┌───────────────────┼───────────────────┐
              │                   │                   │
    ┌─────────▼─────────┐ ┌──────▼──────────┐ ┌──────▼──────────┐
    │  Rate Limiter #1  │ │ Rate Limiter #2 │ │ Rate Limiter #3 │
    │  (local cache)    │ │ (local cache)   │ │ (local cache)   │
    └─────────┬─────────┘ └──────┬──────────┘ └──────┬──────────┘
              │                   │                   │
              └───────────────────┼───────────────────┘
                                  │
                    ┌─────────────▼───────────────────┐
                    │         Redis Cluster           │
                    │  (Sentinel/Cluster for HA)      │
                    └─────────────────────────────────┘
                                  │
                    ┌─────────────▼───────────────────┐
                    │        Backend Services         │
                    └─────────────────────────────────┘

Мониторинг отказоустойчивости:

type FailoverMetrics struct {
    redisFailures     prometheus.Counter
    localFallback     prometheus.Counter
    failoverEvents    prometheus.Counter
    currentState      prometheus.Gauge
}

func (m *FailoverMetrics) RecordFailover(from, to string) {
    m.failoverEvents.Inc()
    log.Error().
        Str("from", from).
        Str("to", to).
        Msg("failover_occurred")
}

Алерты:

- alert: RateLimiterFailoverActive
  expr: rate_limiter_failover_events_total[5m] > 0
  labels:
    severity: warning
  annotations:
    summary: "Rate limiter failover detected"

- alert: RateLimiterRedisDown
  expr: rate_limiter_redis_healthy == 0
  for: 30s
  labels:
    severity: critical
  annotations:
    summary: "Rate limiter Redis is down"

Ключевые принципы:

Fail-open по умолчанию — лучше пропустить лишний трафик, чем отказать легитимным пользователям
Многоуровневый fallback — Redis → local cache → пропуск всего
Автоматическое восстановление — при восстановлении Redis плавный переход обратно
Мониторинг — отслеживание всех failover-событий
Graceful degradation — снижение функциональности, а не полный отказ

Вопрос 15. Если вынести ограничитель в отдельный сервис, как лучше организовать его взаимодействие с другими сервисами?

Таймкод: 01:07:16

Ответ собеседника: Правильный. Кандидат пояснил, что если все эндпоинты находятся под авторизацией, то имеет смысл объединить лимитер с сервисом авторизации. Однако если есть публичные ручки без авторизации, то лимитер лучше вынести в отдельный сервис. Объединение сервисов может нарушить принцип единственной ответственности, поэтому в итоге было решено делать отдельный сервис. В текущей компании используется Cloudflare для защиты от DDoS-атак.

Правильный ответ:

Варианты интеграции rate limiter сервиса:

А. Sidecar pattern (per-service):

Каждый сервис имеет локальный rate limiter, который синхронизируется с центральным Redis.

// Встраиваем rate limiter в каждый сервис
type Service struct {
    rateLimiter *SidecarRateLimiter
    // ... остальные зависимости
}

type SidecarRateLimiter struct {
    redis *redis.Client
    local *LocalRateLimiter // Локальный кэш для снижения latency
}

func (s *Service) HandleRequest(ctx context.Context, req Request) error {
    // Проверяем rate limit локально
    if !s.rateLimiter.Allow(ctx, req.UserID) {
        return ErrRateLimitExceeded
    }
    // ... обработка запроса
}

Плюсы: низкий latency, нет дополнительного сетевого хопа. Минусы: сложность обновления конфигурации, дублирование логики.

Б. Centralized rate limiter service:

Отдельный сервис, который вызывается через gRPC/HTTP.

// Rate limiter service с gRPC API
service RateLimiterService {
    rpc CheckLimit(CheckLimitRequest) returns (CheckLimitResponse);
    rpc BatchCheck(BatchCheckRequest) returns (BatchCheckResponse);
}

message CheckLimitRequest {
    string key = 1;
    string limit_type = 2;  // "user", "ip", "api_key"
    string endpoint = 3;
}

message CheckLimitResponse {
    bool allowed = 1;
    int32 remaining = 2;
    int64 reset_at = 3;
    int32 retry_after = 4;
}

Реализация на Go:

// gRPC сервер
type RateLimiterServer struct {
    limiter *RateLimiterService
}

func (s *RateLimiterServer) CheckLimit(ctx context.Context, req *pb.CheckLimitRequest) (*pb.CheckLimitResponse, error) {
    result, err := s.limiter.Check(ctx, req.Key, req.LimitType)
    if err != nil {
        // Fail-open при ошибке
        return &pb.CheckLimitResponse{Allowed: true}, nil
    }
    
    return &pb.CheckLimitResponse{
        Allowed:    result.Allowed,
        Remaining:  int32(result.Remaining),
        ResetAt:    result.ResetAt.Unix(),
        RetryAfter: int32(result.RetryAfter),
    }, nil
}

// gRPC клиент с circuit breaker
type RateLimiterClient struct {
    conn   *grpc.ClientConn
    client pb.RateLimiterServiceClient
    cb     *gobreaker.CircuitBreaker
}

func (c *RateLimiterClient) CheckLimit(ctx context.Context, key, limitType string) (bool, error) {
    result, err := c.cb.Execute(func() (interface{}, error) {
        ctx, cancel := context.WithTimeout(ctx, 50*time.Millisecond)
        defer cancel()
        
        return c.client.CheckLimit(ctx, &pb.CheckLimitRequest{
            Key:       key,
            LimitType: limitType,
        })
    })
    
    if err != nil {
        // Circuit breaker открыт или ошибка — fail-open
        return true, nil
    }
    
    resp := result.(*pb.CheckLimitResponse)
    return resp.Allowed, nil
}

В. API Gateway integration:

Rate limiter интегрируется на уровне API Gateway (Kong, Envoy, AWS API Gateway).

# Kong plugin configuration
plugins:
  - name: rate-limiting
    config:
      minute: 1000
      policy: redis
      redis_host: redis-cluster
      redis_timeout: 2000
      fault_tolerant: true  # fail-open
      hide_client_headers: false

Сравнение подходов:

Подход	Latency	Сложность	Гибкость	Масштабируемость
Sidecar	Низкий	Высокая	Низкая	Высокая
Centralized service	Средний	Средняя	Высокая	Высокая
API Gateway	Низкий	Низкая	Средняя	Зависит от GW

Рекомендуемая архитектура:

┌─────────────────────────────────────────────────────────────────┐
│                         API Gateway                             │
│              (Kong/Envoy — basic rate limiting)                 │
└─────────────────────────────┬───────────────────────────────────┘
                              │
              ┌───────────────┼───────────────┐
              │               │               │
    ┌─────────▼─────────┐ ┌───▼───────────┐ ┌▼────────────────┐
    │   Auth Service    │ │  Rate Limiter │ │  Other Services │
    │                   │ │   Service     │ │                 │
    └───────────────────┘ └───────┬───────┘ └─────────────────┘
                                  │
                        ┌─────────▼─────────┐
                        │   Redis Cluster   │
                        └───────────────────┘

Гибридный подход (рекомендуемый):

API Gateway — базовый rate limiting по IP, DDoS protection
Rate Limiter Service — бизнес-логика (user-based, API key-based limits)
Sidecar — только для критичных сервисов с особыми требованиями к latency

// Клиентская библиотека для интеграции с сервисами
package ratelimit

import (
    "context"
    "time"
    
    "google.golang.org/grpc"
    "github.com/sony/gobreaker"
)

type Client struct {
    grpcClient pb.RateLimiterServiceClient
    cb         *gobreaker.CircuitBreaker
    timeout    time.Duration
}

func NewClient(addr string) (*Client, error) {
    conn, err := grpc.Dial(addr, grpc.WithInsecure())
    if err != nil {
        return nil, err
    }
    
    return &Client{
        grpcClient: pb.NewRateLimiterServiceClient(conn),
        cb: gobreaker.NewCircuitBreaker(gobreaker.Settings{
            Name:        "rate-limiter-client",
            MaxRequests: 100,
            Interval:    10 * time.Second,
            Timeout:     5 * time.Second,
        }),
        timeout: 50 * time.Millisecond,
    }, nil
}

func (c *Client) Check(ctx context.Context, key, limitType string) (bool, error) {
    ctx, cancel := context.WithTimeout(ctx, c.timeout)
    defer cancel()
    
    result, err := c.cb.Execute(func() (interface{}, error) {
        return c.grpcClient.CheckLimit(ctx, &pb.CheckLimitRequest{
            Key:       key,
            LimitType: limitType,
        })
    })
    
    if err != nil {
        // Fail-open
        return true, nil
    }
    
    return result.(*pb.CheckLimitResponse).Allowed, nil
}

Ключевые принципы:

Fail-open на всех уровнях — при любой ошибке пропускаем запрос
Таймауты — 50ms на проверку rate limit, иначе fail-open
Circuit Breaker — защита от каскадных сбоев
Асинхронные обновления — метрики и логи отправлять асинхронно для неблокирующей работы

Вопрос 16. Как Redis справляется с хранением большого количества ключей и какие механизмы масштабирования использовать?

Таймкод: 01:09:55

Ответ собеседника: Правильный. Redis имеет механизм слотов (hash slots), который позволяет равномерно распределить ключи по кластеру. Для IPv6 можно использовать кластер Redis, что решает проблемы с производительностью и объёмами хранения. Token Bucket использует Redis минимально — это просто счётчик по ключу, что значительно проще, чем хранение сложных структур данных.

Правильный ответ:

Масштабирование Redis для rate limiting:

Redis Cluster и Hash Slots:

Redis Cluster использует 16384 hash slots для распределения ключей между нодами.

// Redis Cluster автоматически распределяет ключи по слотам
// CRC16(key) mod 16384

// Hash tags для группировки связанных ключей на одном шарде
func (rl *RateLimiter) makeKey(userID string) string {
    // {user123} — hash tag, гарантирует что все ключи user123 будут на одном шарде
    return fmt.Sprintf("ratelimit:{%s}:tokens", userID)
}

Важно: без hash tags ключи одного пользователя могут оказаться на разных шардах, что сломает атомарность Lua-скриптов.

Архитектура Redis Cluster:

┌─────────────────────────────────────────────────────────────────┐
│                        Redis Cluster                            │
│                                                                 │
│  ┌─────────────────┐  ┌─────────────────┐  ┌─────────────────┐ │
│  │   Master 1      │  │   Master 2      │  │   Master 3      │ │
│  │ Slots: 0-5460   │  │ Slots: 5461-10922│  │ Slots: 10923-16383│
│  └────────┬────────┘  └────────┬────────┘  └────────┬────────┘ │
│           │                    │                    │          │
│  ┌────────▼────────┐  ┌────────▼────────┐  ┌────────▼────────┐ │
│  │   Replica 1A    │  │   Replica 2A    │  │   Replica 3A    │ │
│  └─────────────────┘  └─────────────────┘  └─────────────────┘ │
└─────────────────────────────────────────────────────────────────┘

Оценка ресурсов:

1,000,000 активных ключей (Token Bucket)
~50 bytes на ключ (String с TTL)

Память: 1M × 50 bytes = 50 MB
CPU: ~2-4 cores при 1000 RPS

100,000,000 ключей (Sliding Window Log)
~500 bytes на ключ (Sorted Set с 50 элементами)

Память: 100M × 500 bytes = 50 GB
CPU: ~16-32 cores при 10000 RPS

Конфигурация Redis для rate limiting:

import "github.com/go-redis/redis/v8"

func NewRedisClusterClient() *redis.ClusterClient {
    return redis.NewClusterClient(&redis.ClusterOptions{
        Addrs: []string{
            "redis-node-1:6379",
            "redis-node-2:6379",
            "redis-node-3:6379",
        },
        
        // Пул соединений
        PoolSize:     100,
        MinIdleConns: 20,
        
        // Таймауты
        ReadTimeout:  200 * time.Millisecond,
        WriteTimeout: 200 * time.Millisecond,
        
        // Поведение при ошибках
        MaxRetries:      3,
        MinRetryBackoff: 8 * time.Millisecond,
        MaxRetryBackoff: 512 * time.Millisecond,
        
        // Route reads to replicas
        RouteRandomly: true,
    })
}

Оптимизация памяти в Redis:

// Используем короткие ключи
// Плохо: "rate_limit:user:1234567890:tokens:60"
// Хорошо: "rl:u:123:t"

func (rl *RateLimiter) makeCompactKey(limitType, identifier string, window time.Duration) string {
    return fmt.Sprintf("rl:%s:%s:%d", 
        limitTypeShort(limitType), 
        identifier, 
        int(window.Seconds()))
}

func limitTypeShort(t string) string {
    switch t {
    case "user":
        return "u"
    case "ip":
        return "i"
    case "api_key":
        return "k"
    default:
        return "x"
    }
}

Стратегия TTL для автоматической очистки:

// Устанавливаем TTL с запасом для предотвращения "утечки" ключей
const ttlMultiplier = 2

func (rl *RateLimiter) setWithTTL(ctx context.Context, key string, value interface{}, window time.Duration) error {
    ttl := window * time.Duration(ttlMultiplier)
    return rl.client.Set(ctx, key, value, ttl).Err()
}

Мониторинг использования Redis:

func monitorRedisMemory(client *redis.Client) {
    info, err := client.Info(context.Background(), "memory").Result()
    if err != nil {
        log.Error().Err(err).Msg("failed to get Redis memory info")
        return
    }
    
    // Парсим used_memory_human
    // used_memory_human:50.5M
    log.Info().
        Str("memory_info", info).
        Msg("redis_memory_usage")
}

Масштабирование при росте нагрузки:

Этап	Ключи	Архитектура	Память
Стартап	< 1M	Single Redis	50 MB
Рост	1-10M	Redis Sentinel	500 MB
Масштаб	10-100M	Redis Cluster (3 мастера)	5 GB
Enterprise	100M+	Redis Cluster (6+ мастеров)	50+ GB

Рекомендации:

Используйте Token Bucket вместо Sliding Window Log для экономии памяти (O(1) vs O(n))
Устанавливайте TTL на все ключи для автоматической очистки
Мониторьте used_memory и настройте alerts при достижении 80% от maxmemory
Используйте hash tags для группировки связанных ключей на одном шарде
Тестируйте нагрузку перед деплоем: redis-benchmark для оценки реальной производительности

Вопрос 1. Для каких специалистов обычно проводят собеседования по системному дизайну и какую пользу они приносят разработчикам разного уровня?​

Вопрос 2. Какой тип трафика нужно ограничивать при проектировании ограничителя трафика для защиты сервисов от DDoS и снижения нагрузки?​

Вопрос 3. По какому признаку идентифицировать клиентов для ограничения трафика и какую нагрузку система должна выдерживать?​

Вопрос 5. Нужно ли масштабирование по регионам и стоит ли использовать готовые решения вместо собственной разработки?​

Вопрос 6. Как выглядит верхнеуровневая архитектура системы ограничения трафика и где оптимально разместить ограничитель?​

Вопрос 7. Какие алгоритмы ограничения трафика существуют и какой лучше выбрать для данной задачи?​

Вопрос 8. Какие технологии использовать для хранения данных ограничителя в распределённой системе и как организовать масштабирование?​

Вопрос 9. Как пояснять клиенту причину отклонения запроса и какие HTTP-коды и заголовки использовать?​

Вопрос 10. Как организовать структуру хранения данных в Redis и избежать гонки данных при реализации rate limiting?​

Вопрос 11. Как организовать структуру хранения данных в Redis и избежать гонки данных при реализации Token Bucket?​

Вопрос 12. Какие метрики и мониторинг нужно настроить для системы ограничения трафика?​

Вопрос 13. Чем Token Bucket отличается от Sliding Window Log и в чём выигрыш по памяти и производительности?​

Вопрос 14. Как обеспечить отказоустойчивость системы при падении сервиса ограничителя трафика?​

Вопрос 15. Если вынести ограничитель в отдельный сервис, как лучше организовать его взаимодействие с другими сервисами?​

Вопрос 16. Как Redis справляется с хранением большого количества ключей и какие механизмы масштабирования использовать?​

Вопрос 1. Для каких специалистов обычно проводят собеседования по системному дизайну и какую пользу они приносят разработчикам разного уровня?

Вопрос 2. Какой тип трафика нужно ограничивать при проектировании ограничителя трафика для защиты сервисов от DDoS и снижения нагрузки?

Вопрос 3. По какому признаку идентифицировать клиентов для ограничения трафика и какую нагрузку система должна выдерживать?

Вопрос 5. Нужно ли масштабирование по регионам и стоит ли использовать готовые решения вместо собственной разработки?

Вопрос 6. Как выглядит верхнеуровневая архитектура системы ограничения трафика и где оптимально разместить ограничитель?

Вопрос 7. Какие алгоритмы ограничения трафика существуют и какой лучше выбрать для данной задачи?

Вопрос 8. Какие технологии использовать для хранения данных ограничителя в распределённой системе и как организовать масштабирование?

Вопрос 9. Как пояснять клиенту причину отклонения запроса и какие HTTP-коды и заголовки использовать?

Вопрос 10. Как организовать структуру хранения данных в Redis и избежать гонки данных при реализации rate limiting?

Вопрос 11. Как организовать структуру хранения данных в Redis и избежать гонки данных при реализации Token Bucket?

Вопрос 12. Какие метрики и мониторинг нужно настроить для системы ограничения трафика?

Вопрос 13. Чем Token Bucket отличается от Sliding Window Log и в чём выигрыш по памяти и производительности?

Вопрос 14. Как обеспечить отказоустойчивость системы при падении сервиса ограничителя трафика?

Вопрос 15. Если вынести ограничитель в отдельный сервис, как лучше организовать его взаимодействие с другими сервисами?

Вопрос 16. Как Redis справляется с хранением большого количества ключей и какие механизмы масштабирования использовать?