03 - Design a URL Shortener

🎁 Seven characters in a URL. That's all you get. How do you guarantee uniqueness across billions of links without a single collision?

A URL shortener (like bit.ly or TinyURL) converts long URLs into short links and redirects visitors to the original. It builds on the Pastebin lesson, the same key-value pattern, but adds redirection, encoding choices, and a read-heavy access pattern that benefits from caching.

URL Shortener Requirements

URL Shortener Functional Requirements

• Given a long URL, generate a unique short URL
• Visiting the short URL redirects to the original (HTTP redirect)
• Short URLs expire after a configurable time (default: 5 years)
• Optional: custom short codes chosen by the user

URL Shortener Non-Functional Requirements

URL Shortener Scope Exclusions

• Analytics dashboard (click counts, geo, referrer)
• Link editing (short URLs are immutable once created)
• User accounts (anonymous creation)

URL Shortener Estimation

URL Shortener Traffic

• 1M new URLs/day → Write QPS: 1M / 86,400 ≈ 12 writes/sec
• 10M redirects/day → Read QPS: 10M / 86,400 ≈ 115 reads/sec
• Peak (3×): ~350 reads/sec

Moderate traffic. One server handles it, but we'll add caching because redirect latency must be < 50ms.

URL Shortener Storage

• Per URL record: ~500 bytes (short code + long URL + timestamps)
• 5-year total: 1M/day × 365 × 5 = 1.8 billion URLs
• 1.8B × 500 bytes = ~900 GB

Under 1 TB. Fits on a single database with room to spare.

Short Code Length Calculation

How many characters do we need?

Base62 characters: a-z, A-Z, 0-9 = 62 options per position
62^6 = 56 billion combinations
62^7 = 3.5 trillion combinations

At 1M URLs/day × 365 × 5 = 1.8 billion URLs needed
→ 6 characters is enough (56B >> 1.8B)
→ 7 characters gives massive headroom

We'll use 7 characters for safety margin.

URL Shortener High-Level Design

┌─────────────────────────────────────────────────────────────┐
│                      URL SHORTENER                          │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  ┌──────────┐     ┌──────────────┐     ┌──────────────┐     │
│  │  Client  │────►│  API Server  │────►│  Database    │     │
│  │          │◄────│              │     │  (PostgreSQL)│     │
│  └──────────┘     └──────┬───────┘     │              │     │
│                          │             │  short_code  │     │
│                          ▼             │  long_url    │     │
│                   ┌──────────────┐     │  expires_at  │     │
│                   │  Cache       │     └──────────────┘     │
│                   │  (Redis)     │                          │
│                   │  hot URLs    │                          │
│                   └──────────────┘                          │
└─────────────────────────────────────────────────────────────┘

Two operations:

• Create: Client sends long URL → API generates short code → store in DB → return short URL
• Redirect: Client visits short URL → check cache → if miss, check DB → return 301/302 redirect

301 vs 302 Redirect

For our design (no analytics): 301 is fine. It reduces server load because browsers cache the redirect. If you add analytics later, switch to 302.

URL Shortener Deep Dive

Short Code Generation Strategies

Same question as Pastebin IDs, but now we have more options because URL shorteners have different tradeoffs:

Which to choose?

• Random base62 if you want simplicity and unpredictability. Collision check is fast (indexed lookup).
• Counter + base62 if you want zero collisions and don't care about predictability. Works well with a pre-allocated range per server (no coordination needed).
• Hash truncation if you want deduplication (same long URL always produces the same short code). But: different users shortening the same URL share a code. Is that okay?

For this design: Random base62 with collision retry.

1. Generate random 7-char base62 string
2. Check if exists in DB (indexed lookup, fast)
3. If collision: generate again (probability: 1.8B / 3.5T = 0.05%)
4. Insert into DB
5. Return short URL

URL Shortener Caching

Unlike Pastebin (where any latency < 200ms is fine), redirects must be near-instant. Users clicking a link expect it to load immediately.

Redirect flow:
  1. Check Redis: GET short:xK9mP2q → "https://example.com/very/long/path"
  2. If found: return 301 redirect (cache hit, ~1ms)
  3. If not found: query PostgreSQL → cache result → return 301 (~5-10ms)

What to cache: The top 20% of URLs handle ~80% of traffic (Pareto principle). Popular links shared on social media get millions of clicks. Caching them eliminates most DB reads.

Cache eviction: LRU (Least Recently Used). URLs that haven't been accessed recently get evicted to make room for hot ones.

URL Shortener Schema

urls
├── short_code (VARCHAR(7), PRIMARY KEY)
├── long_url (VARCHAR(2048))
├── created_at (TIMESTAMP)
└── expires_at (TIMESTAMP, nullable)

Index: PRIMARY KEY on short_code (already indexed)
Index: expires_at for cleanup job

Why short_code as primary key? Every read is WHERE short_code = ?. Making it the primary key means the lookup uses the clustered index, the fastest possible read.

Custom Short Codes

Users want short.ly/my-brand instead of short.ly/xK9mP2q:

POST /api/shorten
  Body: { url: "https://...", custom_code: "my-brand" }

Validation:
  - 3-20 characters, alphanumeric + hyphens only
  - Check if already taken (same collision check as random)
  - If taken: return 409 Conflict

No special architecture needed. Custom codes go in the same table. Just validate format and uniqueness.

URL Expiration

Same pattern as Pastebin:

1. Lazy check on redirect: If expires_at < NOW(), return 404 instead of redirecting
2. Background cleanup: Cron job deletes expired rows + evicts from cache

Scaling to 100× Traffic

If traffic grows to 100M URLs/day and 1B redirects/day:

But at our current scale (12 writes/sec, 350 reads/sec peak), none of this is needed. Design for today, know how to scale for tomorrow.

Key Takeaways

• URL shorteners are read-heavy, so optimize the redirect path

  10:1 read-to-write ratio means caching is essential. Redis gives sub-millisecond redirects for hot URLs. The write path (creating short URLs) is simple and low-volume.

• 301 vs 302 is a product decision, not a technical one

  301 (permanent) reduces server load but loses analytics. 302 (temporary) lets you track every click. Choose based on whether you need click data.

• Short code generation has multiple valid approaches

  Random (simple, unpredictable), counter (zero collisions), hash (dedup). Each has tradeoffs. In an interview, pick one, explain why, and mention the alternatives.

• Cache the hot 20% to serve 80% of traffic

  Pareto principle applies strongly to URL shorteners. A viral link gets millions of clicks. Serving it from Redis at 1ms instead of PostgreSQL at 5ms makes a real difference at scale.

• Design for current scale, explain how to grow

  At 12 writes/sec, a single PostgreSQL is correct. Don't shard prematurely. But show the interviewer you know the path: sharding, replicas, load balancing, range-based ID allocation.

🎁 Every system you've designed so far produces thousands of log events per second. Where do they go, and how do you find the one that matters?