Design a URL Shortener
A full worked design: requirements, estimates, API, data model, base62 id encoding, redirect path, caching, scaling, and trade-offs such as 301 versus 302.
intermediate45 min#system-design#url-shortener#base62#id-generation#worked-example
Prerequisites: A Framework for System Design, Caching Strategies, Databases at Scale
Why it matters
The URL shortener is the "hello world" of system design. It is small enough to finish in an interview, yet it touches every part of the framework: requirements, estimation, API, data model, id generation, caching, and scaling. Working through it end to end shows you how the generic ideas from the earlier lessons combine in one concrete system.
Intuition
A shortener is a giant dictionary. The key is a short code like aZ3k9; the value is the long URL. Creating a short link means inventing a fresh key and storing the pair. Following one means looking the key up and redirecting. Everything interesting is in two questions: how do we invent unique short keys without collisions, and how do we make a lookup-heavy system fast and durable?
How it works
1. Requirements
Functional: create a short link for a long URL; redirect a short link to the original; optionally custom aliases and expiry. Non-functional: redirects must be very fast and highly available (a dead link is a broken page for someone else), codes must be unique, and links should not be easily guessable if they are private. Out of scope for now: analytics dashboards, user accounts.
2. Estimates
Assume 100 million new links per month and a read-to-write ratio of 100 to 1.
- Writes: 100 million per month is about 40 per second on average (a month is about 2.6 million seconds).
- Reads: 100 times that, roughly 4,000 per second on average, with peaks several times higher.
- Storage: if each record is about 500 bytes, 100 million records per month is about 50 GB per month, or roughly 3 TB over five years before replication.
- Code length: with 62 characters, 6 characters give about 56.8 billion codes and 7 give about 3.5 trillion. Seven is plenty for decades of growth.
This is a read-heavy system with modest write volume and a small total dataset, so caching helps a lot and a single sharded store is realistic.
3. API
POST /links body: long_url, optional alias, optional expires_at
returns: short_code, short_url
GET /{code} returns: 301 or 302 redirect with Location header
404 if unknown, 410 if expired
301 versus 302. A permanent redirect (301) may be cached by browsers, which reduces your load but means you stop seeing those clicks and cannot change the target. A temporary redirect (302) sends every click through you, which keeps analytics and edits possible at the cost of more traffic.
4. Data model
One table or collection: code (primary key), long_url, created_at, expires_at, optional owner_id. The dominant access pattern is a point lookup by code, which fits a key-value store or a relational table with a primary-key index. Because lookups are by key, the shard key is the code itself.
5. Generating the code
Options:
- Hash the URL and take the first few characters. Simple and gives the same code for the same URL, but different URLs can collide, so you must check and retry.
- Random code with a uniqueness check. Not guessable, but needs a retry on collision.
- Counter plus base62. Allocate a unique integer id and encode it in base 62 (digits, lowercase, uppercase). No collisions by construction and short codes. The downside is that sequential ids are guessable and enumerable. If that matters, shuffle the bits or use a keyed permutation of the id before encoding.
The counter must work across many servers. Common approaches: a central sequence service handing out ranges (each app server takes a block of, say, 1,000 ids and uses them locally, so the counter is touched rarely), or a time-and-machine-based id scheme. Range allocation wastes some ids on a crash, which is harmless.
Here is the counter-plus-base62 option encoding id 125, the first id the code below hands out. Repeated division by 62 produces digits from the right.
Encoding 125 in base 62. Each division peels off the last digit, so digits come out in reverse and must be flipped at the end.
6. High-level design
client --> load balancer --> app servers --> cache (code -> url)
| | miss
| v
+-------> database (sharded by code)
|
id allocator (hands out id ranges)
Read path (the hot one): check the cache; on a miss, read the database, fill the cache, return the redirect. Link mappings rarely change, so a long TTL with LRU eviction works well, and a small cache holds the popular head of the distribution.
Write path: validate the URL, take the next id, encode it, store the pair, return the short URL.
7. Deep dives and trade-offs
- Availability of the read path. Redirects dominate, so replicate the database and cache across zones. Writes can degrade independently.
- Expiry. Check
expires_aton read and clean up in a background job. - Abuse. Rate limit link creation and scan targets for malicious URLs.
- Custom aliases. Insert with a unique constraint and return a conflict if taken.
- Deleting and reusing codes. Avoid reusing a code quickly; an old link floating around should not suddenly point somewhere new.
| Operation | Time | Notes |
|---|---|---|
| Encode id to base62 | O(log_62 n) | About 7 steps for trillions of ids |
| Redirect (cache hit) | O(1) | One cache lookup |
| Redirect (cache miss) | O(1) | One indexed database lookup |
| Create link | O(1) | Allocate id, encode, insert |
Code: base62 encoding and a tiny shortener
The id allocator here is a simple counter; in production it would hand out ranges from a shared service.
ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
def encode(n):
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):
n = 0
for ch in code:
n = n * 62 + ALPHABET.index(ch)
return n
class Shortener:
def __init__(self, start=125):
self.next_id = start
self.by_code = {}
self.by_url = {}
def shorten(self, url):
if url in self.by_url: # same URL gets the same code
return self.by_url[url]
code = encode(self.next_id)
self.next_id += 1
self.by_code[code] = url
self.by_url[url] = code
return code
def resolve(self, code):
return self.by_code.get(code)
for n in [0, 61, 62, 125, 1_000_000_000]:
print(n, "->", encode(n), "->", decode(encode(n)))
print("62^6 =", 62 ** 6, "| 62^7 =", 62 ** 7)
s = Shortener()
a = s.shorten("https://example.com/a/very/long/path?x=1")
b = s.shorten("https://example.com/other")
again = s.shorten("https://example.com/a/very/long/path?x=1")
print(a, b, again == a)
print(s.resolve(b), s.resolve("zzz"))const ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
function encode(n) {
if (n === 0) return ALPHABET[0];
const digits = [];
while (n > 0) {
digits.push(ALPHABET[n % 62]);
n = Math.floor(n / 62);
}
return digits.reverse().join("");
}
function decode(code) {
let n = 0;
for (const ch of code) n = n * 62 + ALPHABET.indexOf(ch);
return n;
}
class Shortener {
constructor(start = 125) {
this.nextId = start;
this.byCode = new Map();
this.byUrl = new Map();
}
shorten(url) {
if (this.byUrl.has(url)) return this.byUrl.get(url); // same URL, same code
const code = encode(this.nextId++);
this.byCode.set(code, url);
this.byUrl.set(url, code);
return code;
}
resolve(code) {
return this.byCode.has(code) ? this.byCode.get(code) : null;
}
}
for (const n of [0, 61, 62, 125, 1_000_000_000]) {
console.log(n, "->", encode(n), "->", decode(encode(n)));
}
console.log("62^6 =", 62 ** 6, "| 62^7 =", 62 ** 7);
const s = new Shortener();
const a = s.shorten("https://example.com/a/very/long/path?x=1");
const b = s.shorten("https://example.com/other");
const again = s.shorten("https://example.com/a/very/long/path?x=1");
console.log(a, b, again === a ? "True" : "False");
console.log(s.resolve(b), s.resolve("zzz") === null ? "None" : "found");Both versions print:
0 -> 0 -> 0
61 -> Z -> 61
62 -> 10 -> 62
125 -> 21 -> 125
1000000000 -> 15FTGg -> 1000000000
62^6 = 56800235584 | 62^7 = 3521614606208
21 22 True
https://example.com/other None
Id 125 is 21 because 125 = 2 * 62 + 1. A billion ids still fit in just six characters. Decoding the encoded value always returns the original id, which is the property that makes the scheme collision-free.
Common pitfalls
- Sequential ids that leak information. Anyone can walk
1, 2, 3...and discover every link, and learn your volume. Permute the id if links are private. - Hash truncation without collision handling. Two URLs can share a prefix. Check for conflicts or avoid hashing.
- Forgetting that redirects dominate. Optimize and protect the read path; creation can be slower and rate limited.
- Open redirect and abuse. Shorteners are used to hide phishing links. Validate, scan, and rate limit.
- Treating 301 as free. It reduces load but removes your ability to count clicks or change the destination.
- Single points of failure in the id allocator or the cache. The read path should survive either being down.
Practice
How many characters do we need? easy
Hint
Compare the total number of links you expect against 62 to the power of length.
Show solution
Say 100 million links per month for ten years is about 12 billion. 62^6 is about 56.8 billion, which already covers that, and 62^7 gives roughly 3.5 trillion for headroom. Choose 7 so growth, wasted id ranges, and sparse permutations are all comfortable.
Support custom aliases medium
Hint
What database feature guarantees an alias is not taken twice?
Show solution
Insert the alias as the primary key with a unique constraint. If the insert fails, return a conflict error to the caller. Reserve a character pattern or length range for generated codes so a custom alias can never collide with a future generated one.
Make codes unguessable medium
Hint
You want uniqueness of a counter but randomness of appearance.
Show solution
Apply a reversible, keyed permutation to the counter value (for example a few rounds of a Feistel-style mixing of its bits) and base62-encode the result. Uniqueness is preserved because the mapping is one-to-one, and the codes no longer look sequential. Keep the key secret.
Scale reads 10x hard
Hint
Where does the load land first: cache, database, or app tier?
Show solution
Add app servers behind the load balancer (they are stateless), grow and replicate the cache, and add database read replicas. Cache hit rate matters most: the popular links are a small share of all links, so even a modest cache absorbs most reads. Use a CDN or edge caching for the very hottest redirects if you use 301 or can tolerate caching.
Interview questions
- How do you generate short codes? Counter plus base62 for guaranteed uniqueness; random with a collision check or a hash with collision handling as alternatives. State the trade-offs, especially guessability.
- 301 or 302? 301 is cacheable and cuts load but hides clicks and freezes the target; 302 keeps every click visible and flexible at higher cost.
- How do you scale it? Cache the hot read path, replicate the database, shard by code, and allocate ids in ranges.
- What are the failure modes? The id allocator, cache, or database being unavailable; handle with replication, id ranges held locally, and serving redirects from cache when the database is slow.
Interviewers look for: a clear estimate showing the system is read-heavy, a collision-free id strategy, and awareness of 301 versus 302 and abuse.
Quick check
Which property makes the counter-plus-base62 approach collision-free?
Finished this lesson?
Further resources
- URL shortening (Wikipedia) (article)
- Cache (computing) (Wikipedia) (article)
- The System Design Primer (article)