Overview
A URL shortener turns a long URL into a short code such as sho.rt/aB3xY9 and redirects visitors to the original. It is a classic interview problem because it is simple to describe but touches ID generation, storage, caching, read scaling, and analytics.
The system is extremely read-heavy: a link is created once and may be clicked millions of times. The redirect path must be fast and highly available.
You hand over a large coat and receive a small numbered ticket. Later, anyone with the ticket gets the coat back. The attendant only needs a fast way to look up ticket numbers and a way to never hand out the same number twice.
Requirements
- Functional: create a short URL for a long URL; redirect a short URL to the original; optional custom aliases and expiration.
- Non-functional: redirects under 50 ms at P99; 99.99% availability; short codes must not be guessable in sequence.
- Scale assumption: 100 million new URLs per month and a 100:1 read-to-write ratio.
- Out of scope: user accounts and a dashboard UI beyond basic click counts.
Where it shows up in interviews
Recognize it when: read-heavy, simple key lookups, ID generation.
- Design TinyURL / bit.ly
- Design Pastebin
Recognize it when: generate short unique keys at scale.
- Design a distributed ID generator
- Design an invite-code system
Where it is used in real software
Serve billions of redirects with aggressive caching and analytics pipelines for click tracking.
Wraps every link for security scanning and analytics before redirecting.
Twitter's time-ordered 64-bit IDs inspired many short-code generation schemes.
Key terms
- Short code
- The unique identifier, typically 7 base62 characters.
- Base62
- Encoding with 0-9, a-z, A-Z. 62^7 is about 3.5 trillion codes.
- 301 vs 302
- 301 is permanent and cached by browsers; 302 is temporary and lets every click reach your servers for analytics.
- Key generation service
- A component that pre-allocates unique IDs or ranges.
Design walkthrough
- 1Estimate capacity
Writes: 100M per month is about 40 per second. Reads at 100:1 are about 4,000 per second, peaking near 20,000. Storage: 100M x 12 months x 5 years x 500 bytes is about 3 TB.
- 2Define the API
POST /api/urls { longUrl, customAlias?, expiresAt? } returns { shortUrl }. GET /{code} returns 302 with Location: longUrl.
- 3Generate unique codes
Use a distributed counter or ID ranges: each app server reserves a block of 1,000 IDs from a coordinator, then base62-encodes each ID. No collisions and no database check per write.
- 4Store the mapping
A key-value store keyed by code: { code, longUrl, createdAt, expiresAt, ownerId }. DynamoDB, Cassandra, or sharded PostgreSQL all work since access is by primary key.
- 5Make redirects fast
Cache code-to-URL in Redis. Popular links follow a power law, so a cache holding 20% of links can serve over 80% of traffic. Put a CDN in front for the hottest links.
- 6Track analytics asynchronously
On redirect, publish a click event to Kafka and return immediately. Consumers aggregate counts by code, country, and referrer.
Back-of-the-envelope estimates
100M new URLs per month, 100:1 reads to writes, 5-year retention
| Metric | Calculation | Result |
|---|---|---|
| Write QPS | 100M / (30 x 86,400) | ~40 / s |
| Read QPS | 40 x 100 | ~4,000 / s (peak ~20k) |
| Total URLs | 100M x 60 months | 6 billion |
| Storage | 6B x 500 bytes | ~3 TB |
| Code length | 62^7 = 3.5 trillion > 6B | 7 characters |
| Cache size | 20% of daily reads x 500 B | a few GB of Redis |
NOWMetric: Write QPS | Calculation: 100M / (30 x 86,400) | Result: ~40 / s
The workload is small on writes and large on reads, so the design centers on caching and fast key lookups rather than write throughput.
Implementation
const ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"; function encodeBase62(id: bigint): string { if (id === 0n) return ALPHABET[0]; let code = ""; while (id > 0n) { code = ALPHABET[Number(id % 62n)] + code; id /= 62n; } return code;} // Reserve IDs in blocks so servers never collide or hit the DB per write.class IdAllocator { private next = 0n; private end = 0n; async nextId(): Promise<bigint> { if (this.next >= this.end) { const start = await coordinator.reserveBlock(1000); // atomic INCRBY in Redis/ZooKeeper this.next = start; this.end = start + 1000n; } return this.next++; }}Complexity and performance
Redis lookup plus response.
Primary-key read from the database.
Local ID from a reserved block plus one insert.
Trade-offs
Hashing the long URL (MD5, take 7 chars) needs collision checks. A counter with base62 is collision-free but sequential; shuffle the ID with a reversible permutation to prevent enumeration.
301 reduces server load because browsers cache it, but you lose click analytics and cannot change the target. Most commercial shorteners use 302.
Access is almost always by primary key with no joins, so a key-value store scales simply. PostgreSQL with sharding also works and adds transactional features for custom aliases.
Variants and related techniques
Insert with a uniqueness constraint; reject if taken. Keep aliases in the same table.
Store expires_at, check on read, and delete expired rows with a background job.
Scan targets against malware and phishing lists, rate limit creation, and require auth for bulk use.
Common mistakes
- Checking the database for collisions on every write.
Fix: Use pre-allocated ID ranges so uniqueness is guaranteed without reads.
- Writing analytics synchronously on redirect.
Fix: Publish events asynchronously so analytics outages do not break redirects.
- Allowing open redirects to any scheme.
Fix: Validate that URLs are http or https and block javascript: and data: schemes.
Interview questions
How do you guarantee unique short codes across many servers?
Each server reserves a range of IDs from a coordinator (Redis INCRBY, ZooKeeper, or a database sequence) and encodes them locally. Ranges never overlap, so no collision check is needed.
How do you scale reads to 100k per second?
Add a Redis cluster for hot mappings, a CDN for the hottest links, and stateless redirect servers behind a load balancer. The database only sees cache misses.
What if the same long URL is submitted twice?
Either return a new code (simple) or look up an index on a hash of the long URL to return the existing one. The second option saves space but adds a read.
Practice problems
| Problem | Difficulty | What it trains |
|---|---|---|
| Encode and Decode TinyURL | Medium | Code generation logic. |
| Add per-link click analytics | Medium | Event pipeline and aggregation. |
| Make it multi-region | Hard | Global ID ranges and replicated reads. |