Requirements

Functional Requirements:

List the key functional requirements for the system (Ask the AI for hints if stuck)...

• The system needs to take a url and shorten it.
• The system should redirect to the origin url using the shortened one.
• The shortened url should be valid for a set period of time and then reclaimed so it can be reused.

Non-Functional Requirements:

List the key non-functional requirements (performance, scalability, reliability, etc.)...

• The system needs to be able to handle thousands of requests per second to generate shortened urls.
• The system needs to be fast in redirecting using the shortened url. Latency should be less than 100ms.
• The system should be highly available otherwise the links will not work. Aim for 99.99% availability. We need multiple servers so if there are any failures then users can still use the service.
• The links are accessed more often then they are generated therefore read speeds need to be fast.

Capacity Estimation

Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...

API Design

Define the APIs expected from the system. This is your chance to analyze and define the read and write paths so that you can come up with the high-level design...

CREATE operation: "takes a long URL and generates a shorter alias" → POST /api/urls/shorten (accepts longUrl, returns shortUrl)

READ operation: "redirects users to the original URL" → GET /api/urls/{shortUrl} (accepts shortUrl, returns longUrl or 302 redirect)

We might need some rate limiting so you cannot send 1000s of requests and overwhelm the server.

High-Level Design

Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.

URL Creation:

1. Client: The frontend application sends HTTP POST requests containing long URLs to the URL Shortening service.

2. URL Shortening Service: The backend receives requests and is responsible for creating and returning shortened URLs. It performs these key functions:

Generates a unique, short alias by encoding the URL or using hashing techniques to ensure uniqueness.

Stores the mapping of long URLs to short aliases in the database.

Manages errors and ensures each short URL is unique across all users.

3. Database: A highly available database (e.g., DynamoDB or Cassandra) is used to persist mappings between long URLs and short aliases.

URL Redirection:

1. API Gateway: As we now have two request types, we need an API Gateway. This acts as the entry point for all incoming requests, routing POST requests to the URL Shortening Service and GET requests to the URL Redirection Handler.

2. URL Redirection Request Handler: Accepts GET requests with the shortened URL, queries the cache for the original URL, and responds with a 302 Found status and the original URL in the Location header to facilitate seamless redirection.

3. Caching Layer: To reduce latency and offload read requests from the database, we implement a read-through caching layer (e.g., Redis with cache libraries) that stores frequently accessed URL mappings in memory. When a URL is not found in the cache, the cache itself automatically retrieves it from the database and stores it for future requests, making the process transparent to the Request Handler.

4. Database: The database stores all URL mappings. The cache layer automatically queries the database when needed, without requiring the Request Handler to manage cache misses directly.

Database Design

Define the data model. Identify the main entities, their attributes, and relationships. Consider the choice of database type (SQL vs NoSQL) and justify your decision based on access patterns...

The core need: given a short code, get the long URL back. That's it. So the natural shape is just a key-value pair. Therefore use Key-value stores (Redis, DynamoDB) which are very fast.

NoSQL is also used when you need very high write/read throughput. In our case we will have a high read throughput.

The user will post at minimum the following data

{

originalUrl: string

}

In the database we will store:

{

createdAt: timestamp,

originalUrl: string,

shortenedUrl: string,

expiry: timestamp

expired: boolean

}

Detailed Component Design

Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.

Short URL Generation

There are two main approaches to generating short URLs: hashing and random generation.

Hashing (e.g., using MD5 or SHA-2) creates a deterministic mapping of long URLs to short URLs. While it avoids the need for random number generation, it introduces a higher risk of collisions, particularly because the generated hash (20 bytes or more) must be truncated to fit within the shorter 8-character length of the short URL.

Random generation minimises the likelihood of collisions by randomly selecting strings for short URLs. If a collision occurs, the system can simply regenerate another random string. Though this approach requires computational resources for random number generation, modern operating systems like Linux provide efficient random generation.

Caching

To optimise the performance of the redirectURL() API, which is vital for this system, we employ a two-level caching strategy. Given the natural locality of access for requests, caching is particularly effective.

At the edge, Content Delivery Networks (CDNs) will store mappings from short URLs to long URLs for the most frequently requested links. For example, if a celebrity shares a short URL on social media, this mapping should be available in the CDN. CDNs, hosted at Internet Exchange Points (IXPs), provide ultra-low latency responses to clients. Their limited storage space focuses on high-demand mappings, ensuring scalability and fault tolerance by handling significant traffic without overloading the API Gateway.