System requirements

Functional:

1. We'll return a short URL when user give us a long url to process
2. Return the original long URL when user hit short URL in their browser

Non-Functional:

1. Performance: The system should be able to handle large number of requests per second with low latency. Especially for read performance.
2. Scalability: The service must be scalable when user numbers increase
3. Availability: The service should be highly available(e.g., 99.9% uptime)
4. Usability: We provide both web interface and API access

Capacity estimation

We expact to have 100 M of users. Each users stores 100 url on average. That's 100 M * 100 = 10 Billion Key-value pair. Each K-V pair needs 1k byte. The total storage we need is 100 TB.

Assume 10% of users are DAU. That's 10M DAU. Each user would use 10 time each day.

So QPS = 100M / (24 * 60 * 60) = ~10 ^ 3

API design

With Base62 encoding, we might need log62(10 ^ 10) = 7 characters for short URL

We'll need two API for this service.

Get: tiny.url/abcdXYZ, we'll returns the original URL

POST: tiny.url with original URL in the body. We'll return shorten URL

Database design

The database will show as follows

shorten url - primary key

user id - secondary key

original url

creation time

expiration time

We'll use k-v store to store data to achieve high throughput and availability. We can use DynamoDB or Cassandra and set it to high consistency to meet our performacne requirement

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 have a API gateway to prevent DDOS attack. The API gateway also served as load-balancer to distribute traffic evenly to each server. It also functions as a router to route request to either shortening services or mapping services

The Shortening services will process POST request(i.e. add new shorten URL). It's stateless since it doesn't need context to create short URL and write to DB.

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?