System design practice

URL Shortener

easy caching read-heavy durability

Cache-first redirects that survive losing any single machine.

Solve it in your browser Read the lesson first

Design a service that turns long URLs into short codes and sends visitors who open a short link to the original URL.

Functional requirements

Use these use case and scenario names exactly: the traffic, requirements and tests in problem.proschi refer to them.

Scale

Constraints

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.

Start designing

Lesson · 14 min read

Learn it: URL Shortener #

What you'll learn #

The problem, explained #

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:

The non-functional requirements are where the design lives:

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:

  1. A redirect asks the cache before the database, and a cache hit never touches the database.
  2. A cache miss fills the cache after reading the database.
  3. Shortening writes to a database before responding, and answers 201.
  4. Redirects answer 302.

On top come the requirement checks: p99 per use case, availability, durability, surviving any single node failure, and the monthly cost.

Back-of-the-envelope #

reads for every write
100 : 1
redirects answered by the cache
9,500 rps
redirects that reach the database
500 rps
new data per year
≈ 1.6 TB
6-character Base62 codes
57 billion

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.

QuantityArithmeticResult
Read:write ratio10,000 ÷ 100100 : 1
New codes per day100 × 86,400 s8.64 million
New codes per year8.64 M × 365≈ 3.2 billion
Storage per year3.2 B × ~500 bytes per row≈ 1.6 TB
Codes available, 6 Base62 chars62⁶≈ 57 billion (≈ 18 years)
Codes available, 7 Base62 chars62⁷≈ 3.5 trillion
Redirects that hit the cache10,000 × 95%9,500 rps
Redirects that reach the database10,000 × 5%500 rps
Cache writes (fills on miss)same as misses500 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):

ComponentLoad it seesCapacity per replicaReplicas at 100% busy
API service ([REST API])10,000 + 100 = 10,100 rps2,000 rps6 (5.05, rounded up)
Cache ([Redis])10,000 reads + 500 writes100,000 rps1
Database ([DynamoDB])500 reads + 100 writes20,000 rps1

Three more estimates show up directly in the numbers:

Concepts #

Cache-aside (lazy loading) #

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]   x2
cache "Item cache"  [Redis]      x2
db    "Items DB"    [PostgreSQL] x2

user -> api
api  -> cache : GET / SET
api  -> db    : SQL

usecase "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.

Redundancy and availability arithmetic #

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.

A minimal redundant tier:

title "Redundant tier"

client "Client"        [Actor]
lb     "Load Balancer" [AWS Load Balancer] x2
web    "Web"           [REST API]          x3

client -> lb
lb     -> web : HTTPS

Generating short codes #

Three classic approaches:

ApproachHowUpsideCost
Counter + Base62A unique integer written in 0-9a-zA-ZShort, never collidesSequential codes are guessable (a reversible permutation fixes it)
Hash the URLMD5 or SHA-256, keep 7 charactersThe same URL gets the same codeTruncated hashes collide: check and retry
Random codesDraw 7 random charactersSimple, unguessableCollision 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]   x3
seq  "Sequence" [PostgreSQL] x2

user -> api
api  -> seq : SQL

usecase "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.

Designing it step by step #

Step 1: Scope the problem #

Pin down what you are building before drawing anything. Questions worth asking out loud:

Step 2: High-level design #

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.

Step 3: Deep dive #

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.

Step 4: Wrap up #

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.

Common mistakes #

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.

In the interview #

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:

Further reading #

Now design it

Review cards for this problem

Short questions on the ideas it needs, from the review cards. Review them daily so they stick.

More system design problems