All you need to know about designing URL Shortener

Introduction

One of the widely asked System Design question in an interview is — Design a URL Shortener. Let’s see how to approach it and solve this question.

Let’s start by naming our service — URL Cut By Dewansh (urlcutbydewansh.com)

Question Statement

You are required to design a URL shortener. As the name suggests, you need to come up with a system design which can provide a short url for a long url. (like tinyurl.com). After generating a short URL for a long URL, when the user enters that short url in the browser, it should automatically redirected to the long url page.

For example-

Long url : https://www.google.com/search?q=images&sca_esv=581137776&rlz=1C5GCEM_enIN1055IN1055&tbm=isch&sxsrf=AM9HkKnNaTmOGyhaV0zApt3fRHLlOhuJQA:1699604798007&source=lnms&sa=X&ved=2ahUKEwj3qfmhgbmCAxU-S0EAHSgRCJQQ_AUoAnoECAIQBA&biw=1728&bih=907&dpr=2#imgrc=_-Vib8M68QmuuM

Short url: tinyurl.com/ah3b5uxu5c83

Understanding the requirements— “Back of the envelope calculation”

Back of the envelope calculation means noting down all the memory and processing requirements and understanding the complexity of the service we are about to design. Asking and analysing questions like — How much traffic the service will handle, how much storage will be required, etc. Let’s see for this case.

Performance Analysis

Let’s break down the system complexity into two parts — read operation and write operation.

1. write operation — user uploads a long url and want us to generate the shortened url for it.
2. read operation — user has the shortened url and wants us to redirect to the long url page.

Let’s say — 
write operations ~ 1000 per sec
read operations ~ 10,000 per sec

So, our service should be highly available and fault-tolerant. From above, we can derive read/write ratio is 10:1.

Let’s say our service takes

• 1ms to perform read operation : Therefore one instance of the service can serve 1000 requests per sec. If one instance takes 1000 requests per sec, naturally we need 10 such instances or servers runnings simultaneously to server 10,000 requests in one sec otherwise our service would throttle the requests. To be able to balance the load and route the incoming requests to current idle server, we will also need a load balancer (more on this later).
• 20ms to perform write operation: It would mean one instance can server 50 requests per sec. Therefore, we would require 20 servers to run simultaneously to serve the need of 1000 write operations per second.

Total servers needed = 10 + 20 = 30 servers for concurrent executions.

Storage Analysis

During the write operation, we also will need to store the long url and its corresponding shortened url in our storage, so that in the read operation when user has the shortened url and wants to fetch the long url (redirection), service should be able to access and fetch it from the database.

• Let’s say the maximum length of long URL = 1000 characters (alpha-numeric). Each character takes 1 Byte, hence max size of the long URL is restricted to = 1000 Bytes or 1KB.
• Imagine, if shortened URL we generate, we restrict it to 50 characters (alphanumeric), then the size of shortened URL = 50 Bytes or 0.05 KB.

Let’s analyse the numbers, as we know –

Number of write operations = 1000 per sec 
which means => 1000 * 3600 * 24 ~ 86.4M records per day
which means => 86.4M * 365 * 10 ~ 2³⁹ records in 10 years
which means => ~ 1 Trillion records in 10 years

Since we will store this data in a relational database with three columns :

CREATE TABLE URL_SHORTENER_TABLE(
  id (integer, auto-increment, primary key)
  long_url (string)
  shortened_url (string)
);

As we know for one record we need = 1.05 KB (1 KB + 0.5 KB ) + size of the primary key.

Size of the primary key can be determined by seeing the number of records = 2³⁹ records meaning we need 39 bits to represent these numbers and we have primary key as an auto-increment number. we can say we need 39 (or ~40 bits) (and one Byte = 8 Bits) = 5 B or 0.005 KB. Therefore,

Total size of one record = 1.05 KB + 0.005KB = 1.055 KB
Total records in 10 years = 1 Trillion

Total storage capacity you need to store the data for 10 years (without deleting records) = 1 Trillion * 1.055 KB = 1055 TB (Terabytes of data)

Designing the service

So, those numbers look huge, but that’s a good thing, because now we know the scope of application. The intensity that our service will bear.

We can design a simple ARest Service with APIs to handle the operations.
We have two operations —

1. Write operation — we can a have a function called ‘generate’ to peform this task.
2. Read operation — we can a have a function called ‘redirect’ to perform this task.

generate will be a POST API call function taking a long URL 
redirect will be a GET call function taking a short URL

generate API (POST)

// generate API (POST)
@RequestMapping(value = "/generate", method = RequestMethod.POST)
public String generate(String longUrl){
  // validate input ..
  
  // generate shortened url for the given long url
  // the service will use base62 conversion to perform the url
  String shortenedUrl = urlShortenerService.generateShortenedUrl(longUrl);
  
  // persist the new record in database.
  boolean isCompleted = database.persist(shortenedUrl, longUrl);
  if(isCompleted) {
    return shortenedUrl;
  }
  // throw Persistence Exception
  return null; // For simplicity returning null string.
}

redirect API (GET)

// redirect API (GET)
@RequestMapping(value = "/redirect/{shortenedUrl}", method = RequestMethod.GET)
public Response redirect(@PathVariable String shortenedUrl){
  try {
    // check if the input is valid
    checkValidShortenedUrl(shortenedUrl);
    
    // fetch the long url from the database or cache
    String longUrl = database.getLongUrl(shortenedUrl);
    
    // redirect to the long url.
    redirectionService.redirect(longUrl);
    
    // peform some more metric actions...
    ResponseEntity.ok().build;
  }
  catch(IllegalArgumentException exception){
    log.error("Shortened Url entered is invalid");
    ResponseEntity.badRequest().build();
  }
}

Now we have seen how our API call functions will perform the tasks. For generate POST API call, our main service to design isString shortenedUrl = urlShortenerService.generateShortenedUrl(longUrl);

What will this function generateShortenedUrl do? Let’s understand.

Concept: Hashing

We can think of hashing concept where key is long_url and value is shortened_url (we will call it token). So, we need a hash function which can have the logic to generate the token for a key (long url).

Input = https://example.com/long_url_extension 
Output = https://urlcutbydewansh.com/token

Now what should be the size of the token generated?
This depends on number of records we will actually end up generating token for so that we don’t end up with a hash collision.
We already know we will generate 1 Trillion records = 2⁴⁰ records.

Each character we have in the token will be alphanumeric = [0–9] or [a-z] or [A-Z] => 10 + 26 + 26 = 62 possibilities for each character.

So let’s say the token size is n then,

62^n (62 power n) > 1 Trillion (2⁴⁰)
Taking log to the base 2 we get.

n(log(62) base 2) > 40
n > 40 / log (62) base 2 = 7

hence we can use the token size of 7 which is sufficient to generate 1 trillion records over the period of 10 years.

so sample shortened url from our service would look like — https://urlcutbydewansh/a0b1c2D

Determining Hash Function

All set and done, we are coming to finish our solution ! The last piece is to determine the logic of generating the token of the long url.

We can use multiple renowned hash functions, but the most famous one is Base62 conversion. The way Base62 works, is that it takes a number in decimal form and converts into the Base62. 62 denotes all the alphanumerics discussed above ([0–9] + [a-z] + [A-Z]).

Since we are storing ID as the primary key, we will use this ID and convert it into Base62 string. This string will become our token for shortened url.

Let’s see an example :

ID : 48044 <= Base62 Conversion=> Token : 3woO94u

How will redirection work?

The redirection works as follows —

Components :

• Load Balancer — To route the incoming request to appropriate server. This will improve efficiency of servers and also ensure high-availability as LB will be determining the idle server ready to take the request.
• Cache — Simple yet useful component to improve latency for a commonly raised request of a shortened url by faster access.
• SQL Database — Actual relational database storage where the data is stored.
• Web servers — These host our service which will process the request and perform the task.
• User — from where the request arises.

Steps :

1. First the user enters the shortened url in the browser and presses send. The request reaches DNS which resolves the IP address (public) of our Load Balancer.
2. The request reaches our load balancer which will determine which web server to call depending upon how our LB is configured. It will route the request to the chosen web server’s IP address (private).
3. The request reaches the web server which will validate the request, process it and then query the cache for the corresponding long url.
4. The cache will try to find if the record is stored, if yes, it will return the record, else send ‘not found’ response.
   The server, on a cache-miss, will query the actual database from which the record is returned.
5. Once the long url is received, the same is sent back to the user.

Congratulations on solving this system design question — URL Shortener. See you in the next one !