a link wrapper
Twitter wraps every link posted in a tweet with its own t.co address, which lets it check destinations for malware and phishing, count clicks, and show a fixed-length link regardless of the original URL's length.
Design Interviews · lesson 1 of 15 · about 28 min
Design a URL shortener
The classic first design question, end to end: how big it is, where short keys come from, how redirects stay fast, what a status code changes, how to keep abusive links out, and how an attacker can walk your keys. Tap any for a plain-language card.
0 / 9 sections done
Start with the numbers
“Design a URL shortener.” Before drawing any boxes: how many links, how many clicks, and how much disk?
Those few numbers settle the shape of the system: writes of a few dozen per second are trivial for one database; reads in the thousands per second per region need a cache and several app servers; a few terabytes of tiny records fit comfortably on a replicated, sharded store. Notice what the numbers say as much as what they ask for. Move them.
100 million new links a month and 100 reads per write: about 39 writes/s and 3,900 reads/s, 11,600 at 3× peak. Five years of 500-byte records come to 3 TB.
Writes per second38.6
Redirects per second (average)3,858
Redirects per second (peak)11,574
Links stored6B
Storage3.0 TB
Cache for the hot 20% of a day's reads33 GB
100 million new links a month is 39 writes a second, but 100 reads for each makes 3,858 redirects a second (11,574 at peak). 5 years of 500-byte records is 6B links and 3.0 TB. The system is read-heavy and small: cache the reads, shard later.
Rule-of-thumb arithmetic with 30-day months. Cache = 20% of the records read in a day (the usual 80/20 assumption). Use the numbers your interviewer gives you instead of these.
Where do the 7 characters come from?
Every link needs a unique short key. Count with a counter, hash the URL, or pick at random and check?
The retry rate is the : with n keys already stored in a space of N, a new random key collides with probability n ÷ N. For 6 billion links in 3.5 trillion that is 0.17% per insert, harmless; for a space that is too small it grows quickly. The simulator uses a short key so you can see real collisions happen.
With 7 characters and 1 billion links a random key collides on 0.028% of inserts. With only 4 characters (14.8 million keys) inserting 600,000 links already costs about 12,000 retries.
Counter-based key length for that many6 characters
Example: link #125 becomes21
Random 7-char key collides on0.028% of inserts
Random keys drawn until unique: extra draws12,614
Predicted by n² ÷ 2N12,182
Collision chance on the last insert4.06%
Inserting 600,000 random 4-character keys into a space of 14,776,336 needed 12,614 extra draws (theory: about 12,182). A 7-character space is 62^7 = 3.52T, so 1B links collide on only 0.028% of inserts.
The collision experiment is a real seeded simulation (draw a random key; if it exists, draw again). The 7-character figures are the formula n ÷ 62^7.
Redirects are almost all reads
Eleven thousand redirects a second at peak. Most links are rarely clicked; a few are clicked constantly. How much cache is enough?
This simulation runs real traffic through a real LRU cache over 20,000 links with Zipf popularity. The more skewed the traffic, the more a small cache helps; the flatter it is, the more it has to hold. Cache size is the cheapest knob you have, so check the miss load you leave for the database.
With Zipf skew 1.0 and a cache holding 5% of the links, about 60% of requests hit the cache; at 20% it is about 74%. With flatter traffic (skew 0.6) the same 5% catches only 16%.
Cache hit ratio60%
Cache holds1,000 of 20,000 links
Database reads per second4,587
An LRU cache holding 5% of the links served 60% of requests at Zipf skew 1.0, leaving 4,587 database reads a second out of 11,600.
Real simulation: 30,000 requests drawn from a Zipf distribution over 20,000 links through an LRU cache (cold start included, so steady-state hit ratios are slightly higher).
One status code, two products
The redirect can say “moved permanently” (301) or “found, for now” (302). One saves traffic; the other lets you count it.
Most services that sell analytics or allow edits use 302 and handle the load with a cache in front, then record each click asynchronously (an event on a consumed by the analytics pipeline) so counting never slows the redirect. Compare how many requests your servers see.
1 million visitors clicking 3 times each: with 302 the servers see 3 million requests. With 301 and 70% of repeat clicks served from browser caches they see about 1.6 million, and the other 1.4 million clicks are never counted.
Clicks that happened3,000,000
Requests your servers see3,000,000
Clicks you cannot count0
With 302 your servers see all 3,000,000 clicks: every one can be counted and the destination can change at any time, at full request load.
Arithmetic: 301 requests = first visits + repeat clicks not served from the browser cache. Browser and proxy caching behaviour varies; this is the idealised case.
Short links hide where they go
Spammers love shorteners: nobody can see the destination. How do you refuse known-bad URLs without a database lookup on every create?
The false-positive rate depends on bits per entry: roughly 10 bits per URL gives under 1%. The other defences are not data structures: creation per account and IP, require sign-in for bulk creation, scan the destination asynchronously and disable links later, add interstitial warning pages for flagged domains, and make reporting easy.
50 million blocked URLs at 10 bits each need about 63 MB and give a 0.8% false-positive rate; at 8 bits, 50 MB and 2.2%.
Filter memory63 MB
Hash functions (optimal)7
False positives0.82%
Exact lookups needed per second (clean traffic)0.3
50M blocked URLs at 10 bits each use 63 MB and 7 hash functions, a 0.82% false-positive rate. Of 40 clean links created a second only 0.3 need the exact database check; the filter never lets a listed URL through.
False-positive rate for the optimal number of hash functions k = bits × ln 2: (1 − e^(−k/bits))^k. Memory = entries × bits ÷ 8.
Pick the fix
Six problems, four fixes.
Each situation has one fix that fits best. Each answer is worth 20 XP.
Match the symptom: hot reads, counting clicks, guessable keys, or a huge membership check?
Question 1 / 6
11,000 redirects a second are hammering the database for the same popular links.
Tip: press 1 to 4 to answer, Enter for the next one.
Who lives by this
Short links in the wild.
Published facts about shorteners at scale.
one of the first shorteners
TinyURL, launched in 2002, popularised the idea of turning a long address into a short one that redirects, and remains a reminder that the service must keep serving those links for as long as anyone holds them.
wind-down from 2018
Google announced in 2018 that goo.gl would be phased out and stopped creating new links in March 2019; the episode showed the permanence problem, because every old link printed or embedded somewhere depends on the service continuing to run.
branded domains and analytics
Link-management services such as Bitly build on the redirect itself: branded domains, click analytics, and editable destinations, which is why they use a redirect that reaches their servers every time.
Interview angle
What interviewers actually ask.
Six questions, each worth 20 XP. Strong answers start with the numbers and justify each choice.
State the scale, then the key, the cache, the status code and the abuse plan.
Question 1 / 6
What shape of workload is a URL shortener?
Tip: press 1 to 3 to answer, Enter for the next one.
Break it
Someone writes a loop: try /a, /b, /c… Every hit is a real link, and some of them point at private documents.
Defences: use random (or a keyed permutation of a counter) rather than sequential keys; make keys longer when they guard anything sensitive; by IP and treat many 404s as an attack signal; and never rely on an unguessable URL as the only protection for private data. If it must be private, require authentication.
1 billion links among 3.5 trillion possible 7-character keys is a density of 0.028%: a scanner at 1,000 guesses a second finds about 24,500 live links a day. Sequential keys let the same scanner read 86 million a day.
Share of all keys that are live1.0e+2%
Live links found per day86.4M
One live link every1.0 ms
With sequential keys every guess is live: a scanner at 1,000/s reads 86.4M links a day, in order.
Expected-value arithmetic: found per day = (live keys ÷ all keys) × guesses per second × 86,400. Rate limits and blocking reduce the guess rate; they do not change the density.