Перейти к основному содержимому

Генератор коротких ссылок

В этой главе мы разберем интересный и уже классический вопрос из системного дизайна: как спроектировать сервис сокращения URL наподобие TinyURL.

Шаг 1 — Понять задачу и определить рамки дизайна​

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

Кандидат: Можете привести пример того, как работает URL shortener?
Интервьюер: Пусть исходный URL — https://www.systeminterview.com/q=chatsystem&c=loggedin&v=v3&l=long. Ваш сервис создает более короткий алиас: https://tinyurl.com/y7keocwj. Если открыть этот алиас, произойдет редирект на исходный URL.

Кандидат: Какой объем трафика?
Интервьюер: 100 миллионов URL в день.

Кандидат: Какой длины должен быть короткий URL?
Интервьюер: Как можно короче.

Кандидат: Какие символы допустимы в сокращенном URL?
Интервьюер: Короткий URL может содержать цифры (0-9) и буквы (a-z, A-Z).

Кандидат: Можно ли удалять или обновлять короткие URL?
Интервьюер: Для простоты предположим, что сокращенные URL нельзя удалять или изменять.

Базовые сценарии использования:

  1. Сокращение URL: на вход подается длинный URL, на выходе возвращается гораздо более короткий.

  2. Редирект по URL: по короткому URL нужно перенаправить пользователя на исходный URL.

  3. Высокая доступность, масштабируемость и отказоустойчивость.

Оценка на салфетке​

  • Операции записи: 100 миллионов URL создаются в день.

  • Операций записи в секунду: 100 million / 24 / 3600 = 1160

  • Операции чтения: предположим, что соотношение чтений к записям равно 10:1, тогда чтений в секунду будет 1160 * 10 = 11,600

  • Если сервис сокращения URL работает 10 лет, нам нужно поддерживать 100 million * 365 * 10 = 365 billion записей.

  • Предположим, что средняя длина URL равна 100.

  • Требуемое хранилище на 10 лет: 365 billion * 100 bytes = 36.5 TB

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

Шаг 2 — Предложить высокоуровневый дизайн и согласовать его​

В этом разделе мы обсудим API-эндпоинты, поток редиректа и поток сокращения URL.

API-эндпоинты​

API-эндпоинты обеспечивают взаимодействие между клиентами и серверами. Мы спроектируем API в REST-стиле. Если вы не знакомы с RESTful API, можно обратиться к внешним материалам, например к ссылке в списке литературы [1]. Сервис сокращения URL в первую очередь нуждается в двух эндпоинтах.

  1. Сокращение URL. Чтобы создать новый короткий URL, клиент отправляет POST-запрос, который содержит один параметр: исходный длинный URL. API выглядит так:
POST api/v1/data/shorten

- request parameter: {longUrl: longURLString}
- return: shortURL
  1. Редирект по URL. Чтобы перенаправить короткий URL на соответствующий длинный URL, клиент отправляет GET-запрос. API выглядит так:
GET api/v1/shortUrl

- return: longURL for HTTP redirection

Редирект URL​

На рисунке 1 показано, что происходит, когда вы вводите tinyurl в браузере. Как только сервер получает запрос tinyurl, он преобразует короткий URL в длинный при помощи HTTP 301 redirect.

Изображение показывает детали HTTP GET-запроса к https://tinyurl.com/qtj5opu и ответ со статусом 301, в заголовках которого присутствует location с исходным длинным URL.

Рисунок 1

Более подробное взаимодействие между клиентом и сервером показано на рисунке 2.

Изображение показывает, как клиент запрашивает короткий URL у tinyurl-сервера, получает ответ 301 с location, а затем автоматически переходит на длинный URL на Amazon.

Рисунок 2

Здесь стоит отдельно обсудить 301 redirect и 302 redirect.

301 redirect. Код 301 означает, что запрошенный URL «постоянно» перенесен на длинный URL. Поскольку редирект постоянный, браузер кэширует ответ, и последующие запросы к тому же короткому URL уже не будут отправляться в сервис сокращения URL. Вместо этого пользователь будет сразу переходить на сервер длинного URL.

302 redirect. Код 302 означает, что URL «временно» перенесен на длинный URL, поэтому последующие запросы к тому же короткому URL сначала будут приходить в сервис сокращения URL, а уже потом перенаправляться на сервер длинного URL.

У каждого способа есть свои плюсы и минусы. Если приоритет — снизить нагрузку на сервер, логичнее использовать 301 redirect, потому что только первый запрос для конкретного URL попадет в сервис сокращения URL. Однако если важна аналитика, 302 redirect лучше, потому что позволяет проще отслеживать CTR и источник перехода.

Самый интуитивный способ реализовать редирект — использовать хеш-таблицу. Предположим, в хеш-таблице хранятся пары <shortURL, longURL>. Тогда редирект можно реализовать так:

  • Получить longURL: longURL = hashTable.get(shortURL)

  • После получения longURL выполнить редирект.

Сокращение URL​

Предположим, короткий URL имеет вид www.tinyurl.com/{hashValue}. Чтобы поддержать сценарий сокращения URL, нам нужно найти хеш-функцию f(x), которая переводит длинный URL в hashValue, как показано на рисунке 3.

Изображение показывает длинный URL, который подается на функцию f(x), а на выходе получается короткий URL вида https://tinyurl.com/qtj5opu.

Рисунок 3

Хеш-функция должна удовлетворять двум требованиям:

  • Каждый longURL должен преобразовываться в один hashValue.

  • Каждый hashValue должен однозначно отображаться обратно в longURL.

Подробный дизайн хеш-функции мы рассмотрим дальше.

Шаг 3 — Детальный разбор дизайна​

До этого мы обсудили высокоуровневый дизайн сокращения URL и редиректа. Теперь рассмотрим подробнее модель данных, хеш-функцию, сам процесс сокращения и процесс редиректа.

Модель данных​

В высокоуровневом дизайне все хранится в хеш-таблице. Это хорошая отправная точка, но для реальных систем такой подход непрактичен, потому что память ограничена и дорога. Более разумный вариант — хранить отображение <shortURL, longURL> в реляционной базе данных. На рисунке 4 показан простой дизайн таблицы. В упрощенной версии таблица содержит 3 столбца: id, shortURL, longURL.

Изображение показывает таблицу url с тремя столбцами: первичный ключ id, а также shortURL и longURL.

Рисунок 4

Хеш-функция​

Хеш-функция используется для преобразования длинного URL в короткий URL, который также называют hashValue.

Длина hashValue​

hashValue состоит из символов [0-9, a-z, A-Z], то есть всего имеется 10 + 26 + 26 = 62 возможных символа. Чтобы определить длину hashValue, найдем минимальное n, такое что 62^n ≥ 365 billion. По нашей грубой оценке система должна поддерживать до 365 миллиардов URL. В таблице 1 показаны длины hashValue и соответствующее максимальное количество URL.

nМаксимальное количество URL
162^1 = 62
262^2 = 3,844
362^3 = 238,328
462^4 = 14,776,336
562^5 = 916,132,832
662^6 = 56,800,235,584
762^7 = 3,521,614,606,208 ≈ 3.5 триллиона
862^8 = 218,340,105,584,896

Таблица 1

Когда n = 7, получаем примерно 3.5 триллиона комбинаций, чего более чем достаточно для хранения 365 миллиардов URL, поэтому длина hashValue должна быть равна 7.

Мы рассмотрим два вида хеш-функций для URL shortener. Первый — «hash + разрешение коллизий», второй — «base 62 conversion». Разберем их по очереди.

Hash + разрешение коллизий​

Чтобы сократить длинный URL, можно реализовать хеш-функцию, которая преобразует его в строку из 7 символов. Прямолинейный вариант — использовать известные хеш-функции вроде CRC32, MD5 или SHA-1. Ниже показаны результаты применения этих хеш-функций к URL https://en.wikipedia.org/wiki/Systems_design.

Хеш-функцияХеш-значение (в hex)
CRC325cb54054
MD55a62509a84df9ee03fe1230b9df8b84e
SHA-10eeae7916c06853901d9ccbefbfcaf4de57ed85b

Таблица 2

Как видно из таблицы 2, даже самое короткое значение хеша (CRC32) слишком длинное — больше 7 символов. Как его сократить?

Первый подход — взять первые 7 символов хеша, но это может приводить к коллизиям. Чтобы их разрешить, можно рекурсивно добавлять заранее определенную строку и пересчитывать хеш, пока коллизия не исчезнет. Этот процесс показан на рисунке 5.

Изображение показывает блок-схему: на вход подается longURL, затем применяется hash function, получается shortURL, после чего система проверяет, существует ли он уже в БД. При коллизии к URL добавляется дополнительная строка, и процесс повторяется.

Рисунок 5

Этот метод действительно позволяет устранить коллизии, но он дорогой, потому что для каждого запроса приходится обращаться к базе данных и проверять, существует ли такой shortURL. Улучшить производительность помогает техника bloom filter [2]. Bloom filter — это эффективный по памяти вероятностный способ проверить, принадлежит ли элемент множеству. Подробнее см. материалы [2].

Конвертация в base 62​

Преобразование систем счисления — еще один популярный подход для URL shortener. Оно позволяет представлять одно и то же число в разных системах счисления. Здесь используется base 62, потому что для hashValue у нас есть 62 допустимых символа. Разберем пример: переведем 11157_10 в запись по основанию 62 (11157_10 означает число 11157 в десятичной системе).

  • Base 62 использует 62 символа. Соответствие такое: 0-0, ..., 9-9, 10-a, 11-b, ..., 35-z, 36-A, ..., 61-Z, где a соответствует 10, Z соответствует 61 и т. д.

  • 11157_10 = 2 * 62^2 + 55 * 62^1 + 59 * 62^0 = [2, 55, 59] -> [2, T, X] в системе base 62. На рисунке 6 показан процесс преобразования.

Изображение показывает последовательное деление числа 11157 на 62, остатки 59, 55, 2 и построение итогового представления в base 62.

Рисунок 6

  • Таким образом, короткий URL будет https://tinyurl.com/2TX

Сравнение двух подходов​

Таблица 3 показывает различия между двумя подходами.

Hash + разрешение коллизийКонвертация в base 62
Длина короткого URL фиксирована.Длина короткого URL нефиксированная и растет вместе с ID.
Не требует генератора уникальных ID.Этот вариант зависит от генератора уникальных ID.
Коллизии возможны и требуют разрешения.Коллизии невозможны, потому что ID уникален.
Невозможно определить следующий короткий URL, так как он не зависит от ID.Легко понять, каким будет следующий короткий URL, если ID увеличивается на 1, и это может быть проблемой безопасности.

Таблица 3

Детали сокращения URL​

Поскольку это одна из ключевых частей системы, нам важно, чтобы поток сокращения URL был логически простым и рабочим. В нашем дизайне используется base 62 conversion. На рисунке 7 показан этот поток.

Изображение показывает блок-схему: входной longURL, проверка его наличия в БД, возврат существующего shortURL либо генерация нового ID, преобразование ID в short URL и сохранение результата.

Рисунок 7

  1. На вход подается longURL.

  2. Система проверяет, есть ли этот longURL в базе данных.

  3. Если есть, значит longURL уже был преобразован в shortURL. В этом случае система достает shortURL из базы и возвращает его клиенту.

  4. Если нет, значит longURL новый. Генератор уникальных ID создает новый идентификатор (первичный ключ).

  5. ID преобразуется в shortURL через base 62 conversion.

  6. В БД создается новая строка с id, shortURL и longURL.

Чтобы поток было проще понять, рассмотрим конкретный пример.

  • Пусть входной longURL равен https://en.wikipedia.org/wiki/Systems_design

  • Генератор уникальных ID возвращает ID: 2009215674938

  • После преобразования в base 62 этот ID становится zn9edcu

  • Сохраняем ID, shortURL и longURL в таблицу, как показано в таблице 4

idshortURLlongURL
2009215674938zn9edcuhttps://en.wikipedia.org/wiki/Systems_design

Таблица 4

Стоит отдельно упомянуть распределенный генератор уникальных ID. Его главная задача — генерировать глобально уникальные идентификаторы, которые затем используются при создании shortURL. В сильно распределенной среде реализация такого генератора — непростая задача. К счастью, мы уже обсуждали несколько решений в главе «Проектирование генератора уникальных идентификаторов в распределенных системах».

Детали редиректа URL​

На рисунке 8 показан подробный дизайн редиректа. Поскольку чтений больше, чем записей, отображение <shortURL, longURL> хранится в кэше для ускорения работы.

Изображение показывает пользователя, отправляющего запрос к https://tinyurl.com/zn9edcu, затем балансировщик, web-серверы, кэш и базу данных, после чего пользователю возвращается исходный длинный URL.

Рисунок 8

Поток редиректа URL можно описать так:

  1. Пользователь кликает по короткой ссылке: https://tinyurl.com/zn9edcu

  2. Балансировщик отправляет запрос на web-серверы.

  3. Если shortURL уже есть в кэше, longURL возвращается напрямую.

  4. Если shortURL нет в кэше, longURL запрашивается из БД. Если и в БД его нет, скорее всего, пользователь ввел невалидный shortURL.

  5. longURL возвращается пользователю.

Шаг 4 — Подведем итоги​

В этой главе мы обсудили дизайн API, модель данных, хеш-функцию, сокращение URL и редирект URL.

Если в конце интервью останется время, можно затронуть еще несколько тем.

  • Rate limiter. Возможная проблема безопасности — злоумышленники могут отправлять огромное число запросов на сокращение URL. Rate limiter помогает отфильтровать такие запросы по IP-адресу или другим правилам.

  • Масштабирование web-серверов. Поскольку web-уровень stateless, его легко масштабировать, добавляя или убирая web-серверы.

  • Масштабирование базы данных. Для этого часто используют репликацию и шардинг.

  • Аналитика. Данные все важнее для бизнеса. Интеграция аналитики в URL shortener поможет отвечать на вопросы вроде: сколько людей кликнули по ссылке, когда это произошло и т. д.

  • Availability, consistency и reliability. Эти идеи лежат в основе успеха любой крупной системы. Мы уже подробно обсуждали их в главе «Масштабирование от нуля до миллионов пользователей».

Поздравляем, вы дошли до этого места! Можно похлопать себя по плечу. Отличная работа!

Справочные материалы​

[1] A RESTful Tutorial:
https://www.restapitutorial.com/index.html

[2] Bloom filter:
https://en.wikipedia.org/wiki/Bloom_filter