System Design Interviews, Step by Step · Classic Walkthroughs, Part 1
Design a URL Shortener
The classic warm-up: turn long links into short codes and redirect fast. Covers code generation (counter + base62 vs hashing), a read-heavy cache design, and analytics without slowing redirects.
The question
"Design a service like a link shortener: users paste a long URL and get a short one such as sho.rt/aZ3k9Q; visiting it redirects to the original."
Clarify the requirements
Questions to ask, and the answers we'll assume:
- Functional: create a short link (optionally with a custom alias and an expiry); redirect; basic click counts.
- Scale: 100 million new links per month; redirects outnumber creations 100 to 1.
- Non-functional: redirects must be fast (< 50 ms) and highly available; a short code must never point to the wrong URL; codes should not be guessable in sequence (nice to have).
- Out of scope: user accounts beyond an API key, link editing, detailed analytics dashboards.
Estimate the scale
- Creations: 100M / month ≈ 3.3M / day ≈ 40 writes/s (peak ~100/s).
- Redirects: 100× → 4,000 reads/s (peak ~10,000/s). Read-heavy: cache it.
- Storage: ~500 bytes per link × 100M × 12 × 5 years = 3 TB. Fits a sharded database comfortably.
- Code length: base62 (a–z, A–Z, 0–9) with 7 characters gives 62⁷ ≈ 3.5 trillion codes, plenty for 6 billion links.
API and data model
POST /api/links { "url": "...", "alias": "optional", "expires_at": "optional" }
-> 201 { "code": "aZ3k9Q", "short_url": "https://sho.rt/aZ3k9Q" }
GET /{code} -> 301/302 redirect to the long URL (404 if unknown or expired)
GET /api/links/{code}/stats -> { "clicks": 1234 }
links: code (PK, varchar 10) | long_url (text) | created_at | expires_at | owner_key
A key-value lookup by code is the hot path, so the store can be a key-value database or a SQL table with code as the primary key.
High-level design
┌──────────────┐ miss ┌──────────────┐
client ───► │ load balancer│──► app ──► cache (Redis) ──► links DB (sharded by code)
└──────────────┘ │
└──► click events ──► queue ──► analytics workers ──► counts
- Create: the app gets a new unique code, stores
code → long_url, returns the short URL. - Redirect: look up the code in the cache, fall back to the database, then answer with a redirect. Publish a click event to a queue after responding, so analytics never slows the redirect.
Deep dives
1. Generating unique codes. Three options:
| Approach | How | Trade-off |
|---|---|---|
| Hash the URL (MD5/SHA) and take 7 chars | Deterministic | Collisions must be checked and retried; same URL → same code (may or may not be wanted) |
| Random 7 chars | Simple, not guessable | Collision check on every insert (rare at first, more common as the table fills) |
| Counter + base62 | A unique number encoded in base62 | No collisions; sequential codes are guessable unless the number is scrambled |
A robust choice: each app server reserves a block of IDs (e.g. 1,000 at a time) from a counter (a database sequence or a small ID service), encodes each ID in base62, and optionally passes the number through a reversible scramble so neighbouring codes don't look related.
ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
SPACE = 62 ** 7 # all 7-character codes
MULT = 1_580_030_173 # odd and coprime with 62^7, so the scramble is reversible
INVERSE = pow(MULT, -1, SPACE)
def base62(n, width=7):
chars = []
for _ in range(width):
n, r = divmod(n, 62)
chars.append(ALPHABET[r])
return "".join(reversed(chars))
def from_base62(code):
n = 0
for ch in code:
n = n * 62 + ALPHABET.index(ch)
return n
def code_for(link_id):
return base62(link_id * MULT % SPACE) # unique: a permutation of 0..62^7-1
def id_for(code):
return from_base62(code) * INVERSE % SPACE
class IdBlock:
'''Each app server reserves ids in blocks, so it rarely talks to the counter.'''
def __init__(self, counter, size=1000):
self.counter, self.size = counter, size
self.next = self.end = 0
def take(self):
if self.next == self.end:
self.next = self.counter["value"]
self.counter["value"] += self.size # one atomic increment per block in real life
self.end = self.next + self.size
self.next += 1
return self.next - 1
counter = {"value": 1_000_000}
server_a, server_b = IdBlock(counter), IdBlock(counter)
for server in (server_a, server_a, server_b, server_a):
link_id = server.take()
code = code_for(link_id)
print(f"id {link_id} -> {code} -> back to id {id_for(code)}")
print("possible codes:", f"{SPACE:,}")
Output
id 1000000 -> FjFv4Ig -> back to id 1000000 id 1000001 -> FloqIJT -> back to id 1000001 id 1001000 -> 78lgEZi -> back to id 1001000 id 1000002 -> Fn7mmLw -> back to id 1000002 possible codes: 3,521,614,606,208
2. Redirect speed and the cache. With a 100:1 read ratio, a cache of the most popular links (a small fraction of all links gets most clicks) serves the large majority of redirects. Use a cache-aside pattern with a TTL; links rarely change, so staleness is a non-issue except for deletions (delete the cache key too).
3. 301 vs 302. A 301 (permanent) lets browsers cache the redirect, which cuts load but hides repeat clicks from analytics. A 302 (temporary) sends every click through you. Choose 302 if click counts matter.
4. Analytics without slowing redirects. Respond first, then publish a click event to a queue; workers aggregate counts per code per minute. Losing a few events in a crash is acceptable for counts.
Trade-offs
- Counter vs random codes: counters never collide but need a coordinated counter; random codes need a collision check but no coordination.
- SQL vs key-value store: both work; key-value scales writes more easily, SQL makes alias uniqueness and expiry queries simpler.
- Custom aliases share the code namespace: enforce uniqueness with a unique constraint, and reserve offensive or system words.
- Abuse: short links hide destinations, so add rate limits per API key and check URLs against a malware list.
What interviewers look for
- Estimating code length from the expected number of links.
- A clear choice of code generation with its collision story.
- Recognising the read-heavy pattern and caching it.
- Keeping analytics off the critical path.
- Bonus: the 301/302 trade-off and abuse prevention.
Key points
- 7 base62 characters ≈ 3.5 trillion codes.
- Counter + base62 (with a scramble) avoids collisions; reserve ID blocks per server.
- Read-heavy → cache-aside with TTL; respond, then record the click asynchronously.
- 302 keeps analytics accurate; 301 saves load.
Practice questions
How would you generate short codes so two servers never hand out the same one?
Answer
Use a shared counter, but have each server reserve a block of IDs (for example 1,000) with one atomic increment, then encode each ID in base62. IDs never overlap between blocks, so codes are unique without per-request coordination. Scramble the number reversibly if codes shouldn't look sequential.
Why would a URL shortener prefer a 302 redirect over a 301?
Answer
Browsers cache a 301 and stop asking the shortener, so repeat clicks aren't counted and the destination can't be changed later. A 302 sends every click through the service, keeping analytics accurate at the cost of more traffic.
Open in the app to mark lessons complete, take notes and track your progress.