Высокоуровневый дизайн URL Shortner
Вступление
Дизайн системы Задачи собеседования намеренно открыты. Это дает интервьюеру возможность оценить дизайнерские навыки, а также глубину технических концепций. Ежедневная инженерная работа включает в себя создание множества масштабируемых систем. Это собеседование также предоставляет платформу для оценки навыков решения проблем и коммуникативных навыков кандидата.
Без достаточной подготовки и практики сложно добиться успеха в разработке системы. Кроме того, это пугает кандидатов, не имеющих опыта работы в распределенных системах. Иногда кажется, что собеседники теряют фокус и отклоняются от темы, если не следуют структурированной методологии.
Очень важно иметь концептуальную ясность концепций проектирования системы, прежде чем решать проблему. В этой статье я выбрал простую задачу разработки службы сокращения URL-адресов. Это простая задача для любого новичка. Нет конкретного правильного или неправильного ответа на проблему проектирования системы. Однако кандидат должен обосновать выбор дизайна, сделанный при решении проблемы.
Мы рассмотрим, как мы должны систематически решать проблему дизайна. Попутно я также коснусь основ распределенных систем, API, проектирования схемы базы данных и компромиссов при проектировании. Давайте начнем.
Понимание проблемы / продукта
Формулировка проблемы здесь такова: Создайте инструмент для сокращения URL-адресов, например tinyurl.com. Если вы не знаете или никогда не слышали о TinyUrl.com, сделайте паузу и посетите веб-сайт. Прежде чем начать обсуждение, нужно понять продукт и его поведение.
Использование продукта даст вам представление о том, как клиенты взаимодействуют с ним. Кроме того, всегда полезно задать интервьюеру несколько уточняющих вопросов -
- Кто являются пользователями этой системы - корпоративные пользователи или вообще любой пользователь
- Как они собираются его использовать - веб-браузеры или мобильные устройства
- Цель приложения - сократить любой URL-адрес в Интернете или внутренний URL-адрес организации.
- Могут ли клиенты предоставлять собственные короткие URL-адреса?
- Хранение данных - временные короткие URL-адреса или постоянные.
Ответы на приведенные выше вопросы помогут лучше понять проблему. Задавание вопросов также показывает, что человек не спешит с решением. Это помогает рассеять любые сомнения и приступить к дизайну с достаточной ясностью.
Требования
Давайте разделим наши требования на функциональные и нефункциональные.
Ниже приведены функциональные требования: -
- Система должна преобразовать длинный URL в короткий URL.
- При вводе короткого URL-адреса в браузере пользователь должен быть перенаправлен на длинную URL-ссылку.
- Пользователь должен иметь возможность предоставить собственный короткий URL-адрес для данного длинного URL-адреса.
- Система должна хранить URL в течение года, а позже удалить все старые записи.
Ниже приведены нефункциональные требования: -
- Сервис должен быть высокодоступным и масштабируемым.
- Он должен обрабатывать высокую пропускную способность с минимальной задержкой.
- Приложение должно быть долговечным и отказоустойчивым.
Поскольку у нас есть ясность в отношении того, что необходимо разработать, мы можем перейти к следующему этапу проектирования.
CP против системы AP
Нам нужно решить, будет ли система системой CP или AP.
Что касается сокращателя URL, можем ли мы поставить под угрозу согласованность, а не доступность? Это то, что требует обсуждения с интервьюером.
В этом случае предположим, что если создается новый URL, он может не сразу стать доступным для использования. Например: - Недавно созданный URL-адрес может быть доступен после задержки в несколько миллисекунд. До тех пор система выдаст ошибку, указывающую, что URL-адрес не найден. Система будет высокодоступной и продолжит отвечать на запросы пользователей.
Поскольку мы решили разработать систему AP, каждый запрос на чтение может не следовать за самой последней записью. Однако в конечном итоге система будет согласованной.
Оценка емкости
Расчет трафика
При разработке крупномасштабной системы нам необходимо знать, сколько пользователей будет ее использовать. Каковы будут шаблоны доступа к данным? сколько серверов приложений и данных потребуется.
Ответ на поставленные вопросы в предположении. Предполагается, что кандидат сделает приблизительную оценку того, сколько пользователей будет пользоваться услугой?
Предположим, что у нас 200 млн пользователей. Из 200 миллионов пользователей 2 миллиона могут активно сокращать URL. В среднем за каждый день поступает 10 запросов (чтение + запись).
Итак, у нас каждый день создается 20 млн таких записей. Остальные 20 млн пользователей получат длинный URL-адрес обратно из короткого URL-адреса. Предполагая, что каждый пользователь запускает 10 запросов, у нас получается 200 миллионов запросов. Это получается 2300 запросов в секунду.
Вычисление хранилища
Ежедневно генерируется 20 млн URL. Допустим, система предназначена для обработки запросов в течение следующих пяти лет.
Общее количество URL-адресов для хранения = 20 млн * 30 (дней) * 12 * 5 = 36 млрд
Мы будем хранить длинный URL, короткий URL, созданные и измененные поля в хранилище данных. Каждая запись будет занимать 0,5 КБ памяти. Таким образом, общий объем необходимого хранилища составит 36 млрд * 0,5 КБ = 18 ТБ.
API
В соответствии с требованиями, у нас будут следующие API:
- Сократите длинный URL
В теле запроса в качестве необязательного параметра будет использоваться customShortUrl. Если его нет, он будет считаться пустым.
Внутренний сервер будет выполнять проверку длины длинного URL-адреса. Соответственно, он вернет следующие коды ответов: -
▹ 400 - Неверный запрос
▹ 201- Создано. Добавлена запись сопоставления URL
▹ 200- ОК. Идемпотентный ответ на повторяющийся запрос
- Получить длинный URL из короткого
Если система находит длинный URL-адрес, соответствующий короткому URL-адресу, пользователь будет перенаправлен. Код ответа HTTP будет 302.
Служба выдаст ошибку 404 (Not Found), если короткий URL-адрес отсутствует. Он выполнит проверку длины ввода. В случае, если длина превышает пороговое значение, будет выбрано 400 (неверный запрос).
Стандартные блоки и алгоритм сокращения URL
Ключевые компоненты
Ниже перечислены ключевые компоненты приложения для сокращения URL-адресов:
- Клиенты - веб-браузеры / мобильное приложение. Он будет связываться с внутренними серверами по протоколу HTTP.
- Балансировщик нагрузки - для равномерного распределения нагрузки между внутренними серверами.
- Веб-серверы - для горизонтального масштабирования будут развернуты несколько экземпляров веб-серверов.
- База данных - будет использоваться для хранения сопоставления длинных URL-адресов с короткими URL-адресами.
Ниже приведен общий эскиз компонентов и взаимодействия между ними: -
Алгоритм сокращения
По нашим оценкам, системе потребуется хранить 36 миллиардов URL. Короткий URL-адрес может состоять из нижнего регистра ('a' - 'z'), верхнего регистра ('A' - 'Z') и чисел ( 0–9). Для поддержки 36 миллиардов URL-адресов короткий URL-адрес должен содержать не менее 6 символов.
⁶²⁶ = 56.8 Bn.
Один из простейших подходов к преобразованию длинного URL-адреса в короткий - использовать хеширование. Передайте длинный URL-адрес функции хеширования, чтобы получить строку фиксированной длины (например: - 32-байтовая строка). Затем извлеките первые 6 символов, чтобы получить короткий URL.
Однако у использования вышеупомянутого подхода есть два недостатка:
- Два разных URL-адреса могут соответствовать одному короткому URL-адресу. Это результат столкновений. Использование единой хеш-функции может снизить вероятность столкновения. Кроме того, для хеширования можно использовать псевдослучайное число.
- Если пользователь пытается несколько раз сократить один и тот же длинный URL-адрес, он должен каждый раз получать разные результаты. В этом случае из-за коллизии вероятность того, что длинный URL вернет тот же короткий URL, высока.
Генератор URL-адресов
Нам необходимо гарантировать уникальность каждого сокращаемого длинного URL. Для этого мы можем предварительно сгенерировать набор коротких URL-адресов и сохранить его в базе данных. Для управления этими короткими URL-адресами можно ввести новый уровень. Назовем этот уровень службы службой генерации URL.
Сервис будет действовать как источник всех коротких URL-адресов. Служба сокращения URL-адресов получит от этой службы новый короткий URL-адрес. Впоследствии он будет хранить сопоставление между длинными и короткими URL-адресами. Следующая диаграмма иллюстрирует этот процесс: -
Вышеупомянутый процесс гарантирует, что каждому запросу будет назначен уникальный короткий URL-адрес. У описанного выше подхода есть несколько проблем. Мы рассмотрели случай, когда одна служба запрашивает крошечный URL-адрес. Что делать, если запущено несколько служб сокращения URL-адресов?
Проблемы параллелизма
Масштабирование указанной выше системы может привести к проблемам с параллелизмом. При неправильной обработке один и тот же URL-адрес может быть выделен двум разным службам.
Чтобы решить эту проблему, мы можем связать состояние с крошечным URL-адресом. Крошечный URL-адрес может иметь два состояния - АКТИВНЫЙ и НЕАКТИВНЫЙ. По умолчанию все URL-адреса находятся в состоянии НЕАКТИВНО. После того, как он выделен клиенту, он должен быть помечен как АКТИВНЫЙ. Клиентам могут быть назначены только АКТИВНЫЕ URL-адреса.
Чтобы уменьшить задержку, служба генерации URL может предварительно выбрать все крошечные URL-адреса из хранилища данных. Это позволит избежать обращений к базе данных для каждого нового запроса. Более того, теперь он может использовать структуру данных блокировки для синхронизации доступа нескольких клиентских приложений.
Схема базы данных
Нам понадобится одна таблица для хранения сопоставления между длинными URL-адресами и короткими URL-адресами. Может использоваться следующая схема: -
Схема сопоставления URL-адресов
Поскольку столбец short_url является первичным ключом, его индексирование и поиск будут быстрыми. Были включены два поля отметки времени created_at и modified_at. Эти поля помогут удалить все старые записи в таблице.
Чтобы выбрать между СУБД или СУБД без SQL, давайте еще раз рассмотрим наши оценки хранилища. Мы хотим хранить не менее 18 ТБ данных. Кроме того, мы хотим обслуживать запросы с минимальной задержкой.
Лучше, чтобы данные были распределены по разным машинам. Это предотвратит возникновение единой точки отказа. Следовательно, в этом случае потребуется сегментирование данных.
Кроме того, у нас нет модели данных с отношениями. Здесь нет требований к присоединению. Кроме того, мы ожидаем, что размер наших данных будет постепенно увеличиваться. Кроме того, наша система должна работать как система AP.
Принимая во внимание вышеизложенное, NoSQL кажется здесь явным победителем. Базы данных NoSQL имеют встроенное сегментирование и их легче масштабировать.
Компромиссы и узкие места
Как масштабировать читает
- Кеширование. Добавив кеш, мы можем масштабировать запросы чтения. Если с одним и тем же коротким URL-адресом получено несколько запросов, служба может вернуть длинный URL-адрес из кеша. Мы можем использовать LRU (Least Recently Used) в качестве политики выселения кеша.
- Репликация данных - мы можем отделить чтение от запросов записи. Запись может выполняться на ведущем устройстве, а данные могут быть реплицированы на ведомые устройства. Подчиненные устройства могут использоваться для выполнения запросов чтения.
Как сегментировать данные
Хранение данных на одном сервере базы данных может вызвать узкие места. Может быть единственная точка отказа. С ростом трафика возрастет и давление чтения / записи в базе данных. Следовательно, лучше распределять данные по разным серверам баз данных.
У нас есть следующие три стратегии для сегментирования данных:
- Разделение на основе диапазона. В этой стратегии URL-адреса, начинающиеся с "ah", могут быть назначены серверу 1, а URL-адреса, начинающиеся с "io" к серверу 2 и так далее. При таком подходе существует вероятность неравномерного распределения данных. Это может привести к тому, что один осколок будет иметь в два или три раза больше данных другого.
- Разделение на основе хэша - этот метод исключает возможность неравномерного распределения данных. Однако он плохо масштабируется при добавлении новых серверов или удалении существующих.
- Последовательное хеширование. Эта стратегия разделения преодолевает ограничения двух вышеупомянутых стратегий. Распределение данных равномерное, и добавление или удаление новых серверов влияет на минимальное количество записей.
Очистка URL-адресов
Необходимо запланировать асинхронное задание для удаления всех сокращенных URL-адресов с истекшим сроком действия. Это задание отфильтрует все URL-адреса с истекшим сроком действия и вернет их в хранилище данных для использования в будущем. После очистки URL-адресов состояние крошечного URL-адреса изменится на НЕАКТИВНЫЙ. Служба продолжит функционировать как есть и назначит один из НЕАКТИВНЫХ URL-адресов для нового клиентского запроса.
использованная литература
Уровень кодирования
Спасибо, что стали частью нашего сообщества! Подпишитесь на наш канал YouTube или присоединитесь к Интервью по программированию Skilled.dev.
