Design a service that turns long URLs into short codes and sends visitors who open a short link to the original URL.
Functional requirements
Shorten: a visitor posts a long URL and gets a short code back.
Redirect: a visitor opens /<code> and is redirected (302) to the long URL. Name its two scenarios "Cache hit" and "Cache miss". A cache miss reads the code from the database and puts it in the cache, so the next visitor hits.
Use these use case and scenario names exactly: the traffic, requirements and tests in problem.proschi refer to them.
Scale
Redirects: 10k rps, 95% of them for codes that were opened recently.
Shortening: 100 rps.
Constraints
p99 of a redirect under 50 ms, of shortening under 200 ms.
Redirects available 99.9% of the time.
A short code is never lost once it has been returned to the visitor: it is written (INSERT, PutItem, …) to a database before the answer.
Losing any single machine must not take the service down.
At most $3,000 / month.
What is given
problem.proschi declares the visitor and holds the traffic, requirements and tests. Your file imports it; add the components, connections and the two use cases.
How your design is checked
You write the design as text in Proschi. Tests run in your browser: a simulation of the traffic above checks latency, availability, cost and what happens when a machine fails. How the simulation works.
A URL shortener takes a long link and hands back something like https://sho.rt/aZ3x9. Opening the short link sends you on to the long one. Think of bit.ly or TinyURL: links in tweets, text messages and printed posters, where every character counts.
There are two use cases:
Shorten: a visitor posts a long URL and gets a short code back with 201 Created.
Redirect: a visitor opens /<code> and gets a 302 Found whose Location header points at the long URL. The browser follows it on its own.
The non-functional requirements are where the design lives:
Scale: 10k redirects and 100 shortenings per second. 95% of redirects are for codes opened recently.
Latency: p99 of a redirect under 50 ms, of shortening under 200 ms. p99 is the 99th percentile: 99 out of 100 requests are at least that fast.
Availability: redirects work 99.9% of the time. A dead short link is a broken link on every poster that printed it.
Durability: once a code has been returned, it is never lost. It must reach a database (not only memory) before the answer.
Fault tolerance: losing any one machine must not take the service down.
Budget: at most $3,000 a month.
given.proschi fixes only the visitor, the traffic, the requirements and the tests; everything between the visitor and the data is yours to draw. The traffic also fixes the scenario mix: "Cache hit" 95% and "Cache miss" 5%. You don't pick your hit rate; you decide what happens on each path.
The tests check four ideas:
A redirect asks the cache before the database, and a cache hit never touches the database.
A cache miss fills the cache after reading the database.
Shortening writes to a database before responding, and answers 201.
Redirects answer 302.
On top come the requirement checks: p99 per use case, availability, durability, surviving any single node failure, and the monthly cost.
Start with the ratio. 10,000 redirects against 100 shortenings is 100 reads for every write: optimise the read path, keep the write path simple.
Quantity
Arithmetic
Result
Read:write ratio
10,000 ÷ 100
100 : 1
New codes per day
100 × 86,400 s
8.64 million
New codes per year
8.64 M × 365
≈ 3.2 billion
Storage per year
3.2 B × ~500 bytes per row
≈ 1.6 TB
Codes available, 6 Base62 chars
62⁶
≈ 57 billion (≈ 18 years)
Codes available, 7 Base62 chars
62⁷
≈ 3.5 trillion
Redirects that hit the cache
10,000 × 95%
9,500 rps
Redirects that reach the database
10,000 × 5%
500 rps
Cache writes (fills on miss)
same as misses
500 rps
The 500-byte row is an assumption (code, URL, timestamp, overhead). About 1.6 TB a year fits one modern database: storage is not what makes this problem hard.
Base62 writes a number with the 62 characters 0-9, a-z and A-Z, so a code of n characters has 62ⁿ values. Six characters last about 18 years at this write rate; seven last about a thousand.
Now the per-component load. In Proschi's simulation each kind of node has a default capacity per replica (How the simulation works lists them all):
Component
Load it sees
Capacity per replica
Replicas at 100% busy
API service ([REST API])
10,000 + 100 = 10,100 rps
2,000 rps
6 (5.05, rounded up)
Cache ([Redis])
10,000 reads + 500 writes
100,000 rps
1
Database ([DynamoDB])
500 reads + 100 writes
20,000 rps
1
Three more estimates show up directly in the numbers:
Latency. Idle latencies are about 2 ms for a load balancer, 10 ms for a service, 1 ms for Redis and 5 ms for a database. A hit is roughly load balancer + API + cache, about 13 ms; a miss adds the database read, about 18 ms (the cache fill can be asynchronous, off the path). An idle hop's p99 is about 2.8× its mean, so a hit's p99 is near 36 ms and a miss's near 50 ms. The 50 ms limit is checked over all redirects together, hits and misses mixed, so an idle design passes with some room. Queueing eats that room quickly: a busy API slows both paths.
Availability. One service replica is up 99.5% of the time, which alone fails 99.9%. Two replicas are both down only 0.5% × 0.5% = 0.0025% of the time (up 99.9975%). Every node on the path multiplies in, hence "two of everything".
Cost. Each replica has a flat monthly price: about $50 for a load balancer, $100 for a service, $150 for Redis, $400 for PostgreSQL, $500 for DynamoDB. Multiply out your replica counts before running anything.
What it is. The application owns the cache. On a read it asks the cache first; on a hit, it is done. On a miss, it reads the database, writes the value into the cache (usually with a time-to-live, TTL) and returns it. The database never talks to the cache.
Why it works. Clicks are very uneven: a viral link gets millions in an hour, most links a handful ever. Keeping only recently used codes in memory gives a high hit rate from a cache far smaller than the database, answering in about a millisecond.
Trade-offs. The first reader of every code pays a miss. Cached values go stale if the row changes, which is why caches carry a TTL. A cold cache (after a restart) sends a burst of misses to the database.
When not to use it. When data changes on every read, when every key is read once (nothing to reuse), when reads are rare, or when a stale value is dangerous, like a balance or a permission.
Here is the pattern in Proschi, for a generic product catalogue:
title"Cache-aside"user "User"[Actor]api "Catalog API"[REST API] x2cache "Item cache"[Redis] x2db "Items DB"[PostgreSQL] x2user -> apiapi -> cache : GET / SETapi -> db : SQLusecase"Get item" { user -> api : GET /items/42 api -> cache : GET item:42 alt"Hit" { cache --> api : item} alt"Miss" { cache --> api : nil api -> db : SELECT item 42 db --> api : item api ->> cache : SET item:42 } api --> user : 200}
Notice ->> on the fill: the API doesn't wait for the SET before answering, so the fill is off the critical path.
What it is. Every machine fails sooner or later: hardware, kernel panics, deployments. A single point of failure (SPOF) is a component whose loss takes the use case down. The fix is replicas behind something that routes around a dead one.
The arithmetic. In sequence, availabilities multiply: three nodes at 99.9% make a 99.7% path. In parallel, unavailabilities multiply: two replicas at 99.5% are down together 0.0025% of the time. Add replicas to each node until the product of the path clears the target.
Trade-offs. Each replica costs money, and stateful replicas need replication (and a story for which copy is right). Stateless services like the API are cheap and simple to replicate.
When not to. A prototype or internal tool with no availability promise can run one instance. Just know what you're accepting.
Sequential codes are guessable (a reversible permutation fixes it)
Hash the URL
MD5 or SHA-256, keep 7 characters
The same URL gets the same code
Truncated hashes collide: check and retry
Random codes
Draw 7 random characters
Simple, unguessable
Collision checks grow as the keyspace fills
Deep dive Counter blocks: a counter without a database trip per link
Each API server claims a block of numbers once and hands them out from memory:
title"Counter blocks"user "User"[Actor]api "Link API"[REST API] x3seq "Sequence"[PostgreSQL] x2user -> apiapi -> seq : SQLusecase"Claim block" { api -> seq : UPDATE ranges SET next = next + 1000 seq --> api : 52000 to 52999}usecase"New code" { user -> api : POST /links api -> seq : INSERT link with the next number seq --> api : ok api --> user : 201 the number in Base62}
A server that crashes loses the rest of its block: a few gaps in the sequence, never a duplicate.
The reference design picks the counter. Unique-ID generation comes back in depth in the Snowflake problem later on this roadmap.
Draw the simplest thing that works: visitor → API → database. Shorten inserts a row; Redirect looks it up. Say that it works, then check it against the numbers: every one of 10k redirects pays a database round trip, the database carries the whole read load, and the redirect test fails because nothing is cached.
Now add the cache on the read path, with cache-aside. Draw the Redirect use case with two alt scenarios named exactly "Cache hit" and "Cache miss". On the hit the cache answers and the database is never called; on the miss, read the database, then fill the cache.
Put a load balancer in front of the API so a visitor never depends on one API instance.
Which database? A key → value lookup with no joins. A key-value store (DynamoDB, Cassandra) or PostgreSQL both handle 100 writes and 500 reads per second. Key-value scales writes horizontally as the service grows; relational is cheaper per replica here and gives you uniqueness constraints for free. Pick one and say why.
The write path.Shorten writes to the database before it responds; a code that lives only in a cache or a queue can vanish. Skip a cache write on this path: the link may never be opened, and the miss path will fill the cache when it is.
The miss path. Count its hops: load balancer, API, cache (miss), database, fill. Make the fill asynchronous (->>), and keep queueing low on each hop: busy API replicas make every request wait.
Sizing. Choose replica counts that keep every node comfortably below 70%, and check each still holds with one replica fewer: survive any node failure removes one from each node and re-runs the analysis. Then read the Analysis tab: p99 of Redirect under 50 ms with room to spare, the total under $3,000.
Deep dive What if Redis is down?
Two cache replicas make the cache very available, and losing one is survivable. A more robust design also handles the whole cache being unreachable: a scenario where the API's cache call fails (-x) and it goes straight to the database, a fallback. It is optional here, but great to mention in an interview with its risk: if the cache really dies at 10k rps, the database suddenly sees 20× its normal read load.
Summarise in one breath: "A stateless API behind a load balancer; codes written to a database before we answer; a Redis cache with cache-aside, so 95% of redirects never touch the database; two or more of everything." Then name what's next: click analytics through a queue, abuse detection, custom aliases, expiry.
The miss never fills the cache (wrong/miss-never-fills-cache). The design reads the cache, misses, reads the database and answers, but never writes the code into the cache. In production this is a silent disaster: the cache holds only what something else put there, the hit rate drops toward zero, and the database takes the full read load. A simulation with a fixed 95% hit rate can hide it, which is why a flow test catches it: Misses fill the cache wants a cache call after the database call in "Cache miss".
No cache at all. Every redirect goes to the database. Enough database replicas might meet the latency on paper, but it fails Redirects read the cache first, and you'd pay for a database sized for the full read load.
Cache after the database. Reading the database first gets the order backwards: the cache saves nothing. Redirects read the cache first checks the order.
Only writing to the cache on Shorten. Fast, but memory: a restart or eviction loses codes already handed out. Codes are stored before they are returned (and durable) catch it.
One of anything. A single API, cache or load balancer is a SPOF, and one API replica alone fails 99.9% (99.5% each). survive any node failure catches it.
Running the API hot. Six API replicas carry 10.1k rps on paper, but at 84% busy queueing wrecks p99, and losing one replica saturates the other five. The p99 requirement on Redirect and survive any node failure catch it.
Answering 200 or 301. A 200 is not a redirect, and browsers cache a 301, so later clicks never reach the service. The tests ask for 302: Redirects redirect.
How to present it. Lead with the ratio: "100 reads per write, so this is a read-optimisation problem." Sketch the naive design in ten seconds, point at the database as the bottleneck, then add the cache and walk through hit and miss. Keep the write path boring on purpose. Finish with redundancy and the numbers behind your replica counts.
Follow-up questions you'll likely get:
"How do you generate codes without collisions?" A counter in Base62 never collides. To avoid one counter bottleneck, give each API server a block of numbers (say 1,000) from a central sequence; permute them if enumeration is a concern.
"301 or 302?" A 301 is permanent: browsers cache it and skip us next time, which is cheaper, but we lose click counts and can't change the target. A 302 is temporary: every click comes back to us. Pick 302 when you count clicks or may edit links, 301 when you only want less load.
"What's your cache eviction policy?" LRU (least recently used) with a TTL. Codes never change, so staleness isn't the worry; memory is.
"What happens when the cache goes down?" Fall back to the database, ideally with a limit on how hard you hit it, and warm the cache back up. Mention the thundering herd: with the cache empty, every redirect misses at once and the database gets 20× its normal reads.
"How would you add click analytics?" Publish a click event to a queue asynchronously on each redirect and count in a separate pipeline. Never put analytics on the redirect's critical path.
"How do you stop abuse?" Rate-limit shortening per user or IP, and check targets against a phishing list.
System Design Interview – An Insider's Guide, Vol. 1 (Alex Xu), chapter "Design A URL Shortener": the interview-format walkthrough of this exact problem, including hash vs counter codes.
How the simulation works: every default capacity, latency and price behind the numbers in this lesson.
awesome-system-design: a curated list of articles, books and videos to keep going after the foundations.