{{announcement.body}}
{{announcement.title}}

URL Shortener: A Detailed Explanation

DZone 's Guide to

URL Shortener: A Detailed Explanation

In this article, we provide a high-level discussion of how to implement a URL shortening service and then walk you through an example with Java.

· Java Zone ·
Free Resource

Introduction

A URL shortener is a service that is used to create short links from very long URLs. Usually, short links have the size of one third or even one-fourth of the original URL, which makes them easier to type, present, or tweet. Clicking on a short link user will be automatically redirected to the original URL. 

There are many URL shortening services available online, like tiny.cc, bitly.com, cutt.ly, etc. Implementing a URL shortening service is not a complex task, and it is often part of system design interviews. In this post, I will try to explain the process of implementing the service. 

Theory 

Before implementation, it is always a good idea to write down what it is needed to be done in the form of functional and non-functional requirements. 

Functional Requirements: 

  • Users need to be able to enter a long URL. Our service should save that URL and generate a short link
  • Users should have the option to enter the expiration date. After that date passed, the short link should be invalid
  • Clicking on the short link should redirect the user to the original long URL
  • Users should create an account to use service. Service can have usage limit per user*
  • User is allowed to create his own short link*
  • Service should have metrics, for example, most visited links*

Non-Functional Requirements:

  • Service should be up and running 100% of time
  • Redirecting should not last longer than two seconds

* Requirements are optional.

URL Conversion

Let's say that we want to have a short link with a maximum length of 7. The most important thing in a URL shortener is the conversion algorithm. URL conversion can be implemented in several different ways, and each way has its pros and cons. 

One way of generating short links would be hashing the original URL with some hash function (for example MD5 or SHA-2). When using a hash function, it is sure that different inputs will result in different outputs. The result of the hash is longer than seven characters, so we would need to take the first seven characters. But, in this case, there could be a collision because the first seven characters could already be in use as a short link. Then, we take the next seven characters, until we find a short link that is not used.

The second way of generating a short link is by using UUIDs. The probability that a UUID will be duplicated is not zero, but it is close enough to zero to be negligible. Since a UUID has 36 characters, that means that we have the same problem as above. We should take the first seven characters and check if that combination is already in use.

The third way would be converting numbers from base 10 to base 62. A base is a number of digits or characters that can be used to represent a particular number. Base 10 are digits [0-9], which we use in everyday life and base 62 are [0-9][a-z][A-Z]. This means that, for example, a number in base 10 with four digits would be the same number in base 62 but with two characters.

Using base 62 in URL conversion with a maximum length of seven characters allows us to have 62^7 unique values for short links.

How Base 62 Conversion Works

We have a base 10 number that we want to convert base 62. We are going to use the following algorithm:

Java
 




xxxxxxxxxx
1


 
1
while(number > 0)
2
    remainder = number % 62
3
    number = number / 62
4
    // attach remainder to start of result collection



After that, we just need to map numbers from the result collection to the base 62 Alphabet = [0,1,2,...,a,b,c...,A,B,C,...].

Let's see how this works with a real example. In this example, let's convert 1000 from base 10 to base 62.

Java
 




xxxxxxxxxx
1
11


 
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



Mapping [16,8] to base 62 would be g8. This means that 1000base10 = g8base62.

Converting from base 62 to base 10 is also simple:

Java
 




xxxxxxxxxx
1


 
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++



Real example: 

Java
 




xxxxxxxxxx
1
12


 
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



Implementation

Note: The whole solution is on my GitHub. I implemented this service using Spring boot and MySQL. 

We are going to use our database's auto-increment feature. The auto-incrementing number is going to be used for base 62 conversion. You can use any other database that has an auto-increment feature.

First, visit Spring initializer and select Spring Web and MySql Driver. After that, click on the Generate button, and download the zip file. Unzip the file and open the project in your favorite IDE. Every time I start a new project, I like to create some folders to logically divide my code. My folders in this case are controller, entity, service, repository, dto, and config.

Inside the entity folder, let's create a Url.java class with four attributes: id, longUrl, createdDate, expiresDate

Notice that there is no short link attribute. We won't save short links. We are going to convert the id attribute from base 10 to base 62 every time there is a GET request. This way, we are saving space in our database.

The LongUrl attribute is the URL we should redirect to once a user accesses a short link. The created date is just to see when the longUrl is saved (it is not important), and expiresDate is there if a user wants to make a short link unavailable after some time. 

Next, let's create a BaseService.java in the service folder. BaseService contains methods to convert from base 10 to base 62 and vice versa. 

Java
 




xxxxxxxxxx
1


 
1
private static final String allowedString = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
2
private char[] allowedCharacters = allowedString.toCharArray();
3
private int base = allowedCharacters.length;



Like I mentioned before, if we want to use base 62 conversions, we need to have a base 62 alphabet, which in this case, is called allowedCharacters. Also, the value of the base variable is calculated from the length of the allowed characters in case we want to change the allowed characters.

The encode method takes a number as input and returns a short link. The decode method takes a string (short link) as an input and returns number. The algorithms should be implemented as they were explained above.

After that, inside the repository folder, let's create a UrlRepository.java file, which is just an extension of JpaRepository. It gives us a lot of methods, like findById, save, etc. We don't need to add anything else to this. 

Then, let's create a UrlController.java file in the controller folder. The controller should have one POST method for creating short links and one GET method for redirecting to the original URL. 

Java
 




xxxxxxxxxx
1


 
1
@PostMapping("create-short")
2
public String convertToShortUrl(@RequestBody UrlLongRequest request) {
3
    return urlService.convertToShortUrl(request);
4
}




Java
 




xxxxxxxxxx
1


 
1
@GetMapping(value = "{shortUrl}")
2
public ResponseEntity<Void> getAndRedirect(@PathVariable String shortUrl) {
3
    var url = urlService.getOriginalUrl(shortUrl);
4
    return ResponseEntity.status(HttpStatus.FOUND)
5
            .location(URI.create(url))
6
            .build();
7
}



The POST method has a UrlLongRequest as its request body. It is just a class with longUrl and expiresDate attributes.

The GET method takes a short URL as a path variable and then gets and redirects to the original URL. At the top of the controller, UrlService is injected as a dependency, which will be explained next.

UrlService.java is where most logic is and is the service used by the controller. ConvertToShortUrl is used by the POST method from the controller. It just creates a new record in the database and gets an id. That id is then converted to a base 62 short link and returned to the controller. 

GetOriginalUrl is a method used by the GET method from the controller. It first converts a string to base 10, and the result of that is an id. Then, it gets a record from the database by that id and throws an exception if it does not exist. After that, it returns the original URL to the controller. 

And that is it. We have implemented everything to have a working URL shortening service!

Conclusion

A URL shortening service is a simple service that takes long URL and converts it to a short link. Once that link is visited, the user is redirected to the original URL. 

In this article, I explained the theory behind shortening service and showed how to implement one. In the next article, I will explain some 'advanced' things like docker, cache, data partitioning and job to automatically delete expired links.

Topics:
java ,mysql ,open source ,spring boot ,system design ,tutorial

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}