Module F-16·24 min read

A full single-region walk-through — key generation, schema, cache layer, the redirect hot path, and analytics that do not slow the redirect down.

Written by Jatin Jain Saraf · Architect of SupraScan

Module F-16 — Capstone: Design a URL Shortener

What this module covers: One complete system, designed end to end, using every tool from Phase 1. A URL shortener looks trivial and isn't — it has a brutally hot read path, a key-generation problem with real trade-offs, an analytics requirement that fights the latency requirement, and an abuse surface. This is a worked design, not an exercise: requirements, estimation, API, key generation with the collision arithmetic done, schema and indexes, the redirect hot path and its cache hierarchy, analytics that don't slow the redirect, abuse prevention, a capacity plan, what breaks first — and an explicit list of what I deliberately did not build, with the signal that would change each decision.


1. Requirements

Following Module F-1: functional requirements are short, non-functional requirements are the design.

Functional (in scope)

  • Submit a long URL, receive a short one.
  • Visiting the short URL redirects to the long one.
  • Optional custom alias (short.ly/spring-sale).
  • Optional expiry.
  • Per-link click analytics: total clicks, plus breakdown by day, referrer, and country.

Explicitly out of scope (this phase)

  • Multi-region deployment (Module A-9).
  • Custom domains per customer.
  • Link editing after creation.
  • Real-time analytics dashboards — daily aggregates are enough.

Writing down what's out is half the value, as Module F-1 argued. "Link editing" in particular has a large hidden cost that we'll see when we get to caching.

Non-functional

RequirementTargetWhy this number
Redirect latencyp99 < 50ms at the edgeIt's on the critical path of someone else's page load
Redirect availability99.99%A dead redirect breaks links already printed, emailed, and posted
Creation latencyp99 < 300msInteractive but not latency-critical
Click-count stalenessUp to 5 minutesNobody is making decisions on a per-second click count
DurabilityA created link is never lostThe URL is in circulation; losing it is unrecoverable
Short code length≤ 7 charactersProduct requirement — it has to be short to be useful

Note the asymmetry that shapes everything: redirects must be fast and always available; creation can be slower; analytics can be stale. Three different requirements on three paths, and conflating them is how you end up making redirects wait for an analytics write.


2. Estimation

Module F-3's four calculations.

Assumption: 100M new links/month, read:write ratio 100:1
 
WRITES
  100M / 2.6M s   =  ~38 creates/s average
  × 5 peak factor =  ~200 creates/s peak      (campaign-driven, so bursty)
 
READS
  10B redirects/month / 2.6M s = ~3,850 redirects/s average
  × 5 peak factor              = ~19,000 redirects/s peak
 
STORAGE (per link row: code 8B, URL ~120B avg, owner 8B, timestamps 16B,
         plus row and index overhead → call it 300B)
  100M × 300B          = 30 GB/month
  5 years              = 1.8 TB logical
  × 3 replicas × 1.5 (index overhead) ≈ 8 TB paid storage
 
BANDWIDTH
  Redirect response is a 301/302 with a Location header: ~500 bytes with headers.
  19,000/s × 500B = ~10 MB/s egress. Trivial.
 
KEYSPACE
  base62, 7 characters = 62⁷ = 3.52 × 10¹² codes
  5 years of usage     = 6 × 10⁹ codes
  Load factor          = 0.17% of the keyspace consumed

Four conclusions land immediately, before any design:

  1. This is an overwhelmingly read-heavy system (100:1). Caching is the primary tool, and the redirect path deserves nearly all the design attention.
  2. The write path is tiny. 200 creates/s at peak is comfortable for a single Postgres primary (Module F-3's anchors). No sharding, no queue for creation.
  3. 19,000 redirects/s is well past one Postgres. With a 95% cache hit rate that's ~950/s reaching the database — fine. The cache is load-bearing, not an optimisation (Module F-12).
  4. 7 characters is plenty of keyspace, using 0.17% in five years. That number matters for the collision analysis next.

3. API

Following Module F-8.

POST /links
  { "url": "https://example.com/very/long/path", "alias": "spring-sale",
    "expires_at": "2027-01-01T00:00:00Z" }
  → 201 { "code": "aB3xY9z", "short_url": "https://short.ly/aB3xY9z" }
  Header: Idempotency-Key: <client-generated UUID>
 
GET  /:code                  → 302 with Location (the hot path)
GET  /api/links/:code        → link metadata (owner only)
GET  /api/links/:code/stats?from=&to=  → aggregated analytics
DELETE /api/links/:code      → soft delete (the code is never reused)

Two decisions worth stating:

Creation takes an idempotency key. It's a POST, so it isn't idempotent by definition (Module F-8), and a client retrying after a timeout must not create a second link. Module P-16 covers the full mechanism; here it's a stored key with the resulting code, returned on a repeat.

Delete is soft, and codes are never reused. A reused code would redirect an old, in-circulation link to a new destination — which is both a broken-link problem and an open-redirect security problem. The keyspace is 3.5 trillion; retirement is free.


4. Key Generation: The Actual Design Problem

Four approaches, each with a real failure mode.

Option A: Hash the URL and truncate

base62(sha256(url))[0..7]. Deterministic, so the same URL yields the same code — which sounds elegant and is usually wrong: two users shortening the same URL then share analytics, and one deleting it affects the other. It also can't support per-user expiry. Rejected on product grounds, before we even discuss collisions.

Option B: Random 7-character base62, with collision detection

Generate randomly, insert, and let a UNIQUE constraint catch collisions. Do the arithmetic rather than hand-waving:

Keyspace N = 3.52 × 10¹²
Codes used n = 6 × 10⁹ (after five years)
Load factor  = n/N = 0.0017
 
Probability that any single insert collides with an existing code ≈ 0.17%
Expected retries per insert                                      ≈ 0.0017

So collisions across the whole corpus are certain — with 6 billion codes drawn from 3.5 trillion slots, the birthday bound puts the expected number of collision events in the millions — but each individual insert has a 0.17% chance of hitting one, which a unique constraint plus a retry handles for essentially free. That's the honest framing: collisions are a normal, handled event, not a rare accident.

Cost, named: every create needs a database round trip to detect the collision, so the write path can't be fully decoupled from the database. At 200 creates/s that's irrelevant.

Option C: A global counter, base62-encoded

Take a monotonically increasing integer and encode it. No collisions ever, and the shortest possible codes early on.

Two serious problems:

  • The counter is a coordination point. A single sequence in one database means every create serialises through it, and it becomes the write bottleneck and a single point of failure. Mitigated by range allocation: each application instance claims a block of 10,000 IDs from a coordination store and hands them out locally, refilling when it runs low. Now creates are local, and a crashed instance just wastes at most 10,000 codes out of 3.5 trillion.
  • Sequential codes are enumerable. aB3xY9z next to aB3xYA0 means anyone can walk the entire corpus, harvesting every shortened link — including private documents people assumed were unlisted. This is a real and repeatedly-exploited class of vulnerability in link shorteners, and it's the same information-leak concern Module P-3 raises about monotonic public IDs.

Option D: Pre-generated key pool

A background job generates random codes, verifies uniqueness, and writes them to a available_codes table. Creation claims one with SELECT ... FOR UPDATE SKIP LOCKED. No collision retries on the hot path, non-enumerable codes, and creation latency is a single indexed read.

Cost, named: another moving part — a generator job to monitor, and a pool that must never run dry. Add an alert on pool depth.

The decision

Option B (random with collision detection) for this design, with a DesignDecision recorded:

const keyGenerationDecision: DesignDecision = {
  decision: 'Random 7-char base62 codes, uniqueness enforced by a DB constraint',
  axis: 'creation volume is low (200/s peak) and codes must not be enumerable',
  chosenBecause: [
    'non-enumerable — no corpus harvesting',
    'no coordination point, no counter to shard or fail over',
    'one moving part fewer than a pre-generated pool',
  ],
  acceptedCost: [
    'each create needs a DB round trip to detect collisions (~0.17% retry rate)',
    'retry rate rises as the keyspace fills — revisit past ~10% load factor',
    'codes are 7 chars from day one, not 1–2 chars as a counter would give',
  ],
  revisitWhen: 'creation exceeds ~5,000/s, or load factor passes 10%',
};

Sign in to keep reading

The rest of this module is free — sign in with Google to unlock it and track your progress.

Sign in & Register

Discussion

0

Join the discussion

Loading comments...