System Design: TinyURL

Introduction

URLUniform Resource Locator (URL), is an address that uniquely identifies a resource on the web. shortening is a service that produces short aliases for long URLs, commonly referred to as short links. Upon clicking, these short links direct to the original URLs. The following illustration depicts how the process works:

Advantages

The key advantages of a URL shortening service are:

• Shortened URLs are convenient to use: they optimize link usage across different forms of devices due to their enhanced accessibility and non-breakability.

• They are visually professional, engaging and facilitate a higher degree of sharing possibilities.

• They are less error-prone while typing.

• They require smaller storage space at the user’s end.

Disadvantages

The URL shortening service has some associated drawbacks as well. Some of them are as follows:

• We lose the originality of our brand by using a short URL generated by a third-party service. Many different brands using the same service get short URLs containing the same domain.

• Since we're using a third-party service for URL shortening, the possibility of it getting shut down and wiping all our shortened URLs will always be there.

• Our business brand image depends on the trustworthiness of a URL shortening service. The wrong business move might negatively impact our business. The competition for acquiring the in-demand custom short URLs is immense, so it might be possible that the best custom URLs are already taken by the time we start generating short URLs.

To move from concept to creation, we must first lay a solid foundation by specifying the requirements of the service.

Requirements for URL Shortening Design

Let’s look at the functional and non-functional requirements for the service we’ll be designing:

Functional requirements

• Short URL generation: Our service should be able to generate a unique shorter alias of the given URL.

• Redirection: Given a short link, our system should be able to redirect the user to the original URL.

• Custom short links: Users should be able to generate custom short links for their URLs using our system.

• Deletion: Users should be able to delete a short link generated by our system, given the rights.

• Update: Users should be able to update the long URL associated with the short link, given the proper rights.

• Expiry time: There must be a default expiration time for the short links, but users should be able to set the expiration time based on their requirements.

Non-functional requirements

• Availability: Our system should be highly available, because even a fraction of a second of downtime would result in URL redirection failures. Since our system’s domain is in URLs, we don’t have the leverage of downtime, and our design must have fault-tolerance conditions instilled in it.

• Scalability: Our system should be horizontally scalable with increasing demand.

• Readability: The short links generated by our system should be easily readable, distinguishable, and typeable.

• Latency: The system should perform at low latency to provide the user with a smooth experience.

• Unpredictability: From a security standpoint, the short links generated by our system should be highly unpredictable. This ensures that the next-in-line short URL is not serially produced, eliminating the possibility of someone guessing all the short URLs that our system has ever produced or will produce.

With our requirements clearly defined, we can now quantify the scale of the system.

Resource estimation

It’s better to have realistic estimations at the start. For instance, we might need to change them in the future based on the design modifications. Let’s make some assumptions to complete our estimation.

Assumptions

• We assume that the shortening: redirection request ratio is 1:100.

• There are 200 million new URL shortening requests per month.

• A URL shortening entry requires 500 Bytes of database storage.

• Each entry will have a maximum of five years of expiry time, unless explicitly deleted.

• There are 100 million Daily Active Users (DAU).

Storage estimation

Since entries are saved for a time period of 5 years and there are a total of 200 million entries per month, the total entries will be approximately 12 billion.

$200\ \text{Million/month} \times 12\ \text{months/year} \times 5\ \text{years} = 12\ \text{Billion URL shortening requests}$

Since each entry is 500 Bytes, the total storage estimate would be 6 TB:$12\ \text{Billion} \times 500\ \text{Bytes} = 6\ \text{TB}$

Query rate estimation

Based on the estimations above, we can expect 20 billion redirection requests per month.

$200\ \text{Million} \times 100 = 20\ \text{Billion}$

We can extend our calculations for Queries Per Second (QPS) for our system from this baseline. The number of seconds in one month, given the average number of days per month is 30.42:

$30.42\ \text{days} \times 24\ \text{hours} \times 60\ \text{minutes} \times 60\ \text{seconds} = 2628288\ \text{seconds}$

Considering the calculation above, new URL shortening requests per second will be:

$\frac{200\ \text{Million}}{2628288\ \text{seconds}} = 76\ \text{URLs/s}$

With a $1:100$ shortening to redirecting ratio, the URL redirection rate per second will be:

$100 \times 76\ \text{URLs/s} = 7.6\ \text{K URLs/s}$

Bandwidth estimation

Shortening requests: The expected arrival rate will be 76 new URLs per second. The total incoming data would be $304\ Kbps$ per second:

$76 \times 500\ \text{Bytes} \times 8\ \text{bits} = 304\ \text{Kbps}$ ...