Design a URL shortener

Problem Statement

Design a URL shortener like bit.ly

---

Functional Requirements

1. Given a long URL → generate a unique short URL
2. Given a short URL → redirect to original long URL
3. Link Analytics — click count per short URL
4. Optional: custom aliases, expiry dates

Non-Functional Requirements

1. Low redirect latency — < 10ms p99 (read-heavy, must be fast)
2. Scale — 100M DAU, 1B reads/day, 100M writes/day
3. Storage — 1–5B total lifetime URLs
4. Highly Available — 99.99% uptime
5. High Durability — no URL should ever be lost
6. No collisions — two long URLs must never map to same short URL

---

Estimations

---

API Design

POST /api/urls/shorten
  Request:  { "longUrl": "https://...", "alias": "optional", "expiresAt": "optional" }
  Response: { "shortUrl": "https://short.ly/aB3xY9z" }

GET /{shortCode}
  Response: 302 Redirect → Location: <originalUrl>
             (use 301 for caching, 302 for accurate analytics — prefer 302)

GET /api/urls/{shortCode}/stats
  Response: { "clicks": 1234, "createdAt": "...", "lastAccessed": "..." }

301 vs 302:

• 301 Permanent — browser caches redirect, no future requests hit server → less load, but no analytics
• 302 Temporary — every redirect hits server → accurate click tracking ✅ (bit.ly uses this)

---

URL Generation Strategies

Option 1: Hash + Base62 Encode (Recommended)

longUrl → MD5/SHA256 hash → take first 7 chars → Base62 encode → shortCode

• Base62 = [a-z, A-Z, 0-9] = 62 chars
• 7 chars = 62^7 = ~3.5 trillion unique codes
• Problem: hash collisions — two different URLs could produce same 7-char prefix
• Fix: check DB before storing; if collision, append counter and re-hash

Option 2: Counter-based (Auto-increment ID → Base62)

DB auto-increment ID → Base62 encode → shortCode
  1       → "1"
  100     → "1C"
  1000000 → "4c92"

• Pros: guaranteed unique, no collision
• Cons: predictable/sequential — security concern, easy to enumerate
• Fix: use distributed ID generator (Twitter Snowflake)

Option 3: Pre-generated Keys (Key Generation Service)

KGS generates random 7-char keys upfront → stores in "available keys" table
URL shortener picks one key → marks as used

• Pros: no collision risk, fast (just pick a key)
• Cons: KGS is a single point of failure → need replication
• KGS keeps a small in-memory buffer of keys to avoid DB hit per request

Recommendation for interview: Base62 + counter (Snowflake ID) or KGS

---

High Level Architecture

graph TD
    Client([Client]) -->|POST /shorten| LB
    Client -->|GET /shortCode| LB
    LB[Load Balancer] --> AG[API Gateway]

    AG -->|write| WS
    AG -->|read| RS

    subgraph write["Write Path"]
        WS[URL Shortener Service]
        KGS[Key Generation Service]
        DB[(Primary DB <br/> DynamoDB)]
        MQ[[Kafka]]
        WS --> KGS
        WS --> DB
        WS -.->|async| MQ
    end

    subgraph read["Read Path"]
        RS[URL Redirect Service]
        Cache[(Redis Cache)]
        Replica[(Read Replicas)]
        RS --> Cache
        RS --> Replica
        Cache -.->|cache miss| DB
        DB --> Replica
    end

    subgraph analytics["Analytics"]
        AS[Analytics Service]
        ADB[(Cassandra)]
        AS --> ADB
    end

    MQ --> AS

    style write fill:#fff7ed,stroke:#f97316,stroke-width:1.5px
    style read fill:#f0fdf4,stroke:#22c55e,stroke-width:1.5px
    style analytics fill:#faf5ff,stroke:#a855f7,stroke-width:1.5px
    style Client fill:#dbeafe,stroke:#3b82f6
    style LB fill:#e9d5ff,stroke:#7c3aed
    style AG fill:#e9d5ff,stroke:#7c3aed
    style WS fill:#fed7aa,stroke:#ea580c
    style KGS fill:#fef9c3,stroke:#ca8a04
    style DB fill:#ccfbf1,stroke:#0d9488
    style MQ fill:#fed7aa,stroke:#ea580c
    style RS fill:#bbf7d0,stroke:#16a34a
    style Cache fill:#ccfbf1,stroke:#0d9488
    style Replica fill:#ccfbf1,stroke:#0d9488
    style AS fill:#f3e8ff,stroke:#9333ea
    style ADB fill:#f3e8ff,stroke:#9333ea

---

Deep Dive

Write Flow (Shorten URL)

1. Client → POST /shorten with longUrl
2. API Gateway → URL Shortener Service
3. Check if longUrl already exists in DB (dedup) → return existing shortCode
4. KGS provides unique shortCode (or generate via Base62)
5. Store { shortCode → longUrl, createdAt, userId, expiresAt } in DB
6. Return shortUrl to client

Read Flow (Redirect)

1. Client → GET /aB3xY9z
2. URL Redirect Service checks Redis cache first
3. Cache HIT → return 302 with longUrl (< 1ms)
4. Cache MISS → query DB → store in cache → return 302
5. Async: publish click event to Kafka → Analytics Service updates click count

Caching Strategy

• Cache: Redis with LRU eviction
• Cache what: shortCode → longUrl mappings (read-heavy, values rarely change)
• TTL: match URL expiry or 24hrs default
• Hit rate: ~80% of traffic hits top 20% URLs (Pareto) → cache very effective
• Cache size: 12,000 RPS × 500 bytes × 20% hot URLs ≈ manageable

Database Schema

URLs Table (DynamoDB / Cassandra)

shortCode   (PK)  | String  | "aB3xY9z"
longUrl           | String  | "https://..."
userId            | String  | owner
createdAt         | Long    | epoch ms
expiresAt         | Long    | epoch ms (nullable)
clickCount        | Int     | updated async

Why NoSQL:

• Key-value access pattern (shortCode → longUrl) — perfect fit
• High write throughput
• Horizontal scaling built-in
• No complex joins needed

---

Scalability

---

Tradeoffs

---

Edge Cases

• Duplicate longUrl → do NOT dedup across users or by default. Same longUrl must generate a new shortCode each time — different users own different shortCodes, and same user may want separate links per campaign (e.g. two influencers tracking same product URL independently). Cross-user dedup breaks ownership — User B's link could be deleted/modified by User A. bit.ly never dedups by default.
• Expired URLs → lazy delete on access + background TTL cleanup job
• Custom aliases → validate uniqueness before storing
• Malicious URLs → integrate URL safety API (Google Safe Browsing) on write
• KGS failure → fallback to hash-based generation

---

What Interviewers Look For

• Clarify functional vs non-functional requirements first ✅ 2026-03-29
• Back-of-envelope estimation (storage, RPS)
• Explain 301 vs 302 tradeoff ✅ 2026-03-29
• Justify NoSQL over SQL ✅ 2026-03-29
• Cache layer for read performance ✅ 2026-03-29
• Async analytics to not block redirect ✅ 2026-03-29
• Handle collisions in URL generation ✅ 2026-03-29
• Mention expiry + cleanup strategy