Спроектируйте сервис коротких ссылок.

Требования (уточнить у интервьюера): создать короткую ссылку, редирект по ней, свой алиас, срок жизни, статистика переходов. Нефункциональные: редирект быстрый (< 50 мс) и очень доступный, коды не угадываются подряд, ссылки живут годами.

Оценка: 100 млн новых ссылок в месяц ≈ 40 в секунду (пик ×3 — 120); чтений в 100 раз больше — 4000/с, пик 12 000/с. Запись ~500 байт — 50 ГБ в месяц, ~3 ТБ за 5 лет. Нагрузка умеренная; основная трудность — чтения и доступность.

API:

• POST /api/links {url, alias?, ttl?} → {code, short_url};
• GET /{code} → 302 Location: <url> (или 301);
• GET /api/links/{code}/stats.

Генерация кода:

• base62 от уникального числа — счётчик в базе или распределённый генератор. Чтобы не ходить в общий счётчик на каждую ссылку, сервис берёт диапазон (по 10 000 номеров) и выдаёт из памяти. Чтобы коды не шли подряд (перебор чужих ссылок), число перемешивают обратимой функцией (умножение на нечётную константу по модулю, Feistel);
• хеш от URL (MD5/SHA → первые 7 символов base62) — одинаковые URL дают один код (дедупликация), но обрезанный хеш даёт коллизии: при вставке проверять и при конфликте добавлять соль;
• случайный код с проверкой уникальности — просто, при заполнении пространства коллизии учащаются. Фильтр Блума ускоряет проверку.

Хранилище: таблица code → url, owner, created, expires. Доступ только по ключу — key-value или PostgreSQL с шардированием по коду (хешем). Реплики для чтения.

Чтение:

• кэш (Redis или локальный) code → url: популярные ссылки следуют Ципфу, hit ratio высокий; отрицательное кэширование для несуществующих кодов;
• CDN или edge-функция для самых горячих;
• 301 или 302: 301 браузер кэширует навсегда — меньше нагрузки, но нельзя поменять цель и посчитать повторные клики; обычно 302.

Статистика — событие клика в Kafka асинхронно (не задерживая редирект), агрегирование в ClickHouse; уникальные — HyperLogLog.

Остальное: проверка URL на фишинг и вредоносность при создании, лимиты создания на пользователя, удаление истёкших (TTL в хранилище или фоновая чистка), защита алиасов от занятых слов.

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def encode(n: int) -> str:
    s = ""
    while n:
        n, r = divmod(n, 62)
        s = ALPHABET[r] + s
    return s or "0"

def scramble(n: int) -> int:                      # обратимое перемешивание, чтобы коды не шли подряд
    return (n * 0x5DEECE66D) % 62**7

encode(scramble(1_000_001))                       # 7 символов, соседние номера дают несвязанные коды