Как укорачиваются ссылки на TinyURL и Bit.ly?

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

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

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

Понадобится знание:

1. Генератора последовательностей.


2. Типов кодировки: Base 58, Base 64.


3. Глобальной балансировки нагрузки серверов.


4. Рукописных математических расчетов по оценке ресурсов.

Что изучим о проектировании систем?

Мы разделили это на семь модулей:

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

2. Оценка ресурсов  —  серверов, пропускной способности, хранилища.

3. Подробно о строительных блоках.

4. Системные API-интерфейсы.

5. Компоненты и схема рабочего процесса.

6. Схемы кодирования и вычисления.

7. Соответствие нефункциональным требованиям.

Почему сокращенный URL-адрес удобнее?

• Легко запоминается/вводится: использование ссылок на различных устройствах оптимизируется благодаря их повышенной доступности и защите от вымирания.


• Выглядит профессионально, привлекательно, упрощает обмен информацией.


• Требует меньшего объема памяти на стороне пользователя.

Модуль 1. Требования

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

Рассмотрим фактическую функциональность этой системы, без требований начинать проектирование нельзя:

• Короткий URL-адрес: сервисом генерируется уникальный короткий псевдоним данного URL-адреса.


• Перенаправление: по короткой ссылке пользователь перенаправляется системой на исходный URL-адрес.


• Пользовательские короткие ссылки: генерируются в системе пользователями для своих URL-адресов.


• Удаление: пользователи удаляют сгенерированную системой короткую ссылку.

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

Этими критериями определяется поведение системы, а не действия:

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


• Масштабируемость: система горизонтально масштабируется с учетом растущей потребности.


• Удобство восприятия: короткие ссылки, генерируемые системой, удобны для восприятия, различимы, пригодны для ввода.


• Задержка: система функционирует с низкой задержкой, чем обеспечивается хорошее пользовательское взаимодействие.


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

Модуль 2. Оценка ресурсов

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

Допущения

• Соотношение запросов на сокращение/перенаправление  —  1:100. То есть, если сокращается 1000 URL-адресов, то перенаправлений на эти сокращенные URL-адреса ~100 000.


• Новых, уникальных запросов от пользователей на сокращение URL-адресов  —  200 млн в месяц.


• На запись сокращения каждого URL-адреса требуется 500 байт в базе данных, включая всю необходимую информацию для перенаправления пользователей на исходный URL-адрес.


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


• Активных пользователей ежедневно  —  100 млн: столько людей активно используют сервис каждый день, создают сокращенные URL-адреса и/или переходят по сокращенным ссылкам.

Оценка хранилища

Поскольку записи хранятся пять лет и каждый месяц их по 200 млн, всего будет ~12 млрд записей:

Поскольку каждая запись  —  500 байт, общая оценка хранилища  —  6 Тбайт:

Частота запросов

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

Исходя из приведенных выше оценок, для 200 млн запросов на сокращение URL-адресов ожидается 20 млрд запросов на перенаправление в месяц:

У нас 200 млн запросов на сокращение URL-адресов и 20 млрд запросов на перенаправление в месяц.

Посчитаем теперь для системы количество запросов в секунду, взяв полученное только что значение, количество секунд и в среднем 30 дней в месяце:

С учетом соотношения сокращения к перенаправлению 1:100 рассчитаем скорость перенаправления URL-адресов в секунду:

Оценка пропускной способности

Пропускная способность = трафик × средний размер ответа.

• Трафик  —  это количество запросов в единицу времени, например запросов в секунду.


• Средний размер ответа считается в байтах.

Запросы на сокращение: известна ожидаемая частота поступления 77 новых URL-адресов в секунду.

Всего поступающих данных 308 Kбит в секунду.

Запросы на перенаправление: ожидаемая частота перенаправления 7,7 тыс. URL-адресов в секунду, поэтому всего исходящих данных 30,8 Мбит/с:

Входящая пропускная способность = 308 Кбит/с.

Исходящая пропускная способность = 30,8 Мбит/с.

Оценка сервера

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

Допущения

• Активных пользователей ежедневно  —  500 млн.


• В среднем один пользователь делает 20 запросов в день.


• На одном сервере обрабатывается 8000 запросов в секунду.

Для 500 миллионов пользователей 15 серверов явно не достаточно, в крупных сервисах их намного больше. Значит, что-то не так с вычислениями, простой подсчет количества запросов в секунду не дает полной картины потребностей в серверах.

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

Поэтому, чтобы рассчитать необходимое количество серверов, учтем два фактора:

• ежедневное количество активных пользователей;


• ежедневный лимит обработки пользователей сервером.

Эта цифра реалистичнее  —  12 500 серверов.

Кэш: оценка памяти

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

Кэшируя только 20% этих ежедневных запросов на перенаправление, получим общую оценку требуемой памяти 66 ГБ.

То есть 66 ГБ кэша вполне достаточно.

Модуль 3. Строительные блоки

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

• База данных: для хранения сопоставлений длинных URL-адресов с короткими.


• Генератор последовательностей: с уникальными идентификаторами  —  отправной точкой для создания каждого короткого URL-адреса.


• Балансировщик нагрузки: для равномерного распределение запросов между доступными серверами на различных уровнях.


• Кэш: для хранения частотных запросов, связанных с короткими URL-адресами.


• Ограничитель скорости: для предотвращения злонамеренного использования системы.


• Серверы: для обработки запросов сервисов вместе с запуском логики приложения.


• Кодировщик Base-58: для преобразования цифровых выходных данных генератора последовательностей в более удобную буквенно-цифровую форму.

Модуль 4. Системные API-интерфейсы

Для функциональности сервиса снабдим REST API-интерфейсами:

• сокращение URL-адреса;


• перенаправление короткого URL-адреса;


• удаление короткого URL-адреса.

Сокращение URL-адреса

Создадим новые короткие URL-адреса с таким определением:

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

Перенаправление короткого URL-адреса

Вот определение REST API для перенаправления короткого URL-адреса:

При успешном перенаправлении пользователь оказывается в исходном URL-адресе, связанном с url_key.

Удаление короткого URL-адреса

Вот аналогичное определение REST API для удаления короткого URL-адреса:

При успешном удалении возвращается системное сообщение URL Removed Successfully (URL-адрес удален).

Проектирование базы данных

Посмотрим на данные для сохранения:

Данные пользователя

• UserID: специальный идентификатор или API-ключ для однозначной идентификации пользователей по всему миру.


• Name: имя пользователя.


• Email: адрес электронной почты пользователя.


• Creation Date: дата, когда пользователь зарегистрировался для создания короткого URL-адреса.

Данные короткого URL-адреса

• Короткий URL-адрес: уникальный короткий URL-адрес длиной обычно в семь символов.


• Исходный URL-адрес: исходный длинный URL-адрес.


• UserID: уникальный идентификатор или API-ключ пользователя, создавшего короткий URL-адрес.

Модуль 5. Компоненты и рабочий процесс подробно

1. База данных: для сервисов сокращения URL-адресов объем сохраняемых данных минимален, но хранилище горизонтально масштабируется. Какие данные сохраняются:

• сведения о пользователе;


• сопоставления URL-адресов: длинных с короткими.

Почему система/хранилище горизонтально масштабируется?

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

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

MongoDB ― хороший вариант, потому что:

• им применяются реплики для интенсивного считывания;


• без проблем справляется с одновременными операциями записи.

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

2. Генератор коротких URL-адресов, он состоит из двух частей:

• генератора последовательностей для создания уникальных идентификаторов;


• кодировщика Base-58 для удобства восприятия коротких URL-адресов.

Генератор последовательностей:

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

Кодировщик Base-58:

Так же, как генерирование уникальных идентификаторов, для пользовательского взаимодействия важно создание сокращенных URL-адресов, удобных для человеческого восприятия и совместного использования. Здесь приходится кстати кодировщик Base-58, который отличается от Base-64 исключением символов 0, O, I и l  —  нуля, заглавных букв o, i и строчной L соответственно. Так удается избежать путаницы, сделать кодировку удобнее.

3. Балансировка нагрузки

Для высокой доступности применим:

• глобальную балансировку нагрузки на серверы, когда запросы распределяются между различными глобальными серверами, особенно во время сбоев на местах, чем обеспечивается эффективная обработка трафика;


• локальную балансировку нагрузки.

Почему нужны обе балансировки?

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

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

4. Кэш: идеальный инструмент кэширования для приложений интенсивного считывания  —  Memcached. В каждом дата-центре для обработки ближайших запросов реализуется слой кэширования, ранее также обсуждались требования по хранилищу кэша.

5. Ограничитель скорости: для ограничения задач сокращения и перенаправления, выполняемых за определенное время, у каждого пользователя имеется уникальный ключ api_dev_key.

Рабочий процесс

Рассмотрим, как реализуется функциональность системы при взаимодействии всех ее частей.

1. Сокращение: когда пользователь запрашивает короткую ссылку, сервером приложений его запрос перенаправляется генератору коротких URL-адресов. Как только короткая ссылка сгенерирована, одна копия отправляется пользователю, а url_key сохраняется в базе данных для дальнейшего использования.


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


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


4. Пользовательские короткие ссылки: системой проверяется соответствие запрашиваемого короткого URL-адреса критериям, максимальная длина  —  11 буквенно-цифровых символов. В случае соответствия системой проверяется его наличие в базе данных. При наличии пользователь получает сообщение о генерировании короткого URL-адреса, в противном случае  —  сообщение об ошибке.

Вот схема рабочего процесса:

Модуль 6. Кодирование

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

Имеются такие кодировки:

• Base 64: применяется 64 символа (A-Z, a-z, 0–9, +, /) для представления двоичных данных.


• Base 62: отличается от Base-64 исключением символов, небезопасных для URL-адресов, например +, /. Применяется 62 символа (A-Z, a-z, 0–9).


• Base 58: отличается от Base 62 дополнительным исключением похожих символов 0, O, I и l  —  нуля, заглавных букв o, i и строчной L соответственно. Так повышается удобство восприятия.

Для удобства восприятия и во избежание путаницы между внешне похожими символами в системе применяется кодировка Base 58:

Преобразуем число из Base 58 в Base 10, и наоборот.

Преобразование из Base 58 в Base 10:

Преобразование из Base 10 в Base 58:

Определим оптимальное количество символов для сокращенного URL-адреса:

Для URL-адреса длиной 5 получим 58⁵, то есть ~656 млн URL-адресов.
Для URL-адреса длиной 6 получим 58⁶, то есть ~38 млрд URL-адресов.

Поскольку системой за счет использования хранилища генерируется 12 млрд URL-адресов, для шести символов в base58 получаем приблизительно 38 миллиардов URL-адресов. Следовательно, каждый сгенерированный короткий URL-адрес состоит из шести символов.

С чего начинается расчет генератора последовательностей для шести символов в коротком URL-адресе?

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

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

Выполнив обратные вычисления, мы определили: чтобы достигнуть минимум шести символов в base-58, требуемое количество в base-10  —  приблизительно миллиард.

Число Base 10: 1 000 000 000

1000000000 % 58 = 18
  17241379 % 58 = 9
    297265 % 58 = 15
      5125 % 58 = 21
        88 % 58 = 30
         1 % 58 = 1
Эквивалент Base 58: [1][30][21][15][9][18]
                  : 2XNGAK

Итак, минимальное число base 10 для последовательности base 58 длиной шесть равно одному миллиарду. Короткие URL-адреса для любого случайного пользователя начинают генерироваться генератором последовательностей с одного миллиарда.

Модуль 7. Обзор нефункциональных требований

Итак, исходя из уже спроектированного, мы обнаруживаем соответствие всем функциональным требованиям.

Как насчет нефункциональных?

Обсудим и подведем итоги.

Доступность

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


• Глобальной балансировкой нагрузки на серверы обрабатывается трафик системы, запросы распределяются.


• Ограничителями скорости ограничивается распределение ресурсов каждого пользователя, предотвращаются DDOS-атаки.

Масштабируемость

• Используются горизонтально сегментированные базы данных.


• MongoDB  —  как нереляционная БД.

Удобство восприятия

• Внедрение кодировщика base-58 для генерирования коротких URL-адресов.


• Удаление не буквенно-цифровых символов.


• Удаление похожих символов.

Задержка

MongoDB, благодаря низкой задержке и высокой пропускной способности в задачах считывания.

Непредсказуемость

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

Кроме того, чтобы хешировать исходный URL-адрес и далее кодировать получаемый хеш в представление покороче, неплохо использовать криптографические хеш-функции, такие как SHA-256.

Вот и все.