Chapter 18 — Design a URL Shortener (TinyURL)
Chapter 18 — Design a URL Shortener (TinyURL)
Hey everyone! Welcome back to Namaste System Design! 🙏
This is the classic warm-up interview question — if you can only prepare one, prepare this. It's simple enough to finish in 45 minutes but touches every core concept: hashing, caching, read-heavy scaling, and databases. We'll walk the exact 6-step framework from Chapter 17. Grab a pen and follow along.
GOAL: turn https://a-very-long-url.com/xyz?a=1&b=2
into https://short.ly/aX9bK2 (and redirect back)
Step 1 — Clarify Requirements
FUNCTIONAL: ✔ Shorten a long URL → short URL ✔ Redirect short URL → original long URL ✔ (optional) custom aliases, expiry, click analytics NON-FUNCTIONAL: ✔ VERY read-heavy (redirects ≫ new links, ~100:1) ✔ Low latency redirects (feels instant) ✔ Highly available (a dead redirect = broken links everywhere) ✔ Short IDs, not guessable-sequential (nice to have) SCOPE (state it): "I'll focus on shorten + redirect, optimize for fast reads and high availability, skip analytics."
Step 2 — Estimate Scale
Assume 100M new URLs / month
→ 100M / (30×24×3600) ≈ ~40 writes/sec
Reads at 100:1 → ~4,000 reads/sec (READ-HEAVY confirmed)
Storage: each row ~500 bytes
100M/month × 12 × 5 years ≈ 6 billion URLs × 500B ≈ 3 TB
Takeaway: reads dominate → CACHE hard + read replicas.
3TB fits one big DB for now; plan sharding for later.
Step 3 — APIs & Data Model
POST /shorten body: { longUrl } → { shortUrl }
GET /{shortId} → 302 redirect to longUrl
Table: urls
┌──────────┬───────────────┬────────────┬─────────┐
│ short_id │ long_url │ created_at │ expiry │
│ (PK) │ │ │ │
├──────────┼───────────────┼────────────┼─────────┤
│ aX9bK2 │ https://... │ 2026-07-08 │ null │
└──────────┴───────────────┴────────────┴─────────┘
Step 4 — High-Level Design
[ Client ]
│
[ Load Balancer ]
│
[ App Servers (stateless) ]
│ │
WRITE path ────┘ └──── READ path
│ │
▼ 1. check [ Redis cache ]
generate short_id │ HIT → redirect ⚡
store in DB │ MISS ↓
│ 2. read [ DB (+replicas) ]
▼ │ fill cache, redirect
[ Database ] ◀────────────────────┘
REDIRECT FLOW (the hot path — must be fast): 1. GET /aX9bK2 hits an app server 2. Look up "aX9bK2" in Redis → HIT ⚡ → 302 redirect (done) 3. MISS → read from DB → store in Redis → 302 redirect Because it's read-heavy, ~99% are cache hits. Blazing fast.
Step 5 — Deep Dive: Generating the Short ID
This is the heart of the problem. How do we make a short, unique ID?
OPTION A — Hash the long URL (e.g. MD5), take first 7 chars
+ stateless, simple
− COLLISIONS possible (two URLs → same prefix); same URL
always maps same → can't have two different expiries
OPTION B — Random 7-char base62 string [a-zA-Z0-9]
62^7 ≈ 3.5 TRILLION combos → huge space
+ simple, unguessable
− must check DB for collision (rare) and retry
OPTION C — Counter + base62 encode ⭐ (my pick)
Keep a global counter: 1, 2, 3... encode number → base62
count 125 → "cb", count 1,000,000 → "4c92"
+ GUARANTEED unique (no collision checks)
+ short & grows slowly
− sequential/guessable; the counter needs coordination
BASE62 refresher: 26 lower + 26 upper + 10 digits = 62 symbols 7 chars → 62^7 ≈ 3.5 trillion URLs. More than enough. ✅ SCALING THE COUNTER (so it's not a single bottleneck): Use a service like a "ticket server" (e.g. Redis INCR) or hand each app server a RANGE of numbers to use (server A: 1–1M, server B: 1M–2M) so they never collide and don't coordinate per-request.
Step 6 — Bottlenecks & Trade-offs
⚠ DB read load → solved by Redis cache (~99% hit rate)
⚠ DB write/size → shard by short_id hash when 3TB grows
⚠ Cache is a SPOF → run a Redis cluster with replicas
⚠ Counter SPOF → range-allocation per server / Redis cluster
⚠ Hot links go → CDN / edge cache the 302 for viral URLs
viral
⚠ Availability → multi-region read replicas so redirects
work even if one region is down
Nice extensions to mention: custom aliases (check the alias is free before inserting), expiry (a background job or TTL removes old links), analytics (fire a click event onto a message queue — Chapter 10 — so counting never slows the redirect).
Interview Questions — Quick Fire!
Q: How do you generate the short URL?
"My preferred approach is a global counter encoded in base62. Each new URL gets the next number, which I encode using 62 characters — lowercase, uppercase, and digits — producing a short, guaranteed-unique ID with no collision checks. Alternatives are hashing the long URL and taking a prefix, which risks collisions, or generating a random base62 string and checking for collisions. To scale the counter, I hand each server a range of numbers so they don't coordinate on every request."
Q: Why base62 and how long should the ID be?
"Base62 uses all alphanumeric characters, so it packs more values into fewer characters than base10 — keeping URLs short and readable. Seven base62 characters give about 3.5 trillion combinations, which is far more than we'd ever need, so a 7-character ID is a safe choice."
Q: How do you make redirects fast?
"Since the system is heavily read-dominated, I put a Redis cache in front of the database keyed by short ID. Most redirects are cache hits served in about a millisecond. On a miss, I read from the database, populate the cache, and redirect. I'd also use read replicas and possibly edge caching for viral links to keep latency low and availability high."
Q: How would you scale the database as it grows?
"First, read replicas to handle the heavy read load. As storage grows past what one machine holds, I'd shard by a hash of the short ID so lookups by short ID hit a single shard. Since the main query is a direct key lookup, sharding by short ID keeps every read on one shard, avoiding expensive cross-shard queries."
Q: How would you add click analytics without slowing redirects?
"I'd keep the redirect path minimal and fire a click event onto a message queue asynchronously. A separate consumer aggregates the analytics in the background, so counting clicks never adds latency to the redirect itself."
Key Points to Remember
| Concept | Key Takeaway |
|---|---|
| Nature | Extremely read-heavy → cache aggressively + read replicas. |
| ID generation | Counter + base62 = guaranteed unique, short. 7 chars ≈ 3.5 trillion. |
| Hot path | Redirect = Redis lookup → 302. ~99% cache hits → instant. |
| Scaling | Read replicas → shard by short_id hash → keeps lookups on one shard. |
| Extras | Analytics via async queue; expiry via TTL/job; CDN for viral links. |
What's Next?
Warm-up done! Chapter 19 steps up to a much richer problem: Design a News Feed (Instagram/Twitter). We'll tackle the famous fan-out problem and the celebrity headache.
Keep designing, keep scaling! See you in the next one!
Post a Comment