Design a URL shortener
Design a bit.ly-style URL shortener from scratch: requirements, estimates, short-code generation, a cached redirect path, 301 vs 302, and how it fails at scale.
On this page
The problem: a tiny service with a huge read path
A URL shortener turns https://shop.example.com/collections/summer-sale?utm_source=newsletter&ref=a81f into byte.ly/jU. Anyone who opens the short link is sent on to the long one. It sounds like a weekend project, and the first version is: one web server, one table, a few lines of code.
Then a celebrity shares one of your links with five million followers. Thousands of people click the same link in the same second, every click runs a database query, and the one server falls over. Links that were promised to work "forever" now return errors.
A long link becomes a short one, and the numbers behind it
- Time to design a real system: a URL shortener, like bit.ly. Paste a long link, get a short one; anyone who opens the short link is redirected to the original.
- Start every design with requirements. Must have: create a short link, redirect fast, links never break. Nice to have: custom names and click counts. And a quick estimate: say 200 new links a second, but 8,000 redirects a second.
This lesson is a first design: it applies caching, scaling out and redundancy to one small, complete system. It is the most common warm-up interview question because it fits in 30 minutes and still has real decisions in it.
Step 1: pin down the requirements
Never start drawing boxes. Start by agreeing what the system must do and how well.
| Kind | Requirement | Why it matters for the design |
|---|---|---|
| Functional | Create a short link from a long URL | The write path |
| Functional | Opening a short link redirects to the long URL | The read path: this is most of the traffic |
| Functional (nice to have) | Custom aliases (byte.ly/summer-sale), expiry dates, click counts | Each adds a small twist |
| Non-functional | Redirect in under 25 ms at the server | Rules out a database query on every click at scale |
| Non-functional | Redirects available 99.99% of the time | A broken link is broken for everyone who has it |
| Non-functional | Links never break and codes are never reused | Storage only grows; codes must be unique forever |
Out of scope: user accounts and dashboards, link previews, editing a link's destination (we revisit this in a try box).
Step 2: quick estimates
Suppose the service creates 200 links a second and serves 8,000 redirects a second on average. Those two numbers drive everything.
| Quantity | Working | Result |
|---|---|---|
| Read-to-write ratio | 8,000 ÷ 200 | 40 : 1, read-heavy |
| Links per year | 200 × 86,400 × 365 | ≈ 6.3 billion |
| Bytes per link | 7-char code + ~150-byte URL + timestamps, index and row overhead | ≈ 300 bytes |
| Storage per year | 6.3 B × 300 B | ≈ 2 TB (about 20 TB after 10 years, ×3 with replication) |
| Peak redirects | 8,000 × 3 | ≈ 24,000 / s |
| Redirect bandwidth | 8,000 × ~500-byte response | ≈ 4 MB/s: negligible |
| Hot set to cache | the 20 M most-clicked links × ~400 B with Redis overhead | ≈ 8 GB: one Redis node plus a replica |
Two conclusions. The system is read-heavy, so design effort goes into the redirect path. And the load is modest (one database takes 200 writes a second easily), but storage grows forever, which is what eventually forces you to split the data.
Codes use the 62 characters 0-9, a-z, A-Z. At 6.3 billion new links a year, how many years do 6-character codes last? And 7-character codes? Which would you pick, and why not just use 10?
Compare with our answer
- 62⁶ ≈ 56.8 billion codes: about 9 years at 6.3 B a year. Too tight for "links never break".
- 62⁷ ≈ 3.5 trillion codes: over 500 years. Plenty.
- Shorter is the whole point of the product, so don't pay for characters you don't need; but leave room for growth and for random codes, which need a sparse space to avoid collisions.
A strong answer mentions: 62ⁿ as the size of the space · links per year from the write rate · 6 chars running out within a decade · 7 chars as the sensible choice · spare space if codes are random rather than sequential.
Step 3: the API and the one table
The whole public API is two calls.
POST /v1/links
Content-Type: application/json
{"long_url": "https://shop.example.com/collections/summer-sale?ref=a81f",
"custom_alias": null, "expires_at": null}
201 Created
{"code": "jU", "short_url": "https://byte.ly/jU"}
GET /jU
302 Found
Location: https://shop.example.com/collections/summer-sale?ref=a81f
The data model is a single table, and every read is a lookup by its primary key:
CREATE TABLE links (
code VARCHAR(16) PRIMARY KEY, -- generated code or custom alias
long_url TEXT NOT NULL,
created_at TIMESTAMPTZ NOT NULL DEFAULT now(),
expires_at TIMESTAMPTZ -- NULL = never expires
);
The core: one table from short code to long URL
- The core is tiny. A table maps each short code to its long URL. To create a code, take a unique counter value and write it in base 62, using digits plus lower and upper case letters. Seven characters give over three trillion codes.
Because every query is "get the row with this key", almost any database works: Postgres or MySQL for the first few years, or a key-value store such as DynamoDB or Cassandra if you want sharding handled for you. The PRIMARY KEY constraint matters more than the brand: it is what finally guarantees that no two links ever share a code. See SQL vs NoSQL for the general trade-off.
Step 4: generating short codes
This is the decision interviewers most want to hear you reason about. A code must be short, unique forever, and ideally not guessable.
| Option | How | Good at | Weak at |
|---|---|---|---|
| Counter + base 62 | Take the next number from a counter, write it in base 62 | Never collides; codes are as short as possible | Sequential codes are guessable; the counter must be shared safely |
| Random code + insert-if-absent | Pick 7 random characters; insert, and retry on a duplicate key | No coordination at all; not guessable | Collisions grow as the space fills; each retry is another write |
| Hash of the long URL | MD5 or SHA-256 of the URL, keep the first 7 base-62 characters | The same URL always gets the same code | Truncated hashes collide often (see below); handling that turns it into option 2 |
| Pre-generated key pool | A background job fills a table of unused random codes; creates take one | Fast, no collisions at create time | One more service to run; must hand out each key exactly once |
Base 62 is just counting with 62 symbols instead of 10. The number 1,234 is 19 × 62 + 56; symbol 19 is j and symbol 56 is U, so 1,234 becomes jU.
ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
def encode(n: int) -> str:
if n == 0:
return ALPHABET[0]
digits = []
while n > 0:
n, r = divmod(n, 62)
digits.append(ALPHABET[r])
return "".join(reversed(digits))
def decode(code: str) -> int:
n = 0
for ch in code:
n = n * 62 + ALPHABET.index(ch)
return n
assert encode(1234) == "jU" and decode("jU") == 1234
Choice: a counter, handed out in blocks. If every create asked one shared counter for the next number, the counter would sit on every write and become a single point of failure. Instead, each app server reserves a block of numbers and spends them from memory.
Handing out IDs in blocks, so the counter is rarely touched
The counter can be a database row (UPDATE counters SET next = next + 1000 RETURNING next) or a key in ZooKeeper or etcd. At 200 creates a second and blocks of 1,000, it is touched every five seconds. A crashed server loses the rest of its block, which only leaves a harmless gap.
Why not just hash the URL?
A 7-character base-62 code holds about 41.7 bits. By the birthday paradox, after roughly √(62⁷) ≈ 1.9 million codes the chance that some two URLs share a truncated hash is already about 40%; at 6 billion links collisions are constant. You must check on insert and re-hash with a salt, which is a random-code scheme with extra steps. And "same URL, same code" is often unwanted: two users may want separate expiry dates and click counts.
Step 5: the redirect path
A redirect is a read: look up the code, reply with the long URL in a Location header. At 8,000 a second, with a few links far more popular than the rest, this is the textbook case for cache-aside: look in Redis first, and only on a miss read the database and fill the cache.
Most redirects are answered from the cache
- A redirect is a read: look up the code, reply with a redirect to the long URL. Because it’s so read-heavy, put a cache in front of the database. Popular links get clicked again and again, so most redirects never touch the database.
from datetime import datetime, timezone
@app.get("/<code>")
def follow(code: str):
key = f"link:{code}"
cached = redis.get(key) # 1. try the cache (~0.5 ms)
if cached == b"": # a remembered "not found"
abort(404)
if cached is not None:
return redirect(cached.decode(), code=302)
row = db.fetch_one( # 2. miss: primary-key read (~1-5 ms)
"SELECT long_url, expires_at FROM links WHERE code = %s", (code,))
now = datetime.now(timezone.utc)
if row is None or (row.expires_at is not None and row.expires_at <= now):
redis.set(key, "", ex=60) # negative cache: stops scanners hammering the DB
abort(404)
ttl = 86_400 # keep popular links for a day...
if row.expires_at is not None: # ...but never past the link's own expiry
ttl = max(1, min(ttl, int((row.expires_at - now).total_seconds())))
redis.set(key, row.long_url, ex=ttl) # 3. fill the cache
return redirect(row.long_url, code=302)
With a 90% hit ratio, the database sees about 800 reads a second plus 200 writes: comfortable for one primary. The average redirect costs roughly 0.9 × 0.5 ms + 0.1 × 5.5 ms ≈ 1 ms of lookup time, well inside the 25 ms target.
301 or 302?
The HTTP status code you redirect with is a real design decision, and a favourite follow-up question.
| Status | Meaning to the browser | Good at | Weak at | Use when |
|---|---|---|---|---|
| 301 Moved Permanently | "Remember this; go straight there next time" | Repeat clicks from the same browser never reach you: less load | You stop seeing those clicks, and you cannot change or disable the link for anyone who has cached it | Links are permanent and you don't count clicks |
| 302 Found (or 307) | "Go there this time; ask me again next time" | Every click reaches you: counts, expiry and abuse takedowns all work | Every click costs you a request | Click counts, expiry or takedowns matter (the usual case) |
Choice: 302. Click counts are on the wish list, links can expire, and a shortener will be used for phishing, so you need the power to switch a link off. The extra traffic is what the cache is for. You can still let a CDN hold a 302 for a short time with Cache-Control: max-age=60 to absorb a viral spike, trading up to a minute of delay on a takedown.
Step 6: scale and keep it running
Enough app servers for the peak, plus a spare
- Eight thousand redirects a second needs several app servers behind the load balancer. Add one spare, so a crash doesn’t hurt. The database barely notices, thanks to the cache.
The finished design, piece by piece:
- Load balancer in front, with a health check, so a dead app server stops receiving traffic within seconds.
- Stateless app servers. Plan conservatively at 1,000–2,000 redirects a second each, so the 24,000 / s peak needs 12–24 servers, plus one spare (N+1). They hold no state except an ID block they can afford to lose.
- Redis with a replica for the hot links. If it fails, redirects get slower but stay correct, because cache-aside falls back to the database.
- The database with a replica in another zone for failover; redirects may read from replicas, since a link a second late to appear is fine.
- Later, sharding. Load never forces it, but 20 TB after ten years does. Shard by a hash of
code: every lookup carries the code, so each request goes to exactly one shard (sharding). This is where a key-value store such as DynamoDB or Cassandra earns its place, since it shards and replicates for you; with Postgres or MySQL you split the data yourself.
Click counts without slowing redirects
Never write to the database on every redirect: that turns 8,000 cheap reads a second into 8,000 writes. Instead, the app server emits a small click event (code, time, country) to a log or message queue such as Kafka and returns the redirect immediately. A separate consumer aggregates counts per link per hour and writes them in batches. Counts become a few seconds late, which nobody minds.
Where this breaks
Two smaller traps worth naming:
- Custom aliases can collide with generated codes. If someone reserves
abc, a counter will eventually produceabctoo. Either the generator retries when the insert fails, or aliases live in a separate space the generator never produces (for example, aliases must be at least 8 characters, or contain a-). - Abuse. Shorteners hide phishing links. Rate-limit creates, check new URLs against a blocklist such as Google Safe Browsing, and keep the power to disable a code (another reason for 302).
What not to build
Resist adding every box from the course. No queue on the create path: a create is one 300-byte insert, so do it synchronously and return the code at once. No sharding on day one: 2 TB a year fits one database for several years; choose the shard key now, shard later. No microservices: one stateless service with two endpoints is the right size.
In the interview
A candidate proposes: "Codes are the first 7 characters of MD5(long URL). We insert with INSERT ... ON CONFLICT DO UPDATE SET long_url = EXCLUDED.long_url. Redirects return 301 with no expiry. Each redirect runs UPDATE links SET clicks = clicks + 1." List every problem.
Compare with our answer
- Truncated MD5 collides within a few million links, and
ON CONFLICT DO UPDATEsilently overwrites someone else's link. UseDO NOTHING, detect the conflict, pick a new code. - 301 with no expiry: browsers cache it, so clicks go uncounted and a phishing link can't be fully disabled.
- A write per redirect turns 8,000 reads a second into 8,000 updates, and a viral link makes them all fight over one row lock. Queue click events and aggregate in batches.
- No cache on the redirect path.
A strong answer mentions: hash collisions at this scale · overwrite on conflict loses data · 301 caching defeats counting and takedowns · per-click writes create a hot row · an async click pipeline · a cache in front of the database.
Marketing now wants two things: links whose destination can be edited after creation, and a dashboard of clicks per link per hour by country. What changes in your design?
Compare with our answer
- 302, not 301: a cached 301 keeps sending old visitors to the old destination.
- On edit, update the row, then delete the cache key and purge the CDN; keep a TTL as a safety net against a racing reader.
- Clicks: emit
{code, ts, country}events to Kafka; a consumer aggregates per(code, hour, country); the dashboard reads only aggregates. - Ownership: edits need accounts and an
owner_idcolumn.
A strong answer mentions: 302 not 301 · delete the cache key on edit · CDN purge · TTL as a safety net · asynchronous click events · pre-aggregated counts per hour.
Where to go next
For the same recipe at full interview length on a close cousin (a Pastebin, which stores text and so adds object storage), read The design interview recipe. Next in this module: design a chat app.
- Requirements: create, redirect (< 25 ms, 99.99%), never break or reuse a code; nice to have: aliases, expiry, click counts.
- Numbers: 200 creates/s vs 8,000 redirects/s (40:1); 6.3 B links/year ≈ 2 TB; hot set ≈ 8 GB.
- Codes: 62⁷ ≈ 3.5 T; counter handed out in blocks of 1,000, scrambled so codes aren't sequential; or random codes with insert-if-absent.
- Never truncate a hash without a collision check; the
PRIMARY KEYoncodeis the final guarantee. - Redirect path: cache-aside in Redis, TTL capped at link expiry, negative caching for unknown codes.
- 302 over 301 when you count clicks, expire links or need takedowns; a CDN can still cache the 302 briefly.
- Clicks: async events → queue → batch aggregation; never a write per redirect.
- Scale: stateless app servers N+1 behind a load balancer; replicas for failover; shard by hash of
codewhen storage demands it.
1. A shortener serves 8,000 redirects and 200 creates per second. Where should most of the design effort go?
It is read-heavy, so caching and redundancy on the redirect path matter most. 200 inserts a second is easy for one database, and clicks can be recorded asynchronously.
2. A team generates codes from the first 7 base-62 characters of MD5(long URL), with no duplicate check. What happens as the service grows?
Truncating a hash throws most of it away. By the birthday paradox, collisions are likely after a few million links, so a duplicate check (and a retry with a salt) is required.
3. Why do app servers reserve blocks of 1,000 IDs from the counter instead of one ID per create?
Blocks take the counter off the hot path. A crashed server's unused IDs are simply skipped; gaps are harmless. The counter must still be durable, or it may reissue blocks.
4. The product needs click counts and the ability to disable phishing links. Which redirect status fits?
A 301 may be cached by the browser indefinitely, so later clicks never reach you: you can't count them or block the link. A 302 is re-requested each time; a short CDN cache can still absorb spikes.
5. Bots request millions of random codes that were never created. Each one misses Redis and queries the database. What helps most?
Lookups for codes that don't exist can never become cache hits. Stopping them before the database (rate limits, Bloom filter, short negative caching) fixes the leak; replicas only pay for it.
6. How long should a cached redirect live in Redis for a link that expires in 10 minutes?
Cap the TTL at the link's remaining lifetime. Otherwise the cache keeps redirecting after the link should have died, and relying on a manual delete fails the first time a delete is missed.
7. After ten years the links table holds about 20 TB. How should it be split?
Every redirect is a lookup by code, so hashing the code sends each request to exactly one shard and spreads data evenly. Date-based shards put all new writes, and the hottest reads, on one shard.
Score 60% or more and the lesson is marked complete.