Module 02: Designing a URL Shortener

Why this matters

The URL shortener (think bit.ly, TinyURL) is the classic warm-up design problem, and it earns that status honestly: it looks trivial — "just store a mapping and redirect" — but running it through the framework surfaces a surprising density of real distributed-systems concepts in a small, tractable package. You'll confront unique-id generation at scale (how do you mint billions of distinct short codes without collisions and without a central bottleneck?), the archetypal extremely read-heavy workload (redirects vastly outnumber creations, so caching and read replicas dominate the design), storage estimation over years, and a genuine consistency vs. availability decision on the write path.

Because it's small, it's the perfect place to practice the whole framework end to end without drowning in scope — you can actually finish all seven steps. And because every later problem in this track reuses these building blocks (id generation, cache-aside reads, read replicas, key-based partitioning), getting them crisp here pays off everywhere. Treat this module as the reference implementation of "run the framework cleanly on a bounded problem."

Concepts

Requirements and scope

Functional:

• Given a long URL, return a short URL (a short code on your domain, e.g. sho.rt/aB3xK9).
• Given a short URL, redirect to the original long URL.
• (Optional) custom alias chosen by the user.
• (Optional) expiration / TTL on links.

Non-functional (the ones that shape everything):

• Massively read-heavy. Redirects dominate creations — assume ~100:1 read:write. This single NFR pushes the entire design toward caching and read replicas.
• Low-latency redirects. A redirect is on the user's critical path to the destination site; target <100 ms. Users won't tolerate a slow indirection.
• High availability. If the shortener is down, every link everywhere breaks. Redirects especially must stay up — leaning toward availability over strong consistency (recall the CAP tradeoff from 10-distributed-systems- patterns).
• Not-so-strict durability/consistency on creation. It's acceptable if a freshly created link takes a second to be globally visible; it is not acceptable to ever hand out the same short code for two different long URLs.

Out of scope for the warm-up: user accounts, analytics dashboards, spam detection (mention them, defer them).

Capacity estimation

Run the module-00 recipe. Assume 100M new URLs/day.

writes:  100M/day ÷ 10^5 s        = 1,000 writes/sec average
         × 3 peak                 ≈ 3,000 writes/sec peak
reads:   1,000 × 100 (r:w ratio)  = 100,000 reads/sec average
         × 3 peak                 ≈ 300,000 redirects/sec peak

Storage (each row: short code + long URL + metadata ≈ 500 bytes, kept 5 years):

per day    = 100M × 500 B         = 50 GB/day
5 years    = 50 GB × 365 × 5      ≈ 91 TB
× 3 replication                   ≈ ~270 TB

Two conclusions that drive the architecture: (1) 300K reads/sec mandates a cache and read replicas — you will not serve that from a single primary; (2) ~270 TB exceeds one machine, so the key-value store must be partitioned/ sharded. The write rate (3K/sec) is modest and a well-chosen datastore handles it, so writes are not the bottleneck — reads are.

The core problem: short-code generation

The heart of the design is minting a short, unique code for each URL. Codes are base62 ([a-z A-Z 0-9], 62 characters), which is compact and URL-safe. Length math:

62^6 ≈ 5.7 × 10^10  (57 billion)   → 6 chars covers years at 100M/day
62^7 ≈ 3.5 × 10^12                 → 7 chars is very comfortable headroom

So 7 base62 characters gives ample space. Now, how to generate the code — three viable strategies, each with a tradeoff:

1. Counter → base62 (id encoding). Maintain a global monotonically increasing 64-bit counter; each new URL gets the next integer, which you base62-encode into the short code. Pros: guaranteed unique, no collision checks, dense (short codes). Cons: needs a distributed counter without a single bottleneck — solved with a key-generation service or a ranged ticket server (each app server pre-allocates a block of ids, e.g. 1,000 at a time, from a central allocator, so it only talks to the allocator once per thousand URLs). Also, sequential codes are guessable/enumerable — a downside if that matters.
2. Random code + collision check. Generate a random 7-char base62 string, check the datastore for existence, retry on the rare collision. Pros: codes are non-enumerable; no central counter. Cons: an extra read per creation to check uniqueness (cheap at low collision density but not free), and collision probability grows as the space fills.
3. Hash the long URL (e.g. MD5/SHA) → take first N base62 chars. Pros: deterministic (same long URL → same code, which can dedupe). Cons: hash collisions on the truncated prefix must still be handled, and determinism leaks that two people shortened the same URL.

The pre-allocated-block counter approach is usually the strongest default: it removes the central bottleneck (each server hands out codes from its local block) while guaranteeing uniqueness with no collision checks. Each app server leases a block once, then converts local integers to codes with no coordination:

  Allocator          App server A            base62 encode
  (global) ─ lease ─► [1000..1999] ─┐
     │                              ├─ 1001 ──► divmod by 62 ──► "aB3xK9"
     └──── lease ────► App server B │           (7 chars)
                       [2000..2999] ┘
   one round-trip per 1000 URLs; a crash just skips a block (id space is huge)

This is the same "batch to amortize a central coordination cost" idea you'll see again in module 04's key-value store.

The read path: cache-aside and redirects

Redirects are 99% of traffic, so the read path is the system. The flow:

GET /aB3xK9
  → Load Balancer
  → App server
  → check Redis cache for "aB3xK9"     ── hit (common) ──► 301/302 redirect
                                       └─ miss ─► read replica → cache it → redirect

Key design points on the read path:

• Cache-aside (recall 05-caching-and-performance): on a miss, read from the store, populate the cache, then serve. With a 100:1 read ratio and hot links following an 80/20 distribution, cache hit rates are very high, so almost every redirect is served from memory in <1 ms.
• 301 vs. 302. A 301 (permanent) lets browsers and intermediaries cache the redirect, slashing load on your service — but then you lose the ability to track clicks and you can't easily change the target. A 302 (temporary/found) keeps every redirect flowing through your service (so you can count clicks and change targets) at the cost of more traffic. The choice is a real tradeoff tied to whether analytics matter.
• Read replicas + CDN. Behind the cache, replicate the datastore for read scaling; optionally push hot redirects to edge/CDN. Redirects are trivially cacheable because they rarely change.

Data model and partitioning

The data is a simple key-value mapping, so a NoSQL key-value store (or a partitioned SQL table) fits naturally — you only ever look up by short code.

short_code (PK)   long_url        created_at   expires_at   owner_id?
"aB3xK9"          "https://…"     2026-07-24   null         null

• Access pattern: point lookup by short_code on reads; insert on writes. No range scans, no joins. This is the ideal shape for a hash-partitioned KV store.
• Shard key: short_code. Hash-partition on it so lookups go straight to the owning shard, and the ~270 TB spreads evenly across nodes. Because reads are single-key point lookups, sharding adds no scatter-gather cost — every read hits exactly one shard.
• Custom aliases are just user-supplied short_codes; you must check uniqueness on insert (a conditional write) and reject duplicates with 409.
• Expiration is a TTL column; a background cleanup job (recall 06-background-processing-and-realtime) lazily purges expired rows, or you check expires_at on read and treat expired as 404.

Reference architecture

Putting the write path, the read path, and the async analytics pipeline together, the whole shortener looks like this — the hot redirect path is the thick spine, everything else hangs off it:

                          ┌──────────────────┐
   Client ──────────────► │  Load Balancer   │
   (POST create /         └───────┬──────────┘
    GET redirect)                 ▼
                          ┌──────────────────┐
                          │   App servers    │
                          │   (stateless)    │
                          └──┬────────┬───┬──┘
        WRITE path          │        │   │        READ path
   ┌──────────────────┐     │        │   │   ┌──────────────────┐  hit
   │ ID-gen /         │◄────┘        │   └──►│   Redis cache    │─────► 302 redirect
   │ Block allocator  │  lease block │       │  (hot codes,<1ms)│
   │ (counter→base62) │              │       └────────┬─────────┘
   └────────┬─────────┘              │        miss    │  populate on miss
            │ insert                 │               ▼
            ▼                        │      ┌──────────────────────┐
   ┌────────────────────────────────▼──┐   │  Partitioned KV store │
   │     Partitioned KV store          │◄──┤  read replicas        │
   │  (hash by short_code) + replicas  │   └──────────────────────┘
   └───────────────────────────────────┘
            │  redirect handler fires click event (non-blocking)
            ▼
   ┌──────────────────┐    ┌──────────────────┐    ┌──────────────────────┐
   │  Analytics queue │───►│ Analytics workers│───►│ Analytics/time-series │
   │  (async stream)  │    │ (aggregate)      │    │ store  + dashboard    │
   └──────────────────┘    └──────────────────┘    └──────────────────────┘

Component walkthrough:

• Load Balancer — spreads both creates (POST) and redirects (GET) across the stateless app fleet; the read side must absorb the ~300K peak redirects/sec.
• App servers — stateless request handlers. They branch to the write path on create and the read path on redirect; statelessness is what lets you scale them horizontally behind the LB.
• ID-gen / Block allocator — the short-code-generation component. Each app server leases a block of ids from the central allocator once per ~1,000 URLs and base62-encodes them locally, giving unique codes with no per-request bottleneck (the pre-allocated-block strategy from the concepts above).
• Redis cache — the heart of the cache-aside read path. Hot codes (80/20 distribution) serve from memory in <1 ms; on a miss the app reads a replica, populates the cache, then redirects. This is what makes 100:1 read-heavy traffic survivable.
• Partitioned KV store + read replicas — the durable mapping, hash- partitioned by short_code so each point lookup hits exactly one shard (no scatter-gather) and the ~270 TB spreads evenly. Read replicas scale reads; writes insert via put-if-absent to enforce alias uniqueness.
• Analytics queue — the redirect handler fires a click event onto this async stream without blocking the 302, keeping the redirect under 100 ms. This is the fan-out-to-a-queue decoupling that lets analytics lag.
• Analytics workers + store — consume the queue, aggregate click events into a time-series/analytics store, and back the dashboard. The click count is deliberately eventually consistent — seconds of lag is acceptable per the NFRs.

Command reference

The design at a glance — reference numbers, API, and architecture.

Capacity summary (100M new URLs/day assumption):

Core API (a redirect is a plain GET; creation is a POST):

from fastapi import FastAPI, HTTPException
from fastapi.responses import RedirectResponse
from pydantic import BaseModel, HttpUrl

app = FastAPI()

class ShortenRequest(BaseModel):
    long_url: HttpUrl
    custom_alias: str | None = None
    ttl_days: int | None = None

class ShortenResponse(BaseModel):
    short_url: str

@app.post("/api/v1/shorten", response_model=ShortenResponse, status_code=201)
def shorten(req: ShortenRequest):
    code = req.custom_alias or generate_code()   # counter→base62, or random
    if not store.put_if_absent(code, str(req.long_url), req.ttl_days):
        raise HTTPException(409, "alias already taken")   # uniqueness conflict
    return ShortenResponse(short_url=f"https://sho.rt/{code}")

@app.get("/{code}")
def redirect(code: str):
    long_url = cache.get(code) or store.get(code)   # cache-aside
    if long_url is None:
        raise HTTPException(404, "unknown or expired link")
    cache.set(code, long_url)
    return RedirectResponse(long_url, status_code=302)   # 302 to keep click tracking

Base62 encoding of a counter value (strategy 1):

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def base62_encode(n: int) -> str:
    if n == 0:
        return ALPHABET[0]
    out = []
    while n > 0:
        n, rem = divmod(n, 62)
        out.append(ALPHABET[rem])
    return "".join(reversed(out))

High-level architecture:

                        ┌──────────────┐
  Client ─── GET /code ►│ Load Balancer│
                        └──────┬───────┘
                               ▼
                        ┌──────────────┐   hit    ┌──────────┐
                        │ App servers  │ ───────► │  Redis   │  (hot codes, <1ms)
                        │ (stateless)  │ ◄─────── │  cache   │
                        └──────┬───────┘   miss   └──────────┘
             writes (POST)     │  read miss
                               ▼
                     ┌────────────────────┐    ┌───────────────────┐
                     │ Key-Gen / Allocator│    │ Partitioned KV     │
                     │ (block of ids)     │    │ store (hash by     │
                     └────────────────────┘    │ short_code) +      │
                                               │ read replicas      │
                                               └───────────────────┘

Hands-on exercises

Written design exercises — reason on paper, state assumptions and tradeoffs.

1. Size the short code

Assume the service must not run out of codes for 20 years at 100M new URLs/day. Compute total codes needed and the minimum base62 length. Show that 7 characters suffices and by how much headroom. Then argue whether you'd still pick 7 or go to 8, and why.

2. Estimate and conclude

Redo the full capacity estimate for a smaller internal shortener: 1M new URLs/day, 100:1 reads, 5-year retention, 500-byte rows, ×3 replication. Compute write/read QPS (peak) and total storage. Then state the architectural consequence: at this scale, do you still need sharding and read replicas, or would a single primary + one cache suffice? Justify from the numbers.

3. Choose an id-generation strategy

For each of the three strategies (counter→base62, random+check, hash-of-URL), list one scenario where it's the best choice. Then pick a default for a public shortener where codes should be non-enumerable and creation must not hit a central counter on every request, and describe how you'd get both properties.

4. Design the cache-aside read path

Write pseudocode for the redirect handler including: cache check, miss → replica read → cache populate, expired-link handling, and unknown-code 404. Then state your cache eviction policy and TTL, and justify them against the 80/20 hot-link assumption.

5. 301 vs. 302 tradeoff

Your product team wants per-link click analytics and the lowest possible infrastructure cost. Explain why these two goals conflict through the 301/302 choice, and recommend one, stating exactly what you give up.

6. Handle custom aliases and collisions

Describe how you enforce uniqueness for user-chosen custom aliases without a race condition when two users request the same alias simultaneously. Name the specific datastore primitive you'd use (hint: recall conditional writes / put-if-absent and idempotency from 10-distributed-systems-patterns) and the status code you return on conflict.

7. Scale the write path's counter

Your single global counter has become a bottleneck at high write volume. Design the pre-allocated block (ticket) allocator: how big a block each app server grabs, what happens to unused ids when a server crashes, and why this is acceptable. Estimate how much you reduce load on the central allocator with a block size of 1,000.

8. Diagnose and fix a flawed design

Critique this proposed design and fix every flaw.

"Every redirect does a SELECT * FROM urls WHERE long_url = ? on the primary Postgres database to find the short code — wait, no, to find the long URL from the short code, so WHERE short_code = ?. There's one Postgres instance, no cache, and no replicas. Short codes are generated by SELECT MAX(id)+1 FROM urls on each insert. We use a 301 permanent redirect and also want to show users a live click counter on their dashboard."

Independent challenge

No solution given. Extend the shortener into a link-analytics platform: on top of redirects, capture per-link click events (timestamp, coarse geo, referrer, device) and serve a dashboard showing click counts over time — without slowing the redirect down. Design the ingestion and aggregation path end to end, and be explicit about where you accept eventual consistency. Lean on the async processing patterns from 06-background-processing-and-realtime: the redirect must stay <100 ms, so the click event cannot be written synchronously to an analytics store on the hot path.

Common mistakes & troubleshooting

• No cache on a read-heavy system. The defining mistake here. 100:1 reads means the cache is the design; serving redirects from the primary DB doesn't scale.
• SELECT MAX(id)+1 (or any read-then-write) for id generation. A race condition and a serialization bottleneck. Use an atomic sequence or block allocator.
• Ignoring the 301/302 tradeoff. Picking 301 for "performance" then being unable to count clicks, or 302 without realizing you've forgone browser-side caching. Tie the choice to whether analytics matter.
• Over-long or over-short codes. Guessing a length instead of computing it from base62ⁿ vs. required capacity. Do the math: 7 chars ≈ 3.5×10¹², plenty.
• Modeling a pure point-lookup as a relational scan. Access is by key only; reaching for joins/scans on a single relational box misses the natural KV/ hash-partition fit.
• Forgetting expiration cleanup. TTL'd links pile up forever without a purge strategy (lazy on-read, or a background sweeper).
• Central counter as a single point of failure/bottleneck. A naive global counter serializes all writes; batch it with block pre-allocation.

Checkpoint quiz

Write down your answer to each question before expanding it — checking without attempting first is the single easiest way to fool yourself into thinking you've learned this.

1. Why is a URL shortener overwhelmingly read-heavy, and what two architectural components does that single fact force into the design?
2. How many base62 characters do you need to comfortably cover 100M new URLs/day for years, and how did you arrive at that length?
3. Compare the three short-code generation strategies (counter→base62, random+check, hash-of-URL). Which gives non-enumerable codes, and which avoids a per-creation uniqueness read?
4. Explain the block/ticket allocator: what problem it solves and why it's acceptable to lose a few ids when a server crashes.
5. What's the concrete tradeoff between a 301 and a 302 redirect, and which do you pick if click analytics are required?
6. Why is short_code the natural shard key, and why does sharding on it add no scatter-gather penalty to reads?
7. Two users request the same custom alias at the same instant. What primitive prevents a double-assignment, and what do you return to the loser?

Further reading & sources

• System Design Primer — Designing a URL shortener (Pastebin) - a full worked design of the same warm-up problem, covering id generation, read-heavy caching, and storage estimation.
• Base62 / positional numeral encoding - the URL-safe alphabet and encoding math behind mapping an integer counter to a short code.
• 301 vs 302 redirects (MDN HTTP redirections) - the authoritative reference for permanent vs. temporary redirects and how each interacts with browser caching and click tracking.
• Instagram Engineering — Sharding & IDs at Instagram - how a real service mints unique, roughly-ordered IDs at scale without a single central counter bottleneck.
• How bit.ly serves billions of redirects (High Scalability) - a real-world look at the read-heavy, cache-dominated architecture this module models.

Next

03-designing-a-rate-limiter — you've run the framework on a read-heavy storage problem; next you'll design a rate limiter, which flips the focus to write-path enforcement, distributed counter state, and precise algorithm tradeoffs (token bucket, sliding window). It also carries the track's first cumulative review, mixing everything from modules 00–03.