Проектирование Bit.ly

Постановка задачи

Проектирование сервиса сокращения ссылок - один из самых распространенных System Design вопросов для начинающих. В то время как в большинстве других разборов мы углубляемся в детали, здесь мы будем ориентироваться на более Junior-аудиторию. Если вы новичок в System Design, это отличная задача для старта! Мы постараемся идти медленнее и объяснять концепции, которые в других разборах часто опускаются.

Функциональные требования

Первое, что нужно сделать в System Design интервью - четко понять требования к системе. Функциональные требования - это возможности/фичи, которые система должна предоставлять пользователю.

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

Самое важное - сфокусироваться на 3–4 ключевых возможностях и не отвлекаться на вспомогательные вещи.

Сконцентрируемся на следующем наборе функциональных требований:

Основные требования

1. Пользователь может отправить длинный URL и получить сокращенную версию
   • Опционально пользователь может указать предопределенное значение (alias) для короткой ссылки (например, www.short.ly/my-custom-alias)
   • Опционально пользователь может указать дату истечения (expiration date) для своей сокращенной ссылки
2. Пользователь перенаправляется на оригинальный URL, когда переходит по сокращенной ссылке

За рамками задачи

• Аутентификация и управление аккаунтами
• Аналитика кликов/переходов по ссылкам (например, число кликов, география)

Нефункциональные требования

Дальше стоит обозначить ключевые нефункциональные требования. Нефункциональные требования - это характеристики того, как система работает, а не что она делает. Эти требования важны потому что определяют такие ключевые характеристики, как масштабируемость, время ответа, безопасность, доступность и т. п., часто выраженные в виде конкретных числовых значений - например "система должна обслуживать 100M DAU" или "отвечать быстрее 200 мс".

Основные требования

1. Система должна гарантировать уникальность коротких ссылок (никакие два длинных URL не должны отображаться в одну и ту же короткую ссылку)
2. Редирект должен происходить с минимальной задержкой (< 100 мс)
3. Система должна быть надежной и доступной 99.99% времени (доступность > согласованность)
4. Система должна хранить до 1 млрд сокращенных URL и масштабироваться до 100 млн DAU

За рамками задачи

• Согласованность данных в real-time аналитике
• Продвинутые security-возможности, такие как спам-детектор и фильтрация вредоносных URL

Вот как это могло бы выглядеть на доске:

Проектирование API

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

В сервисе сокращения ссылок ключевые сущности очень простые:

1. OriginalUrl: исходный длинный URL, который пользователь хочет сократить
2. ShortUrl: короткий URL, который пользователь получает в ответ
3. User: пользователь, который создал сокращенный URL

Теперь мы можем определить API системы. API задает контракт взаимодействия между клиентом и сервером и становится отправной точкой для high-level дизайна.

Ваша цель - пройти по основным функциональным требованиям одно за другим и определить API, которые нужны, чтобы удовлетворить их. Обычно для каждого функционального требования нужен один эндпоинт, но иногда их может быть несколько. В большинстве случаев мы используем REST API и нам нужно выбрать правильный HTTP method:

• POST: создать новый ресурс
• GET: прочитать существующий ресурс
• PUT: обновить существующий ресурс
• DELETE: удалить ресурс

Чтобы сократить URL, нам нужен POST эндпоинт, который принимает длинный URL и опциональные параметры, и возвращает короткий URL. Здесь POST уместен, потому что мы создаем новую запись в базе - соответствие OriginalUrl -> ShortUrl.

// Сократить URL
POST /urls -> string
{
  "original_url": "https://www.example.com/some/very/long/url",
  "alias": "optional_custom_alias",
  "expires_at": "optional_expiration_date"
}

Для редиректа нам нужен GET эндпоинт, который принимает короткий URL и делает redirect на исходный длинный URL. GET используется, потому что мы читаем из базы существующий OriginalUrl по ShortUrl.

// Редирект на исходный URL
GET /{short_url} -> HTTP 302 Redirect на исходный URL

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

Мы начнем с того, что пройдем по функциональным требованиям одно за другим и спроектируем систему, которая их удовлетворяет. После этого добавим детализацию и усложним дизайн (там, где это необходимо) в секции "Потенциальные погружения в детали".

1. Пользователь может отправить длинный URL и получить сокращенную версию

Первое, о чем нужно подумать в этой системе - как мы будем генерировать короткий URL. Пользователи будут приходить с длинными URL и ожидать, что мы "сожмем" их до удобного размера.

Опишем основные компоненты, которые для этого нужны.

1. Клиент: пользователи взаимодействуют с системой через Web или мобильное приложение.
2. Сервер: принимает запросы от клиента и содержит логику создания коротких ссылок и валидации.
3. База данных: хранит соответствие ShortUrl -> OriginalUrl, а также опциональные параметры, такие как expires_at.

Когда пользователь отправляет длинный URL:

1. Клиент делает POST запрос на /urls с длинным URL и опциональными параметрами.
2. Сервер принимает запрос и валидирует длинный URL. Это нужно, чтобы убедиться, что URL валидный (нет смысла сокращать невалидный URL) и что его еще нет в нашей системе (мы хотим избежать коллизий).
   • Чтобы валидировать URL, можно использовать популярные open-source библиотеки, например is-url или написать свою простую валидацию.
   • Чтобы проверить, есть ли исходный URL в базе данных, можно сделать отдельный запрос в базу.
3. Если URL валидный и его нет в системе, мы можем генерировать короткий URL, если только:
   • Пока мы абстрагируем этот шаг как некую "магическую" функцию, которая принимает исходный URL и возвращает короткий URL. В следующей секции мы подробно разберем, как генерировать короткие URL.
   • Если пользователь указал псевдоним (alias), мы можем использовать его как короткий URL (после проверки, что он не занят).
4. Когда короткий URL получен, мы вставляем запись в базу: короткий URL (или псевдоним), исходный URL и expires_at.
5. Возвращаем короткий URL клиенту.

2. Пользователь может открыть оригинальный URL, используя сокращенный URL

Теперь пользователи могут переходить на оригинальный URL, используя сокращенный. Важно: сокращенный URL находится на домене, которым владеем мы. Например, если наш домен - short.ly, то короткие ссылки выглядят как short.ly/abc123, и все запросы к этому URL идут на наш сервер.

Когда пользователь открывает сокращенный URL, происходит следующее:

1. Браузер пользователя отправляет GET запрос на наш сервер с коротким URL (например, GET /abc123).
2. Сервер принимает запрос и ищет короткий URL в базе.
3. Если короткий URL найден и срок его действия не истек (сравниваем текущую дату с expires_at в базе), сервер получает соответствующий исходный URL.
4. Сервер отправляет ответ с HTTP redirect браузеру пользователя, инструктируя его перейти на исходный URL.

Есть два основных типа перенаправлений HTTP, которые мы могли бы использовать:

1. 301 (Permanent Redirect): означает, что ресурс навсегда переехал на целевой URL. Браузеры обычно кэшируют такой ответ, поэтому последующие запросы к той же короткой ссылке могут идти напрямую к исходному URL, минуя наш сервер.

Ответ клиенту выглядит так:

HTTP/1.1 301 Moved Permanently
Location: https://www.original-long-url.com

2. 302 (Temporary Redirect): означает, что ресурс временно находится по другому URL. Браузеры не кэшируют такой ответ - будущие запросы к короткой ссылке всегда будут сначала проходить через наш сервер.

Ответ клиенту выглядит так:

HTTP/1.1 302 Found
Location: https://www.original-long-url.com

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

Для сервиса сокращения ссылок часто предпочитают 302, потому что:

1. Это дает возможность контролировать срок действия коротких ссылок.
2. Это не позволяет браузеру кэшировать перенаправление, что может создать проблемы, если нам понадобится изменить или удалить короткую ссылку в будущем.
3. Это позволяет считать аналитику по кликам по каждой короткой ссылке (хотя это и вне рамок задачи для нашего дизайна).

Потенциальные погружения в детали

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

1. Как гарантировать уникальность коротких URL?

В high‑level дизайне мы абстрагировали детали генерации коротких URL, но теперь пора разобрать эту часть. Есть несколько ограничений, которые нам нужно принимать во внимание:

1. Мы должны гарантировать уникальность коротких URL.
2. Мы хотим, чтобы генерируемые URL были максимально короткими (это же сервис сокращения).
3. Мы хотим, чтобы короткие URL генерировались быстро и эффективно.

Давайте рассмотрим несколько вариантов и оценим их плюсы и минусы.

2. Как обеспечить быстрые редиректы?

Когда база данных становится большой, быстрый поиск соответствия становится критичным для хорошего UX. Без оптимизаций системе пришлось бы проверять каждую пару короткого URL/исходного URL в базе, чтобы найти нужную. Этот процесс называется Full Table Scan и может быть крайне медленным, особенно когда число строк вырастает до миллионов или миллиардов.

3. Как масштабироваться до 1 млрд URL и 100 млн DAU?

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

Начнем с размера базы данных.

Каждая строка в нашей базе включает short_url (~8 bytes), original_url (~100 bytes) и несколько дополнительных столбцов. Можно округлить до 500 bytes, учитывая дополнительные метаданные вроде created_at, created_by, analytics_id и т. п.

Если мы храним 1 млрд строк, получаем 500 bytes * 1 млрд строк = 500 GB данных. На практике это в пределах возможностей современных SSD. Число URL в интернете - верхняя граница, и оно будет расти, но, вероятно, умеренно. Если мы упремся в лимит на один сервер, всегда можно шардировать данные по нескольким серверам. Но один экземпляр Postgres пока вполне подойдет.

Какую технологию базы выбрать?

На самом деле подойдет почти любая. Мы вынесли большую часть чтения в кэш, а объем записи невысокий. Можно оценить, что создается ~100,000 новых URL в день - это примерно 1 строка в секунду. Значит подойдет любая разумная база данных (Postgres, MySQL, DynamoDB и т. д.). На интервью можете выбрать ту, с которой у вас больше опыта. Если опыта нет - берите Postgres.

Но что если произойдет отказ базы данных?

Это хороший вопрос, и на интервью о нем всегда стоит думать. Есть несколько стратегий, чтобы обеспечить высокую доступность:

1. Репликация базы данных: используя Postgres с поддержкой репликации, можно сделать несколько одинаковых копий базы на разных серверах. Если один сервер отказал - переключаемся на другой. Это повышает сложность нашей системы - нужно, чтобы ведущий сервер корректно работал со всеми репликами. Тут есть подводные камни, и это добавляет дополнительные накладные расходы.
2. Резервное копирование базы данных: можно делать регулярные бэкапы базы и хранить их в отдельном месте. Это тоже добавляет сложности: нужно уметь восстанавливаться из бэкапов и корректно управлять процессом.

Теперь вернемся к основному серверу.

Учитывая, что чтений гораздо больше, чем записей, мы можем масштабировать сервер, разделив read и write операции. Это приводит к микросервисной архитектуре: Сервис чтения обрабатывает редиректы, а Сервис записи - создание новых коротких URL. Такое разделение позволяет независимо масштабировать сервисы горизонтально, в зависимости от нагрузки на них.

Что насчет нашего счетчика?

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

Мы можем реализовать это, используя централизованный экземпляр Redis для хранения счетчика. Redis однопоточный и отлично подходит для этого сценария. Также он поддерживает атомарный инкремент, что позволяет безопасно увеличивать счетчик. Теперь, когда пользователь хочет сократить URL, сервис записи получает следующее значение счетчика из Redis, вычисляет короткую ссылку и сохраняет соответствие в базе.

Нужно ли беспокоиться о накладных расходах на дополнительный запрос по сети на каждую запись?

Скорее всего - нет. Но, тем не менее, можно использовать подход называемый "пакетирование счетчика" (counter batching), чтобы уменьшить число обращений к Redis.

Это работает так:

1. Каждый экземпляр сервиса записи запрашивает пакет значений счетчика у Redis (например, пакет из 1000 значений).
2. Redis атомарно увеличивает счетчик на 1000 и возвращает начало диапазона.
3. Сервис записи может использовать эти 1000 значений локально без обращения к Redis для каждого нового URL.
4. Когда пакет заканчивается, сервис записи запрашивает новый.

Это снижает нагрузку на Redis, сохраняя уникальность между всеми экземплярами сервиса записи. Это также улучшает производительность за счет уменьшения числа сетевых вызовов для получения значений счетчика.

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