--- 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 (временно) — каждый клик через сервис → счётчики, источники переходов. **Генерация короткого кода**, два подхода: 1. **Hash + разрешение коллизий** (MD5/CRC32 → первые 7 символов; при коллизии — пересчитать с добавленной строкой): фиксированная длина, но нужны проверки БД (ускоряет **фильтр Блума**), длина из 62 символов: 62^7 ≈ 3.5 трлн > 365 млрд. 2. **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-адресов. Здесь же мы подробно рассмотрим модель данных, функцию хеширования и процессы сокра­ щения/перенаправления. Модель данных При обсуждении общей архитектуры мы решили хранить все в хеш- таблице. Это хорошая отправная точка, но в реальных системах такой подход непрактичен, поскольку ресурсы памяти ограничены и дороги. Пары лучше хранить в реляционной базе данных. На рис. 8.4 показана схема простой таблицы БД, состоящей из трех столбцов: id, shortURL, longURL. url PK id shortURL longURL Рис. 8.4 Проектирование системы для сокращения 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-адресов. Поскольку чтение происходит чаще, чем запись, пара хранится в кэше для улучшения производительности. Веб-серверы Баланси- ровщик нагрузки База данных Кэш GET https://tinyurl.com/zn9edcu Возврат длинного URL: https://en.wikipeida.org/wiki/Systems_design 1 3 5 2 4 Пользователь КЭШ КЭШ КЭШ Рис. 8.8 Ниже кратко изложен процесс перенаправления URL-адресов: 1. Пользователь кликает по короткой ссылке https://tinyurl.com/ zn9edcu. 2. Балансировщик нагрузки направляет запрос к веб-серверам. 3. Если shortURL уже есть в кэше, то сразу возвращается longURL. 4. Если shortURL нет в кэше, то longURL извлекается из базы данных. Если этого адреса нет в БД, пользователь, скорее всего, ввел его неправильно. 5. Пользователю возвращается longURL. Проектирование системы для сокращения URL-адресов      143 ШАГ 4: ПОДВЕДЕНИЕ ИТОГОВ В этой главе мы поговорили о проектировании API, модели данных, функции хеширования, а также о сокращении и перенаправлении URL- адресов. Если в конце интервью остается время, можно обсудить дополнительные вопросы. Ограничитель трафика. Мы можем столкнуться с потенциальной проблемой безопасности: злоумышленники могут послать чрез­ мерно большое количество запросов на сокращение URL-адреса. Ограничитель трафика помогает фильтровать запросы с учетом IP-адреса или других правил. Если вам нужно вспомнить эту тему, вернитесь к главе 4 «Проектирование ограничителя трафика». Масштабирование веб-серверов. Поскольку веб-уровень не хранит свое состояние, его легко масштабировать, добавляя или удаляя веб-серверы. Масштабирование базы данных. Репликация и сегментирование базы данных являются распространенными методиками. Аналитика. Данные играют все более важную роль в успехе бизнеса. Интеграция аналитической системы в сервис для сокращения URL- адресов поможет получить такие ценные сведения, как количество пользователей, перешедших по ссылке, точное время перехода и т. д. Доступность, согласованность и надежность. Эти характеристики являются ключом к успеху любой крупной системы. Мы подробно обсуждали их в главе 1. Пожалуйста, вспомните эту тему. Поздравляем, вы проделали длинный путь и можете собой гордиться. Отличная работа! СПРАВОЧНЫЕ МАТЕРИАЛЫ [1]  Руководство по REST: https://www.restapitutorial.com/index.html [2]  Фильтр Блума: https://ru.wikipedia.org/wiki/Фильтр_Блума