Модуль: 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 символов.

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. Уникальность гарантирована конструктивно, коллизий нет.

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 при гео-распределении? Один глобальный счётчик = латентность записи через океан; решение — региональные диапазоны (каждому региону свой непересекающийся поддиапазон счётчика).
Backward Rate Limiter DevOps Forward