Loading...
1. Given a long URL, create an associated short URL.
2. Given a short URL, return the associated long URL.
Availability - This service has to be highly available. Especially functionality (2) (redirection).
Response time - Functionality (2) has to have low response time, e.g., less than 10ms. Functionality (1) (creating short URL) can takes more time - less than 10 seconds.
Scalability - We will get more and more requests to create short URLs, so the storage has to be highly scalable.
[Generally speaking, you would like to keep the requirements scope small. You only have 35 - 50 min in an interview. If you have a lot of requirements, you'd risk running out of time. We could add other requirements like custom link. But we will start with a small set of requirements. Easier to expand later than shrink.]
Estimate the scale of the system you are going to design...
200 requests per second for functionality (1) (creating short URL).
20,000 requests per second for functionality (2) (redirecting request with a short URL to long URL).
I assume the random portion of shortened URLs to be 8 characters.
I also assume long URLs are on average 100 characters.
Each long -> short URL conversion would include:
Each entry is 144 bytes. We will round it up to 256 bytes.
[You do not have to be exact in this calculation. You can say this object would have these data, and it would roughly be 128 bytes, 256 bytes, 1KB, etc.]
Per day, the service would generate 200 * 60 * 60 * 24 * 256 = 4.4GB of data.
Within 5 years, it would generate about 4.4 * 365 * 5 =
8 TB of data. Considering some growth and some buffer, let's assume it would be 15 TB.
Define what APIs are expected from the system...
shortenURL(str long_url, user_ID, expiration_time=None): Takes a long URL and returns a short URL.
redirectURL(str short_url): Takes a long URL and returns the associated long URL.
Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...
The primary data model for this system is a simple mapping from short URL to a long URL. We do not need complex relational query.
It requires strong consistency. Once the short -> long mapping is written, all readers should be able to read it.
A key-value pair, such as DynamoDB, would fit the bill. It is horizontally scalable and performant. It can be configured to be strongly consistent.
As discussed above, the data model would be:
We may choose to have some secondary indices for additional features. For example, if we put a secondary index on User ID, we would be able to list all the short URLs created by the user.
You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...
Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...
Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...
Explain any trade offs you have made and why you made certain tech choices...
Try to discuss as many failure scenarios/bottlenecks as possible.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?