S127 · Design a URL Shortener — the Classic Warm-Up

Module M15: System Design · Session 127 of 130 · Track: SYS 🔗

What you'll be able to do after this session

• Explain Design a URL Shortener to a friend in one minute, out loud, no notes.
• Recognise it when you see it in real code / systems / papers.
• Complete the hands-on exercise at the end without looking up help.

Prerequisites

If you can't answer these in 30 seconds each, redo the linked session first:

• S063 — Caching — Cache-Aside, Write-Through, TTLs, Invalidation

Pre-read (skim before the session)

• 🎥 Intuition (5–15 min) · System Design: URL Shortener — 15-min clean explanation of the classic problem.
• 🎥 Deep dive (30–60 min) · Design a URL Shortener like TinyURL — full 45-min walkthrough with capacity math.
• 🎥 Hands-on demo (10–20 min) · Build a URL Shortener in Python — code it end-to-end.
• 📖 Canonical article · System Design Primer — Design a URL Shortener — closest analogue, worked in full.
• 📖 Book chapter / tutorial · High Scalability — URL Shortener Case Study — real-world constraints.
• 📖 Engineering blog · Instagram Engineering — Sharding & IDs at Instagram — where the "generate a globally unique short ID" problem was solved at scale.

(a) Intuition · 5 min

The one-paragraph mental model. Why this concept exists, what problem it solves, and the analogy that makes it stick.

In one sentence: Simple problem, deep trade-offs.

A URL shortener sounds trivial — take a long URL, return a short one, redirect when clicked. Why does it get asked in every FAANG interview? Because it packs almost every distributed-systems trade-off into a problem simple enough to reason about in 45 minutes: unique ID generation, key-value storage at scale, cache design, read-heavy scaling, redirect latency, analytics pipelines, abuse prevention. It's a training koan — the design is simple, but every decision reveals what you understand.

At its core, the system does two operations. Write: POST /shorten {url} → generate a unique short code (e.g. bit.ly/aX9k2p) and store (short_code → long_url) in a database. Read: GET /aX9k2p → look up long_url, return HTTP 301 or 302. Read-to-write ratio is typically 100:1 or higher (people click links more than they create them). The interesting choices are: how do you generate short codes at scale without collisions? How do you make redirect latency < 30ms globally? What do you cache and where?

The gotcha you must carry forever: the "obvious" choice — hash(url) truncated to 7 chars — sounds clever but is a trap. Different URLs can hash to the same short code (collision), and hashing is deterministic so you leak info about whether a URL was already shortened. Real systems either (a) use a monotonic counter that's base62-encoded, or (b) generate a random 62^7 ≈ 3.5 trillion-space ID and check for collision on insert. Both are safer. The interviewer wants to see you spot the hash pitfall.

(b) Visual walkthrough · 15 min

Diagrams, worked examples, step-by-step visuals.

Two dominant designs. Which you pick is a real trade-off, not a right answer.

Capacity estimate (for the interview):

• Say 100M new URLs / month = ~40 URLs/sec write. Peak ~200/sec. Trivial.
• Reads: 100:1 → ~4000 reads/sec average, peak ~20k/sec. Serious but very cacheable.
• Storage: 100M/month × 500 bytes (URL + metadata) × 12 months × 5 years = ~3 TB total. Fits on a single Postgres replica; still, shard for safety.
• Short code space: 62^7 ≈ 3.5 × 10^12. Enough for 3.5 trillion URLs before you need 8-char codes. Enough forever.

Redirect latency budget (the interesting part):

Design the system so 99% of requests never leave the CDN edge. This drives your architecture: aggressive Cache-Control headers, edge KV stores (Cloudflare KV, Fastly), and pre-warming for known-hot URLs.

Full HLD:

Note the analytics path is async — click tracking must never block the redirect.

Sharding key: code (the short ID itself). Because reads are point lookups by code, and writes are random codes, hash-sharding gives even distribution. Don't shard by user or by URL — bad access patterns.

(c) Hands-on · 20 min

Code you type and run. Not pseudo-code — real, runnable, copy-pasteable.

Build a working URL shortener with Flask + Redis + Postgres. Runs locally in a few minutes.

# pip install flask redis psycopg2-binary
# docker run -d -p 6379:6379 redis:7
# docker run -d -p 5432:5432 -e POSTGRES_PASSWORD=pw postgres:16
import os, string, hashlib, secrets
from flask import Flask, request, redirect, jsonify, abort
import redis, psycopg2
 
app = Flask(__name__)
r = redis.Redis(host="localhost", port=6379, decode_responses=True)
pg = psycopg2.connect("dbname=postgres user=postgres password=pw host=localhost")
pg.autocommit = True
 
with pg.cursor() as c:
    c.execute('''CREATE TABLE IF NOT EXISTS urls (
        code TEXT PRIMARY KEY,
        long_url TEXT NOT NULL,
        created_at TIMESTAMPTZ DEFAULT now()
    )''')
 
ALPHABET = string.ascii_letters + string.digits  # 62 chars
 
def encode_base62(n: int) -> str:
    if n == 0: return ALPHABET[0]
    out = []
    while n:
        n, rem = divmod(n, 62)
        out.append(ALPHABET[rem])
    return "".join(reversed(out))
 
def next_id() -> int:
    # Real systems use ZooKeeper / a range-allocation service.
    # Redis INCR is fine for our demo.
    return r.incr("url:counter")
 
@app.post("/shorten")
def shorten():
    long_url = request.json.get("url")
    if not long_url or not long_url.startswith(("http://", "https://")):
        abort(400)
    code = encode_base62(next_id())
    with pg.cursor() as c:
        c.execute("INSERT INTO urls (code, long_url) VALUES (%s, %s)", (code, long_url))
    r.set(f"url:{code}", long_url, ex=86400)  # cache for 24h
    return jsonify({"short": f"http://localhost:5000/{code}"})
 
@app.get("/<code>")
def follow(code):
    # Try cache first
    cached = r.get(f"url:{code}")
    if cached:
        r.incr(f"clicks:{code}")  # async in prod: push to Kafka
        return redirect(cached, code=302)
    # Cache miss → DB
    with pg.cursor() as c:
        c.execute("SELECT long_url FROM urls WHERE code=%s", (code,))
        row = c.fetchone()
    if not row: abort(404)
    long_url = row[0]
    r.set(f"url:{code}", long_url, ex=86400)
    return redirect(long_url, code=302)
 
if __name__ == "__main__":
    app.run(port=5000)

Observe when you run:

1. curl -X POST http://localhost:5000/shorten -H "Content-Type: application/json" -d '{"url":"https://example.com"}' — get back a short URL.
2. Hit the short URL in a browser → redirects to example.com. Second hit is served from Redis (no DB call).
3. Watch Postgres logs: the SELECT only fires on the first click; subsequent clicks are pure Redis.
4. redis-cli KEYS 'clicks:*' shows per-code click counts.
5. Kill Postgres — reads still work for cached codes; writes fail immediately (good — no silent data loss).

Try this modification: replace next_id() with a distributed variant. Instead of one Redis counter (single point of contention), have each app server request a range of 10,000 IDs from Redis in one call and hand them out locally. This is called range allocation and is how Instagram / Twitter solved the same problem at scale. Compare write throughput before and after.

(d) Production reality · 10 min

How this shows up in real systems, gotchas, war stories, common bugs.

War story — the day bit.ly went down and half the internet 404'd. In 2016, bit.ly's Redis primary hit an OOM and cascaded failures across their fleet. Redirects that should have taken 15ms turned into 3-second Postgres queries, then timeouts. Impact: millions of shortened links across Twitter, ads, marketing emails temporarily broken. Postmortem lessons: (1) always have a stale-cache-is-better-than-no-cache policy — serve expired entries during origin outages. (2) never let redirect latency exceed the browser's default retry timeout (~30s) — clients start hammering. (3) Redis eviction policy must be allkeys-lru, never noeviction, or your OOM turns into a full outage.

Common bugs top teams handle for:

• 301 vs 302 redirects — 301 is permanent and gets cached by browsers and CDNs forever. If you 301 and later need to change the target (e.g. update a broken URL, remove abusive content), users with cached responses can't be updated. Use 302 unless you're 100% sure the mapping is immutable.
• Custom aliases + collisions — allowing bit.ly/my-brand is a nice feature; it also lets attackers race to claim brand names. Rate-limit alias creation per user, reserve a namespace for enterprise customers.
• Abuse & phishing — 30-40% of shortened URL traffic on public shorteners is spam/phishing. Real systems: (a) scan URLs against Google Safe Browsing on shorten and periodically, (b) allow one-click reporting, (c) show an interstitial warning page for suspicious URLs.
• Analytics avalanche — every click = 1 analytics event × billions of clicks = TB/day. Batch client-side (accumulate 100 events, POST once), sample at ingest, and use ClickHouse or BigQuery — never OLTP DBs.
• URL length attacks — attackers submit 4KB URLs to fill your DB. Enforce max 2048-char input.
• Cache stampede — a viral URL suddenly goes from 10 QPS to 100k QPS. If it's not cached, 100k requests hit Postgres simultaneously. Solutions: singleflight (only one request goes to DB, others wait), stale-while-revalidate, pre-warm cache on high-traffic detection.

Real-world capacity data: Bit.ly reportedly handled ~600 million short URLs per month at peak (2017), with billions of redirects per day. Their architecture: Cassandra for storage (write-heavy sharding), Redis for hot cache, HAProxy for load balancing, custom analytics pipeline. Postgres works fine for smaller-scale internal shorteners (e.g. company-internal go/ links) — reach for Cassandra when you cross ~10k writes/sec sustained.

(e) Quiz + exercise · 10 min

1. Walk through what happens when a user clicks a short URL, from browser to redirect response. Name each hop.
2. Why is hash(url)[:7] a bad choice for generating short codes? Give two specific problems.
3. When would you use HTTP 301 vs 302 for the redirect, and what's the risk of picking wrong?
4. Estimate storage growth for a URL shortener with 100M new links per month, 500 bytes per record, over 5 years.
5. Design a mitigation for cache stampede when a single short URL suddenly goes viral.

Stretch problem (connects to S063 — Databases): In S063 you learned about primary keys, sharding, and index design. For our URL shortener, argue for one concrete sharding strategy in Postgres/Cassandra (choose a shard key, explain the read/write access patterns, and identify the biggest failure mode of your choice). Then argue why the opposite choice would be worse.

Explain-out-loud test

If you can't teach these 3 things to a friend without notes, redo the session:

1. What is Design a URL Shortener? (one sentence, no jargon)
2. When would you use it? (one concrete example)
3. When would you NOT use it? (one anti-pattern)

What comes next

• Next session (S128): Design a Chat System — WebSockets, Delivery, Presence
• Previous (S126): System Design Framework — Reqs, Capacity, HLD, Deep-Dive
• Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: (a) intuition · (b) visual walkthrough · (c) hands-on · (d) production reality · (e) quiz + exercise. Duration: 60 minutes.