System requirements

Functional:

We need to return short url of length 6 for a given long url, the short url should only contain English letters and digits.

Non-Functional:

The system should be highly available and respond with low latency.

They system should be reliable that can store the short url for years.

Capacity estimation

Assume we have 1M new short urls generated everyday, which is 1M/86400 = 11/second

For each request, we have to include the metadata and short, long url, average length of long url is 100 characteres, and 6 characters, and metadata 10KB, so the average storage for each request is (10K + 100 * 2 + 6 * 2) =10KB

Assume we need to store the short url for 5 years, then total storage we need is : 10KB * 1M * 365*5= 18TB

API design

We should have the API to generate the short url

• generate(longUrl, user_id, creation_time)

We should be able to visit the original website for a given shortUrl

• visit(shortUrl)

Database design

Table1: newly generate shortUrl - (id, shortUrl)

Table2: used shortUrl - (id, shortUrl)

Table3: longToShortUrl - (id, shortUrl, longUrl)

High-level design

Request flows

• Client sent request to the system for generating a shortUrl
• The request will come to load balancer first, then distribute it to applicatioin servers
• The application servers get a valid short url from the cache in memory
• store the shortUrl together with the longUrl to the database
• Next time client sent request to visit original website using this shortUrl
• It will check the cache to see this mapping (shortUrl -> longUrl) is available, then just return the longUrl and direct client to original website
• If it's not in the cache, then just check with databse to get the longUrl

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?