URL Shortener | TinyURL | System Design Interview Question

Use case

URL Shorteners are widely used on the Internet. One of the most popular services is TinyURL. It can generate a short URL tinyurl.com/algomo that redirects to algo.monster. And when you post a link on Twitter, it will automatically generate a short URL, such as t.co/tfIrCKKUrd. You can read more about how URL redirection works on MDN.

We will design a scalable URL shortening service with real demo code.

API

For simplicity, our demo will not have user authentication and all requests are made anonymously.

  • GET /<short> 302 redirects to the long URL if the short id is valid, otherwise return 404 not found.
  • POST /api/link request: longURL is the long URL to be shortened. response: short is the short id encoded in Base58. tinyurl is the shortened URL. Both request and response are in JSON.

In practice, we often need to support additional fields like custom_alias and expiry_date.

Back of the Envelope Calculation

Let's do some estimation and calculation. Suppose we have 1 million DAU(Daily Active User) and each user make 3 shortening requests per day. Then there are 3 million new links per day and about 1 billion per year. We have 1000000/86400≈12 requests per second on average. Suppose the peak traffic is 5 times of the average, our system should be able to handle 60 shortening requests per second at peak. Suppose the read to write ratio is 10:1, we need to handle 600 redirection requests at peak.

We also need to determine the length of the short id, which should be as short as possible. Assume we have an alphabet of 58 characters (reason in the implementation section) for the short id, here is a table about the number of distinct short id of the given length.

LengthNumber of distinct short ID
158^1 = 58
258^2 = 3,364
358^3 = 195,112
458^4 = 11,316,496
558^5 = 656,356,768
658^6 = 38,068,692,544
758^7 = 2,207,984,167,552

As from this table, there are 38 billion distinct short IDs of length 6 in Base58 and 2 trillion of length 7. Although length 6 is enough for more than 30 years, we will use length 7 in our demo to avoid possible collisions.

As for storage, assume each long URL is 100 bytes on average, then we can store about 10 million links in 1GB storage. Hence we need about 100GB storage per year.

Service

Title

Script

Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book.

Contrary to popular belief, Lorem Ipsum is not simply random text.

1  >>> a = [1, 2, 3]
2  >>> a[-1]
3  3

Get premium for instant access to all content and solutions