Design a URL Shortener

Design a URL Shortener — the 45-minute interview walkthrough

This lesson is the interview version of the URL shortener (bit.ly, TinyURL): how to pace the conversation and which deep dives to prepare. The full reference design is the case study Design a URL Shortener in this chapter.

It looks trivial ("map a short code to a long URL"), which is exactly why interviewers use it. The interesting parts are generating unique short codes at scale without collisions or coordination bottlenecks, serving an extremely read-heavy redirect path with very low latency, and handling abuse and analytics without slowing redirects down.

Minutes 0–5: clarify requirements

• Core: create a short link for a long URL; visiting the short link redirects to the original.
• Optional: custom aliases (sho.rt/summer-sale), expiry, click analytics, user accounts to manage links.
• Scale assumptions: ~100M new links/day (~1,200 writes/s average) and ~10B redirects/day (~115,000 reads/s average, several times that at peak). Reads outnumber writes about 100:1.
• Latency: redirects in single-digit to low tens of milliseconds.
• Availability: very high. A broken shortener breaks every link that was ever shared.
• Links are effectively immutable once created, which makes caching straightforward.

Code length: Base62 (a–z A–Z 0–9) with 7 characters gives 62⁷ ≈ 3.5 trillion codes. At 100M/day that lasts about 95 years, so 7 characters is enough.

Storage: 100M/day × 365 × ~500 bytes ≈ 18 TB/year. That's large but ordinary for a horizontally scaled key-value store.

Minutes 5–15: high-level design

 create:   client ─▶ API ─▶ ID generator ─▶ Base62 encode ─▶ store {code → longUrl, owner, expiry}
 redirect: client ─▶ edge/CDN ─▶ redirect service ─▶ cache (Redis) ─miss─▶ key-value store
                                        │
                                        └─ click event ─▶ queue ─▶ analytics pipeline

• Write path: validate the URL, get a unique code, persist it, return the short URL.
• Read path: look up the code (cache first), return an HTTP redirect, and emit a click event asynchronously.
• Storage: a key-value or wide-column store keyed by short code (DynamoDB, Cassandra) fits, since every access is a lookup by key. A relational database also works at moderate scale.

Minutes 15–35: deep dives

1. Generating short codes

Option A: hash the URL and truncate. Take MD5 or SHA-256 of the long URL, Base62-encode it, and keep 7 characters.

• ✅ The same URL always gives the same code (natural deduplication).
• ❌ Truncation causes collisions, so each insert must check and retry with a salt. That's an extra read per write, and races between concurrent writers still need a conditional insert.

Option B: unique counter + Base62 (preferred). Give each link a unique integer ID and Base62-encode it.

• ✅ No collisions by construction.
• ❌ A single global counter is a bottleneck and a single point of failure. Sequential codes are also guessable: anyone can enumerate links.

Making option B scale:

• Range allocation: a coordination service (ZooKeeper, or a database row updated atomically) hands each app server a block of, say, 1 million IDs. Servers allocate from memory and only coordinate when a block runs out. A crashed server wastes the rest of its block, which is harmless.
• Snowflake-style IDs: timestamp + machine ID + sequence, generated without coordination. They're longer than 7 Base62 characters, though.
• Avoiding guessability: pass the counter through a reversible bit-shuffling permutation or a small block cipher before encoding. Codes stay unique, but no longer look sequential.

Custom aliases go into the same keyspace, with a conditional insert ("create only if absent") to reject duplicates atomically.

2. The redirect path

• 301 (permanent) vs 302 (temporary): browsers cache a 301, which reduces load but means later clicks never reach you, so no analytics, and no way to change or disable the link. Most commercial shorteners use 302 (or 307) for control and analytics. Mention this trade-off explicitly.
• Caching: link popularity is highly skewed, so a Redis cache with LRU eviction in front of the store absorbs most reads. Links are immutable, which makes invalidation rare (only on deletion or disabling).
• Edge caching: very hot links can be served from CDN edge logic.
• Negative caching: cache "not found" briefly, so scanners probing random codes don't hammer the database.

3. Analytics without slowing redirects

Never write analytics synchronously on the redirect path. Emit a small event (code, timestamp, referrer, coarse location, user agent) to a queue such as Kafka. Stream processors aggregate counts per link, per time bucket and per country into an analytics store. Exact real-time counts aren't needed.

4. Abuse, expiry and cleanup

• Abuse: check submitted URLs against malware and phishing lists, rate-limit creation per user or IP, and be able to disable a code (which is another reason to prefer 302).
• Expiry: store expiresAt, check it on read, and delete lazily or with a background sweeper. Most teams don't reuse expired codes, because old shared links would suddenly point somewhere new.

Minutes 35–45: trade-offs and wrap-up

• Hash vs counter: a counter with range allocation avoids collisions. Hashing gives deduplication. You can add deduplication separately with a longUrl→code index if needed.
• 302 vs 301: control and analytics vs lower load.
• Store choice: a key-value store matches the access pattern and scales horizontally.
• With more time: multi-region replication (reads served locally, writes in one region or with partitioned ID ranges per region), link previews, QR codes, per-user dashboards.

Common mistakes in interviews

• Hash-and-truncate with no collision handling.
• A single auto-increment database counter with no discussion of the bottleneck or guessability.
• Writing click analytics synchronously on the redirect path.
• Using 301 without realizing that it kills analytics and link control.

Follow-up questions this topic invites — and their answers

Q: How do you prevent two servers from issuing the same code? A: Give each server a disjoint ID range from a coordinator, so uniqueness holds by construction. For custom aliases, rely on a conditional put in the store, which fails if the key exists.

Q: Should the same long URL always return the same short code? A: It's a product decision. Deduplication saves storage, but breaks per-user analytics and ownership, since two users would share one link. Many services create a new code per request, or deduplicate per user through a secondary index on (user, longUrl).

Q: How would you handle 1 million redirects per second for one viral link? A: That one key is a hot key. Serve it from CDN or edge caching, or from an in-process cache on each redirect server, so the load never concentrates on a single cache shard.

Q: How do you make codes non-guessable? A: Apply a reversible permutation (a bit-mix or a format-preserving cipher) to the sequential ID before Base62 encoding, or generate random codes with a conditional insert and retry on the rare collision. Private links can also use longer codes.

Q: What database would you pick and why? A: A horizontally scalable key-value or wide-column store, because every access is a point lookup by code, the data is immutable, and the volume grows steadily. Relational databases are fine at smaller scales, especially if you need rich per-user queries, which can live in a separate store.