The URL shortener is the “intro” system design question, but it leaves plenty of room to show depth: codes that never collide, can’t be guessed, and are read a hundred times more than written. This post walks through every step as in a real interview, with the arithmetic and the places where the original slides get it wrong. It ends with a 45-minute plan and a few diagramming conventions.
1. Clarify the requirements
Key idea: pin down the core features (shorten, redirect) and four numbers: writes per day, read/write ratio, code length, retention.
Features:
- Shorten a long URL into a short one, like Bitly or TinyURL.
- The same long URL may get several different short URLs (one per campaign, to measure each).
- Codes are collision-free and unguessable (nobody can find other people’s links by incrementing a code).
- Users can pick their own code (custom alias), links are SEO-friendly, and clicks are tracked.
Scale questions and the answers given:
| Question | Answer |
|---|---|
| New links per day? | 10 million |
| Read : write ratio? | 100 : 1 |
| Maximum code length? | 8 characters |
| How long to keep them? | 4 years |
Non-functional: high availability (a dead link ruins a customer’s campaign), low redirect latency (server-side p99 under ~50 ms), scalable, durable.
2. Estimate
Key idea: ~116 writes/s, ~12K reads/s, 14.6 billion records over 4 years, a few tens of TB including replicas; the cache for hot links is just a few GB.
Tip: a day has 86,400 seconds; round it to 10⁵ for quick mental math. The numbers worth memorising and the powers-of-ten tricks are in Back-of-the-envelope estimation.
- Writes: 10⁷ / 10⁵ = 100/s (precisely ~116). Peak ×3 ≈ 350/s.
- Reads: 100 × 116 ≈ 12K/s, peak ≈ 35K/s.
- Records over 4 years: 10⁷ × 365 × 4 ≈ 1.46 × 10¹⁰.
- Storage: a record is ~500 bytes (code, long URL averaging ~200 bytes, user, created and expiry times, overhead) → 1.46 × 10¹⁰ × 500 B ≈ 7.3 TB; replication factor 3 → ~22 TB. The slides get 17.6 TB and 52.8 TB, which silently assumes ~1.2 KB per record. What matters is stating your assumption.
- Cache: keep the links created in the last day (new links get the most clicks): 10⁷ × ~220 B ≈ 2.2 GB, one Redis node is enough.
- Keyspace: 62⁶ ≈ 5.7 × 10¹⁰, 62⁷ ≈ 3.5 × 10¹², 62⁸ ≈ 2.2 × 10¹⁴. We need 1.46 × 10¹⁰, so 6 characters already fit; pick 7 for ~240× headroom.
3. API
Key idea: two main paths: create a link (POST, writes) and redirect (GET /{code}, the hot read). Stats and management are secondary.
POST /api/v1/urls
{ "longUrl": "https://shop.example/sale?utm=fb", "customAlias": "sale-tet", "expiresAt": "2027-02-01T00:00:00Z" }
→ 201 { "code": "sale-tet", "shortUrl": "https://sho.rt/sale-tet" }
GET /{code}
→ 302 Location: https://shop.example/sale?utm=fb (404 if unknown, 410 if expired)
GET /api/v1/urls/{code}/stats?from=2026-11-01&to=2026-11-18
→ 200 { "clicks": 18234, "byCountry": { ... } }
POST needs an idempotency key if clients may retry, so one click doesn’t create two links (see idempotency). Rate-limit by API key and by IP to stop spam.
4. Generating codes: four options and a choice
Key idea: split the problem in two: generate a unique integer, then Base62-encode it to make it short and URL-safe. Of the four ways to get the integer, token ranges win: no collisions, short output, no coordination per write.
Why Base62. Base36 (a-z0-9) gives longer codes; Base64 includes + and /, which must be escaped in URLs. Base62 (a-zA-Z0-9) is the largest URL-safe alphabet. A 7-digit Base62 number holds up to 3.5 trillion values.
| Option | Idea | Collisions? | Length | Guessable? | Verdict |
|---|---|---|---|---|---|
| Random (UUID, CSPRNG) | pick at random in 62⁸, then Base62 | yes, birthday paradox, must check on write | 8 | no | workable if every write is conditional |
| Hash (MD5/SHA of the long URL, cut to 7 chars) | hash and truncate | yes, worse the shorter you cut | 7 | same URL gives same code | breaks “one URL, many codes” |
| Snowflake (64 bits: time + machine + sequence) | distributed ID | no | 11 | yes, by time | too long |
| Token range (a counter split into blocks) | each instance owns a block of numbers | no | 7 | yes, unless shuffled | chosen, with shuffling |
How token ranges work
A coordinator hands out non-overlapping blocks of numbers; each Token Service instance keeps its block in memory and issues numbers with an AtomicLong. When the block runs out, it asks for a new one.
flowchart LR
C[(ZooKeeper or PostgreSQL: next_start)] -->|lease 1M numbers| T1["Token service 1: 1 - 1M"]
C --> T2["Token service 2: 1M - 2M"]
T1 -->|next++ in memory| S[Shortener]
T2 --> S
S -->|shuffle + Base62| K[7-char code]
- The coordinator can be ZooKeeper (as on the slides) or something simpler: one PostgreSQL row,
UPDATE id_alloc SET next_start = next_start + 1000000 RETURNING next_start. TheUPDATElocks the row, so two instances never get the same block. - At 116 writes/s, a block of 1 million lasts ~2.4 hours; the coordinator is barely touched.
- If an instance dies, the rest of its block is wasted. That’s fine: with 3.5 trillion codes, losing a few million doesn’t matter.
Unguessable: shuffle the number before encoding
Token ranges produce sequential numbers, so aB3xK9p and the next code differ only in the last character. Someone could crawl every other user’s links. The slides list “predictable” as a drawback but pick it anyway, contradicting the “unguessable” requirement.
The fix: before Base62, run the number through a keyed permutation over a fixed domain, for example a 42-bit Feistel network. A permutation maps distinct inputs to distinct outputs, so codes stay unique; but seeing one code tells you nothing about the next.
Java code: a 42-bit Feistel network and Base62
final class CodeGenerator {
private static final String ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
private static final int HALF = 21; // 2 halves × 21 bits = 42 bits
private static final long MASK = (1L << HALF) - 1;
private final long[] roundKeys; // secret keys, loaded from a secret store
CodeGenerator(long[] roundKeys) { this.roundKeys = roundKeys; }
String encode(long counter) { // counter < 2^42 ≈ 4.4 trillion
long l = (counter >>> HALF) & MASK, r = counter & MASK;
for (long k : roundKeys) { // 4 rounds is enough to scramble
long f = (mix(r ^ k)) & MASK;
long next = l ^ f;
l = r; r = next;
}
return base62((l << HALF) | r);
}
private static long mix(long x) { // any mixing function, need not be invertible
x *= 0x9E3779B97F4A7C15L; x ^= (x >>> 29); return x;
}
private static String base62(long n) {
StringBuilder sb = new StringBuilder();
do { sb.append(ALPHABET.charAt((int) (n % 62))); n /= 62; } while (n > 0);
return sb.reverse().toString();
}
}
A Feistel network is always invertible even if mix isn’t, so this is a permutation of [0, 2⁴²). The output is < 2⁴² ≈ 4.4 × 10¹², which fits in 8 Base62 characters (usually 7). To force exactly 7, use cycle-walking: if the result is ≥ 62⁷, encrypt again until it lands in range.
This isn’t encryption against a well-funded attacker, just enough that codes can’t be guessed by incrementing. The Sqids library (formerly Hashids) does something similar.
5. Storage and data model
Key idea: the URL table is pure key-value (lookup by code, no joins) with tens of billions of rows: a fit for a wide-column store like ScyllaDB/Cassandra, with the code itself as the partition key. Users and subscriptions are relational and need ACID: PostgreSQL.
-- ScyllaDB (CQL)
CREATE TABLE urls (
code text PRIMARY KEY, -- partition key, spread by hash
long_url text,
user_id bigint,
created_at timestamp,
expires_at timestamp
); -- write USING TTL if the link expires
CREATE TABLE url_by_hash ( -- only needed for "one long URL, one code"
long_url_hash blob PRIMARY KEY, -- SHA-256(normalised long_url)
code text
);
Why not PostgreSQL for the URL table? 14.6 billion rows, 22 TB: PostgreSQL can do it but you’d have to shard yourself (Citus, or hash routing in the app). ScyllaDB gives hash partitioning, replication and online node additions out of the box. I wrote about partitioning and sharding.
New requirement: one long URL, one code
Key idea: you must check “does this long URL already have a code” before creating one. Don’t index the whole long string; index hash(long_url) and use a conditional write so two concurrent requests can’t create two codes.
The slides offer two options:
- Bloom filter: says “definitely not here” very cheaply; “maybe here” still needs the DB. The slides drop it because of false positives, but a false positive only costs one extra read. The real problems: keeping the filter in sync across instances, no deletes, and you still need the DB to find the existing code.
- Global secondary index on
hash(long_url): transparent to the app. But ScyllaDB’s GSI is a materialized view, updated asynchronously.
6. Redirects, caching and analytics
Key idea: the read path is cache-aside: Redis first, ScyllaDB on a miss. Use 302 so every click reaches the server, and push click events to Kafka asynchronously; never let analytics slow down the redirect.
flowchart LR
U[User] --> CDN[CDN]
CDN --> GW[API gateway + rate limit]
GW -->|POST| SH[Shortener]
GW -->|GET code| TR[URL translator]
SH --> TS[Token service]
SH --> DB[(ScyllaDB)]
SH --> RC[(Redis)]
TR --> RC
TR -->|miss| DB
TR -.->|click event| K[Kafka]
K -.-> AN[(Analytics: ClickHouse)]
A few read-path details:
- Cache-aside with a 1-day TTL for normal links; for links about to expire, TTL = remaining lifetime (see cache-aside and invalidation).
- Unknown codes (bots scanning random codes) go through the cache to the DB: cache the empty result with a short TTL, or keep a Bloom filter of every issued code. A Bloom filter fits perfectly here (see cache penetration).
- A viral link (one code taking 30% of reads) heats up one Redis node: add an in-process cache (Caffeine, a few seconds TTL) in the translator.
- Analytics: the translator sends
{code, ts, ip, ua, referer}to Kafka without waiting synchronously for the ack; a consumer aggregates per minute into ClickHouse. Losing a few clicks during an incident is acceptable.
7. Failures, scaling and the usual follow-ups
Key idea: for each component, say what still works when it dies: without ZooKeeper you keep creating links until blocks run out; without Redis you read straight from ScyllaDB (12K/s is fine); without one ScyllaDB node the replicas serve.
- Custom alias: conditional write
IF NOT EXISTS. To avoid clashing with future generated codes: aliases must be ≥ 8 characters or contain-, while generated codes are always 7 Base62 characters. - Expiry and cleanup: ScyllaDB TTL deletes them; expired codes are never reused (old links may still be printed on paper).
- Abuse: check long URLs against a malware-scanning service before activating, block bad domains, rate-limit per user.
- Multiple regions: read from the nearest region (ScyllaDB multi-DC,
LOCAL_ONEconsistency for reads); each region has its own token ranges, so writes need no cross-region coordination.
8. Presenting it in 45 minutes
Key idea: go top-down: problem → idea → high-level design → details → edge cases → error handling, and recap at the end. Spend the most time on the genuinely hard part: generating codes.
| Minutes | Step | What to say |
|---|---|---|
| 0–5 | Requirements | features, the 4 numbers, “unguessable” and “one URL, many codes” |
| 5–10 | Estimates | 116 writes/s, 12K reads/s, 14.6 billion records, 7 chars is enough |
| 10–15 | API + data model | POST, GET /{code}, urls table partitioned by code |
| 15–20 | High-level diagram | gateway, shortener, translator, cache, DB |
| 20–35 | Deep dive | four code generators, token ranges, Feistel shuffle, 301/302, dedupe |
| 35–42 | Failures and scaling | what happens when each part dies, viral links, multi-region |
| 42–45 | Recap | the three main decisions and what you’d do next |
Diagramming conventions and presenting tips
Diagramming (UML sequence/activity, C4 or free style all work, as long as you’re consistent; see also C4):
- Every box and arrow has a label. Arrows point from caller to callee.
- Solid lines for synchronous calls, dashed lines for asynchronous ones.
- Shapes: services are rectangles, databases are upright cylinders, message queues are horizontal cylinders.
- Colours carry meaning, no more than 5: red for the main component or fragile spots, green for safe/done, yellow for warnings, grey for disabled.
- Learn your tool’s shortcuts, group related elements, and use background layers to mark areas (“write path”, “read path”).
Presenting:
- Top-down: abstract → detail → abstract. Every time you dive in, say where you are on the diagram.
- Power of three: group things into three main points (“my three decisions are…”), and repeat the important one three times.
- Two channels: speech and drawing. Don’t cram text onto the board; draw less, say more.
- Open with the problem or the user’s pain, close with a recap.
Remember
- Can you quickly work out writes and reads per second, records over 4 years, and why 7 Base62 characters are enough?
- Can you compare the four code generators and point out where the slides are wrong about Snowflake and random IDs?
- Can you explain token ranges and how to make codes unguessable while keeping them unique?
- Do you know when to pick 301 versus 302, and which path analytics takes?
- Do you know why “check the index, then write” creates duplicates, and how a conditional write fixes it?
Interview questions
Junior
Why Base62 rather than Base64 for short codes?
Base62 (a-zA-Z0-9) is the largest alphabet that needs no escaping in URLs; Base64 has + and /, which must be encoded.
A bigger alphabet means shorter codes: 7 Base62 characters hold ~3.5 trillion values, while Base36 needs 8 characters for the same amount.
How long must the code be for 10 million links a day over 4 years?
6 Base62 characters is enough (62⁶ ≈ 5.7 × 10¹⁰ > 1.46 × 10¹⁰ links); pick 7 for about 240× headroom.
The arithmetic: 10⁷ × 365 × 4 ≈ 1.46 × 10¹⁰. The headroom makes random IDs collide less and lets you waste numbers when an instance dies.
Mid
Compare four ways to generate short codes and pick one.
Random (collides, needs conditional writes), hash (collides when truncated, same URL gives same code), Snowflake (no collisions but 11 characters and guessable), token range (no collisions, 7 characters, no coordination per write). Pick token ranges and shuffle the number before Base62.
Also state the cost: a coordinator to lease blocks, and wasted numbers when an instance dies.
301 or 302 for a link shortener that tracks clicks?
302: every click goes through the server, so you can count it and change or disable the link. A 301 is remembered by the browser, which cuts load but loses analytics.
Analytics are sent asynchronously through Kafka so they never slow down the redirect.
The read path takes 35K requests per second at peak. How do you design the cache?
Cache-aside on Redis with a ~1-day TTL; cache empty results or use a Bloom filter for unknown codes; add an in-process cache for viral links.
Memory for hot links is only a few GB. If Redis dies, read straight from ScyllaDB, which can handle this load.
Senior
Token ranges produce sequential numbers, so codes are guessable. How do you fix that without collisions?
Run the number through a keyed permutation over a fixed domain (for example a 42-bit Feistel network) before Base62; a permutation is a bijection, so codes stay unique but the next one can’t be inferred.
To force exactly 7 characters, use cycle-walking. The Sqids library does something similar.
New requirement: each long URL gets exactly one code. How do you stop two concurrent requests from creating two codes?
Use a url_by_hash table with INSERT ... IF NOT EXISTS keyed by the SHA-256 of the normalised URL; the loser reads back the existing code.
Don’t rely on a secondary index (asynchronous in ScyllaDB), and don’t let a Bloom filter decide (use it only to skip the read when the URL is definitely new).
The ZooKeeper cluster that leases token ranges is down for 30 minutes. What happens?
Almost nothing: every instance still has a block in memory, and at 116 writes/s a block of 1 million lasts over 2 hours. Only an instance that just started or just ran out can’t create links.
To be safer, lease the next block when 20% of the current one remains, and keep reads (redirects) completely independent of ZooKeeper.
Useful phrases for interviews
- “Let me start with a quick back-of-the-envelope estimate.”
- “A day is roughly ten to the fifth seconds, so ten million writes a day is about a hundred per second.”
- “The system is read-heavy, so the redirect path is where I’ll spend my latency budget.”
- “I’ll split it into two problems: generating a unique number and encoding it.”
- “Snowflake IDs don’t collide, they’re just too long for an eight-character limit.”
- “Each instance leases a token range, so there’s no network call per write.”
- “Sequential codes are guessable, so I’d run them through a keyed permutation first.”
- “I’d go with a 302 because the product needs click analytics.”
- “To avoid the check-then-write race, I’d use a conditional insert.”
- “If ZooKeeper goes down, we keep serving from the ranges we already hold.”
Notes based on the System Design course (Ronin Engineer), rewritten in my own words.