System requirements

Functional:

User can create short urls

Users can visit short urls, be redirected to original urls

Non-Functional:

Highly available

Low latency

Capacity estimation

100 million daily active users

100 million writes per day

100 billion reads per day

1 million reads per second

1 thousand writes per second

35 billion writes per year

8 characters a-zA-Z0-9 -> ~100 trillion urls. good for 1000 years

1kb per url -> 100 gb a day -> 35 tb a year

API design

POST url (original_url, client_info)

GET url (tiny_url)

Database design

Document DB like MongoDB to store short url to long url mapping and metadata. SQL DB to store list of say next few hundred million keys which are to be used for new URLs. This DB can be refreshed periodically with new keys (say every half hour).

High-level design

Already explained in rest of windows

Request flows

Read:

Load balancer receives request. If client not rate limited by LB, load balancer routes client request to a server. Server checks distributed LRU cache (eg Redis) for URL. If not found in cache, Server goes to Document DB to get url and store it in cache.

Write:

Load balancer receives request. If client not rate limited by LB, Load balancer routes client request to a server. Server

Detailed component design

Already explained in rest of windows

Trade offs/Tech choices

Used MongoDB to store urls as easily horizontally scalable and will not be updating stored urls -> no need for ACID constraints. Use SQL DB to store keys as need to atomically get new keys and mark old as used/avoid collisions

Failure scenarios/bottlenecks

Right now estimate 1000 writes per second, if that increases by an order of magnitude, short url generation will get slower because SQL database will get overloaded.

Future improvements

Can expire old URLs to save storage cost.