Designing a URL shortener (TinyURL)

The problem

Design a URL shortener (TinyURL, bit.ly): take a long URL, return a short code, and redirect anyone who visits the short link to the original. It’s the canonical opener — small enough to finish, rich enough to show estimation, ID generation, caching, and scale.

Step 1 — Requirements

Functional: create a short URL for a long one; redirect a short URL to its target; optionally custom aliases, expiry, and click analytics.

Non-functional: extremely read-heavy (redirects ≫ creations), low-latency redirects, high availability (a dead shortener breaks every link), unique & short codes, and effectively permanent storage.

Scope cut: core = create + redirect; treat analytics and custom aliases as optional.

Step 2 — Estimate (it drives everything)

• Say 100M creates/day → ~1,150 writes/sec average, a few k peak.
• ~100:1 read:write → ~100k redirects/sec. → redirects must come from cache, never the DB on the hot path.
• ~500 B/record × 100M/day × 5 years ≈ tens of TB → partition the store.
• Code length: base62 (a–zA–Z0–9); 62⁷ ≈ 3.5 trillion codes — 7 chars is plenty. (62⁶ ≈ 56B if you want shorter.)

Step 3 — API and data model

POST /shorten { long_url, [custom_alias], [ttl] } → { short_url }
GET  /{code}  → 301/302 redirect to long_url

Mapping: code (PK), long_url, created_at, owner, expires_at

301 (permanent) caches in browsers and saves a hop but loses click tracking; 302 (temporary) lets you count clicks. State the trade.

Step 4 — The real design question: generating the code

The interesting part. Options:

• Hash the URL (e.g. base62 of MD5, take 7 chars) — simple, but collisions need detection/retry, and identical URLs collapse to one code (sometimes fine).
• Counter + base62 encoding — a global auto-increment encoded to base62 guarantees unique, short, no-collision codes. But a single counter is a bottleneck/SPOF → hand out ranges of IDs to each app server (each gets a block of 1,000 and encodes locally), or use a dedicated ID generator.
• Pre-generated keys (KGS) — a key-generation service pre-computes random unused codes into a DB; servers pull batches. No collisions, no hot counter.
• Snowflake-style IDs — distributed unique IDs (timestamp + machine + seq), base62-encoded; longer codes.

Recommend counter-with-ranges or KGS and explain the bottleneck you’re avoiding.

Step 5 — High-level design

create:   client → LB → app → ID gen (range/KGS) → store mapping (sharded KV) → return code
redirect: client → LB → app → cache(code→long_url)
                                  │ miss → KV store → populate cache → 301/302

Shard the store by code (hash/range); a cache (Redis) absorbs the 100k/sec read load; a CDN/edge can cache hot redirects too.

Step 6 — Custom aliases, expiry, analytics

• Custom alias → check uniqueness; reserve it (it’s just a chosen code).
• Expiry → store expires_at; a background job purges, or check on read.
• Analytics → emit a click event to a queue → async aggregation (don’t slow the redirect).

Trade-offs to raise

• Hashing (simple, collisions) vs counter (unique, hot) vs KGS (clean, extra service).
• 301 (cacheable, fast) vs 302 (trackable).
• Read path is cache-first — the DB is sized for writes + misses, not 100k/sec.

The interview cue

“Read-heavy ~100:1, so cache-first redirects; counter-with-ranges or a KGS for unique short codes (avoiding a hot global counter); sharded KV store; 302 if we want analytics via an async event.” Generating IDs without a bottleneck and serving redirects from cache are the two things this problem is really testing.