Loading...
Out of scope:
Assume US population of 200 million. 50% are daily active users (i.e. 100M users). Each user send 1 url per day. That's 100 million url per day. Assume on average url are 100 characters (max is 2000). This is 10GB per day. Forecast this over 5 years, we have 100 million * 365 * 5 = 182 billion urls. This will be about 18 TB of data without compression.
There is only one API to shorten a url:
Then, when the shortened url is visited, it simply redirect to original url.
On average, we need 6 characters in base64 to encode 182 billion urls. To give ourselves some buffer, we can use 8 characters.
The schema can be as followed:
table: long url is primary key, short url is value
index: short url is primary key, long url is index
Using a table, we can store long url and deduplicate them. Using an index, we can support redirection quickly.
We would have a fleet of frontend servers that renders our web page for application. In the application, the user would be able to submit a url and receive a short url. The frontend would receive these requests and send them over to the backend.
We have another fleet of backend server to serve shortening urls and looking up long urls. They would have caching to improve performance of frequently visited urls. The urls is ultimately stored in a cloud-based database like DynamoDB. In addition, for security purpose, this fleet is not publicly visible and only be reached through the frontend.
Submit flow:
Redirect flow:
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...
The web service is the main entry point for our application. This is visible to public internet. It has a load balancer and a fleet of stateless web servers. The service is responsible rendering web applications and serving redirections. If there is enough demand, the redirection can also be separated into another service that is scaled more independently.
The url service is the backend of our architecture. It generates and look up short urls. It also records useful statistic for future purpose. It will utilize a LRU cache to cache frequently used urls before reading the database.
One core problem in the url service is how we can generate short url and look up the long one. Here is some details. One approach is to hash the long url and encode the result via base62. To support multi-account, we can use different seed for the generation so that each user can generate a different short url for the long url. One downside with this approach is that we will not be able to flexibly control the character space. Rather, this is controlled by the hash function we used.
Another approach is to have a reservation system. A short url space is pre-partitioned and shuffled and then allocated on the fly given a long url. For this to work, it will require the backend to be semi-persistent. It also requires dealing with checkpoints and failovers. I did not opt for this approach since there is no requirement to generate the shortest url.
Now that we have a core function to generate short url from the long url. Let's talk about how we will utilize the database. Recall that we will store long url as primary key in the base table and short url as the value; and the index will provide the reverse mapping. In DynamoDB, this can be supported via global secondary index. The frontend can use strong write for the base table write and a small wait for index consistency.
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?