System requirements

Functional:

The service will generate concise aliases that redirect to the original longer URLs.

Non-Functional:

No latency;

Scalability;

Fault tolerance;

Maintenance

Capacity estimation

1. Total database capacity:

The database has 4 attributes, userId, tiny url, original url, create timestamp

A record = 20 + 8 + 100 + 8 = 136 bytes,

Assume the index occupied 50% of a record, so the index size is 136 * 50% = 68 bytes

Total = 68 + 136 = 204 bytes

In case of generating 17.28 million tiny urls in a year, DB capacity is 204 * 17.28 * 1,000,000 * 365 = 1.2 PB

2. Bandwidth:

Write bandwidth (generate shorten url):

TPS * (userId + tinyUrl + originalUrl + timestamp) = 136 bytes * 200/s = 27.2 kb/s

Read bandwidth (Get original Urls)

TPS * (userId + tinyUrl + originalUrl + timestamp) = 20,000/s * 136 bytes = 2.72MB/s

3. Cache

Assume the cache occupied 20%, cache = 240 TB

API design

There are two APIs:

GetTinyUrl(String originalUrl)

GetOriginalUrl(String tinyUrl)

Database design

The database has below attributes:

1. User id
2. Tiny url
3. original Url
4. create timestamp

High-level design

• Client: The user interface (mobile/web) that user interact with
• Api Gateway: Manages api requests, routing them to the appropriate services
• Shorter Service: Generating shorter urls
• Database: Store the mapping between shorter url to original urls
• CDN: Content distributed network
• Get original url service: return original urls with shorter url input
• cache: accelerate mapping s

Request flows

Shorter url Service:

• Client: User sends a shorter url request
• CDN: cdn check if there is any cache for this request, if not, cdn sends the request to the nearest and non-busy point to process
• Api Gateway: provide authentication and also send the request to the appropriate services
• Shorter service: the input is the original url, it provides the algorithm to short the original url and also save the shorter url, user id, timestamp to the database
• Database: Save the shorter url, user id, timestamp, original url

Get original url service:

• Client: User sends a mapping shorter url request
• CDN: cdn check if there is any cache for this request, if not, cdn sends the request to the nearest and non-busy point to process
• Api Gateway: provide authentication and also send the request to the appropriate services
• Get Original URL service: it uses tiny url as the key to check the original url in cache, if not it will get it from the database
• Cache: the tiny url is the key and the original url is the value in cache. If the key exist, return the original url to the service
• Database: Provide the original url and also update the cache if it does not exist it.

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

If the database and cache both down, the shorter service will not work.

Future improvements

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