System requirements

Functional:

1. The system must be able to accept an arbitrary URL and respond with a shortened version.
2. The system should have a clean and usable frontend application, as well as public API.
3. Each shortened URL must be unique.

Non-Functional:

1. URL redirection time should take less than 0.5s

Shortened URLs cannot be modified or deleted, and expire after 1 year.

Capacity estimation

The system should support over 100 billion URLs (1 billion users, 100 URLs per user per year)

API design

1. create_shorened_url
   1. Parameters
      1. url: string
   2. Response
      1. shortened_url: string

Database design

Use a SQL DB such as PostgreSQL.

Table: `shortened_urls`

Columns:

• Primary key: `uuid`: uuid
• `shortened_url`: text
• `redirect_url`: text

High-level design

The User accesses the Web Application via the API Gateway / Load Balancer, and then submits a request to create a new short URL, which is passed to the URL Shortening Service via the API Gateway / Load Balancer. The URL Shortening Service generates a new unique UUID in the `shortened_urls` table, and from that generates the `shortened_url` via a deterministic hashing algorithm. Then both the `shortened_url` and `redirect_url` are set.

Multiple users can generate short URLs with the same input URL; the short URLs are guaranteed to be unique due to the generated UUID from the Database.

When the user later visits the shortened URL, they are routed to the Redirect Service via the API Gateway / Load Balancer, which fetches the redirect_url corresponding to the link, if it exists, and responds to the User with an HTML file that redirects to the correct URL.

Request flows

User -> API Gateway / Load Balancer -> Web Application

User -> API Gateway / Load Balancer -> URL Shortening Service -> Database

User -> API Gateway / Load Balancer -> Redirect Service -> Database

Detailed component design

We may want to rate limit link creation per user, based on IP or cookies. Additionally, add a total rate limit for all users to prevent DDoS attacks. This can be added to the API Gateway / Load Balancer.

Additionally, for commonly used short URLs, we can add a Redis cache that the Redirect service attempts to read from before looking up in the database.

The database will be sharded with consistent hashing, and there should be additionally multiple shards of the Redis cache.

Trade offs/Tech choices

Using SQL database for performant indexing and since there is no clear advantage of a NoSQL database.

Using API Gateway / Load Balancer since there will be multiple instances of each service in a microservice architecture to auto scale to user load.

Failure scenarios/bottlenecks

Users may visit an invalid short URL, in which case an error should be displayed to the user.

The Database is a single point of failure, and thus should be replicated.

Future improvements

Add the ability to edit or remove short URLs, meaning that they will have owners and thus we need to add an authentication system.