System requirements

Functional:

As a user I would like to provide the original url and get a shortened url

As a user I would like to provide the shortened url and navigate to the original url

The url should be as short as possible

As a user I would like to provide a custom alias to the shortened url to remember or share easily

As an analyst I would like to know how many times the url has been used for analytics purpose

Questions

1. Should the system support sharing the url via email or sms
2. Should the system support expire of the shortened url
3. Shoudl we also tract the ipaddress or user who used the shortened url

Non-Functional:

The latency to get the shortened url should me as minimal as possible like 100ms

The system should be highly available

The system should be highly scalable

The system can be trade off with consistency for high availability

Capacity estimation

Estimate the scale of the system you are going to design...

There would be 1 million unique urls created every day

In 10 years 1M * 365 * 10 ~= 3.5 Billion

Read to write ration is 100:1

Convert 1Million per day to RPS

RPS = 1Million/86400 = 10 RPS

Average url length could be 500 characters i.e 0.5KB

Writes per second = RPS * Avg Length = 10 * 0.5 = 5KBPS

Reads per second = 100 * WPS = 5 * 100KBPS = 500 KBPS ( nearly 1MPBS if i include the shortened url which is returned)

Total storage i.e. original url and shortened url ignoring timestamp whch is constant length

Total storage for 10 years = 10 * 365 * 86400 * WPS

= 3650 * 86400 * 5 KBPS

=3650 * 500MBPS

= 365 * 5 GB

= 1.5 TB

1 character of shortened url can support

26 alphabets *2 + 10 digits

62 unique urls

lets take 6 characters i.e. 62^6 = 56B whch is enough to support for 10 years

API design

Define what APIs are expected from the system...

HTTP

1. POST CreateShortenedURL(original_url: string, alias:string=None) -> string
   1. {"original_url": "https://www.abc.com/defijslasdfds"}
   2. {"shortened_url": "https://www.xyz.com/123456"}
2. GET GetOriginalURL(shortened_url: string) -> string
   1. {"shortened_url": "https://www.xyz.com/123456"}
   2. {"original_url": "https://www.abc.com/defijslasdfds"}
3. GET Count(shortened_url:string) -> int
   1. {"shortened_url": "https://www.xyz.com/123456"}
   2. {"count": 100}

Database design

Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...

Entities

1. User
   1. user_id
   2. username_name/ip_address
   3. first_name
   4. last_name
   5. created_date
2. Urls
   1. url_id
   2. user_id
   3. original_url
   4. shortened_url
   5. created_date
   6. count

High-level design

You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

1 - 12 shows the write path

13,14 shows the read path/redirect

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

Algorithm to generate a shortened url

1. Take base64 encoding and take the first 6 characters or hash it
2. There could be collisions between two different urls which needs a retry and creates latency
3. Use a key generation service which can give unique code in sequence and since it is pregenerated it would take very less time to pick up the new code

Trade offs/Tech choices

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

I would go for NoSQL database like Dynamo DB for high availability and scalability with shortened url as primary key

I would go for API gateway which provides rate limiting, authentication and authorization

I would go for HTTP protocol for stateless to achieve high scalability

I would go for key generation service to generate keys in sequence so that there wouldn't be any conflict

I can reuse the keys in case of expiry or the url is no longer used

There could be permanent redirect without hitting the actual system and hence tracking would be lost

Redirecting would consume system resources

Failure scenarios/bottlenecks

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

1. The original url may no longer be available
2. The shortened url may not exists in the sytem
3. There could be DDOS attack to disrupt the system
4. The user could come after 10 years which would redirect to a different URL
5. Caching service might fail since the data is stored in memory which needs a refresh from database
6. There could be heavy load on database for reads hence its better to go for read replicas and auto scale
7. The data center might go down

Future improvements

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

I would like to convert the solution as API service later to generate revenue and sell to other clients or stakeholders

I can include CDN to redirect as soon as posisble to reduce the latency and cache hot urls