System requirements

Functional:

• given a long url, generate a short url
• given a short url generated from our service, redirect to the original long url

Non-Functional:

• highly available
• provide fast redirects
• handle 200 requests for generation and 20000 redirections per second
• urls generated should be unique, it should reside in the system long term

Capacity estimation

• 200 requests per second for generation
• 20000 for redirecting
• assuming we are storing for 10 years, thats 200 urls * 3600 a day. * 3650 days assuming average length of 100 for the long urls (to be safe) then that is 6,307,200,000,000 bytes = 6.3 TB of storage

API design

POST v1/data/longUrl/ { longUrl: http://.... }

GET v1/{shortUrl}/

Database design

A simple key value store should be enough

key value

shortUrl (str) longUrl (str)

High-level design

Client will call our API gateway/load balancer. Compute, cache tier, and database tier can all be scaled out separately. Web services should be stateless (serverless??) since it just checks for cache hit otherwise gets the data from the key value store.

It also serves the purpose of generating keys. All of these operations can be done on elastic CPU that can be even auto scaled.

need help - how does cache get scaled out? i use aws redis and ddb so that's all handled for me.

Request flows

Generation Flow

1. user calls the POST method with their long url
2. check if we have already generated a long url already. since generation can take a few seconds, we can scan the table, or create another key-value where long url is the key. up to 12TB is not that bad
3. web service generates the tiny url and returns it to the user.

Redirect Flow

1. user calls the get method with the tiny url
2. redirect with 301 code with the long url

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

Tiny URL generation.

we don't want the url to be too long. but it should support our 70 billion url use case. If we choose sha1, its not case sensitive so we will have 26 + 10 chars to work with. 36^n = 70billion. n = 7

we can take the first 7 chars of sha1. In case of collisions, we can check for the shorturl's existence in db and regenerate.

Trade offs/Tech choices

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

Hashing and retrying is not the most efficient. Base62 is another option but i don't know it

Failure scenarios/bottlenecks

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

we should have replication in the db tier so that we don't lose data.

Future improvements

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