System requirements

Functional:

1. The system should generate unique short URLs for long URLs
2. It should be fast
3. The short URL should take the user to the long URL
4. The short URLs should be invalidated after x number of years
5. we may need to check for sensitive (adult content) and malicious URLs

Non-Functional:

1. The system should be consistent; the same URL should give the same output
2. The system should be scalable to address multiple users
3. System should be highly available

Capacity estimation

50 million users per month, assuming 1 million writes and 10kb per write

1*10=10GB per month

120GB per year

API design

check_short_exsists(long_url)-> to prevent overwrites, returns none if empty else, the short string

create_short(long_url)-> creates short and returns the result

get_long(short_url)-> Given the short URL sends the long URL, enabling user to visit the page

generate_token(long_url) called by create_short API creates a short based on the hash

Database design

URL Table:

1)Primary Key (int)

2) Long URL (varchar)

3) Short URL (var char)

4) Created (DateTime)

5) Access times (int)

High-level design

graph LR

A[User] -- Requests --> B((Load Balancer))

B -- Requests --> C{Rate Limiter}

C -- Check Rate Limit --> D{Add to Queue}

D -- Queue Size Check --> E{Deny Service}

E -- Deny Request --> F((Blocked Service))

D -- Allow Request --> G{User API}

G -- Process Request --> H[Database or Cache]

H -. Response .-> A

G -- Write Request --> J(Database Write)

J -- Replication --> K[Database]

G -- Read Request --> L((Cache))

L -- Cache Hit --> K

L -- Cache Miss --> M[Database]

N[Background Job] -- Periodically --> O((Database Cleanup))

O --> K

Request flows

• The User sends requests to the Load Balancer.
• The Load Balancer forwards requests to the Rate Limiter to check the rate limit.
• If the request is allowed by the Rate Limiter, it proceeds to the User API for processing.
• The User API handles both write requests (updates to the database) and read requests (queries to the database and cache).
• The Database responds to write and read requests from the User API.
• The Cache may respond to read requests with cache hits or misses.
• The Background Job conducts periodic cleanup tasks in the Database

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

1) Using a sql db to allow for better scans to delete old shorts

Failure scenarios/bottlenecks

1. The replication may not be fast enough, we write to db but when reading the short may not be available
2. the clean up will delete all records, we may want to keep premium ones or popular ones
3. we may have same hash values for different urls

Future improvements

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