URL shortener
Turn long URLs into 7-character codes and redirect at 100× the write rate. The interesting parts are code generation without collisions and a read path that the cache, not the database, carries.
Component labels and connections
- Clients (client) · calls: Load balancer
- Load balancer (loadBalancer) · calls: API 1, API 2
- API 1 (service) · calls: Redirect cache, URL store
- API 2 (service) · calls: Redirect cache, URL store
- Redirect cache (cache) · calls: none
- URL store (database) · calls: none
Requirements
Functional
- Create a short code for a long URL, optionally with a custom alias and an expiry time.
- Redirect GET /{code} to the long URL with HTTP 301 or 302.
- Return 404 for unknown codes and 410 for expired ones.
- Owners can list and delete their links.
Non-functional
- Redirect latency p99 under 50 ms at the server; it sits in front of every click.
- Redirects 99.99% available (about 52 minutes of downtime a year); creation can tolerate brief outages.
- A code never maps to two different URLs, and codes are not trivially enumerable.
- Links are durable for at least 5 years.
Worked estimates
Write rate
≈ 1,160 writes/s average, ≈ 2,300/s at a 2× peak
100M new URLs/day ÷ 86,400 s
Read rate
≈ 116k redirects/s average, ≈ 230k/s peak
100 reads per write × 1,160/s
Record count
≈ 183 billion links
100M/day × 365 × 5 years
Storage
≈ 91 TB, ≈ 275 TB with 3 replicas
183B × ~500 B per row (URL, code, owner, timestamps, index)
Code length
7 base-62 characters give ≈ 19× headroom; 6 (5.7 × 10¹⁰) do not
62⁷ = 3.5 × 10¹² vs 1.83 × 10¹¹ needed
Cache size
≈ 100 GB of hot entries — a handful of cache nodes
~1B distinct links read/day; hottest 20% ≈ 80% of clicks → 200M × 500 B
Egress
≈ 58 MB/s (≈ 460 Mbit/s): bandwidth is not the constraint
116k/s × ~500 B per redirect response
API
POST /v1/urls
Request: { longUrl, customAlias?, expiresAt? } + Idempotency-Key header
Response: 201 { code, shortUrl } · 409 alias taken · 429 over quota
GET /{code}
Request: —
Response: 301/302 Location: longUrl · 404 unknown · 410 expired
301 lets browsers cache the redirect (less load, no click analytics); 302 sends every click to you.
DELETE /v1/urls/{code}
Request: auth: owner
Response: 204 · 404
Must also delete the cached entry, or the link keeps working until its TTL.
Data model
- urls — store: db
One table, keyed and sharded by code: every redirect is a point lookup on the shard key, so no query fans out.
A secondary index on userId serves 'my links'; it is the only non-key access path and it is rare.
A key-value store fits equally well — there are no joins or multi-row transactions.
High-level design
Trace permitted calls in the architecture above, then open the reference canvas to inspect routing.
Deep dives
Generating codes without collisions
Three workable schemes. (1) A counter encoded in base 62: hand each API server a range of IDs (Flickr's ticket servers, or a Snowflake-style timestamp + worker + sequence ID), so there is no per-request coordination and no collision by construction. Sequential codes are enumerable, so pass the counter through a keyed bijective permutation before encoding. (2) Random 7-character codes with insert-if-absent: with n codes already used out of N = 62⁷, the next insert collides with probability n/N — about 5% when 183B are used — so retry on a 409. (3) Hash truncation, which collides like (2) but also couples codes to URLs. Custom aliases always need the insert-if-absent path.
301 or 302, and where the redirect is cached
A 301 (permanent) may be cached by browsers and proxies, so repeat clicks never reach you: cheaper, but you lose click counts and cannot change or delete the target. A 302 (or 307) sends every click to you. Most commercial shorteners use 301 with short Cache-Control lifetimes or 302 because analytics is the product. Either way, a server-side cache-aside layer serves the hot set: with Zipf-like popularity, caching 20% of links answers roughly 80–85% of redirects.
Expiry and deletion
Check expiresAt on every read (lazy expiry) so an expired link returns 410 immediately, and run a background sweep that deletes expired rows in small batches to reclaim space. Deleting a link must also delete its cache entry; otherwise it keeps redirecting until the cache TTL — the classic invalidation bug. Never recycle expired codes: old printed links would silently point somewhere new.
Abuse
Shorteners are a favourite tool for hiding phishing and malware. Rate-limit creation per account and per IP, check new URLs against a reputation service before returning the code, and keep the ability to disable a code centrally — which again means invalidating caches.
Failure scenarios
The redirect cache restarts empty
Scenario and expected result
At t = 1.5 s the cache node dies and comes back cold 50 ms later. Every redirect misses until the hot set refills, so the database briefly sees the full read rate.
Expected: The hit rate collapses and the URL store queues up, but request coalescing and the Zipf-skewed hot set refill the cache within a few hundred milliseconds. Most redirects still succeed; the tail latency spike is the cost.
One link goes viral
Scenario and expected result
A single code receives 30% of all clicks — a link in a breaking news push.
Expected: Nothing breaks, and the viral link itself costs one database read: it lives in the cache. The store does get busier, but from the other 70% of clicks, which this scenario spreads uniformly over the long tail where the cache helps least. In a sharded cache one shard would take the whole hot key — the fix is to replicate hot keys or keep a small in-process cache.
The URL store's leader dies
Scenario and expected result
The database leader is killed at t = 1.5 s. Failure detection takes 3 missed 100 ms heartbeats plus a 200 ms election, so the store is unavailable for about 0.5 s before a replica takes over.
Expected: Cache hits keep redirecting through the outage; cache misses and new links fail until the replica is promoted. Because replication is semi-synchronous and the old leader is fenced, no acknowledged link is lost.
Alternative designs
Reference
- Inspect the architecture above and run the same scenario.
Key-value store instead of SQL
- Every access is by key, so a Dynamo-style store (N=3, R=W=2) scales writes horizontally with no resharding project. You lose the cheap userId index (you maintain a second table yourself) and uniqueness of custom aliases needs a conditional write instead of a UNIQUE constraint.
Reference
- Inspect the architecture above and run the same scenario.
No cache: send every redirect to the database
- Simpler and always fresh, but the database must absorb the full read rate. In the simulated cell the store saturates: 3,000 reads/s against roughly 2,700/s of capacity, so queues grow until requests miss their deadline.
Reference
- Inspect the architecture above and run the same scenario.
Hash the URL (MD5/SHA-256) and keep the first 7 characters
- The same URL always gets the same code, which deduplicates for free. But truncation makes collisions certain at this scale, so every insert needs a check-and-retry, and two users shortening one URL now share analytics and deletion rights. A counter or random code with insert-if-absent is simpler.
Clarifying questions
- How many links are created per day, and what is the read-to-write ratio?
- Do we need click analytics? (It decides 301 vs 302.)
- Are custom aliases allowed, and can links be edited or deleted?
- Do links expire by default?
- Must codes be unguessable?
Common mistakes
- Using 6 characters: 62⁶ ≈ 57B codes runs out within two years at 100M/day.
- Generating codes with a single global counter — a write bottleneck and a single point of failure.
- Hashing and truncating without a collision check.
- Sizing the database for the full redirect rate instead of the cache miss rate.
- Forgetting to invalidate the cache when a link is deleted or disabled.
Self-assessment rubric
requirements / levels 1-4
- 1/4 Lists create and redirect only.
- 2/4 Adds expiry or custom aliases, but no non-functional targets.
- 3/4 States read-heavy ratio, latency and availability targets.
- 4/4 Also pins down 301 vs 302, enumerability, deletion semantics and durability horizon.
estimates / levels 1-4
- 1/4 No numbers.
- 2/4 Computes QPS but not storage or code length.
- 3/4 QPS, storage and code length with formulas.
- 4/4 Also sizes the cache from popularity skew and shows bandwidth is not the bottleneck.
api / levels 1-4
- 1/4 Endpoints without status codes.
- 2/4 Create and redirect with main status codes.
- 3/4 Adds 404/410/409/429 and idempotency for creation.
- 4/4 Explains the 301/302 trade-off and its effect on analytics and deletion.
data model / levels 1-4
- 1/4 Undefined storage.
- 2/4 A table with code and URL.
- 3/4 Keyed and sharded by code, owner index identified.
- 4/4 Argues SQL vs KV from access patterns and handles alias uniqueness.
high level / levels 1-4
- 1/4 Single server and database.
- 2/4 Load balancer, stateless API, database.
- 3/4 Adds a cache-aside read path sized from the estimates.
- 4/4 Explains which component carries which load and how the design survives losing each one.
deep dive / levels 1-4
- 1/4 No collision story.
- 2/4 Hash or counter without analysis.
- 3/4 Compares counter, random and hash schemes with collision math.
- 4/4 Adds ID-range allocation, non-enumerability and failover behaviour.
wrap-up / levels 1-4
- 1/4 Stops at the diagram.
- 2/4 Mentions monitoring.
- 3/4 Names the bottlenecks and their mitigations.
- 4/4 Prioritises the next risks (abuse, hot keys, cache invalidation on delete) with measurable signals.