URL Shortener | TinyURL | System Design Interview Question
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.
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.
longURLis the long URL to be shortened. response:
shortis the short id encoded in Base58.
tinyurlis the shortened URL. Both request and response are in JSON.
In practice, we often need to support additional fields like
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.
|Length||Number of distinct short ID|
|1||58^1 = 58|
|2||58^2 = 3,364|
|3||58^3 = 195,112|
|4||58^4 = 11,316,496|
|5||58^5 = 656,356,768|
|6||58^6 = 38,068,692,544|
|7||58^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.