Senior Go Interview Prep - Core Go: https://go.vbloher.org/docs/01-core-go/ - Механика defer в Go: https://go.vbloher.org/docs/01-core-go/defer/ - Встраивание структур и интерфейсов (Embedding): https://go.vbloher.org/docs/01-core-go/embedding/ - Ошибки в Go: error, wrapping, errors.Is/As/Join: https://go.vbloher.org/docs/01-core-go/errors/ - Дженерики в Go (1.18+): https://go.vbloher.org/docs/01-core-go/generics/ - Интерфейсы в Go: https://go.vbloher.org/docs/01-core-go/interfaces/ - Устройство map в Go: https://go.vbloher.org/docs/01-core-go/maps/ - panic / recover: механика, раскрутка стека и runtime-паники: https://go.vbloher.org/docs/01-core-go/panic-recover/ - Указатели в Go: https://go.vbloher.org/docs/01-core-go/pointers/ - Рефлексия в Go (reflect): https://go.vbloher.org/docs/01-core-go/reflection/ - Внутреннее устройство слайсов в Go: https://go.vbloher.org/docs/01-core-go/slices/ - Строки, руны и байты в Go: https://go.vbloher.org/docs/01-core-go/strings-runes-bytes/ - Система типов Go: defined types, alignment, memory layout: https://go.vbloher.org/docs/01-core-go/type-system/ - Concurrency: https://go.vbloher.org/docs/02-concurrency/ - sync/atomic: https://go.vbloher.org/docs/02-concurrency/atomic/ - Буферизованные vs небуферизованные каналы: https://go.vbloher.org/docs/02-concurrency/buffered-unbuffered/ - Канал vs Mutex: когда что выбрать: https://go.vbloher.org/docs/02-concurrency/channel-vs-mutex/ - Каналы: устройство hchan: https://go.vbloher.org/docs/02-concurrency/channels/ - Утечки горутин, дедлоки, livelock, starvation: https://go.vbloher.org/docs/02-concurrency/common-leaks-deadlocks/ - sync.Cond: https://go.vbloher.org/docs/02-concurrency/cond/ - context: https://go.vbloher.org/docs/02-concurrency/context/ - Горутины: жизненный цикл, стоимость, стек: https://go.vbloher.org/docs/02-concurrency/goroutines-lifecycle/ - sync.Mutex и sync.RWMutex: https://go.vbloher.org/docs/02-concurrency/mutex-rwmutex/ - sync.Once: https://go.vbloher.org/docs/02-concurrency/once/ - Паттерны конкурентности: https://go.vbloher.org/docs/02-concurrency/patterns/ - Race Detector (гонки данных и -race): https://go.vbloher.org/docs/02-concurrency/race-detector/ - Планировщик GMP: https://go.vbloher.org/docs/02-concurrency/scheduler-gmp/ - select: https://go.vbloher.org/docs/02-concurrency/select/ - sync.WaitGroup: https://go.vbloher.org/docs/02-concurrency/waitgroup/ - Runtime и память: https://go.vbloher.org/docs/03-runtime-memory/ - Паттерны аллокаций и снижение давления на GC: https://go.vbloher.org/docs/03-runtime-memory/allocation-patterns/ - Escape Analysis: когда переменная убегает в кучу: https://go.vbloher.org/docs/03-runtime-memory/escape-analysis/ - Сборщик мусора Go: concurrent tri-color mark-sweep: https://go.vbloher.org/docs/03-runtime-memory/gc/ - Тюнинг GC: GOGC и GOMEMLIMIT: https://go.vbloher.org/docs/03-runtime-memory/gogc-gomemlimit/ - GOMAXPROCS: параллелизм планировщика и проблема контейнеров: https://go.vbloher.org/docs/03-runtime-memory/gomaxprocs/ - Утечки горутин (goroutine leaks): https://go.vbloher.org/docs/03-runtime-memory/goroutine-leaks/ - Утечки памяти в Go (несмотря на GC): https://go.vbloher.org/docs/03-runtime-memory/memory-leaks/ - Модель памяти Go (Go Memory Model): happens-before и синхронизация: https://go.vbloher.org/docs/03-runtime-memory/memory-model/ - pprof: профилирование CPU, памяти и блокировок в Go: https://go.vbloher.org/docs/03-runtime-memory/pprof/ - Execution Tracer и runtime/trace: тайминги вместо агрегатов: https://go.vbloher.org/docs/03-runtime-memory/runtime-tracing/ - Стек vs Куча: где живут данные в Go: https://go.vbloher.org/docs/03-runtime-memory/stack-vs-heap/ - Тестирование: https://go.vbloher.org/docs/04-testing/ - testify, assert/require и golden files: https://go.vbloher.org/docs/04-testing/assertions-testify/ - Бенчмарки в Go: https://go.vbloher.org/docs/04-testing/benchmarks/ - Покрытие, -race и флаки-тесты: https://go.vbloher.org/docs/04-testing/coverage-race/ - Нативный fuzzing в Go (1.18+): https://go.vbloher.org/docs/04-testing/fuzzing/ - Интеграционные тесты, testcontainers-go, TestMain: https://go.vbloher.org/docs/04-testing/integration-testcontainers/ - Моки, стабы и тестируемость: https://go.vbloher.org/docs/04-testing/mocks/ - Table-driven тесты, subtests и параллельность: https://go.vbloher.org/docs/04-testing/table-driven/ - Backend: https://go.vbloher.org/docs/05-backend/ - Аутентификация и авторизация: AuthN/AuthZ, сессии vs токены, RBAC/ABAC, API keys, mTLS, секреты: https://go.vbloher.org/docs/05-backend/auth-authz/ - Graceful Shutdown HTTP/gRPC сервера в Go: https://go.vbloher.org/docs/05-backend/graceful-shutdown/ - gRPC: типы RPC, интерсепторы, контекст, метаданные, error model: https://go.vbloher.org/docs/05-backend/grpc/ - JWT (JSON Web Token): https://go.vbloher.org/docs/05-backend/jwt/ - Middleware-паттерн в Go: https://go.vbloher.org/docs/05-backend/middleware/ - net/http: Server, Handler, ServeMux, таймауты, Client и контекст: https://go.vbloher.org/docs/05-backend/net-http/ - OAuth2: роли, grant types, OIDC, токены и типовые ошибки: https://go.vbloher.org/docs/05-backend/oauth2/ - OpenAPI/Swagger, code generation, contract-first vs code-first, валидация: https://go.vbloher.org/docs/05-backend/openapi/ - Protocol Buffers: схемы, wire format, эволюция и совместимость: https://go.vbloher.org/docs/05-backend/protobuf/ - REST: принципы, версионирование, идемпотентность, статусы, пагинация, ошибки: https://go.vbloher.org/docs/05-backend/rest/ - Сети и протоколы: https://go.vbloher.org/docs/06-networking/ - Пулы соединений: http.Transport, БД, утечки: https://go.vbloher.org/docs/06-networking/connection-pooling/ - DNS: записи, резолвинг, кэширование, DNS в Go: https://go.vbloher.org/docs/06-networking/dns/ - Версии HTTP: 1.1, 2, 3: https://go.vbloher.org/docs/06-networking/http-versions/ - TCP/IP: модель, транспорт и что важно бэкендеру: https://go.vbloher.org/docs/06-networking/tcp-ip/ - TLS: handshake, сертификаты, mTLS, производительность: https://go.vbloher.org/docs/06-networking/tls/ - UDP и надёжность поверх UDP: https://go.vbloher.org/docs/06-networking/udp/ - WebSocket: upgrade, фреймы, масштабирование: https://go.vbloher.org/docs/06-networking/websocket/ - Базы данных: https://go.vbloher.org/docs/07-databases/ - Пул соединений к PostgreSQL в Go: database/sql, pgx, pgxpool, PgBouncer: https://go.vbloher.org/docs/07-databases/connection-pooling-pgx/ - Взаимоблокировки (Deadlocks) в PostgreSQL: https://go.vbloher.org/docs/07-databases/deadlocks/ - Индексы в PostgreSQL: https://go.vbloher.org/docs/07-databases/indexes/ - Уровни изоляции транзакций в PostgreSQL: https://go.vbloher.org/docs/07-databases/isolation-levels/ - MVCC в PostgreSQL: версии строк, видимость, VACUUM и bloat: https://go.vbloher.org/docs/07-databases/mvcc/ - Обзор NoSQL и Redis: https://go.vbloher.org/docs/07-databases/nosql-redis/ - Партиционирование таблиц в PostgreSQL: https://go.vbloher.org/docs/07-databases/partitioning/ - Архитектура PostgreSQL: https://go.vbloher.org/docs/07-databases/postgresql-architecture/ - Планирование и оптимизация запросов в PostgreSQL: https://go.vbloher.org/docs/07-databases/query-planning/ - Репликация в PostgreSQL: https://go.vbloher.org/docs/07-databases/replication/ - Шардирование (горизонтальное масштабирование): https://go.vbloher.org/docs/07-databases/sharding/ - Транзакции в PostgreSQL и Go (database/sql, pgx): https://go.vbloher.org/docs/07-databases/transactions/ - Распределённые системы: https://go.vbloher.org/docs/08-distributed-systems/ - CAP теорема: https://go.vbloher.org/docs/08-distributed-systems/cap-theorem/ - Circuit Breaker: https://go.vbloher.org/docs/08-distributed-systems/circuit-breaker/ - Консенсус и Raft: репликация состояния в присутствии отказов: https://go.vbloher.org/docs/08-distributed-systems/consensus-raft/ - Модели согласованности: https://go.vbloher.org/docs/08-distributed-systems/consistency/ - Гарантии доставки сообщений: at-most-once / at-least-once / exactly-once: https://go.vbloher.org/docs/08-distributed-systems/delivery-guarantees/ - Eventual Consistency: https://go.vbloher.org/docs/08-distributed-systems/eventual-consistency/ - Идемпотентность в распределённых системах: https://go.vbloher.org/docs/08-distributed-systems/idempotency/ - Apache Kafka: https://go.vbloher.org/docs/08-distributed-systems/kafka/ - Transactional Outbox: https://go.vbloher.org/docs/08-distributed-systems/outbox/ - RabbitMQ: AMQP 0-9-1, маршрутизация, надёжность доставки и сравнение с Kafka: https://go.vbloher.org/docs/08-distributed-systems/rabbitmq/ - Ретраи: backoff, jitter, budgets и идемпотентность: https://go.vbloher.org/docs/08-distributed-systems/retries/ - Saga Pattern: https://go.vbloher.org/docs/08-distributed-systems/saga/ - Observability: https://go.vbloher.org/docs/09-observability/ - Grafana: https://go.vbloher.org/docs/09-observability/grafana/ - Метрики: RED, USE, Golden Signals: https://go.vbloher.org/docs/09-observability/metrics/ - OpenTelemetry: https://go.vbloher.org/docs/09-observability/opentelemetry/ - Prometheus: https://go.vbloher.org/docs/09-observability/prometheus/ - SLI / SLO / SLA: https://go.vbloher.org/docs/09-observability/slo-sli/ - Структурированное логирование (slog): https://go.vbloher.org/docs/09-observability/structured-logging/ - Distributed Tracing: https://go.vbloher.org/docs/09-observability/tracing/ - System Design: https://go.vbloher.org/docs/10-system-design/ - Analytics Pipeline: https://go.vbloher.org/docs/10-system-design/analytics-pipeline/ - Chat System: https://go.vbloher.org/docs/10-system-design/chat/ - Фреймворк System Design интервью: https://go.vbloher.org/docs/10-system-design/framework/ - Notification Service: https://go.vbloher.org/docs/10-system-design/notification-service/ - Order Service: https://go.vbloher.org/docs/10-system-design/order-service/ - Payment Service: https://go.vbloher.org/docs/10-system-design/payment-service/ - Rate Limiter: https://go.vbloher.org/docs/10-system-design/rate-limiter/ - URL Shortener: https://go.vbloher.org/docs/10-system-design/url-shortener/ - DevOps: https://go.vbloher.org/docs/11-devops/ - CI/CD: пайплайны, стадии, стратегии деплоя: https://go.vbloher.org/docs/11-devops/cicd/ - Облака (AWS / GCP) для бэкендера: https://go.vbloher.org/docs/11-devops/cloud-aws-gcp/ - Docker для Go-разработчика: https://go.vbloher.org/docs/11-devops/docker/ - GitHub Actions и GitLab CI: https://go.vbloher.org/docs/11-devops/github-gitlab-ci/ - Kubernetes для Go-разработчика: https://go.vbloher.org/docs/11-devops/kubernetes/ - Terraform / Infrastructure as Code: https://go.vbloher.org/docs/11-devops/terraform/ - Алгоритмы: https://go.vbloher.org/docs/12-algorithms/ - Типовые алгоритмические задачи и паттерны: https://go.vbloher.org/docs/12-algorithms/common-problems/ - Асимптотическая сложность (Big-O): https://go.vbloher.org/docs/12-algorithms/complexity/ - Структуры данных в Go: https://go.vbloher.org/docs/12-algorithms/data-structures/ - Специфика live-coding на Go: https://go.vbloher.org/docs/12-algorithms/go-specifics/ - Behavioral: https://go.vbloher.org/docs/13-behavioral/ - Конфликты, разногласия и работа со стейкхолдерами: https://go.vbloher.org/docs/13-behavioral/conflicts/ - Как проходит senior-интервью: этапы, оценка, оффер: https://go.vbloher.org/docs/13-behavioral/interview-flow/ - Лидерство и менторство: https://go.vbloher.org/docs/13-behavioral/leadership-mentoring/ - Типовые поведенческие вопросы для Senior: https://go.vbloher.org/docs/13-behavioral/senior-questions/ > Модуль: System Design · Уровень: Senior ## TL;DR Сервис превращает длинный URL в короткий ключ (`tiny.cc/aZ3kP9`) и редиректит обратно. Это классический **read-heavy** сервис с соотношением чтения к записи ~100:1, где главные проблемы не в редиректе как таковом, а в: - **Генерации уникальных коротких ключей** без коллизий и без single point of contention. Два рабочих подхода: `hash(url) + truncate` (просто, но коллизии) и `counter + base62` (без коллизий, но нужен распределённый монотонный счётчик). - **Редиректе 301 vs 302** — это не косметика: выбор напрямую ломает или сохраняет аналитику и нагрузку на бэкенд. - **Латентности чтения** — путь редиректа должен быть `O(1)` lookup из кэша/CDN, в идеале не доходя до основной БД. Senior-ответ строится вокруг трёх осей: как раздать диапазоны ключей между инстансами без гонок, почему 302 (а не 301) при наличии аналитики, и как удержать p99 редиректа в единицах миллисекунд при масштабе. ## Требования ### Функциональные - `POST /shorten` — принять длинный URL, вернуть короткий. Идемпотентность: один и тот же URL может (опционально) маппиться в один ключ. - `GET /{key}` — редирект на оригинальный URL. - Custom alias: пользователь хочет `tiny.cc/my-brand`. - TTL / expiration: ссылка живёт N дней или вечно. - Аналитика: счётчик кликов, гео, referrer, user-agent. ### Нефункциональные - **Высокая доступность** на чтении. Редирект не должен падать — упавший редирект ломает уже опубликованные ссылки. - **Низкая латентность**: p99 редиректа < 10 мс (хорошая цель — единицы мс через CDN/кэш). - **Уникальность ключей** гарантирована (или коллизии разрешаются детерминированно). - **Непредсказуемость** (по требованию безопасности) — последовательные ключи `1,2,3` дают enumeration-атаку и утечку метрик роста. Иногда это требование, иногда наоборот не важно. - **Масштабируемость** по хранилищу на годы вперёд. - **Durability**: потеря маппинга = битая публичная ссылка навсегда. ## Оценки нагрузки (back-of-the-envelope) Зафиксируем входные числа и посчитаем. **Записи (создание ссылок):** - 500 млн новых URL в месяц. - В секунду: `500M / (30 · 24 · 3600) ≈ 500M / 2.6M ≈ 200 writes/s`. **Чтения (редиректы):** соотношение **100:1**. - `200 · 100 = 20 000 reads/s`. - Пиковый трафик считаем ×2–3: проектируем под **~50k reads/s**. **Storage за 5 лет:** - За 5 лет записей: `500M · 12 · 5 = 30 млрд URL`. - На одну запись: ключ (~8 байт) + длинный URL (~500 байт) + метаданные (created_at, expiry, owner, counter) (~100 байт) ≈ **600 байт**. - Округлим до ~500 байт чистого URL-маппинга → `30B · 500 байт = 15 ТБ` (только маппинг). С метаданными и индексами реалистично **~20–30 ТБ**. Это не помещается в один узел → шардинг. **Длина ключа (base62 — `[a-z A-Z 0-9]`, 62 символа):** Нужно вместить минимум 30 млрд ключей. Считаем степени 62: | Длина | Комбинаций (62^n) | |------:|------------------:| | 5 | ~916 млн (916M) | | 6 | ~56,8 млрд (5.68 · 10^10) | | 7 | ~3,5 трлн (3.52 · 10^12) | | 8 | ~218 трлн (2.18 · 10^14) | - **6 символов** уже дают 56.8 млрд — покрывают 30 млрд с запасом. - На senior-уровне берут **7 символов** как запас на рост, неравномерность шардов, custom alias и чтобы не упереться при удвоении трафика. 7 символов = 3.5 трлн вариантов — хватит на десятилетия. (Bitly исторически использует 6–7.) **Bandwidth:** - Write: `200/s · 600 байт ≈ 120 КБ/с` — пренебрежимо мало. - Read (редирект, ответ = заголовок Location, ~500 байт): `50 000/s · 500 байт ≈ 25 МБ/с` исходящего. Тоже скромно — узкое место не bandwidth, а QPS/латентность lookup'а. **Cache memory (правило 80/20):** - 80% запросов идут к 20% «горячих» ссылок. Дневной объём чтений: `20 000/s · 86 400 ≈ 1.7 млрд чтений/день`. - Кэшируем 20% дневного уникального трафика. Прикидка: ~170 млн горячих записей · ~600 байт ≈ **~100 ГБ**. На практике кэшируют меньше — top-N самых горячих, **десятки ГБ Redis-кластера** покрывают подавляющую долю редиректов. Вывод: сервис не CPU- и не bandwidth-bound. Он **latency- и lookup-bound на чтении** и **contention-bound на генерации ключей при записи**. ## Архитектура ``` ┌──────────┐ GET /{key} │ CDN / │ (кэш редиректов на edge, ─────────────────────▶│ edge │ короткий TTL для 301) └────┬─────┘ │ miss ┌──────────▼───────────┐ POST /shorten │ API Gateway / LB │ ───────────────▶│ (rate limit, auth) │ └─────┬───────────┬─────┘ │ │ write path │ │ read path ▼ ▼ ┌──────────────┐ ┌──────────────┐ │ Write svc │ │ Read svc │ │ + KGS клиент │ │ (редирект) │ └───┬──────┬───┘ └───┬───────┬──┘ │ │ │ │ range req │ │ write │ lookup│ miss ▼ ▼ ▼ ▼ ┌──────────┐ ┌────────────────────────┐ │ KGS │ │ Redis cache (hot) │ │ (Key Gen │ └───────────┬────────────┘ │ Service)│ │ miss └────┬─────┘ ▼ │ ┌────────────────────┐ │ диапазоны│ Sharded KV / NoSQL │ ▼ │ (Cassandra/Dynamo/ │ ┌─────────┐ │ sharded Postgres) │ │ Counter │ │ key -> long_url │ │ store │ └────────────────────┘ │(ZK/Redis)│ └─────────┘ │ async ▼ ┌────────────────────┐ │ Analytics pipeline │ │ (Kafka -> OLAP) │ └────────────────────┘ ``` **Компоненты:** - **CDN / edge** — кэширует ответы редиректа близко к пользователю. Эффективен только для 301 (см. ниже); для 302 + аналитики обычно отключается или ставится очень короткий TTL. - **API Gateway / LB** — терминация TLS, rate limiting (защита от abuse-создания ссылок), аутентификация для приватных операций. - **Read service** — горячий путь. Логика тривиальна: lookup ключа → `Location`. Должен масштабироваться горизонтально и быть stateless. - **Write service** — валидирует URL, запрашивает ключ у KGS, пишет в БД. - **KGS (Key Generation Service)** — централизованно выдаёт пулы заранее сгенерированных уникальных ключей рабочим инстансам диапазонами. Снимает гонки на генерации. - **Counter store** — источник монотонной последовательности (ZooKeeper / Redis `INCRBY` / отдельная БД с range-allocation). - **Cache (Redis)** — LRU/LFU поверх БД для горячих ключей. - **Storage** — шардированное KV: ключ → (URL, метаданные). - **Analytics pipeline** — асинхронный сбор кликов через очередь (Kafka), агрегация в OLAP/ClickHouse, чтобы не нагружать горячий путь редиректа. ## Ключевые решения и trade-offs ### 1. Генерация ключей **Подход A: hash + truncate (`MD5`/`SHA-256`).** `hash(long_url)` → берём первые N байт → base62-кодируем → берём первые 6–7 символов. ```go func hashKey(url string) string { sum := sha256.Sum256([]byte(url)) // берём первые 6 байт (48 бит), кодируем в base62 n := binary.BigEndian.Uint64(append([]byte{0, 0}, sum[:6]...)) return base62Encode(n)[:7] } ``` - ✅ Stateless, не нужен счётчик, дедупликация «бесплатно» (одинаковый URL → одинаковый ключ). - ❌ **Коллизии**: разные URL → одинаковый префикс хэша. Вероятность растёт по парадоксу дней рождения. На 7 символах base62 (3.5 · 10^12) при 30 млрд ключей вероятность хотя бы одной коллизии уже заметна. Нужна проверка-вставка: при коллизии — добавить соль/инкремент и перехэшировать (read-modify-write, замедляет запись). - ❌ Один и тот же URL у двух пользователей даёт один ключ — теряем персональную аналитику, если она нужна. **Подход B: counter + base62.** Глобальный монотонный счётчик; каждое значение кодируем в base62. Уникальность гарантирована конструктивно, коллизий нет. ```go const alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" func base62Encode(n uint64) string { if n == 0 { return string(alphabet[0]) } var buf []byte for n > 0 { buf = append(buf, alphabet[n%62]) n /= 62 } // reverse for i, j := 0, len(buf)-1; i < j; i, j = i+1, j-1 { buf[i], buf[j] = buf[j], buf[i] } return string(buf) } func base62Decode(s string) (uint64, error) { var n uint64 for i := 0; i < len(s); i++ { idx := strings.IndexByte(alphabet, s[i]) if idx < 0 { return 0, fmt.Errorf("invalid char %q", s[i]) } n = n*62 + uint64(idx) } return n, nil } ``` - ✅ Без коллизий, короткие ключи, простая декодировка обратно в счётчик. - ❌ Последовательные ключи **предсказуемы** → enumeration-атака и утечка темпа роста. Митигация: перемешать пространство (умножение на простое число по модулю 62^L — обратимая перестановка), либо XOR/Feistel-шифрование счётчика перед кодированием, либо чередование цифр. - ❌ Главная проблема — **где взять монотонный счётчик распределённо**. **Распределённый счётчик / range allocation.** Если каждый инстанс делает `INCR` в общий Redis на каждую запись — Redis становится bottleneck'ом и SPOF. Решение — **выдавать диапазоны**: - Инстанс запрашивает блок, например `[1 000 000, 1 001 000)` — 1000 ключей одним атомарным `INCRBY 1000`. - Внутри блока инкрементит локально, без сети. Запрашивает новый блок, когда текущий исчерпан. - ✅ Снижает нагрузку на счётчик в 1000×, нет гонок (атомарность `INCRBY`). - ❌ При рестарте инстанса остаток блока «теряется» (gap'ы в последовательности) — это нормально, ключи не обязаны быть плотными. Варианты источника диапазонов: - **ZooKeeper** — раздаёт непересекающиеся диапазоны через znode-counters; сильная консистентность, но операционно тяжёл. - **Redis `INCRBY`** — просто и быстро; нужна репликация/persistence, чтобы не выдать диапазон дважды после сбоя. - **БД-секвенс с range allocation** (паттерн Hi/Lo) — таблица `counters`, `UPDATE ... RETURNING` забирает блок. **KGS (Key Generation Service).** Альтернатива онлайн-генерации: **офлайн** заранее сгенерировать все возможные ключи и сложить в таблицу `unused_keys`. Рабочие инстансы забирают пачки ключей. - ✅ Генерация уходит с горячего пути; гарантированно уникальные, можно заранее перемешать для непредсказуемости. - ✅ Простой read service, никакой математики в рантайме. - ❌ KGS — SPOF (нужна реплика standby). Concurrency: два инстанса не должны взять один ключ → KGS держит две таблицы/флаги `used/unused` и помечает выданные атомарно. - ❌ Хранилище ключей: 3.5 трлн ключей по 7 байт — много; на практике генерируют не всё пространство, а большой пул и пополняют фоном. ### 2. Редирект 301 vs 302 — и влияние на аналитику - **301 Moved Permanently** — браузер и промежуточные кэши/CDN **запоминают** редирект и в следующий раз идут на целевой URL напрямую, **не обращаясь к нашему серверу**. - ✅ Минимальная нагрузка на бэкенд, минимальная латентность для пользователя. - ❌ **Аналитика ломается**: повторные клики не доходят до нас, счётчик кликов занижен. Изменить целевой URL задним числом сложно — у клиентов закэширован старый редирект. - **302 Found (temporary)** — браузер **каждый раз** спрашивает наш сервер. - ✅ **Каждый клик виден** → точная аналитика. Можно менять целевой URL, A/B-тестировать, отзывать ссылку. - ❌ Каждый редирект бьёт в наш бэкенд → выше нагрузка, нужен агрессивный кэш. **Senior-вывод:** если есть требование аналитики (а в URL shortener оно почти всегда есть) — **302**. 301 выбирают только когда аналитика не нужна и важна разгрузка/латентность. Компромисс: 302 + асинхронная запись клика в Kafka, чтобы горячий путь оставался быстрым; аналитику не считаем синхронно. ### 3. Выбор storage - Доступ — **point lookup по ключу** (`key -> value`), без сложных join/range-сканов. Это идеальный кейс для **KV / wide-column NoSQL**: Cassandra, DynamoDB, ScyllaDB. Линейное горизонтальное масштабирование, шардинг по ключу из коробки, высокая доступность (AP). - **Sharded PostgreSQL/MySQL** допустимо, если нужны транзакции (например, атомарность custom alias) и команда сильнее в SQL; шардим по хэшу ключа. - Custom alias и проверка уникальности требуют read-before-write — в Cassandra используем lightweight transactions (`IF NOT EXISTS`, Paxos) или отдельную strongly-consistent таблицу для alias. ### 4. Custom alias - Пользователь задаёт ключ сам → нужно проверить, что он свободен (`INSERT IF NOT EXISTS`). - Держать в том же keyspace, что и сгенерированные ключи, но генерация должна **избегать** диапазона, который могут занять алиасы (например, алиасы только с определённой длиной/префиксом, либо проверка занятости при выдаче из KGS). - Валидация: длина, запрещённые слова, reserved-пути (`/api`, `/login`). ## Масштабирование и узкие места - **Шардинг БД.** Шардим по самому ключу (его хэшу). Range-based шардинг даст hot-шарды (новые ключи идут в один диапазон), поэтому **hash-based / consistent hashing** — чтобы запись и чтение распределялись равномерно. Consistent hashing упрощает добавление узлов без полного решардинга. - **Кэш Redis.** LRU/LFU поверх БД. Cache-aside: read service сначала идёт в Redis, при miss — в БД и заполняет кэш. TTL согласуем с expiration ссылок. Кэш-кластер шардируем; реплики для доступности. - **CDN.** Только для 301-сценария — кэширует редирект на edge, разгружая origin полностью. Для 302 практически бесполезен (короткий/нулевой TTL). - **Hot links** — вирусная ссылка может дать 100k+ req/s на один ключ. - Эта запись гарантированно в Redis и реплицируется на read-реплики/несколько кэш-узлов, чтобы распределить нагрузку (избежать hot-key в одном Redis-шарде). - Локальный in-process кэш (на read service, маленький TTL) поглощает шквал к одному ключу без сетевого хопа. - Для 302 — асинхронная аналитика обязательна, иначе горячая ссылка завалит счётчик-апдейтами синхронный путь. - **Узкие места по приоритету:** 1. Генерация ключей (contention) → решается range allocation / KGS. 2. Latency lookup на чтении → кэш + локальный кэш + read-реплики. 3. Hot key в кэше → репликация горячих ключей, in-process слой. 4. Аналитические апдейты → асинхронный pipeline (Kafka), батчинг счётчиков. - **Очистка expired-ссылок** — ленивое удаление при чтении (если expired — 404 и удалить) + фоновый GC-джоб; полный скан 30 млрд строк дорог, поэтому используем TTL в самой БД (Cassandra TTL / Dynamo TTL). ## Вопросы на собеседовании **В:** Сколько символов base62 нужно, чтобы закодировать 30 млрд URL, и почему берут 7? **О:** 62^6 ≈ 56.8 млрд — формально хватает на 30 млрд. Но берут 7 (62^7 ≈ 3.5 трлн) как запас на рост, неравномерность шардов, custom alias и удвоение трафика. Запас в длину дешевле, чем миграция пространства ключей. **В:** 301 или 302 для редиректа и как это влияет на аналитику? **О:** 302, если нужна аналитика: браузер при 302 каждый раз обращается к нам, поэтому каждый клик виден и целевой URL можно менять. 301 кэшируется браузером/CDN, разгружает бэкенд и снижает латентность, но повторные клики не доходят — аналитика занижается, и старый редирект «застревает» в клиентских кэшах. **В:** hash+truncate или counter+base62? Чем плох каждый? **О:** hash проще и stateless, даёт бесплатную дедупликацию, но коллизии (парадокс дней рождения) требуют проверки и пересчёта при вставке. counter не даёт коллизий, но порождает предсказуемые последовательные ключи (enumeration, утечка темпа роста) и требует распределённого монотонного счётчика. **В:** Как сделать счётчик распределённым, не превратив его в SPOF/bottleneck? **О:** Range allocation: инстанс одним атомарным `INCRBY N` забирает блок из N ключей и инкрементит локально без сети, новый блок — когда исчерпан. Источник — Redis/ZooKeeper/БД-секвенс (Hi/Lo). Снижает нагрузку на счётчик в N раз; gap'ы при рестарте допустимы. **В:** Зачем нужен KGS и в чём его сложности? **О:** KGS офлайн-генерирует пул уникальных (можно заранее перемешанных) ключей в таблицу unused и раздаёт инстансам пачками — генерация уходит с горячего пути, read service тривиален. Сложности: KGS — SPOF (нужен standby), concurrency-выдача (атомарно помечать ключи used, чтобы два инстанса не взяли один), объём хранилища ключей. **В:** Какую БД выбрать и как шардировать? **О:** Доступ — point lookup key→value, поэтому KV/wide-column NoSQL (Cassandra/DynamoDB/Scylla): горизонтальное масштабирование, шардинг и HA из коробки. Шардим по хэшу ключа (hash/consistent hashing), а не по диапазону — иначе новые ключи дают hot-шард. SQL допустим, если нужны транзакции для alias. **В:** Вирусная ссылка даёт 100k req/s на один ключ — что делаешь? **О:** Гарантированно держу её в кэше и реплицирую на несколько кэш-узлов/read-реплик, чтобы не было hot-key в одном Redis-шарде; ставлю локальный in-process кэш на read service для поглощения шквала без сетевого хопа; аналитику пишу асинхронно (Kafka, батч-инкременты), чтобы счётчик кликов не валил горячий путь. **В:** Как сделать ключи непредсказуемыми, оставаясь на counter-подходе? **О:** Применить обратимую перестановку пространства: умножение счётчика на простое число по модулю 62^L, либо Feistel/блочное шифрование значения счётчика перед base62-кодированием. Маппинг остаётся биективным (декодируется обратно), но соседние счётчики дают «разбросанные» ключи. **В:** Как обрабатывать expiration на 30 млрд записей? **О:** TTL в самой БД (Cassandra/Dynamo TTL) + ленивое удаление при чтении (expired → 404 + delete) + лёгкий фоновый GC. Полный скан таблицы для очистки слишком дорог. ## На что копают на senior+ - **Точная математика коллизий.** Не «коллизии маловероятны», а парадокс дней рождения: при пространстве `M = 62^L` ожидаемое число вставок до первой коллизии ~`√M`. Для 7 символов `√(3.5·10^12) ≈ 1.9 млн` — то есть коллизии начнутся раньше, чем кажется, и стратегия их разрешения (rehash с солью, retry) обязана быть в дизайне. - **Консистентность range allocation при сбоях.** Что если инстанс взял блок и упал? (gap'ы — ок). Что если Redis не персистил `INCRBY` и после restart выдал блок повторно? → нужен AOF/fsync или ZooKeeper с кворумом; обсуждение durability счётчика отличает senior. - **Idempotency записи.** Повтор `POST /shorten` (retry клиента) не должен плодить разные ключи на один URL — нужен dedup-ключ/идемпотентность, либо принять, что один URL = много ключей. - **Почему именно 302, а не «301 для скорости».** Кандидат должен понимать, что 301 кэшируется необратимо у клиента и ломает возможность отозвать/изменить ссылку — это не только про аналитику, но и про управляемость. - **Hot-key в кэше vs hot-shard в БД** — разные проблемы с разными решениями (репликация горячего ключа vs ребалансировка шардов). Путать их — красный флаг. - **Асинхронная аналитика и потеря событий.** At-least-once в Kafka → дубли кликов → дедуп/идемпотентные счётчики или принятие неточности. Trade-off точность vs латентность горячего пути. - **Безопасность.** Open redirect (валидация схемы/домена), abuse (rate limit на создание, фишинг-ссылки → проверка по threat-feeds), enumeration через последовательные ключи. - **Single-region vs multi-region.** Где живёт счётчик/KGS при гео-распределении? Один глобальный счётчик = латентность записи через океан; решение — региональные диапазоны (каждому региону свой непересекающийся поддиапазон счётчика).