# Design a URL Shortener: Complete Walkthrough

"Design a URL shortener like bit.ly" is one of the most common system design interview questions. It appears at Google, Meta, Amazon, and almost every tech company.

Why? Because it’s the perfect interview question:

- Simple enough to explain in 30 seconds
- Complex enough to test your understanding of distributed systems
- Touches on multiple important concepts (hashing, databases, caching, scale)

This walkthrough shows you **exactly how to approach this problem** in a 45-minute interview, following the framework that gets you hired.

## Phase 1: Clarify Requirements (5 minutes)

### Functional Requirements

1. The core feature is converting a long URL into a short URL, correct?
2. When users visit the short URL, they should be redirected to the original long URL?
3. Do we need custom short URLs? Like `bit.ly/my-custom-link`?
4. Do we need analytics? (click tracking, geographic data, etc.)
5. Should short URLs expire after some time, or last forever?
6. Do we need a UI, or just API endpoints?

**Core Requirements:**
- Create short URL from long URL
- Redirect short URL to long URL
- Support custom short URLs (nice to have)

### Non-Functional Requirements

1. How many URLs are we shortening per day?
2. What’s the ratio of shortening to redirection? (writes vs reads)
3. What’s our latency requirement for redirects?
4. Do we need high availability? What’s acceptable downtime?
5. How long do we need to store URLs? Forever?

**Non-Functional Requirements:**
- 100M new URLs/day
- 100:1 read/write ratio → very read-heavy
- <100ms latency for redirects
- High availability
- Indefinite storage

## Phase 2: Capacity Estimation (5 minutes)

### Traffic Estimates

```
Write requests (URL shortening):
100M URLs/day ÷ 86,400 seconds = ~1,200 writes/second
Peak traffic (3x average) = ~3,600 writes/second

Read requests (redirects):
100M writes × 100 read/write ratio = 10B redirects/day
10B redirects/day ÷ 86,400 seconds = ~115,000 reads/second
Peak traffic = ~350,000 reads/second
```

### Storage Estimates

```
Assumptions:
- Each URL record: 500 bytes average
  (short_url: 7 chars, long_url: 200 chars, metadata)

Storage per day:
100M URLs × 500 bytes = 50 GB/day

Storage for 10 years:
50 GB × 365 days × 10 years = ~180 TB
```

### Bandwidth Estimates

```
Write bandwidth:
1,200 writes/sec × 500 bytes = 0.6 MB/second

Read bandwidth (just redirects, not full page load):
115K reads/sec × 500 bytes = 57 MB/second

Total: ~60 MB/second bandwidth
```

## Phase 3: High-Level Design (10 minutes)

### Version 1: Basic Architecture

```
[Client] → [Load Balancer] → [Application Servers] → [Database]
```

### API Design

```
POST /api/shorten
Request:
{
  "long_url": "https://example.com/very/long/url",
  "custom_alias": "my-link" (optional)
}

Response:
{
  "short_url": "https://short.ly/abc123",
  "long_url": "https://example.com/very/long/url"
}

GET /{short_code}
Redirects to original URL with 301 redirect
```

### Database Schema

```
CREATE TABLE urls (
  id BIGSERIAL PRIMARY KEY,
  short_code VARCHAR(7) UNIQUE NOT NULL,
  long_url TEXT NOT NULL,
  created_at TIMESTAMP DEFAULT NOW(),
  INDEX(short_code)
);
```

### The Critical Decision: How to Generate Short Codes?

**Recommended Option: Counter-Based (Base62 Encoding)**
- Use auto-incrementing ID from database.
- Guaranteed uniqueness.

### Base62 Encoding Explained

```
Database ID: 12345
Base62 alphabet: a-zA-Z0-9 (62 characters)

12345 in base62 = "dnh"
So URL becomes: short.ly/dnh
```

## Phase 4: Deep Dive (15 minutes)

### Adding Cache Layer

```
[Client] → [Load Balancer] → [App Servers] → [Redis Cache]
                                          ↓
                                      [Database]
```

### Caching Strategy:
- Use LRU (Least Recently Used) eviction policy.
- Cache hot URLs automatically based on access patterns.
- TTL: No expiration (or very long, like 30 days).

### Database Scaling

**Scaling Options:**
1. Vertical Scaling
2. Read Replicas
3. Database Sharding (Partition data across multiple databases).

### Handling High Availability

**Redundancy at every layer:**

```
Architecture with HA:
[Clients]
    ↓
[CDN]
    ↓
[Load Balancer 1] ↔ [Load Balancer 2] (failover)
    ↓
[App Server 1] [App Server 2] [App Server N]
    ↓
[Redis Cluster] (master-replica, automatic failover)
    ↓
[DB Master] ↔ [DB Standby] (replication)
    ↓
[DB Replicas]
```

### Supporting Custom Short URLs

**Database Schema Update:**

```
ALTER TABLE urls ADD COLUMN is_custom BOOLEAN DEFAULT FALSE;
ADD CONSTRAINT unique_custom_code CHECK (is_custom = TRUE);
```

## Phase 5: Bottlenecks & Trade-offs (5 minutes)

### Bottleneck 1: Database Write Contention

**Solutions:**
1. Use UUID instead of sequential IDs.
2. Use distributed ID generator.

### Bottleneck 2: Cache Stampede

**Solutions:**
- Use "cache stampede protection".

### Bottleneck 3: Geographic Latency

**Solution:**
- Multi-region deployment.

### Trade-off Analysis: SQL vs NoSQL
- **PostgreSQL for MVP** due to manageable write volume and strong consistency.

### Security Considerations
1. **Rate Limiting**
2. **Malicious URLs Scanning**
3. **Collision Attacks**

## The Complete Solution

**Final Architecture:**

```
                    [Clients]
                       ↓
                     [CDN]
                       ↓
              [Load Balancer (HA)]
                       ↓
    ┌──────────────────┼──────────────────┐
    ↓                  ↓                  ↓
[App Server 1]   [App Server 2]   [App Server N]
    └──────────────────┼──────────────────┘
                       ↓
              [Redis Cache Cluster]
                       ↓
         [PostgreSQL Master-Standby]
                       ↓
           [PostgreSQL Read Replicas]
```

**Request Flows:**
1. Shorten URL: Client sends a long URL, the App server processes, stores in PostgreSQL and Redis, returning the short URL.
2. Redirect: Client checks Redis, if missed queries PostgreSQL, stores in Redis, and redirects.

**Scale Estimates:**
Handles 350K reads/sec via Redis caching, handles 3.6K writes/sec via PostgreSQL, with 99.99% uptime.