Как создать службу сокращения URL, например TinyURL?

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

Постановка вопроса. Давайте разработаем сервис сокращения URL-адресов, такой как TinyURL. Эта служба будет предоставлять короткие псевдонимы, перенаправляющие на длинные URL-адреса.

1. Зачем нам нужно сокращение URL?

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

Например, когда мы сократили эту страницу через TinyURL:

› https://www.designgurus.org/course/grokking-the-system-design-interview

У нас есть:

› https://tinyurl.com/vzet59pa

Сокращенный URL-адрес почти в три раза меньше фактического URL-адреса.

Сокращение URL-адресов используется для оптимизации ссылок на разных устройствах, отслеживания отдельных ссылок для анализа аудитории, измерения эффективности рекламных кампаний или скрытия связанных исходных URL-адресов.

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

2. Требования и цели системы

Наша система сокращения URL-адресов должна соответствовать следующим требованиям:

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

  1. Учитывая URL-адрес, наша служба должна генерировать более короткий и уникальный псевдоним. Это называется короткой ссылкой. Эта ссылка должна быть достаточно короткой, чтобы ее можно было легко скопировать и вставить в приложения.
  2. Когда пользователи получают доступ к короткой ссылке, наш сервис должен перенаправить их на исходную ссылку.
  3. При желании пользователи должны иметь возможность выбрать собственную короткую ссылку для своего URL-адреса.
  4. Срок действия ссылок истекает через стандартный промежуток времени по умолчанию. Пользователи должны иметь возможность указать время истечения срока действия.

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

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

Расширенные требования:

  1. Аналитика; например, сколько раз произошло перенаправление?
  2. Наш сервис также должен быть доступен через REST API для других сервисов.

3. Оценка пропускной способности и ограничения

Наша система будет загружена чтением. Будет много запросов на перенаправление по сравнению с новыми сокращениями URL. Предположим, что соотношение между чтением и записью составляет 100:1.

Оценка трафика. Предполагая, что у нас будет 500 миллионов новых сокращений URL-адресов в месяц с соотношением чтения/записи 100:1, мы можем ожидать 50 миллиардов переадресаций за тот же период: 100 * 500 млн. =› 50 млрд

Какими будут запросы в секунду (QPS) для нашей системы? Сокращение новых URL-адресов в секунду: 500 миллионов / (30 дней * 24 часа * 3600 секунд) = ~200 URL-адресов/с

Учитывая соотношение чтения/записи 100:1, перенаправления URL-адресов в секунду будут следующими: 100 * 200 URL-адресов/с = 20 000/с

Оценочный объем хранилища. Предположим, мы храним каждый запрос на сокращение URL (и связанную с ним укороченную ссылку) в течение 5 лет. Поскольку мы ожидаем, что ежемесячно будет появляться 500 млн новых URL-адресов, общее количество объектов, которые мы собираемся хранить, составит 30 млрд: 500 млн * 5 лет * 12 месяцев = 30 млрд

Давайте предположим, что каждый сохраненный объект будет иметь размер примерно 500 байт (просто приблизительная оценка — мы углубимся в нее позже). Нам потребуется 15 ТБ общего объема хранилища: 30 миллиардов * 500 байт = 15 ТБ.

Оценка пропускной способности. Для запросов на запись, поскольку мы ожидаем 200 новых URL-адресов каждую секунду, общий объем входящих данных для нашей службы составит 100 КБ в секунду: 200 * 500 байт = 100 КБ/с.

Для запросов на чтение, поскольку каждую секунду мы ожидаем перенаправления ~20 тыс. URL-адресов, общий объем исходящих данных для нашей службы составит 10 МБ в секунду: 20 КБ * 500 байт = ~10 МБ/с

Оценка памяти. Если мы хотим кэшировать некоторые из популярных URL-адресов, к которым часто обращаются, сколько памяти нам потребуется для их хранения? Если мы будем следовать правилу 80–20, что означает, что 20% URL-адресов генерируют 80% трафика, мы хотели бы кэшировать эти 20% горячих URL-адресов.

Так как у нас есть 20 тысяч запросов в секунду, мы будем получать 1,7 миллиарда запросов в день: 20 тысяч * 3600 секунд * 24 часа = ~1,7 миллиарда

Чтобы кэшировать 20 % этих запросов, нам потребуется 170 ГБ памяти: 0,2 * 1,7 миллиарда * 500 байт = ~170 ГБ

Здесь следует отметить, что, поскольку будет много повторяющихся запросов (одного и того же URL), фактическое использование памяти будет меньше 170 ГБ.

4. Системные API

У нас могут быть API-интерфейсы SOAP или REST для раскрытия функциональности нашего сервиса. Ниже приведены определения API для создания и удаления URL-адресов:

createURL(api_dev_key, original_url, custom_alias=None, user_name=None, expire_date=None)

Параметры:

api_dev_key (строка): ключ разработчика API зарегистрированной учетной записи. Это будет использоваться, помимо прочего, для ограничения пользователей на основе их выделенной квоты.

original_url (string): исходный URL-адрес, который необходимо сократить.

custom_alias (строка): необязательный пользовательский ключ для URL.

user_name (строка): необязательное имя пользователя, которое будет использоваться в кодировке.

expire_date (строка): необязательная дата истечения срока действия для сокращенного URL-адреса.

Возврат: (строка)

Успешная вставка возвращает сокращенный URL-адрес; в противном случае возвращается код ошибки.

deleteURL(api_dev_key, url_key)

Где «url_key» — это строка, представляющая сокращенный URL-адрес, который необходимо получить; успешное удаление возвращает «URL удален».

Как мы выявляем и предотвращаем злоупотребления? Злоумышленник может вывести нас из бизнеса, используя все ключи URL в текущем дизайне. Чтобы предотвратить злоупотребления, мы можем ограничить пользователей через их ключ api_dev_key. Каждый ключ api_dev_key может быть ограничен определенным количеством созданий и перенаправлений URL-адресов за определенный период времени (для каждого ключа разработчика может быть установлена ​​разная продолжительность).

5. Дизайн базы данных

Несколько замечаний о характере данных, которые мы будем хранить:

  1. Нам нужно хранить миллиарды записей.
  2. Каждый объект, который мы храним, имеет небольшой размер (менее 1 КБ).
  3. Между записями нет никаких отношений, кроме хранения того, какой пользователь создал URL.
  4. Наш сервис читается тяжело.

Схема базы данных:

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

Какую базу данных мы должны использовать? Поскольку мы предполагаем хранить миллиарды строк и нам не нужно использовать отношения между объектами, лучшим выбором будет хранилище NoSQL, такое как DynamoDB, Cassandra или Riak. Выбор NoSQL также будет легче масштабировать.

6. Базовый дизайн системы и алгоритм

Проблема, которую мы здесь решаем, заключается в том, как сгенерировать короткий и уникальный ключ для заданного URL-адреса.

В примере TinyURL в Разделе 1 сокращенный URL-адрес — «https://tinyurl.com/vzet59pa». Последние восемь символов этого URL составляют короткий ключ, который мы хотим сгенерировать. Здесь мы рассмотрим два решения:

а. Кодирование фактического URL

Мы можем вычислить уникальный хэш (например, MD5 или SHA256 и т. д.) данного URL-адреса. Затем хэш можно закодировать для отображения. Эта кодировка может быть base36 ([az, 0–9]) или base62 ([AZ, a-z, 0–9]), и если мы добавим «+» и «/», мы можем использовать кодировку Base64. Резонным будет вопрос, какой должна быть длина короткого ключа? 6, 8 или 10 символов?

При использовании кодировки base64 ключ длиной в 6 букв дает 64⁶ = ~68,7 млрд возможных строк.

При использовании кодировки base64 ключ длиной в 8 букв дает 64⁸ = ~281 триллион возможных строк.

Предположим, что для нашей системы достаточно 68,7 Б уникальных строк.

Если мы будем использовать алгоритм MD5 в качестве нашей хеш-функции, он создаст 128-битное хеш-значение. После кодирования base64 мы получим строку, содержащую более 21 символа (поскольку каждый символ base64 кодирует 6 бит хеш-значения). Теперь у нас есть место только для 6 (или 8) символов на одну короткую клавишу; как мы тогда выберем наш ключ? В качестве ключа мы можем взять первые 6 (или 8) букв. Это может привести к дублированию ключей; чтобы решить эту проблему, мы можем выбрать некоторые другие символы из строки кодирования или поменять местами некоторые символы.

Каковы другие проблемы с нашим решением? У нас есть следующие две проблемы с нашей схемой кодирования:

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

Что делать, если части URL-адреса закодированы в URL-адресе? например, https://www.designgurus.org/distributed.php?id=design и https://www.designgurus.org/distributed.php%3Fid%3Ddesign идентичны, за исключением кодировки URL.

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

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

б. Генерация ключей в автономном режиме

У нас может быть отдельная служба генерации ключей (KGS), которая заранее генерирует случайные строки из шести букв и сохраняет их в базе данных (назовем ее key-DB). Всякий раз, когда мы хотим сократить URL-адрес, мы берем один из уже сгенерированных ключей и используем его. Такой подход сделает все довольно просто и быстро. Мы не только не кодируем URL-адрес, но нам не придется беспокоиться о дублировании или коллизиях. KGS позаботится о том, чтобы все ключи, вставленные в базу ключей, были уникальными.

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

Серверы могут использовать KGS для чтения/маркировки ключей в базе данных. KGS может использовать две таблицы для хранения ключей: одну для ключей, которые еще не используются, и одну для всех используемых ключей. Как только KGS передает ключи одному из серверов, он может переместить их в таблицу используемых ключей. KGS всегда может хранить некоторые ключи в памяти, чтобы быстро предоставить их, когда они потребуются серверу.

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

KGS также должен следить за тем, чтобы один и тот же ключ не предоставлялся нескольким серверам. Для этого он должен синхронизировать (или заблокировать) структуру данных, содержащую ключи, прежде чем удалять из нее ключи и передавать их серверу.

Каков будет размер базы данных ключей? С помощью кодировки base64 мы можем сгенерировать 68,7 Б уникальных шестибуквенных ключей. Если нам нужен один байт для хранения одного буквенно-цифрового символа, мы можем хранить все эти ключи в:

6 (символов на ключ) * 68,7 Б (уникальные ключи) = 412 ГБ.

Разве KGS не является единственной точкой отказа? Да, это так. Чтобы решить эту проблему, мы можем иметь резервную копию KGS. Всякий раз, когда основной сервер умирает, резервный сервер может взять на себя генерацию и предоставление ключей.

Может ли каждый сервер приложений кэшировать некоторые ключи из базы данных ключей? Да, это, безусловно, может ускорить работу. Хотя в этом случае, если сервер приложений умрет до того, как использует все ключи, мы в конечном итоге потеряем эти ключи. Это может быть приемлемо, поскольку у нас есть 68-битные уникальные шестибуквенные ключи.

Как мы будем выполнять поиск ключа? Мы можем найти ключ в нашей базе данных, чтобы получить полный URL-адрес. Если он присутствует в БД, выдайте статус «HTTP 302 Redirect» обратно в браузер, передав сохраненный URL-адрес в поле «Расположение» запроса. Если этот ключ отсутствует в нашей системе, выдайте статус «HTTP 404 Not Found» или перенаправьте пользователя обратно на домашнюю страницу.

Должны ли мы накладывать ограничения на размер пользовательских псевдонимов? Наша служба поддерживает пользовательские псевдонимы. Пользователи могут выбрать любой «ключ», который им нравится, но предоставление собственного псевдонима не является обязательным. Однако разумно (и часто желательно) налагать ограничение на размер пользовательского псевдонима, чтобы обеспечить согласованность базы данных URL-адресов. Предположим, что пользователи могут указать максимум 16 символов для каждого ключа клиента (как показано в приведенной выше схеме базы данных).

7. Разделение и репликация данных

Чтобы масштабировать нашу БД, нам нужно разделить ее, чтобы она могла хранить информацию о миллиардах URL-адресов. Поэтому нам необходимо разработать схему разбиения, которая разделяла бы и хранила наши данные на разных серверах БД.

а. Разделение на основе диапазона: мы можем хранить URL-адреса в отдельных разделах на основе первой буквы ключа хеша. Следовательно, мы сохраняем все хеш-ключи URL, начинающиеся с буквы «А» (и «а»), в одном разделе, сохраняем те, которые начинаются с буквы «В», в другом разделе и так далее. Такой подход называется секционированием на основе диапазона. Мы даже можем объединить некоторые менее часто встречающиеся буквы в один раздел базы данных. Таким образом, мы должны разработать статическую схему разбиения, чтобы всегда хранить/находить URL предсказуемым образом.

Основная проблема с этим подходом заключается в том, что он может привести к несбалансированности серверов БД. Например, мы решили поместить все URL-адреса, начинающиеся с буквы «Е», в раздел БД, но позже мы поняли, что у нас слишком много URL-адресов, начинающихся с буквы «Е».

б. Разбиение на основе хэша. В этой схеме мы берем хэш объекта, который сохраняем. Затем мы вычисляем, какой раздел использовать на основе хэша. В нашем случае мы можем взять хэш «ключа» или короткую ссылку, чтобы определить раздел, в котором мы храним объект данных.

Наша хэш-функция будет случайным образом распределять URL-адреса по разным разделам (например, наша хеш-функция всегда может сопоставить любой «ключ» с числом между [1…256]). Это число будет представлять раздел, в котором мы храним наш объект.

Такой подход по-прежнему может привести к перегрузке разделов, что можно решить с помощью Consistent Hashing.

8. Кэш

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

Сколько у нас должно быть кэш-памяти? Мы можем начать с 20 % ежедневного трафика и в зависимости от моделей использования клиентов мы можем настроить необходимое количество кэш-серверов. Как было подсчитано выше, нам нужно 170 ГБ памяти для кэширования 20% ежедневного трафика. Поскольку современный сервер может иметь 256 ГБ памяти, мы можем легко разместить весь кэш на одной машине. В качестве альтернативы мы можем использовать пару небольших серверов для хранения всех этих популярных URL-адресов.

Какая политика удаления кеша лучше всего соответствует нашим потребностям? Когда кеш заполнен и мы хотим заменить ссылку более новым/более популярным URL-адресом, что мы выберем? Наименее недавно использованные (LRU) могут быть разумной политикой для нашей системы. В соответствии с этой политикой мы сначала отбрасываем наименее использовавшийся URL-адрес. Мы можем использовать связанную хеш-карту или аналогичную структуру данных для хранения наших URL-адресов и хэшей, которые также будут отслеживать URL-адреса, к которым недавно обращались.

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

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

9. Балансировщик нагрузки (LB)

Мы можем добавить уровень балансировки нагрузки в трех местах нашей системы:

  1. Между клиентами и серверами приложений
  2. Между серверами приложений и серверами баз данных
  3. Между серверами приложений и кэш-серверами

Первоначально мы могли бы использовать простой балансировщик нагрузки Round Robin, который равномерно распределяет входящие запросы между внутренними серверами. Этот LB прост в реализации и не требует дополнительных затрат. Еще одним преимуществом является то, что если сервер мертв, LB выведет его из ротации и перестанет отправлять на него трафик.

Проблема с Round Robin LB заключается в том, что мы не учитываем нагрузку на сервер. В результате, если сервер перегружен или работает медленно, LB не перестанет отправлять новые запросы на этот сервер. Чтобы справиться с этим, можно разместить более интеллектуальное решение LB, которое периодически опрашивает внутренний сервер о его нагрузке и регулирует трафик на основе этого.

10. Очистка или очистка БД

Должны ли записи оставаться навсегда, или они должны быть удалены? Если достигнуто указанное пользователем время истечения срока действия, что должно произойти со ссылкой?

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

  • Всякий раз, когда пользователь пытается получить доступ к просроченной ссылке, мы можем удалить ссылку и вернуть пользователю ошибку.
  • Отдельная служба очистки может периодически запускаться для удаления просроченных ссылок из нашего хранилища и кеша. Эта служба должна быть очень легкой и должна запускаться только тогда, когда ожидается низкий пользовательский трафик.
  • У нас может быть срок действия по умолчанию для каждой ссылки (например, два года).
  • После удаления ссылки с истекшим сроком действия мы можем поместить ключ обратно в базу данных ключей для повторного использования.
  • Должны ли мы удалять ссылки, которые не посещались в течение некоторого времени, скажем, шести месяцев? Это может быть сложно. Поскольку хранение становится дешевым, мы можем решить сохранить ссылки навсегда.

11. Безопасность и разрешения

Могут ли пользователи создавать частные URL-адреса или разрешать определенному набору пользователей доступ к URL-адресу?

Мы можем сохранить уровень разрешений (общедоступный/частный) для каждого URL-адреса в базе данных. Мы также можем создать отдельную таблицу для хранения идентификаторов пользователей, у которых есть разрешение на просмотр определенного URL-адреса. Если у пользователя нет разрешения и он пытается получить доступ к URL-адресу, мы можем отправить ошибку (HTTP 401) обратно. Учитывая, что мы храним наши данные в базе данных с широкими столбцами NoSQL, такой как Cassandra, ключом для хранения разрешений таблицы будет «хэш» (или сгенерированный KGS «ключ»). В столбцах будут храниться UserID тех пользователей, у которых есть разрешение на просмотр URL-адреса.

12. Резюме

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

Пожалуйста, взгляните на Интервью Grokking the System Design Interview, чтобы узнать больше о таких вопросах, как:

  1. Разработка службы обмена файлами, такой как Google Drive или Dropbox.
  2. Разработка популярной службы обмена сообщениями, такой как Facebook Messenger.
  3. Разработка сайтов популярных социальных сетей, таких как Twitter или Facebook.
  4. Разработка глобального сервиса потокового видео, такого как Youtube.
  5. Разработка глобальной службы заказа такси, такой как Uber.

Чтобы изучить архитектуру программного обеспечения и попрактиковаться в вопросах собеседования по продвинутому системному проектированию, ознакомьтесь с разделом Grokking the Advanced System Design Interview.

Спасибо за прочтение