system_design / worked designs / 01_url_shortener.md

Worked Design — URL Shortener

5 interview angles 5 min read source

Worked Design — URL Shortener

The “warm-up” system design question. It looks trivial; the depth is in code generation, the read path at scale, and analytics. Stack assumption: FastAPI + Postgres + Redis + AWS.

1. Requirements

Functional: create a short code for a long URL; redirect a short code to its long URL; optional custom alias; optional click analytics.

Non-functional: redirects must be fast (p99 < 50 ms) and highly available — a dead redirect breaks every link ever shared. Creation can be slower. Read-heavy.

Scope cuts: no user accounts in v1, no link editing, analytics is async/best-effort.

2. Scale

(See ../06_design_framework/02_capacity_estimation.md for the full arithmetic.)

100M new URLs/month → ~40 writes/sec avg, ~100 peak
10:1 read:write     → ~400 reads/sec avg, ~1,000 peak
storage over 5y     → ~3 TB

The key insight to state: write QPS is low — a single Postgres primary handles it easily. Reads are 1k peak — a cache absorbs nearly all of them. Nothing here forces sharding. The whole problem is “make a KV lookup fast and never down.”

3. API

POST /urls          { long_url, custom_alias? }   → { short_code, short_url }
GET  /{short_code}                                → 302 redirect to long_url
GET  /urls/{short_code}/stats                     → { clicks, created_at }

4. Data model

Single table, Postgres:

CREATE TABLE urls (
    short_code  TEXT PRIMARY KEY,
    long_url    TEXT NOT NULL,
    created_at  TIMESTAMPTZ DEFAULT now(),
    created_by  BIGINT,           -- nullable in v1
    click_count BIGINT DEFAULT 0  -- updated async, approximate
);

Access patterns: lookup by short_code (the hot path — primary key, O(1)), insert on create. That’s it. A KV store (DynamoDB) would also fit perfectly — pick Postgres for v1 simplicity, note DynamoDB is the natural choice if this needs to scale past one primary.

5. Short-code generation — the actual interesting part

Three approaches:

Option A — hash the URL, take a prefix

base62(md5(long_url))[:7]. Deterministic (same URL → same code, free dedup) but collision-prone — different URLs can hash to the same prefix. You’d need a collision check + retry. Workable but fiddly.

Option B — random code, check-and-retry

Generate 7 random base62 chars, INSERT ... ON CONFLICT DO NOTHING, retry on collision. 62⁷ ≈ 3.5 trillion codes — collisions are rare until the space fills. Simple, no coordination. Good default.

Option C — counter + base62 encode

A global auto-incrementing counter; base62(counter) is the code. Zero collisions, codes are short and grow predictably. The catch: a single counter is a coordination point. Solve it with a range-allocation scheme — each app instance grabs a block of 1,000 IDs from a central counter (or a DB sequence) and hands them out locally; refill when the block runs low. No per-request coordination.

# Option C with range allocation
class CodeAllocator:
    def __init__(self):
        self._next = 0
        self._end = 0
    def next_code(self) -> str:
        if self._next >= self._end:
            self._next, self._end = self._reserve_block(1000)  # one DB round-trip per 1000 codes
        code = base62_encode(self._next)
        self._next += 1
        return code

State the trade-off: B is simplest and fine at this scale; C gives shortest codes and zero collisions at the cost of the allocation scheme. Custom aliases are just a normal insert with a uniqueness check, on either path.

6. Architecture — the read path is everything

                 ┌── cache hit (99%+) ──────────────► 302
Client ─► CDN ─► API server ─► Redis ─┤
                                      └── miss ─► Postgres ─► (populate cache) ─► 302
  • Redirects are cache-first. short_code → long_url is immutable once created, so it’s the ideal cache entry — no invalidation problem, just a TTL or LRU eviction. Hit rate will be very high.
  • CDN can even cache the 302 itself for the hottest links — though be careful, a 302 cached at the edge is hard to ever change.
  • Postgres is the source of truth; reads only hit it on a cache miss (cold or evicted code).
  • Stateless API servers behind a load balancer — scale horizontally trivially.

7. Analytics — keep it off the hot path

Incrementing click_count synchronously on every redirect adds a DB write to the read path — don’t. Instead:

redirect → emit click event → SQS / Kafka → worker → batch-update counts in Postgres

The redirect returns immediately after the cache lookup; the click event is fire-and-forget. Counts are approximate and eventually consistent — which the requirements said is fine. For richer analytics (referrer, geo, time series), the worker writes to a separate analytics store (or just S3 + Athena).

8. Bottlenecks & trade-offs

  • At 100× scale (100k redirect QPS): the cache is still the answer, but now it’s a Redis cluster; Postgres becomes a read-replica fleet or you migrate the KV lookup to DynamoDB (no connection limits, scales flat).
  • Hot link — one viral URL: the cache handles it (single key, every server caches it); no hot-partition problem because it’s read-only.
  • Cache down — every redirect falls through to Postgres. At 1k QPS Postgres survives it; at 100k it wouldn’t — so at large scale you need the cache to be HA (multi-AZ Redis) and Postgres to have read-replica headroom.
  • Custom alias collisions — handled by the uniqueness constraint; return a clear 409.
  • The 302-vs-301 choice — 301 (permanent) lets browsers cache the redirect forever, slashing your traffic — but then you can never change or measure that link. 302 (temporary) keeps every click coming to you (needed for analytics) at the cost of more traffic. State the trade; 302 is usual for a service that wants analytics.

Interview angle

  • “How do you generate short codes?” — random base62 + insert-on-conflict-retry is the simple default (62⁷ ≈ 3.5T space). Counter + base62 gives shorter, collision-free codes but needs a range-allocation scheme so the counter isn’t a per-request coordination point. Hashing the URL gives free dedup but is collision-prone.
  • “Why is this read-heavy problem easy?” — the mapping is immutable, so it’s a perfect cache entry with no invalidation problem. A very high cache hit rate means Postgres barely sees the read traffic; the write QPS is low enough for a single primary.
  • “How do you handle click analytics without slowing redirects?” — emit the click as a fire-and-forget event to a queue; a worker batch-updates approximate counts. The redirect path stays cache-lookup-only. Requirements allow eventual, approximate counts.
  • “301 vs 302 for the redirect?” — 301 is cacheable by the browser forever (less traffic, but you lose control and analytics); 302 keeps every click coming to you. Use 302 when you need analytics or the ability to change/expire links.
  • “What breaks at 100× scale?” — single Redis node and single Postgres primary. Fix: Redis cluster, and either a Postgres read-replica fleet or move the KV lookup to DynamoDB which scales flat with no connection ceiling.