Chapter 14: Worked Example: URL Shortener

Why this matters

The URL shortener is one of the most commonly assigned system design prompts, specifically because it's small enough to complete in the framework's full five steps within a reasonable time, while still touching caching, database selection, ID generation, and a genuine read/write asymmetry worth reasoning about explicitly.

Step 1: Clarify requirements

Clarifying questions a strong candidate asks: "Should short codes be predictable/sequential, or does it matter if they're guessable? Do we need custom aliases (user-chosen codes), or only system-generated ones? Do links expire? What's the expected scale?"

Assumed answers for this worked example: codes should not be easily guessable (to avoid enumeration); custom aliases are a nice-to-have, not core; links can optionally expire; scale is large (assume ~100M URLs created per year, reads far outnumbering writes).

Step 2: Estimate scale

URL creations: ~100M/year -> ~275,000/day -> ~3.2 creates/second (average)
Reads (resolving a short URL): assume a 100:1 read/write ratio for a
   typical URL shortener (heavily read-skewed) -> ~320 reads/second (average)
   -> with a 3x peak factor (Chapter 4): ~960 reads/second (peak)

Storage: each record ~500 bytes (short code, long URL, metadata) x 100M/year
   = 50GB/year -> over 5 years, 250GB -- comfortably within a single
   well-provisioned database's capacity; SHARDING IS NOT justified by
   this estimate (directly Chapter 7's "don't reach for sharding
   prematurely" lesson).

Step 3: Sketch a high-level design

Client --> Load Balancer --> Application Service
                                   |
                    +--------------+--------------+
                    v                              v
              Cache (Redis)                  Database (PostgreSQL)
         (hot short codes, since       (source of truth: short_code,
          reads vastly outnumber        long_url, created_at, expires_at)
          writes -- Chapter 5)

Write path: generate a short code -> write to database -> (optionally
            populate cache proactively)
Read path: check cache first -> on hit, redirect immediately -> on miss,
           query database, populate cache, then redirect

Step 4: Deep-dive — the hardest part: generating unique short codes at scale

Why this is the hardest part: "The trickiest part of this design isn't the caching or the database — it's generating short, unique codes without collisions, at scale, without a bottleneck."

Option A — random generation with collision checking: generate a random 7-character code, check if it already exists, retry on collision. Simple, but requires a database round-trip per attempt, and collision probability rises as the namespace fills up.

Option B — a counter-based approach with base62 encoding: maintain a globally unique, monotonically increasing counter (e.g., via a dedicated ID-generation service or a database sequence), and encode each counter value in base62 (a-z, A-Z, 0-9) to produce a short, guaranteed-unique code with no collision checking needed at all.

import string

BASE62 = string.digits + string.ascii_lowercase + string.ascii_uppercase

def encode_base62(number: int) -> str:
    if number == 0:
        return BASE62[0]
    result = []
    base = len(BASE62)
    while number > 0:
        number, remainder = divmod(number, base)
        result.append(BASE62[remainder])
    return "".join(reversed(result))

# Counter value 125 -> a short, guaranteed-unique base62 code
# 7 base62 characters can represent 62^7 ≈ 3.5 TRILLION unique codes --
# comfortably more than enough for the estimated 100M/year x many years.

The chosen approach, with reasoning stated explicitly: "I'd choose the counter-based approach specifically because it eliminates collision-checking entirely — Option A's retry-on-collision approach adds unpredictable latency and database load that grows worse as the namespace fills, while Option B guarantees uniqueness structurally. The trade-off: a centralized counter can become a bottleneck at very high write scale, or a single point of failure — I'd mitigate this by partitioning the counter (e.g., each application server pre-allocates a batch of counter values) rather than a single, globally-serialized counter for every single write."

Step 5: Discuss trade-offs and failure modes

"If read traffic were 100x higher than estimated, I'd add more cache capacity and potentially read replicas (Chapter 7) before considering anything more drastic. If the cache goes down entirely, the system degrades to hitting the database directly for every read — slower, but still functionally correct (graceful degradation, Chapter 12), not a full outage. I explicitly chose not to shard the database, since the estimated data volume doesn't justify that complexity yet — I'd revisit this if actual usage significantly exceeds this estimate."

Common mistakes

1. Jumping straight to "I'll use a hash function for the short code" without considering collision handling explicitly — hash-based approaches still need a strategy for the (rare, but real) collision case.
2. Not recognizing the read-heavy nature of this system early, missing the chance to justify caching investment (Chapter 5) with the actual read/write ratio.
3. Proposing database sharding without connecting it to the actual estimated data volume, which in this worked example doesn't come close to justifying it — exactly Chapter 7's premature-complexity warning.
4. Treating "generate a unique code" as a trivial detail rather than recognizing it as this specific system's genuinely interesting, worth-deep-diving problem.

Chapter summary / cheat sheet

• URL shortener: heavily read-skewed (favors caching investment), moderate write volume, moderate data volume (doesn't justify sharding at typical assumed scale).
• The genuinely hard part: generating unique short codes at scale — counter-based base62 encoding (structural uniqueness, no collision checking) generally beats random-generation-with-retry (unpredictable latency, worsens as namespace fills).
• Cache-aside (Chapter 5) fits this system's access pattern well; graceful degradation to direct database reads on cache failure keeps the system functional, just slower.
• This worked example demonstrates Chapter 13's full five-step framework concretely, including explicitly identifying and deep-diving the hardest component rather than spreading equal attention everywhere.

---