System requirements

Functional:

• Generate tiny url
• Redirect user from tiny url to destination
• Tiny URL should be as short as possible
• Tiny URL should be different for different input URL

Non-Functional:

• Support 100 million users
• High availability

Capacity estimation

estimated QPS = 100000000 / 24 / 60 / 60 = 1157

assuming each user generate 10 urls per day

QPS: 10 * 1157 = 11570

peak QPS estimation: 11570 * 2 = 23140

API design

• Generate URL
• Post
• api/url/generate
• data : { url }
• return: { tinyUrl }
• Redirect URL
• Get
• tiny/{generated_tiny_url}

Database design

url table

• id
• long_url
• short_url

High-level design

1. Client
2. Client shows UI for generating tiny url for user
3. For user uses a tiny url, no client is needed
4. Load balancer
5. Balance generating and redirection request to different machines
6. API gateway
7. Forward API request to corresponding service
8. Rate limiting
9. Tiny URL service
10. Generate tiny url for a given url
11. Redirect user from tiny url to the actual web page
12. URL DB
13. Store mapping date of tiny url and actual url

Request flows

URL generation

1. User inputs a url from client and send generate request from a button
2. Load balancer direct the request to API gateway and then to a corresponding tiny URL service machine
3. Tiny URL service checks whether the URL DB already generated a tiny url for the current url, if so, return the tiny url. If not, the service generates a tiny url for the url, store it in the URL DB and return to the user

Tiny URL redirection

1. User enter a tiny url in browser
2. The tiny url redirect request will go through load balancer and API gateway and then responded by a tiny url service machine
3. Tiny url service checks whether the tiny url exists in DB or not, if exists, the service return the actual URL with a permanent redirect http request to the user's browser to the destination web page. If not exits, the service sends back a 404 not found request and redirect users to a graceful 'not found' web page
4. To make step3 respond faster to support high availability, frequently used tiny urls can be stored in a URL cache with K-V pair: (tiny_url, actual_url), tiny url service can first check whether the tiny url is in cache or not

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?