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 posts regarding implementation. Intrigued, I decided to implement one and write my experience about it. StackOverflow Today, we will build one using , Spring Boot, . For the impatient, skip ahead to . Whip out your favorite editor and follow along with me! Java Redis Implementation 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 to convert the request numbers into a shorter representation. base conversions 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 . Be sure to add Web as a dependency. website Next, let’s translate the base conversion methods presented above into code. Create a package in called and create a Java class named src/java/main/urlshortener.app common IDConverter.java IDConverter.java We will use 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 , let’s make it a . IDConverter IDConverter Singleton First, let’s initialize the class with a List and a HashMap to map the representations between base 10 and 62: represents the conversion chart in the base10 to base62 example above while represents the chart displayed in the example of converting shortened URL back to a Dictionary key. indexToCharTable charToIndexTable Next, let’s create a function that takes in a request number (ID) and converts it into a unique URL: 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 conversion to returns a unique URL. createUniqueID indexToCharTable Next, let’s create a function to do the reverse: take in a unique URL and return the request number (id): 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). getDictionaryKeyFromUniqueID 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 . I highly recommend following along the 15 minute tutorial on the site in order to gain better understanding of Redis before moving on. official site Next, we will be including Jedis into our . Jedis is a Redis client for Java: it allows us to use Redis’ functionality directly from Java. build.gradle compile group: 'redis.clients', name: 'jedis', version: '2.9.0' URLRepository.java Next, we’re going to create a new package named repository in . Repositories are a “mechanism for encapsulating storage, retrieval, and search behavior”. It is good practice to abstract database details, so we will create here. src/main/java/urlshortener.app URLRepository The annotation allows Spring to detect the class and include it in the build path. I’ll explain this in more details later. @Repository The functions are self-explanatory for the most part. increments an id (request number) and increases it. takes a key and the original url and stores it into Redis using . takes an id (key) and retrieves it from a Redis using . incrementID saveUrl jedis.hset getUrl jedis.hget Next, let’s create a service package in and create a Java class . src/main/java URLConverterService URLConverterService.java We will use 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 URLConverterService The annotation allows the Spring to include the class into its build path. 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 , the dependencies can be automatically resolved. @Service @Autowired @Repository 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. takes the URL used to perform the POST request and obtains the hostname and port number. takes the uniqueID from the URL and uses the repository to retrieve the original URL. shortenURL formatLocalURLFromShortener getLongURLFromID So far so good! The next step would be to serve this up on to the Web. Next, create a package named controller in and create a class. src/main/java/urlshortener.app URLController URLController.java At a high level, is the point of entry for our web application. We want our to do 2 things: URLController URLController 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 annotation automatically puts a annotation to all functions with annotations. This grants them the functionality to receive and respond to requests. Functions marked with the annotation are able to respond to a specific URI mapped by the value in the annotation. @RestController @ResponseBody @RequestMapping @RequestMapping function is mapped to the endpoint and corresponds to a POST request as indicated by the parameter. refers to the request type the function expects to receive. The function receives a class and a as parameter, processes them using the and return a shortened URL. We accept 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 as a parameter because we declared ShortenRequest as a class and marked it as a , 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. shortenURL /shortener method “consumes” ShortenRequest HttpServletRequest URLConverterService HttpServletRequest ShortenRequest @JsonCreator function is mapped to the . 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 annotation and uses the to retrieve the original URL. Finally, we use a to redirect the browser into the original URL. redirectURL /{id} @PathVariable URLConverterService RedirectView 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 called . src/main/java/urlshortener.app/common URLValidator URLValidator.java We will use to validate URL’s before shortening them. Let’s make it a Singleton to ensure only the instance of the class is shared. URLValidator 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. validateURL We then refactor shortenUrl to the following: URLController’s Finally, let’s create an entry point for the app. Create a class named in URLShortenerApplication src/main/java/urlshortener.app URLShortenerApplication.java URLShortenerApplication is our entry point for our Web Application. The indicates the class as a starting point of the application. This will scan through our configurations and resolve the dependencies for the class. @SpringBootApplication 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 is installed. First, type in the terminal to startup our Redis instance. Next, type and then in the terminal where the project is located. gradle redis-server gradle build gradle run Once running, we can use to test. Open up Postman and enter the URL as , switch the method to POST, and set the body to . Here is an example of how Postman should look at this point: Postman http://localhost:8080/shortener application/json 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, is the full source code for the program! here 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!
