CS Fundamentals Trainer · Guides
Design a URL shortener
Short codes, 301 vs 302, collisions, caching, abuse, and counting clicks without slowing the redirect.
23 min read
A URL shortener turns https://example.com/some/very/long/path?with=parameters into https://sho.rt/Xk3b9Qa and sends visitors who open the short link to the long one. It is a favourite system design question because the idea fits in one sentence, and yet it touches almost everything: ID generation, the choice of database, caching, HTTP semantics, abuse, and analytics.
1. Pin down the problem
Start by agreeing on what the service must do, and what it may leave out.
- Create: given a long URL, return a short one. Optionally let the user choose the alias (
sho.rt/summer-sale) and an expiry date. - Redirect: given a short code, send the visitor to the long URL, fast.
- Maybe: click statistics, accounts, editing or deleting links, QR codes.
Then the qualities that decide the design:
- Reads dwarf writes. A link is created once and followed many times. Ratios of 100 reads to 1 write are a common assumption.
- Redirects must be fast and available. A slow redirect is felt by every visitor on every click. It is better to serve an old destination than to show an error.
- Codes must be short, unique, and hard to guess if links are meant to be private-ish.
- Links live a long time. Printed on paper or buried in old emails, they must keep working for years.
The write path can be slow and careful. The read path must be fast and almost always up. Design them separately.
2. Back-of-the-envelope numbers
Assume 100 million new links a month and 100 redirects for every link created. These are round numbers, so we can check each step.
| Quantity | Calculation | Result |
|---|---|---|
| New links per second | 100 million / (30 × 86 400 s) | about 39 per second |
| Redirects per second | 39 × 100 | about 3 900 per second on average |
| Peak redirects | assume 10 × the average | about 39 000 per second |
| Links in 5 years | 100 million × 12 × 5 | 6 billion |
| Storage | 6 billion × about 500 bytes (URL, code, dates, owner) | about 3 TB |
What these numbers say:
- 39 writes per second is tiny. Any database handles it. The write path is not the hard part.
- 3 900 reads per second is modest, 39 000 at peak is not. That is where a cache and a good read path pay off.
- 3 TB is a floor, not the bill. It counts only the rows, and the 500 bytes per row (mostly the URL itself) is an assumption: measure your own average. The primary key index adds a few percent, every replica is a full extra copy (three copies is about 9 TB), and a database should never run close to full. Plan for 10 TB or more of provisioned disk.
- It is still small enough for one primary, with replicas for reads. Sharding is something you plan for, not a day-one need.
How long must the code be?
A code made of the 62 characters 0-9, A-Z and a-z ("base62") has 62^n possibilities for n characters:
| Length | Possible codes |
|---|---|
| 6 | 62^6 = 56 800 235 584 (about 57 billion) |
| 7 | 62^7 = 3 521 614 606 208 (about 3.5 trillion) |
Six billion links fit in 6 characters, with room to spare. Seven characters give a safety margin of almost 600 times, so 7 is the usual choice. It is short enough to type, and long enough that guessing a valid code is hopeless.
3. The two operations
A small API is enough:
POST /api/links { "url": "https://example.com/a/very/long/path", "alias": "optional", "expires_at": "optional" }
→ 201 { "code": "Xk3b9Qa", "short_url": "https://sho.rt/Xk3b9Qa" }
GET /Xk3b9Qa → redirect to the long URL (or 404 if unknown)
Diagram: Creating a link and following it
301 or 302?
The redirect status code is a real design decision, not a detail. Both are defined in RFC 9110, section 15.4 [1].
- 301 Moved Permanently tells browsers and caches that the short link will always lead there. They may remember it and skip your server on later visits. That saves you traffic, but you lose the click count (the request never arrives), and you cannot change the destination for people who already cached it.
- 302 Found (or 307, which also forbids changing the request method) says "for now". The visitor asks you every time, so you can count clicks, change the destination, expire the link, and block it if it turns out to be malicious.
There is also a search engine side. A 301 tells crawlers that the destination is the real address, so links that point at your short URL are credited to it, and it is a common reason marketing teams ask for a 301. A 302 may leave the short URL in the index for a while. Google says that redirects do not lose ranking signals [7], so this is a point in favour of 301 and not a disaster for 302.
If you offer statistics, editing, or expiry, use a temporary redirect. Choose 301 only for links that really are permanent and where you do not count clicks. Even then, remember that a cached 301 is very hard to take back.
4. Making the code
This is the part interviewers like to dig into. There are four common ways, each with a catch.
| Approach | How it works | Catch |
|---|---|---|
| Hash and cut | Hash the long URL (MD5, SHA-256), keep the first 7 characters in base62 | Different URLs can collide after cutting, so you must check and retry. The same URL always gives the same code, which is nice for deduplication and bad when two users want separate statistics |
| Random code | Draw 7 random base62 characters | Collisions are rare but real. You need a uniqueness check, which the database does for free |
| Counter, then base62 | Take the next number from a counter and write it in base62 | No collisions at all, but codes are guessable and enumerable (1, 2, 3...), and the counter is a shared resource |
| Snowflake-style ids | A 64-bit number made of a timestamp, a machine number and a per-millisecond sequence, then written in base62 | No coordination and no collisions, but the code is 10 or 11 characters and roughly time-ordered, so it is neither short nor secret |
| Pre-made key ranges | A key service hands each app server a block of numbers (say 1 000 000 at a time) to use up locally | Fast and collision-free, but still sequential unless you scramble the numbers. A server crash wastes the rest of its block, which is fine: we have trillions |
A simple, solid choice for a first version is random codes with a unique key in the database. Let the database be the judge of uniqueness.
How often will random codes collide?
If there are already N codes stored out of 62^7 possible ones, a new random code hits an existing one with probability N / 62^7. With 6 billion links stored:
6 000 000 000 / 3 521 614 606 208 ≈ 0.0017 (about 0.17 %)
About one insert in 600 needs a second attempt at the very end of the five years, and almost none at the start. So the rule is simple: try the insert, and if the code already exists, draw another. After a few failed attempts, give up with an error (or switch to a longer code). This is the birthday problem in a friendly form: it only bites when you compare many codes with each other, not when each new code meets a table that already exists [2].
import secrets
ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
def random_code(length=7):
# secrets (not random) so that codes cannot be predicted
return "".join(secrets.choice(ALPHABET) for _ in range(length))
def create_link(db, long_url):
for _ in range(5):
code = random_code()
row = db.execute(
"INSERT INTO links (code, long_url) VALUES (%s, %s) "
"ON CONFLICT (code) DO NOTHING RETURNING code",
(code, long_url),
).fetchone()
if row: # the code was free and is now ours
return code
raise RuntimeError("could not find a free code")
The unique key makes the check and the insert one step: the primary key guarantees that only one of two inserts of the same code can succeed, and ON CONFLICT DO NOTHING turns the loser into an empty result instead of an error. RETURNING gives back only the rows that were really inserted [3], so an empty result means "try another code". Checking with a SELECT first and inserting afterwards would leave a gap between the two statements that two requests can slip through.
Counters and base62
If you prefer numbers, you need to write them in base62. This is the conversion in four languages (pick a language on the tabs; your choice is remembered):
ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
def encode(n):
if n == 0:
return ALPHABET[0]
digits = []
while n:
n, rest = divmod(n, 62)
digits.append(ALPHABET[rest])
return "".join(reversed(digits))
const alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
func Encode(n uint64) string {
if n == 0 {
return string(alphabet[0])
}
var buf [11]byte // the largest uint64 needs 11 base62 digits
i := len(buf)
for n > 0 {
i--
buf[i] = alphabet[n%62]
n /= 62
}
return string(buf[i:])
}
const ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
// n is a BigInt, so ids above 2^53 stay exact
function encode(n) {
if (n === 0n) return ALPHABET[0];
let out = "";
while (n > 0n) {
out = ALPHABET[Number(n % 62n)] + out;
n /= 62n;
}
return out;
}
public static string Encode(ulong n)
{
const string alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
if (n == 0) return alphabet[0].ToString();
var chars = new char[11]; // the largest ulong needs 11 base62 digits
int i = chars.Length;
while (n > 0)
{
chars[--i] = alphabet[(int)(n % 62)];
n /= 62;
}
return new string(chars, i, chars.Length - i);
}
Some values to check an implementation against: encode(0) is 0, encode(61) is z, encode(62) is 10, and encode(62^7 - 1) is zzzzzzz.
A plain counter gives 1, 2, 3: anyone can walk through all your links. If links must not be guessable, either use random codes, or scramble the number first with a reversible mix (multiply by a large odd number that shares no factor with 62^7, modulo 62^7). Do not use "security by obscurity" for truly private content: a shortener is not an access control system. Put real secrets behind a login.
Snowflake-style ids
Systems that must hand out unique ids from many machines without a shared counter often use the Snowflake layout, which Twitter made popular [6]. A 64-bit number is cut into three parts: 41 bits of milliseconds since a start date of your choice (about 69 years), 10 bits for the machine (1 024 machines), and 12 bits for a sequence number (4 096 ids per millisecond per machine). Every machine can make ids on its own, the ids rise with time, and they never collide as long as no two machines share a number and no clock goes backwards.
import threading
import time
EPOCH_MS = 1_700_000_000_000 # your own start date, so the 41 bits last longer
class Snowflake:
def __init__(self, machine_id):
assert 0 <= machine_id < 1024
self.machine_id = machine_id
self.last_ms = -1
self.seq = 0
self.lock = threading.Lock()
def next(self):
with self.lock:
now = int(time.time() * 1000)
if now < self.last_ms:
raise RuntimeError("the clock went backwards") # refuse rather than risk a duplicate
if now == self.last_ms:
self.seq = (self.seq + 1) & 4095
if self.seq == 0: # 4 096 ids this millisecond: wait
while now <= self.last_ms:
now = int(time.time() * 1000)
else:
self.seq = 0
self.last_ms = now
return ((now - EPOCH_MS) << 22) | (self.machine_id << 12) | self.seq
For a shortener this is the wrong tool, for two reasons. The number is large, so its base62 form has 10 or 11 characters instead of 7, which is long for a "short" link. And it starts with a timestamp, so anyone can tell when a link was made and guess its neighbours. Use it where unique ids matter more than short or secret ones (for example, the internal primary key of a link or a click), and keep the public code separate. The same goes for UUIDs and ULIDs: unique, but too long.
Custom aliases
For sho.rt/summer-sale, accept the user's text but treat it like any other code: same unique key, same atomic insert, and a clear "that name is taken" answer on conflict. Restrict the allowed characters and length, and keep a list of reserved words (api, admin, login, static...) so a user cannot shadow your own routes.
5. Where the data lives
One table is enough:
CREATE TABLE links (
code text PRIMARY KEY, -- the unique key is also the index we read by
long_url text NOT NULL,
owner_id bigint, -- null for anonymous links
created_at timestamptz NOT NULL DEFAULT now(),
expires_at timestamptz -- null means never
);
The only query on the hot path is "give me the row for this code", a lookup by primary key. That fits any relational database, and it fits key-value stores (DynamoDB, Cassandra, Redis) just as well, because there are no joins and no range queries. Both are fine answers. The honest reasons to choose:
- Relational (PostgreSQL, MySQL): you probably have one already, you get transactions and constraints, and 3 TB with a primary key index is routine. Choose this unless you have a reason not to.
- Key-value store: easier to spread over many machines when you outgrow one, and built for exactly this access pattern. The price is giving up the flexible queries you will want later for reports and abuse handling.
Codes are case-sensitive: check the collation
Xk3b9Qa and xk3b9qa are different codes in base62, and the database must agree. PostgreSQL compares text exactly by default, so the table above is correct there. MySQL and SQL Server use case-insensitive collations by default, so the two codes would count as the same key: lookups would find the wrong row, and the unique key would reject codes that are really free. In MySQL, declare the column with a binary collation (code VARCHAR(11) CHARACTER SET ascii COLLATE ascii_bin). In any database, write a test that stores aB and Ab and expects two rows.
If your store is case-insensitive and you cannot change it, use an alphabet without upper case (36 characters: 0-9a-z). Then 36^7 is only 78 billion, which would make collisions common at 6 billion links (about 8 %), so move to 8 characters (2.8 trillion).
When one database is not enough
Reads are easy to scale: add replicas, and put a cache in front (next section). If writes or storage outgrow one machine, split the table by code. Because lookups always arrive with the full code, you can shard by a hash of the code, and every request goes to exactly one shard. Use consistent hashing so that adding a shard moves only a small share of the data.
6. Making redirects fast
A redirect is a read of one small value by key, repeated for the same popular links over and over. That is the ideal case for a cache.
Diagram: The redirect path, from fastest to slowest
- Cache code → long URL in Redis (or Memcached). A small number of links gets most of the clicks. A rule of thumb is that the hottest 20 % of links bring about 80 % of the requests, and real traffic is usually even more lopsided, so a cache holding a small fraction of all links can answer the large majority of requests. Measure your own hit ratio and size the cache until it reaches the 95 % used below. Evict with least-recently-used [5]. See caching strategies for patterns and failure modes.
- Cache misses for unknown codes too, briefly (a few seconds to a minute). Bots love to probe random codes; without this every probe goes to the database.
- A CDN can serve redirects if you use a cacheable status and a short
Cache-Control. The price is the same as with 301: the edge answers without telling you, so your click counts are missing. Many services choose to keep clicks counted and skip the CDN for redirects. - Keep the handler tiny. Look up, set the
Locationheader, return. No sessions, no templates, no extra queries.
Rough check: if the cache answers 95 % of the 39 000 peak requests per second, the database sees about 2 000 per second. A single primary-key lookup is cheap, so a modest database server (or a couple of replicas) copes.
7. Expiry, deletion, and codes that come back
- Expiry: on lookup, compare
expires_atwith the current time and answer 410 Gone (or 404) if the link is over. Put the same time limit on the cache entry, so a cache cannot keep an expired link alive. A nightly job can delete old rows in batches to keep the table small. - Deleting: remove the row and delete the cache key. A visitor with an old cached 301 still gets through, which is one more reason to avoid 301 for links that can be deleted.
- Re-using codes: do not give an expired code to someone else too soon. Old emails and printed pages still point to it, and the new owner would receive visitors meant for somebody else. With trillions of codes there is no need to recycle.
8. Abuse and safety
A shortener is a perfect tool to hide a malicious link, so safety is part of the design, not an extra.
- Accept only
httpandhttpsURLs. A storedjavascript:ordata:URL turns your redirect into an attack. Parse the URL properly, do not just check the start of the string. - Do not redirect to yourself, or to other shorteners, which creates loops and chains.
- Check destinations against a list of known bad sites (for example Google Safe Browsing) when a link is created, and again later, because a harmless page can be swapped for a harmful one. Keep the ability to disable a code at once.
- Rate-limit creation per account and per IP, or your service becomes a free spam relay. See design a rate limiter.
- Mind open redirect rules. Your whole product is an open redirect by design, so the usual advice (never redirect to a user-supplied URL) cannot apply as is. The protections above, plus an interstitial "you are leaving..." page for flagged links, are the substitute [4].
9. Counting clicks without slowing the redirect
If you want statistics, the redirect must not wait for them. Instead of updating a counter in the database for each click (a write on the hottest path), put a small event on a queue and answer the visitor immediately:
Diagram: Clicks are counted after the visitor has left
Workers add up the events in batches (counts per code per hour), and the dashboard reads the totals. If the queue is down for a moment, you lose a few counts and not a single redirect. That is the right trade for this feature. Count approximately and cheaply; do not make the product depend on your analytics.
Expect a lot of the traffic to be machines. Crawlers, security scanners, and the link-preview fetchers of chat and social apps (they open a link the moment someone pastes it) all follow short links, and a browser may prefetch one. Record the User-Agent and whether the request was a GET or HEAD, filter known bots in the worker, not on the hot path, and report "human clicks" separately from "all requests". Otherwise the first message you share looks like a viral link.
10. Testing, monitoring, and reliability
Tests worth writing
- The code functions.
encode(0)is0,encode(61)isz,encode(62)is10,encode(62^7 - 1)iszzzzzzz. Codes from the generator have the right length and only valid characters. - Collisions. Replace the random generator with one that returns the same code twice, and check that the second create retries and succeeds. Replace it with one that always collides, and check that you get a clean error after the fifth try.
- Concurrency, against a real database. Start 50 inserts of the same code at once. Exactly one must win. Mocks cannot test this: the guarantee comes from the unique key.
- Case. Store
aBandAband read both back (see the collation note above). - URL validation. Accept
https://example.com/a?b=c. Rejectjavascript:alert(1),data:text/html,...,ftp://..., a URL pointing at your own domain, over-long URLs, and strings with control characters. - The redirect. Right status code and
Location, 404 for an unknown code, 410 for an expired one, and no redirect for a disabled link.
What to watch
| Signal | Why |
|---|---|
| Redirect latency (p50, p99) and error rate | The product is the redirect. Alert on the p99, not the average |
| Cache hit ratio | A fall means a deploy changed the keys, or a scan is in progress |
| Share of 404s | A rise is a scanner or bot probing codes |
| Create retries (collisions) per 1 000 creates | The share is about N / 62^7, so a rise is a sign that the space is filling or the generator is biased |
| Click queue lag | Counts are late, never the redirect |
| Disk used, per replica | Growth is steady, so alert early |
| Flagged and disabled links | How well the abuse process works |
What happens when something fails
- Redis is down: read from the database, a little slower. Set a short timeout on the cache so a sick cache cannot slow every redirect.
- A replica is down or lagging: send reads to the primary or another replica; for a code that is "not found" on a replica, check the primary once before answering 404 (a link created a second ago).
- The primary is down: redirects keep working from replicas and caches. Creating links stops until failover finishes. This is the failure to rehearse.
- The click queue is down: redirects are not affected; clicks in that window may be lost, or buffered in memory if you choose.
- A bad link slips through: you need an admin action that disables a code and deletes its cache key within seconds.
- Backups: the links table is the whole product. Back it up, and restore it somewhere once to prove that it works.
11. Questions interviewers like to add
"What if two users shorten the same URL?"
Both designs are valid. Give each user their own code (simple, and they get separate statistics), or deduplicate by hashing the URL and returning the existing code (saves space, but statistics and ownership get tangled). Say which one you chose and why.
"How do you handle a viral link?"
One code receiving a huge share of traffic is a hot key. A CDN or an in-process cache on every app server absorbs it, because the value is tiny and changes rarely. No shard should be asked for the same row 50 000 times a second.
"What happens when the cache is empty after a restart?"
All traffic hits the database at once. Warm the cache from the most-clicked links first, or let the first request for each code fill it, and make sure only one request per code goes to the database at a time (see the stampede section of the caching guide).
"How would you make it work in several regions?"
Reads are easy to replicate: put read replicas and caches near the visitors. Writes can go to one region, since there are only about 39 per second. Newly created links need a moment to appear in other regions, so it is common to serve the creator from the write region, or to fall back to the primary when a replica says "not found".
12. Things to mention in an interview
- Start with requirements and numbers, and say that the read path matters more than the write path.
- Call out 301 versus 302, and tie it to analytics.
- Compare the ID options and say why you pick one; mention the collision probability and the atomic insert.
- Show the cache in front of a key-value style lookup, and talk about hot keys.
- Bring up abuse before you are asked.
- Keep analytics off the redirect path, and expect bots in the numbers.
- Say how you would test it, what you would alert on, and what happens when Redis or the primary is down.
Quick recap
- Reads are about 100 times more common than writes, so optimise the redirect path.
- A 7-character base62 code gives 3.5 trillion possibilities: enough for years.
- Use a temporary redirect (302 or 307) if you count clicks or allow edits.
- Random codes with a unique key and an atomic
INSERT ... ON CONFLICTare simple and safe; counters are collision-free but guessable. - One table keyed by code is enough. Cache it, replicate it, and shard by code only when you must.
- Validate URLs, rate-limit creation, and keep a kill switch.
- Count clicks asynchronously.
Sources
- IETF, RFC 9110, section 15.4: Redirection 3xx. The meaning of 301, 302, 307 and 308, and which may be cached.
- Wikipedia, Birthday problem. Why collisions appear sooner than intuition says when codes are compared with each other.
- PostgreSQL documentation, INSERT: the ON CONFLICT clause.
DO NOTHING, andRETURNINGgiving only the rows actually inserted. - OWASP, Unvalidated Redirects and Forwards Cheat Sheet.
- Redis documentation, Key eviction. Least-recently-used and other policies for the redirect cache.
- Wikipedia, Snowflake ID. The 41/10/12 bit layout.
- Google Search Central, Redirects and Google Search. How crawlers treat permanent and temporary redirects.
Practise this topic: System Design System Design › Case studies