title: Алекс Сюй, «System Design. Подготовка к сложному интервью» (Vol. 1, рус. изд.) — глава 8: Сокращение URL-адресов source: materials/System Design. Подготовка к сложному интервью.pdf, стр. 131–143 конспект: TASK-45.38, извлечено pymupdf 2026-09-17; ниже полный «грязный» текст главы + выжимка статус: выжимка и перенос в knowledge-base.md / methodology.md / classic-designs.md — см. _map.md
Глава 8. Сокращение URL-адресов
Выжимка
Классический кейс. Оценки: 100 млн новых URL/день = 1160 QPS запись, чтение ×10 = 11.6k QPS; 10 лет → 365 млрд записей ≈ 365 ТБ.
API: POST /api/v1/data/shorten (longUrl → shortURL), GET /api/v1/shortUrl (→ redirect).
Перенаправление: хеш-таблица shortURL→longURL в памяти непрактична — реляционная БД + кэш (чтение доминирует). 301 vs 302: 301 (перемещён навсегда) — браузер кэширует, нагрузка на сервис минимальна, но нет аналитики кликов; 302 (временно) — каждый клик через сервис → счётчики, источники переходов.
Генерация короткого кода, два подхода:
- Hash + разрешение коллизий (MD5/CRC32 → первые 7 символов; при коллизии — пересчитать с добавленной строкой): фиксированная длина, но нужны проверки БД (ускоряет фильтр Блума), длина из 62 символов: 62^7 ≈ 3.5 трлн > 365 млрд.
- Base62(ID): генератор уникальных ID (гл. 7, snowflake) → кодирование в 62-ричную систему: коллизий нет, длина растёт с ID, но следующий URL предсказуем (риск безопасности).
Дополнительно на шаге 4: rate limiter (анти-абьюз), аналитика, масштабирование БД (реплики/шарды).
Перенос: classic-designs §1 (сверка с эталоном Яндекса), KB §14.3 (base62/301-302/Блум).
Полный текст (грязная выгрузка)
8 ПРОЕКТИРОВАНИЕ СИСТЕМЫ ДЛЯ СОКРАЩЕНИЯ URL-АДРЕСОВ В этой главе мы рассмотрим интересную классическую задачу, с которой можно столкнуться на интервью по проектировании ИТ-систем: разра ботка сервиса для сокращения URL-адресов по примеру tinyurl. ШАГ 1: ПОНЯТЬ ЗАДАЧУ И ОПРЕДЕЛИТЬ МАСШТАБ РЕШЕНИЯ На интервью по проектированию ИТ-систем специально дают задачи, допускающие свободную трактовку. Чтобы разработать хорошо проду манную систему, необходимо задавать уточняющие вопросы. Кандидат: «Можете ли привести пример работы сервиса для сокра щения URL-адресов?» Интервьюер: «Допустим, https://www.systeminterview.com/q=chatsyst em&c=loggedin&v=v3&l=long — это исходный URL-адрес. Ваш сервис должен создать ссылку покороче: https://tinyurl.com/y7keocwj. Клик по этой ссылке должен перенаправлять к исходному URL-адресу». Кандидат: «Какой объем трафика?» Интервьюер: «100 миллионов сгенерированных URL-адресов в день». Кандидат: «Какая длина должна быть у сокращенного URL-адреса?» Интервьюер: «Как можно короче». Кандидат: «Какие символы допускаются в сокращенном URL-адресе?» Интервьюер: «Сокращенный URL-адрес может содержать цифры (0–9) и буквы (a–z, A–Z)».
132 ГЛАВА 8 Кандидат: «Допускается ли удаление или обновление сокращенного URL-адреса?» Интервьюер: «Чтобы не усложнять, предположим, что сокращенный URL-адрес не подлежит удалению или обновлению». Вот типичные сценарии использования: 1. Сокращение URL-адресов: дается длинный URL-адрес => воз вращается намного более короткий URL-адрес. 2. Перенаправление URL-адресов: дается сокращенный URL-адрес => пользователь перенаправляется к исходному URL-адресу. 3. Высокая доступность, масштабируемость и устойчивость к сбоям. Приблизительные оценки
Операции записи: генерируется 100 миллионов URL-адресов в день.
Операций записи в секунду: 100 миллионов / 24 / 3600 = 1160.
Операции чтения: если предположить, что операции чтения и за писи имеют соотношение 10 к 1, за одну секунду будет выполняться 1160 * 10 = 11 600 операций чтения.
Если предположить, что сервис для сокращения URL-адресов про работает 10 лет, мы должны поддерживать хранение 100 миллионов * 365 * 10 = 365 миллиардов записей.
Пусть длина среднего URL-адреса составляет 100 символов.
Требования к хранилищу в ближайшие 10 лет: 365 миллиардов * 100 байт * 10 лет = 365 Тб. Вы должны обсудить эти предположения и расчеты с интервьюером и убедиться в том, что вы поняли друг друга правильно. ШАГ 2: ПРЕДЛОЖИТЬ ОБЩЕЕ РЕШЕНИЕ И ПОЛУЧИТЬ СОГЛАСИЕ В этом разделе мы обсудим конечные точки API, перенаправление и со кращение URL-адресов.
Проектирование системы для сокращения URL-адресов 133 Конечные точки API Конечные точки API обеспечивают взаимодействие между клиентами и серверами. Наш API будет в стиле REST. Если вы не знакомы с этим стилем, можете обратиться к справочным материалам (например, [1]). Сервису сокращения URL-адресов нужны две основные конечные точки: 1. Сокращение URL-адреса. Чтобы создать новый сокращенный URL-адрес, клиент отправляет POST-запрос с одним параметром: исходным длинным URL-адресом. Конечная точка выглядит так: POST api/v1/data/shorten параметр запроса: {longUrl: longURLString}; возвращается shortURL. 2. Перенаправление URL-адреса. Чтобы перенаправить сокращенную ссылку к соответствующему длинному URL-адресу, клиент отправ ляет GET-запрос. Конечная точка выглядит так: GET api/v1/shortUrl возвращается longURL для HTTP-перенаправления. Перенаправление URL-адресов На рис. 8.1 показано, что происходит при вводе в браузере URL-адреса tinyurl. Получив запрос, сервер меняет короткий URL-адрес на длинный, используя перенаправление с кодом 301. Рис. 8.1
134 ГЛАВА 8 Подробное взаимодействие между клиентами и серверами показано на рис. 8.2. Клиент Cервер tinyurl Cервер Amazon переход по короткому URL код состояния: 301 переход по длинному URL местоположение: длинный URL длинный URL: https://www.amazon.com/dp/B017V4NTFA?pLink=63eaef76-979c-4d& ref=adblp13nvvxx_0_2_im короткий URL: https://tinyurl.com/qtj5opu Рис. 8.2 Здесь стоит обсудить отличия между кодами перенаправления 301 и 302.
Перенаправление 301. Код состояния 301 означает, что запрошенный URL-адрес «навсегда» перемещен по длинному URL-адресу. Так как перенаправление постоянное, браузер кэширует ответ и последую щие запросы по тому же адресу не будут направляться к нашему сер вису. Вместо этого браузер сразу откроет сокращенный URL-адрес.
Перенаправление 302. Код состояния 302 означает, что URL-адрес «временно» перемещен по длинному URL-адресу. То есть после
Проектирование системы для сокращения URL-адресов
135
дующие запросы того же URL-адреса будут сначала отправляться
нашему сервису, а затем перенаправляться к серверу длинного
URL-адреса.
У обоих методов перенаправления есть свои плюсы и минусы. Если нам
в первую очередь нужно снизить нагрузку на сервер, лучше использовать
код состояния 301, так как для каждого сокращенного URL-адреса сервис
будет получать только первый запрос. Если же нам нужна аналитическая
информация, стоит выбрать код состояния 302, так как он упрощает от
слеживание частоты и источника переходов по ссылке.
Самый очевидный способ реализации перенаправления URL-адресов
заключается в использовании хеш-таблиц. Если предположить, что
хеш-таблица хранит пары
получаем longURL: longURL = hashTable.get(shortURL);
получив longURL, выполняем перенаправление. Сокращение URL-адресов Допустим, сокращенный URL-адрес выглядит как www.tinyurl.com/ {hashValue}. Чтобы его получить, мы должны найти функцию fx, которая привязывает длинный URL-адрес к hashValue, как показано на рис. 8.3. longURL hash https://tinyurl.com/ qtj5opu Рис. 8.3
136 ГЛАВА 8 К функции хеширования предъявляются следующие требования:
каждое значение longURL должно иметь один хеш hashValue;
каждое значение hashValue должно указывать обратно на longURL.
Подробная архитектура функции хеширования обсуждается в следую
щем разделе.
ШАГ 3: ПОДРОБНОЕ ПРОЕКТИРОВАНИЕ
До сих пор мы обсуждали общие вопросы проектирования сервиса для
сокращения и перенаправления URL-адресов. Здесь же мы подробно
рассмотрим модель данных, функцию хеширования и процессы сокра
щения/перенаправления.
Модель данных
При обсуждении общей архитектуры мы решили хранить все в хеш-
таблице. Это хорошая отправная точка, но в реальных системах такой
подход непрактичен, поскольку ресурсы памяти ограничены и дороги.
Пары
Проектирование системы для сокращения URL-адресов 137 Функция хеширования Функция хеширования используется для получения из длинного URL- адреса хеша — hashValue. Длина hashValue hashValue состоит из символов [0-9, a-z, A-Z], число которых равно 10 + 26 + + 26 = 62. Чтобы определить длину hashValue, нужно найти наименьшее n, при котором 62^n ≥ 365 миллиардов. Судя по этим прикидкам, система должна поддерживать до 365 миллиардов URL-адресов. В табл. 8.1 пока заны разные значения длины hashValue и соответствующее максимальное количество поддерживаемых URL-адресов. Таблица 8.1 n Максимальное количество URL-адресов 1 62^1 = 62 2 62^2 = 3 844 3 62^3 = 238 328 4 62^ 4 = 14 776 336 5 62^5 = 916 132 832 6 62^6 = 56 800 235 584 7 62^7 = 3 521 614 606 208 ~3,5 триллиона 8 62^8 = 218 340 105 584 896 3,5 триллиона (когда n = 62 ^ 7) более чем достаточно для хранения 365 миллиардов URL-адресов, поэтому длина hashValue будет равна 7. Мы исследуем два вида функций хеширования для сокращения URL- адресов: «хеш + разрешение конфликтов» и «преобразование base62». Хеш + разрешение конфликтов Чтобы сократить длинный URL-адрес, нужно реализовать хеш-функцию, которая хеширует его в строку из 7 символов. Очевидное решение состоит
138 ГЛАВА 8 в использовании общеизвестных функций хеширования вроде CRC32, MD5 или SHA-1. В следующей таблице приводится сравнение хешей, получен ных с помощью разных функций из URL-адреса https://en.wikipedia.org/ wiki/Systems_design. Таблица 8.2 Хеш-функция Значение хеша (шестнадцатеричное) CRC32 5cb54054 MD5 5a62509a84df9ee03fe1230b9df8b84e SHA-1 0eeae7916c06853901d9ccbefbfcaf4de57ed85b Как видно из табл. 8.2, даже самое короткое значение хеша (из CRC32) получается слишком большим (больше 7 символов). Как его сократить? В качестве одного из решений можно взять первые 7 символов хеша, но это чревато конфликтами. Чтобы значения хеша не дублировались, мы можем рекурсивно добавлять к ним заданную строку, пока они не станут уникальными. Этот процесс проиллюстрирован на рис. 8.5. Ввод: longURL Существует в БД? Хеш-функция shortURL Сохранить в ДБ longURL + заданная строка да есть конфликт Конец Начало нет Рис. 8.5
Проектирование системы для сокращения URL-адресов 139 Этот метод может избавить нас от конфликтов, но обращаться к базе данных при каждом запросе, чтобы проверить наличие в ней shortURL, довольно расточительно. Для улучшения производительности можно использовать фильтр Блума [2]. Это вероятностная методика с эффек тивным использованием пространства, которая позволяет проверить, входит ли элемент в множество. Подробнее об этом читайте в справочных материалах [2]. Преобразование base62 Еще одним распространенным методом сокращения URL-адресов явля ется преобразование значения в другую систему счисления. Поскольку для hashValue используется набор из 62 символов, мы выберем алгоритм base62. Чтобы понять, как происходит это преобразование, переведем десятичное число 1115710 в вид с основанием 62.
Как понятно из названия, base62 — это способ кодирования с ис пользованием 62 символов. Они соотносятся как 0-0, ..., 9-9, 10-a, 11-b, ..., 35-z, 36-A, …, 61-Z, где «a» соответствует 10, «Z» соответ ствует 61 и т. д.
1115710 = 2 x 622 + 55 x 621 + 59 x 620 = [2, 55, 59] -> [2, T, X] в пред ставлении base62. Процесс преобразования показан на рис. 8.6. 11157 62 179 62 2 62 0 59 55 2 X T 2 Остаток Представление в base62 Рис. 8.6
Таким образом, сокращенный URL-адрес выглядит как https:// tinyurl.com/2TX.
140 ГЛАВА 8 Сравнение двух подходов В табл. 8.3 приводятся отличия этих двух подходов. Таблица 8.3 Хеш + разрешение конфликтов Преобразование base62 Фиксированная длина сокращенного URL- адреса Сокращенный URL-адрес имеет переменную длину, которая увеличивается вместе с ID Не требует генератора уникальных ID Этот подход использует генератор уникальных ID Возможны конфликты, которые нужно разрешать Конфликты исключены, так как ID уникальные Невозможно определить, каким будет следующий сокращенный URL-адрес, так как он не зависит от ID Если ID всегда инкрементируется на 1, можно легко определить следующий доступный URL-адрес. Это может стать угрозой безопасности Тщательный анализ сокращения URL-адресов Процесс сокращения URL-адресов является одним из ключевых элемен тов системы, поэтому мы хотим сделать его простым и функциональным. В нашей архитектуре используется преобразование base62. Принцип работы показан на следующей диаграмме (рис. 8.7). 1. longURL подается на вход. 2. Система проверяет, есть ли longURL в базе данных. 3. Если да, это означает, что значение longURL уже было преобразо вано в shortURL. В этом случае мы извлекаем shortURL из базы данных и возвращаем его клиенту. 4. Если нет, longURL является новым адресом и для него генерируется новый уникальный ID (первичный ключ). 5. Преобразуем ID в shortURL методом base62. 6. Создаем в БД новую запись с ID, shortURL и longURL. Чтобы вам было проще понять этот процесс, рассмотрим конкретный пример.
Предположим, longURL имеет значение https://en.wikipedia.org/wiki/ Systems_design.
Проектирование системы для сокращения URL-адресов 141
Генератор уникальных ID возвращает 2009215674938.
Преобразуем ID в shortURL методом base62. 2009215674938 пре вращается в zn9edcu.
Сохраняем ID, shortURL и longURL в базу данных, как показано в табл. 8.4. 1. Ввод: longURL да 2. longURL в БД? 3. Возврат shortURL 5. Превращение ID в shortURL 6. Сохранение ID, shortURL и longURL в БД 4. Генерация нового ID нет Рис. 8.7 Таблица 8.4 id shortURL longURL 2009215674938 zn9edcu https://en.wikipedia.org/wiki/Systems_design Стоит упомянуть о распределенном генераторе уникальных ID. Его ос новная задача состоит в получении идентификаторов, которые исполь зуются для создания значений shortURL и не повторяются в рамках всей
142 ГЛАВА 8
системы. Реализация генератора уникальных ID в сильно распределенном
окружении является непростой задачей. К счастью, мы уже обсудили
несколько решений в главе 7 «Проектирование генератора уникальных
идентификаторов в распределенных системах». Перечитайте ее, если
хотите освежить память.
Тщательный анализ перенаправления URL-адресов
На рис. 8.8 показана подробная схема перенаправления URL-адресов.
Поскольку чтение происходит чаще, чем запись, пара
Проектирование системы для сокращения URL-адресов 143 ШАГ 4: ПОДВЕДЕНИЕ ИТОГОВ В этой главе мы поговорили о проектировании API, модели данных, функции хеширования, а также о сокращении и перенаправлении URL- адресов. Если в конце интервью остается время, можно обсудить дополнительные вопросы.
Ограничитель трафика. Мы можем столкнуться с потенциальной проблемой безопасности: злоумышленники могут послать чрез мерно большое количество запросов на сокращение URL-адреса. Ограничитель трафика помогает фильтровать запросы с учетом IP-адреса или других правил. Если вам нужно вспомнить эту тему, вернитесь к главе 4 «Проектирование ограничителя трафика».
Масштабирование веб-серверов. Поскольку веб-уровень не хранит свое состояние, его легко масштабировать, добавляя или удаляя веб-серверы.
Масштабирование базы данных. Репликация и сегментирование базы данных являются распространенными методиками.
Аналитика. Данные играют все более важную роль в успехе бизнеса. Интеграция аналитической системы в сервис для сокращения URL- адресов поможет получить такие ценные сведения, как количество пользователей, перешедших по ссылке, точное время перехода и т. д.
Доступность, согласованность и надежность. Эти характеристики являются ключом к успеху любой крупной системы. Мы подробно обсуждали их в главе 1. Пожалуйста, вспомните эту тему. Поздравляем, вы проделали длинный путь и можете собой гордиться. Отличная работа! СПРАВОЧНЫЕ МАТЕРИАЛЫ [1] Руководство по REST: https://www.restapitutorial.com/index.html [2] Фильтр Блума: https://ru.wikipedia.org/wiki/Фильтр_Блума