Building a URL-Shortening service from scratch using Java, Spring Boot, and Redis
Url Shortening with Java, Spring Boot, and Redis
Have you ever wondered how URL Shorteners work? A curious question led me to several StackOverflow posts regarding implementation. Intrigued, I decided to implement one and write my experience about it.
Today, we will build one using Java, Spring Boot, Redis. For the impatient, skip ahead to Implementation. Whip out your favorite editor and follow along with me!
Origins to URL Shorteners
The first URL Shortener was created by a web developer named Kevin Gilbertson, the founder of TinyURL in 2002. Annoyed at sending long links on forums, Kevin decided to do something to improve his user experience.
Kevin probably did not enjoy sending links like these
Today, link shortening is not only used to improve link sharing experience. With the growth of Twitter (with its pesky 140 characters limit), comes the apex of URL Shortening. In 2011, Twitter made an announcement to automatically shorten links to 23 characters. We don’t always think of URL Shorteners, but they play an important part in improving our online experience.
Theory behind URL Shortening
Now that we’ve discussed the origins of URL Shortening and its motivations, let’s discuss how they are implemented.
Writing a Dictionary of records
A Dictionary defines meanings to words. Let’s define the words as “key” and the meaning to the word as “value”. Some of you might ask, how does a Dictionary help us shorten URLs?
Are my URLs shorter yet?
Think of it this way:
- Every time the URL Shortener receives a link to shorten, it saves that link into a Dictionary and returns a short URL to the individual requesting the URL.
- When a shortened URL is given to the URL Shortener, the URL Shortener looks into the Dictionary and retrieves the original link.
Let’s see this visually:
A visual representation of how URL shortens
The URL Shortener creates a new ID (also called the key) for every request it receives. So how does the URL Shortener create a new key for every URL that it receives? Well….
Unique key generation
For simplicity, let’s assume the URL Shortener uses the request number as the key for the dictionary. We can use the request number because we can guarantee that each request number will be unique (we can’t have request number 1 happening twice). We can then shorten URLs by converting the request number directly into a shortened link:
URLs grow so fast sometimes
However, such methods will not scale if many users begin to use the URL Shortener. For example, as of writing this article, Twitter averaged 330 million daily users. Even if a fraction of the users were to send links in a day, such methods will quickly produce links longer than the original link. One way to combat that is to use base conversions to convert the request numbers into a shorter representation.
Scaling the URL Shortener with base conversion
What does base conversions mean? Base conversions is the process of converting numbers from different number bases. The numbers we are used to seeing are referred to as base 10 numbers. Base 10 simply means that we have 10 ways to represent numbers (0–9). Hypothetically speaking, we can convert numbers to an arbitrary bases. For example, if we were to use the alphabets (a-z-A-Z), alongside numbers (0–9) to represent numbers, we have base 62 (the sum of 26 lowercase alphabets + 26 uppercase alphabets +10 digits) numbers. Using the following algorithm, we can convert between base 10 to base 62:
Let x be the base10_numberWhile x is greater than 0:Take x and divide by 62. Store the remainder and let x = quotientTake the remainders from bottom-up (Last-In-First-Out)
Using the base 62 number, we can produce a unique ID by converting each individual digits into corresponding character using the conversion chart shown below. Observe an example of the conversion of base10 number into a unique ID through the base conversion process:
Base10 conversion of ID 125 to base62
Now that we have shortened the URL, the step to retrieve the URL is even simpler. We can use the following algorithm to obtain the Base10 number to retrieve from the Dictionary:
Let x represents the length of the shortened urlLet base10_id equal 0For each character c in the url starting from the first:val = value of c from the chart provided abovebase10_id plus(val * pow(62, x))Minus x by 1return base10_id
Let’s see an example of such conversion:
An example for retrieval of shortened url ABC
Observe how we can represent roughly the 100,000th request with only 3 characters (ABC). Using this method will allow us to scale our Shortener significantly better.
Implementation
Let’s get down to business! Let’s begin by looking at Spring Boot:
Spring Boot
Spring Boot is an opinionated way to get a Spring application running: it allow us to get our code running on the web in a short amount of time. Let’s begin by generating a Gradle Spring project from the official website. Be sure to add Web as a dependency.
Next, let’s translate the base conversion methods presented above into code. Create a package in src/java/main/urlshortener.app called common and create a Java class named IDConverter.java
IDConverter.java
We will use IDConverter to abstract the logic of obtaining a unique ID for our shortened URL, as well as converting the unique URL back into a Dictionary key. Because we only need one instance of IDConverter, let’s make it a Singleton.
First, let’s initialize the class with a List and a HashMap to map the representations between base 10 and 62:
indexToCharTable represents the conversion chart in the base10 to base62 example above while charToIndexTable represents the chart displayed in the example of converting shortened URL back to a Dictionary key.
Next, let’s create a function that takes in a request number (ID) and converts it into a unique URL:
createUniqueID takes in an id (base10) and converts it into base62 using a helper function defined above. The function then converts each component of the base62 number into a character using the indexToCharTable conversion to returns a unique URL.
Next, let’s create a function to do the reverse: take in a unique URL and return the request number (id):
getDictionaryKeyFromUniqueID takes in the unique URL ID and converts it back into its base62 number counterparts. The function then takes the base62 number and perform the algorithm to compute the request number (id).
Next, we are going to implement the Dictionary to store the URLs. Before that, let’s take a detour to talk about Redis.
Redis
Redis is an open source (BSD licensed), in-memory data structure store, used as a database, cache and message broker
For the Service, we should use a database to achieve persistence. After sifting through various options ranging from SQL to NoSQL, Redis seemed to be a good fit due to the ability to be used as an in-memory data structure. The Dictionary functionality we require can be obtained from Redis’ [hset](https://redis.io/commands/hset).
In order to use Redis, we must first install it from the official site. I highly recommend following along the 15 minute tutorial on the site in order to gain better understanding of Redis before moving on.
Next, we will be including Jedis into our build.gradle. Jedis is a Redis client for Java: it allows us to use Redis’ functionality directly from Java.
compile group: 'redis.clients', name: 'jedis', version: '2.9.0'
URLRepository.java
Next, we’re going to create a new package named repository in src/main/java/urlshortener.app. Repositories are a “mechanism for encapsulating storage, retrieval, and search behavior”. It is good practice to abstract database details, so we will create URLRepository here.
The @Repository annotation allows Spring to detect the class and include it in the build path. I’ll explain this in more details later.
The functions are self-explanatory for the most part. incrementID increments an id (request number) and increases it. saveUrl takes a key and the original url and stores it into Redis using jedis.hset. getUrl takes an id (key) and retrieves it from a Redis using jedis.hget.
Next, let’s create a service package in src/main/java and create a Java class URLConverterService.
URLConverterService.java
We will use URLConverterService to abstract the request to shorten URL by calling on to both the repository and the helper we created earlier. At a high level, the service should be able to:1. Take the original URL and return a shortened URL2. Take the shortened URL and return the original URL
The @Service annotation allows the Spring to include the class into its build path. @Autowired annotation allows Spring to resolve the class’ dependencies by looking in it’s build path for the classes it depends on (URLRepository). Because we’ve tagged URLRepository with @Repository, the dependencies can be automatically resolved.
shortenURL accepts the URL to be shortened, calls the Repository to save the original URL, and perform String manipulation using the base URL to return a shortened URL. formatLocalURLFromShortener takes the URL used to perform the POST request and obtains the hostname and port number. getLongURLFromID takes the uniqueID from the URL and uses the repository to retrieve the original URL.
So far so good! The next step would be to serve this up on to the Web. Next, create a package named controller in src/main/java/urlshortener.app and create a URLController class.
URLController.java
At a high level, URLController is the point of entry for our web application. We want our URLController to do 2 things:
- Receive requests to shorten URL and respond with a shortened URL
- Receive a shortened URL and automatically redirect the user to the original website
The @RestController annotation automatically puts a @ResponseBody annotation to all functions with @RequestMapping annotations. This grants them the functionality to receive and respond to requests. Functions marked with the @RequestMapping annotation are able to respond to a specific URI mapped by the value in the annotation.
shortenURL function is mapped to the /shortener endpoint and corresponds to a POST request as indicated by the method parameter. “consumes” refers to the request type the function expects to receive. The function receives a ShortenRequest class and a HttpServletRequest as parameter, processes them using the URLConverterService and return a shortened URL. We accept HttpServletRequest because we require the host name and the port number of the request in order to perform our String manipulation to produce a shortened URL. We can use ShortenRequest as a parameter because we declared ShortenRequest as a class and marked it as a @JsonCreator, allowing Jackson (a JSON Serializer) to detect our Request and turn it into a class object. This is good practice because it allows us to avoid hardcoding the get request from the URL.
redirectURL function is mapped to the /{id}. This means that the function is mapped to a dynamic address (which makes sense because the shortened URL are unique). The function then takes the ID using the @PathVariable annotation and uses the URLConverterService to retrieve the original URL. Finally, we use a RedirectView to redirect the browser into the original URL.
Looking good! However, we should handle the case when the URL passed into the shortenUrl function is invalid. For that, we will create a helper class in src/main/java/urlshortener.app/common called URLValidator .
URLValidator.java
We will use URLValidator to validate URL’s before shortening them. Let’s make it a Singleton to ensure only the instance of the class is shared.
validateURL takes in a URL and matches it with the REGEX. The function returns true if the URL matches any of the patterns recognized to be a URL.
We then refactor URLController’s shortenUrl to the following:
Finally, let’s create an entry point for the app. Create a class named URLShortenerApplication in src/main/java/urlshortener.app
URLShortenerApplication.java
URLShortenerApplication is our entry point for our Web Application.
The @SpringBootApplication indicates the class as a starting point of the application. This will scan through our configurations and resolve the dependencies for the class.
Next, we will have to update our build.gradle with the placement of our main class.
mainClassName = "urlshortener.app.URLShortenerApplication"
This allows us to use gradle to build and run our project.
Testing
Now that the basic functionality is finished, we should test it. To avoid making the article run too long, I will describe how to run manual test instead of automated test.
To run the app, make sure that gradle is installed. First, type redis-server in the terminal to startup our Redis instance. Next, type gradle build and then gradle run in the terminal where the project is located.
Once running, we can use Postman to test. Open up Postman and enter the URL as http://localhost:8080/shortener , switch the method to POST, and set the body to application/json. Here is an example of how Postman should look at this point:
Set the url to anything you would like to try with
Press Send and we should see a URL return as a String. Try pasting that URL into the browser. If you’ve followed the tutorial as is, it should succeed!
For reference, here is the full source code for the program!
Conclusions
Congratulations for making it this far! I hope you’ve had fun following along the tutorial and learnt something new about URL Shortening.
This tutorial scratches the surface of Spring Boot and Redis’ functionality. I highly recommend spending more time on them if you found them interesting!
Thank you for reading! Feel free to contact me with any feedback, questions, or any future topics or projects that you would like me to write about :).
Ciao!