Requirements

Functional Requirements:

• Create a short URL for a given long URL.
• Return the long URL associated with a given short URL.

Non-Functional Requirements:

• High Availability
• Scalability
• Low Latency for redirection

Capacity Estimation

100 Million new URLs/month.

100:1 Read/Write ratio.

Storage: 3 Terabytes over 5 years.

API Design

POST /api/v1/shorten

GET /{shortAlias}

High-Level Design

What the box asks for: Describe the overall architecture and identify main components. What you should type in this box:

System Architecture & Request Flow

• Write Request (Creating a URL): Client -> Load Balancer -> Web Server -> ID Generation Service -> NoSQL Database
• Read Request (Clicking a URL): Client -> Load Balancer -> Web Server -> Redis Cache -> (If miss) -> NoSQL Database

Component Breakdown:

1. Load Balancer: Distributes incoming traffic globally to prevent any single web server from being overwhelmed.
2. Web Servers: Stateless API servers that handle the core business logic (validating inputs, routing to cache or DB).
3. Redis Cache: Sits in front of the database to catch the most frequent read requests (since this is a read-heavy system).
4. Database: Persistent storage for the URL mappings.

Database Design

What the box asks for: Define the data model, entities, and justify SQL vs NoSQL. What you should type in this box:

Database Choice: NoSQL (e.g., DynamoDB or Cassandra) Justification: We are storing billions of simple, independent key-value pairs (Short URL -> Long URL). We do not need complex relational joins or strict ACID transactions. We need massive horizontal scalability, high write-throughput, and high availability, which NoSQL handles perfectly.

Schema (URL_Mapping Table):

• short_url_hash (String, Partition Key) - e.g., "b9Lq"
• original_long_url (String)
• created_at (Timestamp)
• expires_at (Timestamp)
• user_id (String - optional for analytics)

Detailed Component Design

The Shortening Algorithm: Base62 Encoding

To generate the short link, we will use Base62 (A-Z, a-z, 0-9).

A length of 7 characters gives us $62^7$ (~3.5 Trillion) unique combinations, easily covering our 6 Billion URL estimate.

Collision Prevention Strategy:

To ensure two identical short links are never generated at the same time, we will use an offline Key Generation Service (KGS).

• The KGS pre-generates unique Base62 strings and stores them in a database.
• Web servers pull a batch of these pre-generated keys into memory.
• When a request comes in, the server just assigns one of the pre-loaded keys. This eliminates database write conflicts and makes generating the URL instantly fast.