System requirements

Functional:

1) Given a short URL, retrieve corresponding long URL

2) Give a long URL, generate a unique short URL.

3) The mapping between short URL and long URL should be unique.

Non-Functional:

1) Scalable: able to handle millions of users and request without performance degradation.

2) Availability: System should be highly available.

3) Performance: Redirect function should be super fast.

Capacity estimation

For functionality 1, 20000 request per second

For functionality 2, 200 request per second

including all alphabets (26) and integers (10)

8 characters ~ 36^8 ~ 2.8billion entries

assume long url is approx 100 characters

200*3600*24*365*20 ~ 0.12billion entries

Each long -> short URL conversion would include:

• Long URL (100B)
• Short URL (8B)
• Created time (8B)
• Created by user ID (20B)
• Expiration time (8B)

Each entry is 144 bytes. Round to 256 Bytes

Per day, the service would generate 200 * 3600 * 24 * 256 = 4.4GB of data.

API design

shortenURL(str long_url, user_ID, expiration_time=None): Takes a long URL and returns a short URL.

redirectURL(str short_url): Takes a short URL and returns the associated long URL.

Database design

DynamoDB : key value pair. horizontal scaling and performance driven. strongly consistent.

• Short URL (8B) - primary key
• Long URL (100B) - secondary index
• Created time (8B)
• Created by user ID (20B) - secondary index
• Expiration time (8B)

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

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

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

Trade offs/Tech choices

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

Failure scenarios/bottlenecks

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

Future improvements

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