URL Shortener | TinyURL | System Design Interview Question

For more comprehensive system design content and to try the design questions yourself, check out System Design School.

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 it returns 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 Users) and each user makes 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 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.

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