System requirements

Functional:

• generate short URL
• short URL should direct user to the same location as the long URL
• provide usage statistics

Non-Functional:

• every short URL should always direct to the correct location with at least 99% accuracy, and in the 1% fail rate it should bring to a page explaining the error
• should generate short URLs within 5 seconds
• target uptime of 99.9%

Capacity estimation

• DAU: 10^5 users
• goal DAU: 10^6 Users
• 10 short URLs per user per day
• goal URLs per day generated -> 10^7 urls per day generated
• goal URLs per second generated -> 100 urls per second

API design

• Post generate_short_url/original_url="" -> generates short URL given a URL
• Get short_url/original_url="" -> returns the short URL of a given URL if it exists
• Get destination/url="" -> returns the webpage location of a URL if it exists
• Get times_visted/url="" -> returns the number of times a url has been clicked by all users

Database design

Entities:

• URL(id, source_url, short_url, location, client_id, times_visited, created_at, expiration_date)
  • keys: short_url and client_id
• Users(id, username, email, date_joined)
  • keys: id or username or email

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

The clients will pass their requests through a Load Balancer as well as a rate limiter, and each service will be a Kubernetes Cluster that can handle auto scaling.

to generate a new URL the request will go through the Generate Short URL API which will forward the Post request to the URL DB, which is a mongoDB DB that can handle many concurrent requests

To find the web location to send the user to when clicking a short URL, the Location API is called and hits the cache, then if no location is found for the URL, it hits the URL DB

to generate statistics, the same request flow as to get the location happens.

Detailed component design

Generate Short URL has an algorithm, possibly base62 algorithm, to take a URL and shorten it, this will need to be written in a highly performant language as this is the only API that involves complex logic.

Location API and Statistics API both simply hit a cache and then the URL DB with Get requests

Trade offs/Tech choices

For the Cache I am using Redis, and for URL DB I am using MongoDB. I am doing this because both this cache and this DB can handle many concurrent requests. MySQL for the DB was also considered, but this service cannot handle as many requests as MongoDB.

Generate Short URLs will be written in C because algorithmic performance is of the utmost importance for this API.

Failure scenarios/bottlenecks

1 bottleneck is the processing speed of Generate Short URL API. If this is too slow, the application will not be able to process the 100 URL per second that is needed. Ideally this API will be able to handle about 100 requests per second with an average execution time of 0.3 second per short URL generation, otherwise we risk not being able to meet the standard due to throughput of Posting to the DB.

Another possible bottleneck is the number of concurrent transactions per second MongoDB and Redis are able to perform. If the user base gets too large, I would have to introduce messaging queues or scale up the number of DBs / Caches available and likely both of these will be sharded on short_url

Future improvements

I plan to introduce logging in the future for enhanced data integrity