A full single-region walk-through — key generation, schema, cache layer, the redirect hot path, and analytics that do not slow the redirect down.
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
| Requirement | Target | Why this number |
|---|---|---|
| Redirect latency | p99 < 50ms at the edge | It's on the critical path of someone else's page load |
| Redirect availability | 99.99% | A dead redirect breaks links already printed, emailed, and posted |
| Creation latency | p99 < 300ms | Interactive but not latency-critical |
| Click-count staleness | Up to 5 minutes | Nobody is making decisions on a per-second click count |
| Durability | A created link is never lost | The URL is in circulation; losing it is unrecoverable |
| Short code length | ≤ 7 characters | Product 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:
- This is an overwhelmingly read-heavy system (100:1). Caching is the primary tool, and the redirect path deserves nearly all the design attention.
- 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.
- 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).
- 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.
aB3xY9znext toaB3xYA0means 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 & RegisterDiscussion
0Join the discussion