System requirements

Functional:

• Shortening: Users can input a long URL and receive a unique, short URL (alias).
• Redirection: Clicking the short URL redirects the user to the original long URL.
• Custom Alias: Users can define a custom alias (e.g., mysite.com/summer-sale) if available.
• Expiration: Users can set an expiration time for links.
• User Accounts: Authenticated users can manage their links (edit, delete).
• Analytics: Tracking metrics including click count, timestamp, country, and user agent.

Non-Functional:

• Scalability: Must handle read-heavy traffic (Read:Write ratio approx. 100:1).
• Latency:
• Redirection: < 20ms (server processing time).
• Shortening: < 200ms.
• Availability: 99.99% uptime. The system must be highly available (AP in CAP theorem).
• Durability: Data must persist efficiently for up to 5 years.
• Security: Prevention of brute-force attacks and malicious URL injection

Capacity Estimation (Back-of-the-envelope)

• New URLs: 100 million/month.
• Write QPS: ~40 writes/second.
• Read QPS: ~4,000 reads/second.
• Storage: * Record size: ~500 bytes.
  • 5-year storage: 100M * 12 months * 5 years * 500 bytes ≈ 3 TB.
• Cache: Storing 20% of daily requests (hot URLs) in memory.

API design

. Create Short URL

• POST /api/v1/urls
• Request:

• Response: 201 Created

2. Get URL Stats

• GET /api/v1/urls/{alias}/stats
• Response: 200 OK

3.2 Internal/Redirection Endpoint

1. Redirect

• GET /{alias}
• Response: 302 Found (Temporary Redirect)
  • Header: Location: {long_url}
  • Note: We use 302 instead of 301 to ensure traffic hits our servers for analytics tracking.

High-level design

Architecture Diagram Flow

1. Client sends a request.
2. Load Balancer (LB): Distributes traffic across Web Servers.
3. Web Server / API Gateway: Handles validation, rate limiting, and authentication.
4. Caching Layer (Redis): Stores mapping of ShortURL -> LongURL. Checks here first for redirection.
5. Application Service:
   • Shortening Service: Generates unique ID.
   • Redirection Service: Handles cache misses.
6. Database: Persistent storage for mappings and users.
7. Async Workers (Kafka + Workers): Decouples analytics logging from the redirection path to ensure low latency.

Detailed component design

To ensure short links are unique and collision-free, we cannot rely on simple database auto-increment (predictable and hard to shard).

Chosen Approach: Base62 Conversion + Distributed ID Generator

1. Base62: Characters [A-Z, a-z, 0-9].
   • 6 characters = $62^6$ ≈ 56.8 billion combinations.
2. ID Generator (Snowflake or Ticket Server):
   • We generate a unique 64-bit integer ID first (e.g., 10000000001).
   • Convert this integer to Base62 (e.g., 10000000001 -> sT4nZ).
   • This guarantees uniqueness without checking the DB for collisions.

5.2 Caching Strategy

• Cache-Aside Pattern:
  • Read: Check Cache -> If miss, Check DB -> Write to Cache -> Return.
  • Write: Write to DB -> (Optional: Write to Cache immediately).
• Eviction Policy: LRU (Least Recently Used).
• TTL: Set expiration for cache keys (e.g., 24 hours) to handle "viral" links that eventually cool down.

5.3 Analytics Processing (Async)

Redirection speed is critical. We must not write to the analytics database synchronously during the redirect request.

1. User clicks link.
2. Server redirects user immediately (Lat < 20ms).
3. Server pushes an event {short_id, timestamp, user_agent, ip} to a Message Queue (Kafka).
4. Analytics Consumers read from Kafka, aggregate data, and write to an OLAP database (e.g., ClickHouse or TimescaleDB) or a NoSQL store.

Database design

We can use a NoSQL database (like DynamoDB or Cassandra) for the URL mappings due to massive scale and simple Key-Value structure.

Table: URL_Mapping

• Partition Key: hash (String) - The short alias
• Columns:
  • original_url (String)
  • created_at (Timestamp)
  • expiration_date (Timestamp)
  • user_id (String)

Table: User (Relational DB is fine here)

• user_id (PK)
• email
• api_key
• plan_type

6.2 Database Partitioning (Sharding)

• Hash-Based Sharding: Use the hash (short alias) to determine which database shard stores the data.
• This ensures even distribution of data across nodes.