Как спроектировать сокращатель ссылок на system design интервью

Коротко

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

Общая схема таких секций описана в статье про подходы к проектированию систем. Здесь та же схема применена к одной задаче от начала до конца.

Как распределить время

Примерная раскладка на 45 минут. Если секция длиннее, лишнее время уходит в углубление.

Частая ошибка: двадцать минут сравнивать хеш-функции и не дойти до чтения, хотя именно там 99% нагрузки. Если чувствуете, что застряли, скажите это вслух и предложите двигаться дальше. Про такие приёмы есть отдельная статья: как думать вслух на интервью.

Шаг 1. Требования

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

Нефункциональные требования предложите сами и попросите подтвердить:

• Редирект доступен 99,99% времени, это около 53 минут простоя в год.
• Создание ссылки доступно 99,9%, это около 8,8 часа в год. Сломанное создание неприятно, сломанный переход ломает чужие сайты и рассылки.
• p99 редиректа внутри нашей инфраструктуры не больше 50 мс.
• Созданная ссылка не теряется и никогда не начинает вести на другой адрес.

Сразу разделите согласованность. Уникальность ключа строгая: два разных URL под одним ключом недопустимы. Чтение может отставать на секунды, но свежая ссылка должна открываться сразу, к этому вернёмся в разделе про кэш.

Не делаем: предпросмотр страниц, команды и роли, биллинг. Сказать это вслух полезно: вы показываете, что контролируете объём работы.

Шаг 2. Оценка нагрузки

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

• 10 млн новых ссылок в день.
• На одну созданную ссылку приходится 100 переходов.
• Храним 5 лет.
• Запись занимает 500 байт вместе с индексами. Большую часть даёт сам URL.
• Пик в 3 раза выше среднего.
• Ответ с редиректом весит 500 байт.
• Событие аналитики весит 200 байт.
• В кэше держим 20% суточных запросов: правило 80/20, грубо, но для начала годится.

Сама по себе таблица ничего не даёт. Интервьюеру важно, какие выводы вы из неё сделали:

1. Чтений в 100 раз больше. Всю архитектуру строим вокруг пути чтения.
2. Запись не проблема. 350 вставок в секунду в пике держит один нормальный сервер БД. Распределённая запись с первого дня здесь не нужна.
3. 9 ТБ не петабайты. Это 1,8 ТБ в год, несколько шардов закроют пять лет.
4. Сеть не узкое место. 139 Мбит/с в пике можно больше не обсуждать.
5. Аналитика в 40 раз тяжелее основных данных. 73 ТБ против 1,8 ТБ в год. Хранить её в той же базе нельзя.

Длина ключа

$62^6 \approx 5{,}7 \cdot 10^{10}, \qquad 62^7 \approx 3{,}5 \cdot 10^{12}$

По счёту хватило бы и шести символов: 18,25 млрд занимают 32% пространства. Но берём семь, и причин две.

Первая: рост. Если нагрузка вырастет в 10 раз, шесть символов кончатся через полтора года, а семи при текущей скорости хватит почти на тысячу лет.

Вторая: плотность. При заполнении 32% случайно придуманный ключ попадает в живую ссылку примерно в одном случае из трёх. При семи символах заполнение 0,5%, то есть один случай из двухсот.

Шаг 3. API

Эндпоинтов нужно немного. Создание:

POST /api/v1/links
Authorization: Bearer <api-key>
Content-Type: application/json

{
  "long_url": "https://example.com/some/very/long/path",
  "custom_alias": "summer-sale",
  "expires_at": "2027-01-01T00:00:00Z"
}

HTTP/1.1 201 Created
Content-Type: application/json

{
  "key": "summer-sale",
  "short_url": "https://short.example/summer-sale",
  "expires_at": "2027-01-01T00:00:00Z"
}

Остальное можно записать таблицей:

Три вещи, которые стоит упомянуть при создании ссылки:

• Проверка URL. Разрешаем только http и https, иначе сервис начнёт раздавать javascript:-ссылки. Ограничиваем длину и не принимаем адреса на собственный домен, чтобы не получать циклы редиректов.
• Зарезервированные слова. api, admin, login и другие пути сайта нельзя занять как свой адрес.
• Фишинг. Сокращатели любят злоумышленники. Лимиты на создание и проверка по чёрным спискам нужны с первой версии.

Шаг 4. Схема данных

CREATE TABLE links (
  short_key   VARCHAR(16) COLLATE "C" PRIMARY KEY,
  long_url    TEXT        NOT NULL,
  user_id     BIGINT,
  created_at  TIMESTAMPTZ NOT NULL DEFAULT now(),
  expires_at  TIMESTAMPTZ
);

CREATE INDEX links_user_idx ON links (user_id, created_at DESC);
CREATE INDEX links_expires_idx ON links (expires_at) WHERE expires_at IS NOT NULL;

Запрос здесь один, поиск по первичному ключу. Запоминается то, чего в схеме нет:

• Нет UNIQUE(long_url). Индекс по длинным строкам дорогой, а дедупликация не входила в требования.
• Нет счётчика кликов. Об этом в разделе про аналитику.
• Ключ чувствителен к регистру. Это классическая ловушка. В base62 aB и Ab разные ключи, но коллации MySQL по умолчанию регистр не различают, и база сочтёт их дубликатом. В MySQL нужна бинарная коллация, в PostgreSQL сравнение и так учитывает регистр, а COLLATE "C" делает его побайтовым.

SQL или NoSQL? Доступ здесь чисто ключ-значение, связей нет, поэтому подойдёт и DynamoDB, и Cassandra, и PostgreSQL с шардированием. По цифрам нагрузка спокойная, так что я бы начал с PostgreSQL и репликами чтения: уникальность и транзакции из коробки, и все их умеют эксплуатировать. Если интервьюер добавит ещё пару порядков, перейду на KV-хранилище. Важно назвать критерий перехода, а не название базы.

Шардирование. Шард выбираем по хешу от short_key. Шардирование по диапазонам для последовательных ключей плохой выбор: вся запись пойдёт в последний шард. Минус у хеша один: запрос «все ссылки пользователя» теперь обходит все шарды. Решается отдельной таблицей user_id -> short_key, которая шардируется по пользователю и пополняется асинхронно.

Схема на доске

Создание:
клиент -> балансировщик -> API -> блок ключей в памяти
                            |
                            +-> БД (основная) -> кэш

Переход:
браузер -> балансировщик -> сервис редиректов -> кэш
                                |                 | промах
                                |                 v
                                |                реплика БД
                                v
                         очередь событий -> обработчик -> аналитическая БД

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

Серверов редиректа нужно немного. Если считать, что один держит 5 тыс. RPS (это допущение, его надо проверять нагрузочным тестом), на пик в 35 тыс. уйдёт 7 штук и запас, около 10.

Шаг 5. Генерация ключей

Это центральная часть секции. Нужны ключи уникальные, короткие, не перебираемые подряд и без общей точки конкуренции. Есть три варианта.

Base62

Сначала про кодирование, оно нужно в любом варианте. Алфавит состоит из цифр и букв в двух регистрах. Base64 не подходит из-за + и /, которые в URL приходится экранировать или заменять.

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
BASE = len(ALPHABET)
INDEX = {ch: i for i, ch in enumerate(ALPHABET)}


def encode(n: int) -> str:
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0:
        return ALPHABET[0]
    chars = []
    while n:
        n, rem = divmod(n, BASE)
        chars.append(ALPHABET[rem])
    return "".join(reversed(chars))


def decode(key: str) -> int:
    n = 0
    for ch in key:
        n = n * BASE + INDEX[ch]
    return n


print(encode(100_000_000_000))  # 1L9zO9O
print(decode("ZZZZZZZ"))  # 3521614606207

Если ссылки будут набирать руками, убирают похожие символы 0, O, I, l. Получается base58, и ключ становится чуть длиннее.

Вариант 1. Счётчик и base62

Берём растущее число и кодируем. Коллизий нет по построению, а ключи получаются самыми короткими из возможных.

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

CREATE SEQUENCE link_id_blocks INCREMENT BY 10000;

-- Сервер получает начало блока и сам расходует 10 000 номеров
SELECT nextval('link_id_blocks');

Посчитаем для 10 серверов в пике, то есть по 35 RPS на каждый:

• Блока хватает почти на 5 минут.
• Сервис счётчика получает запрос примерно раз в 30 секунд на весь кластер.
• Если счётчик упал, серверы работают на остатках блока. Новый блок лучше забирать заранее.
• Если сервер упал, его блок пропал. Даже если каждый из 10 серверов падает раз в день, за 5 лет потеряется 182,5 млн номеров, это 0,005% пространства. Можно не жалеть.

Вторая проблема в предсказуемости. Ключи abc1, abc2, abc3 перебираются простым циклом и заодно показывают конкурентам ваш объём. Это не абстрактная угроза: в исследовании Gone in Six Characters авторы перебирали короткие ссылки и находили через них файлы в OneDrive и маршруты в Google Maps.

Простое решение: взаимно однозначно отобразить номер в другое число в том же диапазоне.

KEY_LEN = 7
SPACE = 62**KEY_LEN
MULTIPLIER = 2_176_435_000_123  # Нечётное и не делится на 31: взаимно просто с SPACE
INVERSE = pow(MULTIPLIER, -1, SPACE)


def id_to_key(n: int) -> str:
    return encode(n * MULTIPLIER % SPACE).rjust(KEY_LEN, "0")


def key_to_id(key: str) -> int:
    return decode(key) * INVERSE % SPACE


print(id_to_key(1), id_to_key(2))  # CjFVswz eDlQV38
print(key_to_id("CjFVswz"))  # 1

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

Почему не Snowflake? Его 64-битные ID с меткой времени, номером машины и последовательностью дают 11 символов base62. Для сокращателя это слишком длинно.

Вариант 2. Хеш с обработкой коллизий

Считаем хеш от URL, приводим к 7 символам, пытаемся вставить. Координация не нужна, серверы работают независимо.

Цена: коллизии. Здесь работает парадокс дней рождения. Первая коллизия с вероятностью 50% случится примерно на

$1{,}18 \cdot \sqrt{62^7} \approx 2{,}2 \text{ млн ключей}$

При 10 млн ссылок в день это первые 5 часов работы. Значит, обработка коллизий обязательна с первого дня. Зато и катастрофы нет: при 18,25 млрд ссылок новый ключ занят с вероятностью 0,52%, а пять занятых подряд случатся примерно раз в 70 лет.

import hashlib
import sqlite3


def candidate(url: str, attempt: int) -> str:
    digest = hashlib.sha256(f"{url}#{attempt}".encode()).digest()
    return encode(int.from_bytes(digest[:8], "big") % SPACE).rjust(KEY_LEN, "0")


def shorten(db: sqlite3.Connection, url: str, max_attempts: int = 5) -> str:
    for attempt in range(max_attempts):
        key = candidate(url, attempt)
        # Вставка атомарна: проверять и вставлять отдельно нельзя, будет гонка
        inserted = db.execute(
            "INSERT INTO links (short_key, long_url) VALUES (?, ?) "
            "ON CONFLICT (short_key) DO NOTHING",
            (key, url),
        ).rowcount
        if inserted:
            db.commit()
            return key
        row = db.execute(
            "SELECT long_url FROM links WHERE short_key = ?", (key,)
        ).fetchone()
        if row[0] == url:  # Этот URL уже сокращали
            return key
    raise RuntimeError("не удалось подобрать ключ")


db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE links (short_key TEXT PRIMARY KEY, long_url TEXT NOT NULL)")
url = "https://example.com/some/very/long/path?with=query"
print(shorten(db, url))  # 59si33z
print(shorten(db, url))  # 59si33z, тот же ключ

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

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

Вариант 3. Предварительная генерация

Отдельный сервис заранее заполняет таблицу случайными ключами, а серверы приложений забирают их пачками:

CREATE TABLE unused_keys (
  short_key VARCHAR(16) COLLATE "C" PRIMARY KEY
);

DELETE FROM unused_keys
WHERE short_key IN (
  SELECT short_key FROM unused_keys
  LIMIT 1000
  FOR UPDATE SKIP LOCKED
)
RETURNING short_key;

FOR UPDATE SKIP LOCKED позволяет серверам не ждать друг друга и не получать одинаковые ключи. Удаление и выдача идут одной операцией.

Все 3,5 трлн ключей хранить не нужно, это 24,7 ТБ. Хватит скользящего запаса: на сутки вперёд нужно 10 млн ключей, около 70 МБ. Генератор при этом обязан сверяться с уже выданными ключами, иначе рано или поздно выдаст занятый.

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

Что выбрать

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

Подвох для всех трёх вариантов: свои адреса. Пользователь занял abc1234, а через год счётчик доходит до этого значения, и вставка падает. Самое простое решение: сгенерированные ключи всегда ровно 7 символов, а для своих адресов длина 7 запрещена. Тогда пространства не пересекаются.

Шаг 6. Редирект: 301 или 302

Интервьюеры любят этот вопрос: он короткий, а влияет сразу на нагрузку, аналитику и продукт.

Формальная часть есть в RFC 9110: 301 входит в список эвристически кэшируемых кодов, 302 в него не входит. На практике браузер может помнить 301 очень долго, и отозвать его с сервера вы не сможете.

Выигрыш от 301 часто переоценивают. Кэш живёт в браузере одного человека, поэтому экономятся только его повторные клики. Если ссылку из рассылки каждый открывает один раз, снижение нагрузки будет скромным, а аналитику всё равно потеряете.

Для наших требований (статистика, срок жизни, удаление) решение очевидно:

HTTP/1.1 302 Found
Location: https://example.com/some/very/long/path
Cache-Control: no-store

no-store гарантирует, что каждый клик дойдёт до сервера. Если нагрузка станет важнее точности, есть промежуточный вариант: 302 с Cache-Control: private, max-age=60. Браузер минуту не будет ходить к вам повторно, а отозвать ссылку можно будет с задержкой не больше минуты.

301 оправдан, когда статистика не нужна и ссылки по-настоящему вечные, а также когда важно передать поисковикам целевой адрес как канонический: Google учитывает это только для постоянных редиректов.

Коды 307 и 308 отличаются запретом менять метод запроса. Для перехода по ссылке это GET, так что разницы нет. Какой код отдаёт конкретный сервис, проверяется одной командой: curl -sI и короткая ссылка. Источники о крупных сокращателях противоречат друг другу, поэтому лучше посмотреть самому.

Шаг 7. Чтение через кэш

Доля попаданий в кэш неизвестна, поэтому допустим 90%. Это предположение, в проде его заменит замер. Тогда в базу приходит 1157 RPS в среднем и около 3500 в пике, и с этим справятся реплики чтения.

Оценка кэша в 100 ГБ завышена: 20% от миллиарда считаются по запросам, а среди них много повторов одного ключа. Для такого объёма хватит нескольких узлов Redis или Memcached с запасом на накладные расходы.

Базовый паттерн cache-aside, где cache и db это тонкие обёртки над клиентами:

import time

NOT_FOUND = ""  # Метка «такого ключа нет» для негативного кэша
HIT_TTL = 24 * 3600
MISS_TTL = 60


def resolve(key, cache, db):
    """Возвращает длинный URL или None, если ссылки нет либо она истекла."""
    cached = cache.get(key)
    if cached == NOT_FOUND:
        return None
    if cached is not None:
        return cached

    row = db.get(key)  # {"long_url": ..., "expires_at": unix-время или None}
    now = time.time()
    if row is None or (row["expires_at"] and row["expires_at"] <= now):
        cache.set(key, NOT_FOUND, ttl=MISS_TTL)
        return None

    # Запись в кэше не должна пережить саму ссылку
    ttl = HIT_TTL
    if row["expires_at"]:
        ttl = min(ttl, int(row["expires_at"] - now))
    if ttl > 0:
        cache.set(key, row["long_url"], ttl=ttl)
    return row["long_url"]

Вот детали, на которых интервьюер будет углубляться:

• Вытеснение. У ссылок резко неравномерная популярность, поэтому подходят LRU или LFU. У Redis есть обе политики: allkeys-lru и allkeys-lfu. LFU лучше держит стабильно популярное, LRU быстрее забывает вчерашний вирусный пост.
• Свежая ссылка и отставание реплик. Ссылку создали, реплика ещё не догнала, и пользователь получает 404. Лечится записью в кэш сразу при создании плюс повторным запросом к основной базе, если ключа нет на реплике.
• Негативный кэш. Бот перебирает несуществующие ключи, и каждый такой запрос идёт в базу. Поэтому кэшируем и отсутствие ключа, но ненадолго. При создании своего адреса эту метку надо стереть, иначе новая ссылка будет минуту отвечать 404.
• Удаление. Удаляем запись из кэша. Если есть локальный кэш в процессе, старое значение проживёт до конца его TTL, и эту задержку лучше назвать вслух.
• Лавина на промахе. У вирусной ссылки истёк TTL, и тысячи запросов разом пошли в базу. Лечится объединением запросов: за значением идёт один, остальные ждут его результат.

Шаг 8. Аналитика

Самая соблазнительная ошибка: UPDATE links SET clicks = clicks + 1 прямо в обработчике редиректа. Это 11,6 тыс. записей в секунду в базу, которая была спроектирована на 116, плюс конкуренция за строку популярной ссылки. И редирект начинает зависеть от здоровья основной базы.

Правильная схема: редирект кладёт событие в очередь и сразу отвечает.

{
  "event_id": "018f3a7e-9c21-7d10-b3f4-2c8e5a1d9f00",
  "key": "CjFVswz",
  "ts": "2026-11-04T12:00:00Z",
  "country": "DE",
  "referrer_domain": "t.me",
  "device": "mobile",
  "ip_hash": "9f2c41ab"
}

Дальше Kafka или её аналог, обработчик, колоночная база вроде ClickHouse и агрегаты по часам и дням. Поток скромный: 2,3 МБ/с в среднем. Проблема в накоплении 73 ТБ в год, поэтому сырые события хранятся ограниченное время, а агрегаты долго.

Что стоит проговорить:

• Потеря событий допустима, потеря редиректа нет. Если очередь недоступна, событие буферизуется в памяти и в крайнем случае отбрасывается, но пользователь уходит по ссылке.
• Дубли. Доставка обычно «хотя бы один раз», поэтому нужен event_id для дедупликации.
• Боты. Мессенджеры запрашивают ссылку ради предпросмотра, и это выглядит как клик. Фильтруем по User-Agent, иначе статистика завышена.
• Уникальные посетители. Точное множество на каждую ссылку слишком дорого, используют HyperLogLog с небольшой погрешностью.
• Персональные данные. IP лучше сразу превратить в страну и хранить только хеш с солью или не хранить совсем.

Шаг 9. Узкие места

Последние минуты посвятите тому, что ломается первым. Лучше назвать это самому, не дожидаясь вопроса.

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

Интервьюер обычно продолжает так:

• Что изменится, если нагрузка вырастет в 100 раз?
• Как убрать единую точку отказа у счётчика?
• Как разрешить менять адрес назначения? (При 302 просто: обновляем базу и инвалидируем кэш.)
• Как считать клики в реальном времени?
• Как раскатить сервис на второй регион без простоя?

Как отвечать на такие продолжения, разобрано в статье про вопросы вглубь.

Типичные ошибки

• Сразу рисовать архитектуру. Без требований непонятно, нужны ли 302 и аналитика.
• Цифры без выводов. Посчитали 9 ТБ и забыли. Каждая оценка должна влиять на решение.
• Шардирование и Kafka с порога. Сначала покажите, что простая схема упирается в конкретное ограничение.
• «Возьмём MD5» и всё. Нужно посчитать коллизии, показать атомарную вставку и назвать последствия дедупликации.
• 301 по умолчанию. Вместе с ним теряются повторные клики и возможность отозвать ссылку.
• Счётчик кликов в строке ссылки. Запись в горячую строку на пути чтения.
• Забытый регистр. Base62 в базе, которая не различает регистр.
• Свои адреса без пространства имён. Конфликт с генератором случится позже и в самый неудобный момент.