Url Shortener
Here we are going to design a url shortener system.
Questions for clear scope
Can you give an example of how a URL shortener work? – https://www.systeminterview.com/q=chatsystem&c=loggedin&v=v3&l=long
What is the traffic volume? – 100 million URLs are generated per day.
How long is the shortened URL? – as short as possible
What characters are allowed in the shortened URL? – Shortened URL can be a combination of numbers (0-9) and characters (a-z, A- Z).
Can shortened URLs be deleted or updated? – For simplicity, let us assume shortened URLs cannot be deleted or updated.
Here are the basic use cases:
- URL shortening: given a long URL => return a much shorter URL
- URL redirecting: given a shorter URL => redirect to the original URL
- High availability, scalability, and fault tolerance considerations
Solution with Base 62 conversion
Base conversion is an approach commonly used for URL shorteners. Base conversion helps to convert the same number between its different number representation systems. Base 62 conversion is used as there are 62 possible characters for hashValue.
Conversion of 11157 to base 62
The short url is https://tinyurl.com/2TX
- longURL is the input.
- The system checks if the longURL is in the database.
- If it is, it means the longURL was converted to shortURL before. In this case, fetch the shortURL from the database and return it to the client.
- If not, the longURL is new. A new unique ID (primary key) Is generated by the unique ID generator.
- Convert the ID to shortURL with base 62 conversion.
- Create a new database row with the ID, shortURL, and longURL.
To make the flow easier to understand, let us look at a concrete example.
- Assuming the input longURL is: https://en.wikipedia.org/wiki/Systems_design • Unique ID generator returns ID: 2009215674938.
- Convert the ID to shortURL using the base 62 conversion. ID (2009215674938) is converted to “zn9edcu”.
- Save ID, shortURL, and longURL to the database
Comparison of Hash solution vs Base 62 conversion
As you can see Base 62 conversion is the clear winner.