System requirements

Functional:

List functional requirements for the system (Ask the chat bot for hints if stuck.)...

1. Submit long url: user can submit a long url and get back a short url
2. Redirect with short url: users who visit the short url will be redirected to the long url

Non-Functional:

List non-functional requirements for the system...

1. Durability: short url will not be expired
2. Latency: the redirection should be quick and not noticeable (<200ms)

Capacity estimation

Estimate the scale of the system you are going to design...

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.

API design

Define what APIs are expected from the system...

There is only one API to shorten a url:

• /shorten?url=...

Then, when the shortened url is visited, it simply redirect to original url.

Database design

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...

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.

High-level design

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...

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.

We would have another fleet of backend server to redirect traffic. The backend server would read data stored in a database and redirect with the long url. This can be done with a simple cloud-based database like DynamoDB.

Request flows

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...

Submit flow:

1. user visit frontend to see web page
2. user submit long url
3. backend receive long url and generate a short url
4. backend checks if the short url is in use; if not, it persist it into database
5. backend returns short url to user request
6. frontend displays the short url

Redirect flow:

1. user visit a shorten url
2. backend receive the short url and lookup the original long url
3. backend issues a http redirect back to user browser
4. user is now redirected to the long url

Detailed component design

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 backend will employ a simple random generate with 8 characters and check if the url is already in use.

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

1. I picked a cloud-based database to avoid operating database instances. It is possible to come up with a design with non-cloud-based or SQL database. Or use another cloud provider.
2. 
   

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

1. There may be collision - two long url generated to the same short url at the same time and index has propagation delay and not caught it.
2. Hotspot - what if a single url is very popular immediately. We can employ caching to reduce hit to database and also auto-scaling to ease network traffic.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?

1. Add in user tracking or analytics capability. For example, tracking most frequent urls.
2. Add functionality to expire old url