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.
Why does this matter so much? Because every number above is a design decision in disguise. 40 writes/sec is trivial — almost any single database handles that. 4,000 reads/sec, though, is where a naive "hit the database every time" design starts to sweat, which is exactly why the next few steps revolve around a cache.
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 │
└──────────┴───────────────┴────────────┴─────────┘
Why not a full ORM-style schema with users, folders, tags? Because the requirement was "shorten + redirect." One table with a primary-key lookup is all step 3 needs — resist the urge to model features you scoped out in step 1.
Step 4 — High-Level Design
Before the diagram, here's the plain-English version: a write (shortening a URL) goes straight to the database, since it's rare and doesn't need to be fast. A read (a redirect) is the hot path — it checks the cache first, and only falls back to the database on a miss.
[ 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 ] ◀────────────────────┘
Walking the redirect (the request that happens 4,000 times a second, so it's the one that must be fast):
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.
Why not skip the cache and just add more database replicas? You could — read replicas alone would handle plenty of load. But a cache hit costs roughly a millisecond versus several milliseconds for even a fast replica read, and it takes that load off the database entirely rather than just spreading it across more copies. At 4,000 reads/sec, a 99% cache hit rate means the database only ever sees about 40 queries/sec — the same order of magnitude as the writes. Cache first, replicas as backup — not replicas instead of a cache.
Step 5 — Deep Dive: Generating the Short ID
This is the heart of the problem. How do we make a short, unique ID? There are three real options, and interviewers want to hear you compare them, not just name your favorite.
5.1 Hash the Long URL (e.g. MD5), Take a Prefix
Run the long URL through a hash function like MD5, then keep the first 7 characters as the short ID.
longUrl = "https://a-very-long-url.com/xyz?a=1&b=2" md5(longUrl) = "3f2a9b8e1c7d..." → take first 7 → "3f2a9b8"
✅ PROS Stateless — no shared counter, no coordination needed.
Simple to implement.
❌ CONS Collisions ARE possible (two different URLs can hash
to the same 7-char prefix — with enough URLs this
will happen, and you need a fallback).
The same URL always maps to the same short ID, so
you can't shorten the same link twice with different
expiries.
👉 USE IT WHEN You want a stateless generator and can tolerate
handling occasional collisions with a retry.
5.2 Random 7-Character Base62 String
Generate 7 random characters from the base62 alphabet (a–z, A–Z, 0–9) and use that directly as the short ID.
62 symbols ^ 7 characters ≈ 3.5 trillion possible IDs req 1 → generate → "kQ3mZ9x" → check DB for collision → save
✅ PROS Simple, unguessable, huge ID space (3.5 trillion).
❌ CONS Must query the database to check "does this ID already
exist?" before saving — an extra read on every write,
and on the rare collision, a retry with a new string.
👉 USE IT WHEN Writes are infrequent enough that the extra
collision-check query per write is a non-issue
(true here — only 40 writes/sec).
5.3 Counter + Base62 Encoding ⭐ (the pick)
Keep one global, ever-increasing counter: 1, 2, 3... Encode each number into base62 to get the short ID.
count 125 → base62 encode → "cb" count 1,000,000 → base62 encode → "4c92" count 3,500,000,000,000 → base62 encode → 7 chars, still fits BASE62 refresher: 26 lower + 26 upper + 10 digits = 62 symbols. 7 characters → 62^7 ≈ 3.5 trillion URLs. Way more than the 6 billion we estimated needing over 5 years. ✅
✅ PROS GUARANTEED unique — no collision checks, no retries.
IDs start short (2 chars) and grow slowly over time.
❌ CONS Sequential and guessable (someone could enumerate
"aa", "ab", "ac"...). The counter itself needs to be
coordinated so two servers never hand out the same number.
👉 USE IT WHEN You want the simplest, cheapest-per-write option
and can live with (or explicitly mitigate)
sequential IDs.
Scaling the counter so it isn't a bottleneck: don't make every app server ask one shared counter for every single request — that's a hot lock. Instead, hand each app server a range of numbers to burn through locally (server A: 1–1,000,000, server B: 1,000,000–2,000,000, ...). A service like a "ticket server," or simply Redis INCR handing out ranges, keeps this coordination cheap and rare instead of per-request.
Visual Comparison
| Option | Collision risk? | Extra DB read on write? | Guessable? | Best for |
|---|---|---|---|---|
| Hash + prefix | ❌ Yes (rare) | ❌ Needs retry logic | ✅ No | Stateless generators |
| Random base62 | ❌ Yes (very rare) | ❌ Yes, to check | ✅ No | Simple setups, low write volume |
| Counter + base62 | ✅ Never | ✅ No | ❌ Yes (sequential) | Guaranteed uniqueness, our pick |
Why the counter wins here specifically: at only 40 writes/sec, none of the three options would struggle under load. The counter wins because it's the only one with zero collision handling — one less failure mode to design around and explain in an interview. If "unguessable IDs" were a hard requirement instead of a nice-to-have, random base62 would be the better trade.
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 not just hash the URL instead of using a counter?
"Hashing is stateless, which is appealing, but two different URLs can hash to the same short prefix, so you need collision-handling logic anyway. The counter has zero collision risk by construction — it simply never repeats a number — which removes an entire failure mode I'd otherwise have to test and explain. The trade-off is the counter needs coordination across servers, which I solve with range allocation rather than a shared lock."
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 — our 5-year estimate was around 6 billion URLs — so a 7-character ID is a safe choice with huge headroom."
Q: How do you make redirects fast?
"Since the system is heavily read-dominated — about 4,000 reads a second against 40 writes a second — 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 — we estimated about 3TB over 5 years — 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 (~4,000 reads/sec vs ~40 writes/sec) → cache aggressively + read replicas. |
| ID generation | Counter + base62 = guaranteed unique, short, no collision checks. 7 chars ≈ 3.5 trillion. |
| Why counter over hash/random | Zero collision handling — one less failure mode to design and defend. |
| Hot path | Redirect = Redis lookup → 302. ~99% cache hits → ~1ms, 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