Вступление
Укорочение URL — это сервис, который используется для создания коротких ссылок из очень длинных URL. Обычно короткие ссылки имеют размер одной трети или даже одной четверти исходного URL, что облегчает их ввод, представление или отправку в Твиттере. При нажатии на короткую ссылку пользователь будет автоматически перенаправлен на исходный URL.
В Интернете доступно множество сервисов сокращения URL-адресов, таких как tiny.cc, bitly.com, cutt.ly и т. Д. Реализация сервиса сокращения URL-адресов не является сложной задачей и часто является частью собеседований по проектированию системы. В этом посте я постараюсь объяснить процесс внедрения сервиса.
теория
Перед внедрением всегда полезно записать, что необходимо сделать, в форме функциональных и нефункциональных требований.
Функциональные требования:
-
Пользователи должны иметь возможность вводить длинный URL. Наш сервис должен сохранить этот URL и создать короткую ссылку.
-
Пользователи должны иметь возможность ввести срок действия. После этой даты короткая ссылка должна быть недействительной.
-
Нажатие на короткую ссылку должно перенаправить пользователя на оригинальный длинный URL.
-
Пользователи должны создать учетную запись для использования сервиса. Сервис может иметь ограничение использования на пользователя. *
-
Пользователь может создать собственную короткую ссылку. *
-
Сервис должен иметь метрики, например, наиболее посещаемые ссылки. *
Нефункциональные требования:
-
Сервис должен быть запущен 100% времени.
-
Перенаправление не должно длиться дольше двух секунд.
* Требования необязательны.
Преобразование URL
Допустим, мы хотим иметь короткую ссылку с максимальной длиной 7. Самое важное в укороченном URL-адресе — это алгоритм преобразования. Преобразование URL может быть реализовано несколькими различными способами, и у каждого способа есть свои плюсы и минусы.
Одним из способов создания коротких ссылок было бы хеширование исходного URL с помощью некоторой хэш-функции (например, MD5 или SHA-2 ). При использовании хеш-функции, несомненно, что разные входы приведут к разным выходам. Результат хеша длиннее семи символов, поэтому нам нужно взять первые семь символов. Но в этом случае может произойти столкновение, поскольку первые семь символов уже могут использоваться в качестве короткой ссылки. Затем мы берем следующие семь символов, пока не найдем короткую ссылку, которая не используется.
Второй способ создания короткой ссылки — использование UUID . Вероятность того, что UUID будет продублирован, не равна нулю, но он достаточно близок к нулю, чтобы быть незначительным. Поскольку UUID имеет 36 символов, это означает, что у нас та же проблема, что и выше. Мы должны взять первые семь символов и проверить, используется ли уже эта комбинация.
Третий способ — преобразование чисел из базы 10 в базу 62. База — это количество цифр или символов, которые можно использовать для представления конкретного числа. База 10 — это цифры [0-9], которые мы используем в повседневной жизни, а база 62 — [0-9] [az] [AZ]. Это означает, что, например, число в базе 10 с четырьмя цифрами будет таким же числом в базе 62, но с двумя символами.
Использование базы 62 в преобразовании URL с максимальной длиной в семь символов позволяет нам иметь 62 ^ 7 уникальных значений для коротких ссылок.
Как работает Base 62 Conversion
У нас есть число 10, которое мы хотим преобразовать в 62. Мы собираемся использовать следующий алгоритм:
Джава
xxxxxxxxxx
1
while(number > 0)
2
remainder = number % 62
3
number = number / 62
4
// attach remainder to start of result collection
После этого нам просто нужно отобразить числа из коллекции результатов в базу 62 Алфавит = [0,1,2, …, a, b, c …, A, B, C, …].
Давайте посмотрим, как это работает на реальном примере. В этом примере давайте преобразуем 1000 из базы 10 в базу 62.
Джава
xxxxxxxxxx
1
1st iteration:
2
number = 1000
3
remainder = 1000 % 62 = 8
4
number = 1000 / 62 = 16
5
result list = [8]
6
2nd iteration:
7
number = 16
8
remainder = 16 % 62 = 16
9
number = 16 / 62 = 0
10
result list = [16,8]
11
There is no more iterations since number = 0 after 2nd iteration
Сопоставление [16,8] с базой 62 будет g8. Это означает, что 1000 base10 = g8 base62 .
Преобразование из базы 62 в базу 10 также просто:
Джава
xxxxxxxxxx
1
i = 0
2
3
while(i < inputString lenght)
4
counter = i + 1
5
mapped = base62alphabet.indexOf(inputString[i])
6
// map character to number based on its index in alphabet
7
result = result + mapped * 62^(inputString lenght - counter)
8
i++
Реальный пример:
Джава
xxxxxxxxxx
1
inputString = g8
2
inputString length = 2
3
i = 0
4
result = 0
5
1st iteration
6
counter = 1
7
mapped = 16 // index of g in base62alphabet is 16
8
result = 0 + 16 * 62^1 = 992
9
2nd iteration
10
counter = 2
11
mapped = 8 // index of 8 in base62alphabet is 8
12
result = 992 + 8 * 62^1 = 1000
Реализация
Примечание : все решение на моем Github . Я реализовал этот сервис, используя Spring boot и MySQL.
Мы собираемся использовать функцию автоматического увеличения нашей базы данных. Автоматически увеличивающееся число будет использоваться для преобразования базы 62. Вы можете использовать любую другую базу данных, которая имеет функцию автоинкремента.
Сначала зайдите в инициализатор Spring и выберите Spring Web и MySql Driver . После этого нажмите кнопку « Создать» и загрузите ZIP-файл. Разархивируйте файл и откройте проект в вашей любимой IDE. Каждый раз, когда я начинаю новый проект, мне нравится создавать несколько папок, чтобы логически разделить мой код. В этом случае моими папками являются контроллер , сущность , служба , репозиторий , dto и config .
Внутри папки сущностей, давайте создадим Url.java класс с четырьмя атрибутами: id, longUrl, createdDate, expiresDate.
Обратите внимание, что атрибут короткой ссылки отсутствует. Мы не будем сохранять короткие ссылки. Мы собираемся преобразовывать атрибут id из базы 10 в базу 62 каждый раз, когда есть запрос GET. Таким образом, мы экономим место в нашей базе данных.
LongUrlАтрибут является URL , мы должны перенаправить , когда пользователь получает доступ короткую ссылку. Дата создания предназначена только для того, чтобы увидеть, когда longUrlсохранено (это не важно), и expiresDateсуществует, если пользователь хочет сделать короткую ссылку недоступной через некоторое время.
Далее, давайте создадим BaseService.java в папке службы . BaseServiceсодержит методы для преобразования из базы 10 в базу 62 и наоборот.
Джава
xxxxxxxxxx
1
private static final String allowedString = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
2
private char[] allowedCharacters = allowedString.toCharArray();
3
private int base = allowedCharacters.length;
Как я упоминал ранее, если мы хотим использовать преобразования базы 62, нам нужен алфавит базы 62, который в этом случае называется allowedCharacters. Кроме того, значение baseпеременной вычисляется из длины разрешенных символов в случае, если мы хотим изменить разрешенные символы.
encodeМетод принимает число в качестве входных данных и возвращает короткую ссылку. decodeМетод принимает строку (короткую ссылку) в качестве входного сигнала и возвращает число. Алгоритмы должны быть реализованы так, как они были описаны выше.
После этого, внутри папки репозитория , давайте создадим файл UrlRepository.java , который является просто расширением JpaRepository. Это дает нам много методов, например findById, saveи т. Д. Нам не нужно ничего добавлять к этому.
Затем давайте создадим файл UrlController.java в папке контроллера. Контроллер должен иметь один метод POST для создания коротких ссылок и один метод GET для перенаправления на исходный URL.
Джава
xxxxxxxxxx
1
("create-short")
2
public String convertToShortUrl( UrlLongRequest request) {
3
return urlService.convertToShortUrl(request);
4
}
Джава
xxxxxxxxxx
1
(value = "{shortUrl}")
2
public ResponseEntity<Void> getAndRedirect( String shortUrl) {
3
var url = urlService.getOriginalUrl(shortUrl);
4
return ResponseEntity.status(HttpStatus.FOUND)
5
.location(URI.create(url))
6
.build();
7
}
Метод POST имеет UrlLongRequest в качестве тела запроса. Это просто класс с longUrlи expiresDateатрибутами.
Метод GET принимает короткий URL-адрес в качестве переменной пути, а затем получает и перенаправляет на исходный URL-адрес. В верхней части контроллера, UrlService будет введено как зависимость, которая будет объяснена далее.
UrlService.java — это место, где больше всего логики и является службой, используемой контроллером. ConvertToShortUrlиспользуется методом POST от контроллера. Он просто создает новую запись в базе данных и получает идентификатор. Этот идентификатор затем преобразуется в базовую короткую ссылку 62 и возвращается в контроллер.
GetOriginalUrlэто метод, используемый методом GET из контроллера. Сначала он преобразует строку в базу 10, а результатом является идентификатор. Затем он получает запись из базы данных по этому идентификатору и выдает исключение, если он не существует. После этого он возвращает исходный URL на контроллер.
И это все. Мы реализовали все, чтобы иметь работающий сервис сокращения URL!
Заключение
Служба сокращения URL-адресов — это простая служба, которая берет длинный URL-адрес и преобразует его в короткую ссылку. Как только эта ссылка посещена, пользователь перенаправляется на исходный URL.
В этой статье я объяснил теорию сокращения службы и показал, как ее реализовать. В следующей статье я расскажу о некоторых «продвинутых» вещах, таких как докер, кеш, разбиение данных и задание для автоматического удаления просроченных ссылок.