Requirements

Functional Requirements:

1. Users can submit a long URL and receive a shortened URL
2. Users visiting the short URL get redirected (HTTP 301/302) to the original long URL
3. Optionally, users can set a custom alias for their short URL

Non-Functional Requirements:

1. High Availability — The system must remain operational even if individual components fail. Use load balancers (with redundancy), multiple app servers, and a master-slave database setup to avoid single points of failure.
2. Low Redirect Latency — Redirects should complete in under 1 second. Use geo-routing (e.g., Route 53 latency-based routing) or a CDN to serve redirects from locations close to the user.
3. Horizontal Scalability — As traffic grows, the system should scale by adding more servers behind the load balancer, not by upgrading individual machines (vertical scaling).

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...

1. POST /shorten — User sends their long URL, you return a short code
2. GET /{shortCode} — User visits the short URL, you redirect them to the original

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.

Components:

• Clients — browsers/apps that create short URLs or visit them
• DNS (Geo-Routing) — Route 53 or Cloudflare DNS routes users to the nearest region based on latency
• Load Balancer — e.g., NGINX or AWS ALB, distributes traffic across app servers
• App Servers — stateless service handling both write (create) and read (redirect) requests
• Redis Cache — stores frequently accessed short→long URL mappings for fast lookups
• Database (Master-Slave) — Master handles writes (new URL mappings), slaves handle read queries

Write Flow (Create Short URL):

1. User sends POST /shorten with { "long_url": "https://..." }
2. Request hits DNS → Load Balancer → App Server
3. App server generates a unique short code:
   • Generate random 6-character base62 string
   • Check DB for collisions; if exists, retry with new random string
4. Save mapping (shortCode → longURL) to database (master)
5. Also cache it in Redis for fast future lookups
6. Return { "short_url": "tinyurl.com/abc123" }

Read Flow (Redirect):

1. User clicks tinyurl.com/abc123
2. DNS routes to nearest region → Load Balancer → App Server
3. App server checks Redis cache for abc123
4. Cache hit: returns long URL immediately (~1ms)
5. Cache miss: queries database (slave), caches result in Redis for next time
6. Returns HTTP 301 redirect to the original long URL

Key Design Decisions:

• Geo-routing + CDN: reduces redirect latency globally
• Redis cache: offloads database reads, enables fast redirects
• Master-slave DB replication: high availability and read scalability
• Stateless app servers: easy horizontal scaling behind load balancer

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...

Table: url_mappings

Indexes:

• UNIQUE INDEX idx_short_code ON url_mappings(short_code) — for fast redirect lookups
• INDEX idx_created_at ON url_mappings(created_at) — for analytics/cleanup of old records

Partitioning (at scale):

• Partition by short_code hash (e.g., 16 partitions) for even data distribution
• Or partition by created_at (e.g., monthly) for time-based archival

Why SQL?

• URL mappings are relational (one short code → one long URL)
• ACID compliance ensures no duplicate short codes
• Indexes make lookups fast even at billions of rows
• Read vs write consistency (major) — important nuance! When a user creates a short URL, do you need strong consistency (guarantee it's written before the user can try it)? For redirects, is eventual consistency okay?

Consistency: Strong consistency for writes (code must be unique and durable). Eventual consistency is fine for redirect reads — a brief delay is acceptable.

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.

1. ID Generation (short code creation)

We generate random 6-character base62 strings (a-z, A-Z, 0-9 = 62^6 ≈ 56 billion combinations).

• Collision handling: Before saving, check if the short code already exists. If it does, generate a new random one (usually 1-2 retries max).
• Hard to guess: Random strings prevent sequential enumeration — attackers can't predict valid codes.
• No single point of failure: The app server generates codes locally (no central ID generator needed), so no split-brain issue.

2. Caching (Redis)

• TTL: Store each mapping in Redis with a 24-hour TTL. Frequently accessed URLs get renewed TTL automatically.
• Eviction: Use LRU (Least Recently Used) eviction to keep hot mappings in memory.
• Cache miss flow: App server queries DB, caches result in Redis, returns redirect. Next hit is instant.
• Viral links: Hot short codes stay in Redis cache, protecting the DB from thundering herd.
• Cache invalidation: If a URL needs updating, we delete the key from Redis + CDN.

3. Database Partitioning

• Partition the url_mappings table by hash(short_code) % 16 — 16 database shards.
• Each redirect lookup hits exactly one shard (no scatter queries).
• Hot short codes are handled by the Redis cache, so no single shard gets overloaded.

4. Rate Limiting

• Per-IP rate limiting using a token bucket algorithm (e.g., 100 create requests per minute per IP).
• Return HTTP 429 with a Retry-After header when exceeded.