Спроектируйте сокращатель URL

Требования

Функциональные

• shorten(longURL) → shortURL — вернуть короткий код, в идеале 7 символов или меньше.
• GET /{code} — редиректнуть браузер на исходный длинный URL.
• Кастомные алиасы: вызывающий может попросить конкретный код (/sale), если он свободен.
• Истечение: ссылки могут иметь TTL; истёкшие коды отдают 404.
• Базовая аналитика: счётчики кликов, в идеале без замедления редиректа.

Нефункциональные

• Задержка редиректа — это SLO. Редирект должен разрешаться за единицы миллисекунд — он стоит перед загрузкой чужой страницы.
• Доступность над согласованностью на чтениях. Редирект обязан работать, даже если путь записи деградировал; недоступность совсем новой ссылки на секунду терпима, 404 на популярной — нет.
• Уникальность. Никакие два длинных URL не должны столкнуться на один код так, чтобы увести пользователя не туда.
• Масштаб. Миллиарды ссылок суммарно, чтения многократно превосходят записи.

Определяющее свойство — отношение чтений к записям. Оцени его, и архитектура напишется сама.

Оценка

• Пусть 100M новых URL/месяц. Это 10^8 / (30 × 10^5 с) ≈ ~40 записей/с в среднем, ~120/с на пике 3×. Записи — мелочь.
• При отношении 100:1 это ~4 000 чтений/с в среднем, ~12 000/с на пике. Чтения — это и есть система.
• Хранение: 100M/месяц × 12 месяцев × 5 лет = ~6 миллиардов URL. По ~500 байт на строку (длинный URL + код + метаданные) → ~3 ТБ. Большое, но обычное; оно не влезает в RAM одного узла, поэтому кешировать надо рабочий набор, а не весь датасет.
• Пространство ключей: при base62 (a–z A–Z 0–9) 62^7 ≈ 3,5 триллиона кодов. Семь символов с запасом покрывают миллиарды ссылок на десятилетия — поэтому 7 — целевая длина.
• Размер кеша (правило 80/20): если 20% ссылок дают 80% чтений, кеширование горячих 20% — скажем самых активных сотен миллионов кодов по ~500 байт — это десятки–низкие сотни ГБ, влезает в RAM небольшого Redis-кластера и обслуживает подавляющее большинство редиректов из памяти.

Итоговые числа: записи — ничто, чтения — всё, а кеш поглощает чтения. Теперь единственное реальное решение — как чеканить короткий код.

Высокоуровневый дизайн

Запись попадает на app-сервер, который генерирует код и кладёт связку code → longURL в key-value хранилище. Чтение (GET /{code}) сначала проверяет кеш; при попадании сразу возвращает редирект, при промахе читает хранилище, заполняет кеш и редиректит.

Глубокое погружение

Чеканка короткого кода

Это единственное по-настоящему интересное решение, и претендентов три.

(1) Хешировать длинный URL — base62(md5(longURL))[:7]. Заманчиво, ведь одинаковые URL естественно дедуплицируются, но коды на 62^7, взятые из хеша, будут сталкиваться по мере роста (парадокс дней рождения кусает куда раньше, чем намекает размер пространства). Каждая коллизия требует проверки в базе и пере-хеша/соли, добавляя чтение к каждой записи — и не уважает кастомные алиасы. Рабочее, но налог на обработку коллизий растёт с таблицей.

(2) Счётчик + base62 — держать глобальный монотонный счётчик, и короткий код — это значение счётчика в base62. Коллизий никогда (каждое значение уникально по построению), нет чтения-перед-записью, и коды коротки, пока счёт мал. Проблема в том, что счётчик — глобальная точка сериализации: один центральный счётчик это узкое место и SPOF. Починка — схема выделения диапазонов: координатор раздаёт каждому app-серверу блок ID (скажем миллион) на локальную трату, так что серверы координируются раз на блок, а не на запись. (Это ровно пререквизит про генерацию уникальных ID, применённый к дружелюбному короткому алфавиту base62.)

(3) Сервис генерации ключей (KGS) — отдельный сервис заранее генерирует случайные уникальные 7-символьные коды офлайн и хранит их в «БД ключей» с двумя таблицами: доступные и использованные. App-серверы берут пачку ключей, раздают их и помечают как использованные. Раз ключи чеканятся заранее, а уникальность проверяется один раз при генерации, путь записи никогда не сталкивается и не блокируется — он просто потребляет проверенный ключ. Цена — сам KGS (нельзя выдать один ключ дважды, нужна репликация, чтобы он не был SPOF), но он даёт непоследовательные, негадаемые коды и чистую поддержку кастомных алиасов.

Тонкая протечка: чистый счётчик делает коды последовательными и гадаемыми — кто угодно может перебрать /1, /2, /3 и выскрести все ссылки, проблема приватности для личных шарингов. Кодирование счётчика в base62 всё равно сохраняет порядок. Если негадаемость важна, либо используй KGS (случайные ключи), либо прогоняй счётчик через обратимую перетасовку (например перестановку Фейстеля/умножения) перед кодированием, чтобы соседние ID отображались в разбросанные коды.

Путь редиректа и кеширование

Редирект — горячий путь, поэтому он cache-aside над key-value хранилищем: проверить кеш, отдать при попадании, а при промахе прочитать хранилище, дозаполнить кеш и редиректнуть. При паттерне доступа 80/20 доля попаданий в устойчивом состоянии очень высока, так что база видит ручеёк чтений холодных ссылок, пока кеш поглощает поток. Само хранилище — это key-value поиск (code → longURL), поэтому и партиционированное KV-хранилище, и шардированная реляционная таблица по code оба работают — нет джойнов, которые надо сохранить.

301 против 302 — статус редиректа, решающий всё

HTTP-статус на редиректе — настоящий рычаг дизайна, а не деталь:

• 301 (Permanent): браузеры и прокси кешируют связку, так что последующие визиты на короткую ссылку полностью минуют твой сервер и идут прямо на длинный URL. Это срезает нагрузку чтения — но также значит, что ты перестаёшь видеть эти клики (сломанная аналитика) и никогда не сможешь переменить, куда указывает ссылка.
• 302 (Found / временный): браузер не кеширует связку, так что каждый визит возвращается через твой сервер. Ты хранишь полную аналитику и сохраняешь возможность перенаправить или истечь ссылку — ценой обслуживания каждого клика.

Выбор — прямой компромисс: 301 ради нагрузки, 302 ради контроля. Сокращатель, монетизирующий аналитику кликов, использует 302 и ест трафик чтения (ровно поэтому кеш так важен); чистый редиректор, которому нужна минимальная инфраструктура, может использовать 301 и дать браузерам кешировать.

Узкие места и компромиссы

• Счётчик как узкое место/SPOF. Один глобальный счётчик сериализует каждую запись и умирает со своим узлом. Выделение диапазонов (раздавать блоки) снимает координацию на запись ценой непоследовательных ID, если сервер упал посреди блока (эти ID просто сгорают — нормально, пространство ключей огромно).
• Cache stampede на горячей новой ссылке. Когда та ссылка с Супербоула создана, она ещё не в кеше, так что первый всплеск весь промахивается и одновременно молотит хранилище. Митигация: коалесинг запросов (single-flight: один промах фетчит, остальные ждут) или прогрев известно-горячих ссылок.
• Аналитика на горячем пути. Считать клики синхронно на каждом редиректе — добавить запись в путь чтения, худшее место для работы. Развяжи: отправь клик в очередь сообщений и агрегируй асинхронно, так редирект остаётся чистым чтением кеша, а аналитика отстаёт на секунды, что нормально.
• Конкуренция и злоупотребление кастомными алиасами. Кастомные алиасы требуют проверки уникальности (реальное чтение-перед-записью, но лишь для этого пути), а весь сервис — мечта спамера (сокращать ссылки с малварью) — так что реальному сокращателю нужны сканирование URL/блоклисты и rate-лимиты, влияющие на доступность вещи, которые игрушечная версия игнорирует.