Case Study: URL Shortener
A classic that exercises every earlier idea: estimation, ID generation, read-heavy caching, and storage.
- 40 / 4,000 per swrites and redirects, 12K/s at peak
- 3.5 trillion7-character base62 codes available
- 200 reads/sPostgres load at 4,000/s and 95% hits
Show what to say
“It's a read-heavy key-value lookup: about 40 writes and 4,000 redirects a second. I generate 7-character base62 codes from a counter handed out in blocks of 1,000 and scrambled so they aren't guessable, return a 302, and serve redirects from the CDN and Redis in front of Postgres. Clicks go on a queue so analytics never slow a redirect.”
Trade-offs
- 301 vs 302: a 301 is fastest but clicks vanish and mistakes stay cached; a 302 reaches you every click, so you can count it.
- Counter vs hash codes: counters are unique and shortest but guessable unless scrambled; hashes need no coordination but collide.
- Range allocation vs one counter: blocks of 1,000 remove the hot spot and single point of failure, but a crash wastes a block.
Bring it up before they ask
A viral link at 50K redirects/s overloads one Redis node, so add a tiny few-second in-process cache on every app server.
A URL shortener is a read-heavy lookup: about 40 writes and 4,000 redirects a second. Hand out short codes from a counter, serve redirects from , and send clicks through a queue so analytics never slow a redirect.
Why it matters
One problem that uses everything so far.
Read more · 54 words
Interviewers dig into codes, 301 vs 302 and speed. Every part is a choice between two or three options, walked here in order.
Play each scenario. Click analytics shows the async side.
Functional
- Shorten a long URL into a short code
- Redirect a short URL to the long one
- Optional custom alias
- Optional expiry date
- Click analytics: clicks per day, top referrers
Non-functional
- Redirect served in under ~20 ms at the server
- 99.99% available for redirects (about 53 min of downtime a year)
- Durable: a created link never disappears
- Codes hard to enumerate
Out of scope
- Editing a link's destination
- User accounts and billing
- QR codes and link-in-bio pages
Redirects matter more than creation. If creation is down, people retry. If redirects are down, every link ever shared breaks at once.
Tap any box to see what it is and what it talks to.
- Client
- CDN
- Service
- ID generator
- Cache
- Database
- Queue
- Worker
Text description
- POST /api/urls with a long URL. Writes are never cached, so the CDN forwards it.
- An app server checks the rate limit and validates the URL: only http and https are allowed.
- This server has used up its block of ids, so it asks the ID service for the next one: INCRBY url:id 1000.
- Redis answers 42,000, so this server now owns ids 41,000 to 41,999. Its next 999 links need no call at all.
- Id 41,000 is scrambled and base62-encoded into 'oqxem9y', then INSERTed with the long URL. The primary key guarantees uniqueness.
- Row committed. A custom alias that already exists would fail here with a unique violation, returned as 409.
- 201 Created with the code and the short URL.
- The user gets https://short.example/oqxem9y.
Estimate, API and data model
100M new links a month is 40 writes a second (a month is 2.6 million seconds).
Read more · 479 words
At 100 reads per write that is 4,000 redirects a second, about 12K at a 3× peak. Six billion links in 5 years at about 500 bytes a row is 3 TB, or 9 TB with 3 . A redirect is a few hundred bytes, so 4,000 a second is about 1 MB/s: bandwidth is not the problem.
One database barely notices 40 writes a second. The read path is the whole game. The popular links fit in about 6 GB (say 10M codes at 600 bytes): one node.
| Reads per write | Redirects/s | Plan |
|---|---|---|
| 1 | 40 | One database, no cache |
| 100 | 4,000 | Add Redis; the database would sweat |
| 1,000 | 40,000 | CDN and Redis, no choice |
A private link tool with 1,000 redirects a day needs none of this. Drag Reads per write in the calculator.
Three endpoints cover the product, and the redirect is the one that matters.
| Method | Path | Result |
|---|---|---|
| POST | /api/urls | 201 { code, shortUrl } · 409 alias taken · 429 rate limited |
| GET | /:code | 302 (or 301) to the long URL · 404 · 410 expired |
| GET | /api/urls/:code/stats | { clicks, byDay[], topReferrers[] } |
The redirect lives at the root to stay short, so reserve api, admin and login: they can never be aliases. If the same long URL is submitted twice, the simple answer is two codes: each creator keeps a separate click count, at the cost of one extra row. only if the interviewer asks.
Every read is a lookup by code, with no joins, so the model is one table.
Never count clicks here: 4,000 updates a second would make a read-only table write-hot.
Start with Postgres. It gives you the primary-key uniqueness that custom aliases need, and 40 writes a second plus a is easy for one . Use a key-value store by hash of the code when the table passes about 1 TB (a rule of thumb, not a law) or several regions must accept writes. At 3 TB either fits, so say which you chose and what would make you change.
CREATE TABLE urls (
code varchar(16) PRIMARY KEY, -- generated (7 chars) or custom alias
long_url text NOT NULL,
user_id bigint,
created_at timestamptz NOT NULL DEFAULT now(),
expires_at timestamptz
);
CREATE INDEX urls_expiry ON urls (expires_at) WHERE expires_at IS NOT NULL; -- for the cleanup jobDo people list, search or report on their links (by user, by date)?
Generating short codes
A short code is a number written with 62 symbols (base62: 0-9, a-z, A-Z).
Read more · 469 words
62⁶ is 56.8 billion, 62⁷ is 3.5 trillion, 62⁸ is 218 trillion. Seven symbols is the default: six billion links fill only 0.2% of it (so a random code collides about 1 time in 600), while six characters would be 10% full after 5 years. Start with the counter.
| Option | How it works | Use it when | Cost |
|---|---|---|---|
| Hash the URL | md5 the URL, write the digest in base62, keep 7 characters. The same URL gives the same code | Identical URLs must share a code (and one click count) | Collisions are routine: by the birthday bound the first clash is expected after a couple of million links, so every insert needs a retry with a salt. The code is computable from the URL |
| Random + check | Draw 7 secure random characters and insert; if the primary key says taken, draw again | Codes must be impossible to guess: private or unlisted links | One failed insert in about 587 at 6B links (0.17%), one retry every 15 s at 40 writes a second. A guess lands on a real link 1 time in 587, with no order to walk |
| Snowflake-style id | A 64-bit id needs 11 base62 characters | You already run one for other services | Too long for a short link |
| Counter in blocks (default) | A counter gives the next number and base62 writes it. Each app server grabs 1,000 ids and hands them out from memory | Zero collisions and the simplest write path: most of the time | A small durable service (Redis INCRBY or a Postgres sequence). Plain base62 is guessable |
At 40 writes a second the counter is called once per 1,000 links, about once every 25 seconds in total. A crash wastes the rest of a block, which is fine: ids must be unique, not contiguous. Play Counter lost: if the counter forgets its position, ids repeat, but the refuses the duplicates, so nothing is overwritten.
Step an id in the playground, then change the block size.
Ask two questions in order: do identical URLs need identical codes, and must codes be impossible to guess?
Counter ids are guessable. Base62 of 1000, 1001, 1002 is g8, g9, ga, so anyone can walk the codes and read private links. Scramble first: multiply the id by a large constant modulo 62⁷. Every id keeps its own 7-character code, and you can reverse it.
| Id | Plain base62 | Scrambled |
|---|---|---|
| 1 | 1 | CjIO2GV |
| 2 | 2 | eDrC5nQ |
| 41,000 | aFi | oqxem9y |
| 41,001 | aFj | 0Kg2oQt |
Tap any box to see what it is and what it talks to.
- Service
- ID generator
- Database
Text description
- Server A has no ids yet, so it calls INCRBY url:id 1000.
- The counter answers 1,000: server A owns ids 0 to 999.
- Server B asks a moment later.
- The counter answers 2,000: server B owns ids 1,000 to 1,999. Atomic INCRBY means the blocks can never overlap.
- Each server now scrambles and encodes ids from its own memory. At 40 links a second the counter is called about once every 25 seconds in total.
Redirects and the read path
Both redirects work; the difference is who remembers the answer.
Read more · 647 words
A 301 says "moved for good": browsers and remember it. A 302 says "try here for now": every click comes back, so you can count it. Default to 302.
| Every click reaches you | Change it later | Use it when | |
|---|---|---|---|
| 301 | No: only the first click per browser | Hard: a browser may cache it indefinitely, so you can never undo it | Nobody needs analytics and links never change: an internal redirect, a vanity URL. Fastest, lightest |
| 302 (default) | Yes | Easy | You promise click analytics, expiry or a kill switch: nearly always |
302 + max-age=60 | The CDN answers for a minute | Up to a minute to take effect | The hottest links, where load matters more than exact counts |
A link clicked 10,000 times a day by 2,000 distinct browsers shows you about 2,000 requests under a 301: your count is 5× wrong and you cannot tell. With a 301, a campaign link you fix later keeps sending returning visitors to the old page. With a 302 and a 60-second max-age, 200 edge locations cost the origin about 200 requests a minute (roughly 3 a second) however many clicks arrive. The CDN-answered clicks must be counted from CDN logs. The browser keeps the answer for the same 60 seconds, a minute, not forever, so this is not the 301 problem.
A few links get most of the clicks, so stack and let most reads end early: CDN, then , then a tiny cache in each app server, then .
| Layer | What it does | Use it when |
|---|---|---|
| CDN | Answers at the edge, shields everything behind it. Only helps for responses it may keep (the short max-age) | The hottest few percent of links, users across regions. Skip it under a few hundred redirects a second |
| Redis (the default) | Cache-aside: check Redis, on a miss read Postgres and fill the key with a TTL capped at the link's expiry. At a 95% hit ratio Postgres sees 200 reads a second; the hot set (~6 GB) fits one node; cached links survive a short database blip | From the start: the single biggest step |
| Tiny cache per app server | A viral link is one key that one Redis node must serve. Keep a copy in each server's memory for a few seconds. Ten servers refreshing every 5 s is 2 Redis reads a second instead of 50,000 | Keys with tens of thousands of reads a second. Servers can briefly disagree, fine for a destination that rarely changes |
| Read replicas | Add read capacity behind the cache. The primary takes the 40 writes; misses read from replicas | Last. At 3 TB and 200 reads a second you do not need them yet |
takes a moment, so a brand new link can be missing from a replica: write the code into Redis at creation and retry the once before returning 404. by hash of the code only when the table outgrows one machine.
Show data table
| reads/s | |
|---|---|
| No cache | 4,000 |
| 90% hit | 400 |
| 95% hit | 200 |
| 99% hit | 40 |
Tap any box to see what it is and what it talks to.
- Service
- Cache
- Database
Text description
- Look up u:oqxem9y.
- Hit in about 1 ms. At a 95% hit ratio, 19 of every 20 redirects end here.
Clicks, expiry and abuse
A redirect never waits for counting.
Read more · 725 words
It drops a click note on a queue and moves on. A worker saves notes in batches to an analytics store, and the stats page reads daily totals. If the queue is down, you lose a few counts, never a redirect.
| Way to count | How it works | Use it when |
|---|---|---|
| Count in the row | UPDATE urls SET clicks = clicks + 1. Updates to one row run one at a time, so a link at 500 clicks a second queues its own redirects, and a read-only table turns write-hot at 4,000 updates a second | A tool with a handful of clicks a day |
| Queue, worker, store (default) | The redirect publishes a click event and does not wait. A worker bulk-inserts batches into a columnar store such as ClickHouse; the stats API reads pre-aggregated rollups | As soon as you promise analytics. Play Store down and Queue down: the first loses nothing, the second loses a few counts and no redirects |
| Count from logs | CDN and server logs already record every request. A scheduled job turns them into rollups | Stats may be an hour or two old, or a CDN answers clicks your app never sees. Many systems do both: queue for fresh numbers, logs to reconcile |
An event of about 200 bytes at 4,000 a second is 0.8 MB/s, or about 69 GB a day. Keep raw events a few weeks and forever. A batch of 5,000 fills in 1.25 seconds, so you write about one bulk insert a second instead of 4,000 single ones. Filter out bots and link-preview fetchers, and store a country instead of the raw IP address.
Expiry. Expired means expired, even when the link is hot in . Two mechanisms work together:
- Check on read. Every lookup compares
expires_atwith now, and the is the smaller of one day and the time left, so the cache never outlives the link. One comparison per miss. - Sweep at night. A job deletes expired rows 1,000 at a time using the partial index on
expires_at, pausing between batches so locks stay short. It reclaims space and nothing else. A sweep, not a delete at read time, so a spike of expired clicks is not a spike of deletes on the hot path. - Answer
410 Gone, then404once the row is gone. - Never reuse codes. Old links live on in emails and printed QR codes.
Abuse. Shorteners are a favourite disguise for malicious links, so defend in layers:
- Allow only
httpandhttps. Keep aliases apart from generated codes (say 8 or more characters), so an alias is never a future generated code. - Rate-limit creation. Say 20 creates a minute per user is far more than a person needs and far less than a script wants. Use a per user and per IP (see the rate limiter question). Never limit redirects: that breaks real visitors.
- Scan destinations against a reputation service after creating the link, from a queue, so creation stays fast. Rescan weekly for every link and daily for the most-clicked, because an attacker can swap the page behind a clean link.
- Disable, don't delete. Flag the row, delete its Redis key and purge the , in that order. The row stays as evidence. Show a warning page with a
410. This only works because the redirect is a 302: with a 301 the bad link lives on in browsers you cannot reach.
Tap any box to see what it is and what it talks to.
- Service
- Queue
- Worker
- Database
Text description
- Each redirect publishes about 200 bytes: code, time, referrer, country. It does not wait for the answer.
- At 4,000 clicks a second a batch of 5,000 fills in about 1.25 seconds.
- One bulk insert instead of 5,000 single ones. Rollups per day feed the stats API.
Failure modes
Four things go wrong on a real shortener. Play the scenarios in the diagrams above and below.
Read more · 247 words
| Failure | What happens | Fix |
|---|---|---|
| Counter lost | A counter without persistence restarts at 0 and hands out ids used last week. The primary key rejects every duplicate, so no old link is overwritten, but creation fails until it catches up | Make it durable (a replica and AOF every second for Redis, or a Postgres sequence). After a failover jump ahead by 1 million: replication is asynchronous, and the jump costs 1 million of 3.5 trillion codes |
| Alias race | Alice and Bob both type sale, and both checks say it is free | Not a smarter check: insert and let the primary key referee. One wins, the other gets a unique violation, and the API returns 409. That is why routes.js catches Postgres error 23505 and runs no SELECT first |
| Redis restarts empty | At 9:00 every redirect misses, so Postgres takes 4,000 reads a second instead of 200, 20 times more, exactly when everyone is awake | Single flight (one request per code rebuilds it), reload the hot set from yesterday's clicks, run a Redis replica so a failover is warm, add a connection limit so the database sheds load |
| Viral link | A celebrity posts a link: 50,000 redirects a second hit one key, one Redis node is nearly full while the cluster idles | A 302 with max-age=60 so the CDN absorbs most of it, a 5-second local copy in each app server for the rest, and per-key monitoring to find the next one early |
- Client
- Database
Text description
- Alice → Postgres: INSERT code sale
- Bob → Postgres: INSERT code sale
- Postgres replies to Alice: 1 row: 201 Created
- Postgres replies to Bob: unique violation: 409
Quick checkAfter a counter restart, ids repeat. What stops overwriting old links?
Code
range-allocator.js shares one refill, so a burst on an empty block makes one call.
Read more · 79 words
routes.js validates the URL, maps a duplicate to 409, and fires the click event without waiting.
Try the URL shortener challenge: wire components on a canvas and get graded.
// Base62 turns a numeric id into a short, URL-safe code and back
const ALPHABET = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
export function toBase62(n) {
let s = '';
do { s = ALPHABET[n % 62] + s; n = Math.floor(n / 62); } while (n > 0);
return s;
}
export function fromBase62(s) {
let n = 0;
for (const ch of s) n = n * 62 + ALPHABET.indexOf(ch);
return n;
}
// toBase62(125) → '21' · fromBase62('21') → 125 · 7 chars cover 62^7 ≈ 3.5 trillion codes
// Numbers stay exact up to 2^53; use BigInt beyond 8 characters.URL shortener in the interview
Go in this order and spend time where the interviewer leans. The deep dives decide the grade.
Read more · 469 words
Pin the scope and the ratio
Create, redirect, alias, expiry, click counts. Redirects outnumber creates about 100 to 1, so reads drive the design.
Do the arithmetic out loud
40 writes and 4,000 redirects a second (12K at peak), 3 TB over 5 years, a 6 GB hot set. One and one node is enough.
Choose the code scheme
Counter in blocks of 1,000, scrambled, 7 base62 characters. Random codes with a uniqueness check when guessing must be impossible.
Choose the redirect and the read path
A 302 so clicks are counted, a short max-age on the hottest links. , then Redis , then a tiny per server.
Own analytics, expiry and abuse
Clicks go on a queue, never awaited. Check expiry on read, sweep at night, never reuse codes. Rate-limit, scan, disable by flag and purge.
| If the interviewer says | You raise |
|---|---|
| "How do you generate the code?" | Counter in blocks, scrambled; random if guessing must fail |
| "Why not a 301?" | It hides repeat clicks and cannot be undone in a browser |
| "A link goes viral" | CDN max-age, then a local cache per server |
| "Two people want the same alias" | Primary key, return 409 |
| "How do you count clicks?" | Queue, batch worker, columnar store, rollups |
| "Users report phishing" | Scan, disable by flag, purge the caches |
5 minutes of scope, 5 of numbers and API, 10 to draw the create and redirect paths, 20 for three deep dives (codes, redirects and caching, analytics and abuse), and 5 to wrap up.
Text description
- Scope: Create, redirect (0–5 min)
- Numbers + API: 40 and 4,000 per s (5–10 min)
- Basic design: Two paths (10–20 min)
- Deep dives: Codes (20–27 min), 302 + caching (27–34 min), Clicks, abuse (34–40 min)
- Wrap-up: Trade-offs (40–45 min)
Quick checkWhich comes first when answering a URL shortener question?
Interview questions
Counter-based vs hash-based short codes?
Counters are unique but guessable unless scrambled. Hashes collide.
301 or 302?
302 if you count clicks or may change the link. 301 only for pure speed.
How do custom aliases work?
Check length and reserved words, and let the reject duplicates with a 409.
How do you expire links?
Check expires_at on read, cap lifetimes, clean up nightly, never reuse codes.
A link goes viral (50K redirects/s). Now what?
Let the answer, add a tiny cache in every app server, and batch the analytics.
Check yourself
Question 1 of 5Score 2 out of 3 or better to mark this page complete.