Design: a URL shortener

The full lesson, with a worked example: Design: a URL shortener.

Requirements

Functional

• Shorten: given a long URL, return a short link such as sho.rt/bk7Q2xa.
• Redirect: opening the short link sends the browser to the long URL.
• Nice to have: custom aliases (/diwali-sale), expiry dates, click counts, editing a link's target, disabling a link.

Non-functional

• Fast redirects: a few milliseconds on the server, p99 under 50 ms end to end inside the data centre.
• Very high availability for reads: a broken link in 50 lakh sent SMS messages can't be recalled. Creating links may pause briefly; redirects may not.
• Unique forever: two links never share a code.
• Not guessable: neighbouring codes must not reveal other people's links.

Out of scope (say so): user accounts and billing, link previews, QR rendering.

Estimates

Say 10 crore new links a month and about 100 clicks per link.

• Writes: 10 crore ÷ about 26 lakh seconds in a month ≈ 40 creates a second.
• Reads: 100 × 40 ≈ 4,000 redirects a second on average; a sale SMS at 10 AM can push peaks to about 20,000 a second.
• Read-to-write ratio: about 100 to 1. This one number shapes the whole design.
• Storage: about 500 bytes a link × 10 crore = 50 GB a month, about 600 GB a year, about 3 TB over five years. A handful of machines.
• Cache: if the top 1 crore links take most clicks, 1 crore × 500 bytes ≈ 5 GB, which fits on one cache server.
• Database load after the cache: 20,000 a second × 1% misses ≈ 200 reads a second.
• Code space: 62⁶ ≈ 5,700 crore; 62⁷ ≈ 3.5 lakh crore. At about 120 crore links a year, seven characters leave the space mostly empty, which helps against guessing.

API

• POST /v1/links with url, optional alias, optional expiresAt → 201 with code and shortUrl. 409 if the alias is taken, 400 if the URL is blocked or malformed.
• GET /:code → 302 with a Location header; 404 if unknown; 410 Gone if expired or disabled.
• PATCH /v1/links/:code with a new url or disabled: true → 200. Deletes the cached copy in the same step.
• GET /v1/links/:code/stats?from=…&to=… → clicks per day, city and device, about a minute behind.
• Auth and limits: creation needs an API key and is rate limited per account and per IP. Redirects are public.

Data model

links, a key-value store or one wide table, sharded by code:

• code (the primary key, 7 characters)
• long_url (up to about 2 KB)
• owner_id, created_at, expires_at (nullable), disabled (true or false)

Every redirect is a lookup by exact code, so the primary key's index is the only one the hot path needs. Add a secondary index on owner_id for "my links" pages; it is never touched by redirects.

click_counts, written by workers, keyed by code plus minute: count, plus counts per city and device. Raw click events can sit in cheap storage for a few months.

number_blocks, one row in the number keeper: next_free. Each block request moves it forward by 1,000.

High-level design

• Link servers are stateless and sit behind a load balancer; add more as clicks grow.
• The links database is the source of truth, sharded by code with a replica or two per shard.
• The shared cache holds popular links and answers about 99% of redirects.
• The click queue takes one tiny event per redirect; workers add them up per minute.
• The number keeper hands out blocks of 1,000 numbers for codes.

The redirect path, the one that matters:

1. 1

   BrowserLink server

   GET /x7Kp2

2. 2

   Link serverLocal copy

   Hot code in my own memory? (most viral links stop here)

3. 3

   Link serverCache

   Shared cache, about 99% hits, under 1 ms

4. 4

   Link serverLinks database

   Miss: one read by code on one shard, a few ms

5. 5

   Link serverClick queue

   Code, time, city, phone type (fire and forget)

6. 6

   Link serverBrowser

   302 with Location: the long URL

The create path, about 40 times a second:

1. 1

   ClientLink server

   POST /v1/links with the long URL

2. 2

   Link serverNumber keeper

   Block used up: next 1,000 numbers please

3. 3

   Number keeperLink server

   Yours: 4,08,77,001 to 4,08,78,000

4. 4

   Link serverLinks database

   Save bk7Q2xa only if the code is new

5. 5

   Link serverClient

   201 with sho.rt/bk7Q2xa

Deep dives

Making unique codes

Write numbers in base 62 (0–9, a–z, A–Z). Three ways to get the number or code:

• Count up in blocks. Each link server takes a block of 1,000 numbers from the number keeper and spends it locally. At 40 creates a second, the keeper is asked about once every 25 seconds per server. Unique by construction; a crashed server just wastes the rest of its block. Scramble each number with a fixed, reversible shuffle before encoding, so 1,001 and 1,002 give unrelated codes.
• Random seven characters. Naturally unguessable. Save with "only if this code is new"; on a clash, pick again. The chance of a clash per save is roughly links stored ÷ 3.5 lakh crore, so retries stay rare for decades.
• Part of a fingerprint of the URL. Same URL gives same code, but different URLs can clash, and two customers would share one code and its counts. Rarely the right choice.

Whatever the scheme, the database's conditional insert is the final guard. Custom aliases go through the same conditional insert, plus a deny list of reserved routes and rude words.

The cache

• What to cache: code → long_url, expires_at, disabled. Links rarely change, so copies can live for hours.
• How: cache-aside. Read the cache; on a miss, read the database and fill the cache.
• Eviction: least recently clicked goes first (LRU), so last week's viral link makes way for today's.
• Expiry: the cached copy's TTL must never outlive the link itself.
• Missing codes: cache "not found" for about a minute, so a typo printed on a poster doesn't hit the database on every scan. At very large scale, a Bloom filter of all codes in each server's memory answers "definitely not a code" instantly.
• Edits and takedowns: write the database first, then delete the cached copy, including any local copies.

Hot links

One viral code lives on one cache machine, so 50,000 clicks a second on a single hot key pile onto that machine while its neighbours idle. Fix: each link server keeps the hottest few thousand codes in its own memory for a few seconds. Viral traffic is then spread across every link server, and the shared cache sees a trickle.

Counting clicks

Never clicks = clicks + 1 inside the redirect: thousands of writes a second to one row queue behind each other, and redirects slow from 5 ms to seconds. Drop an event on the queue and let workers aggregate per minute. If counting has a bad hour, redirects carry on and the queue holds the backlog.

Abuse

• Phishing: check every new URL against lists of known bad sites, re-check popular links later, and keep a domain blocklist.
• Spam creation: limit links per new account and per IP.
• Scanning for private links: non-sequential codes, plus rate limiting on clients that collect many 404s.
• Takedown in seconds: set disabled, purge every cache layer in the same step.

Trade-offs

• 301 vs 302. 301 ("moved permanently") lets browsers remember the target: less load, but those clicks go uncounted and the target can never change for people who already clicked. 302 ("moved for now") sends every click back through you. Default to 302 for a shortener.
• Counter blocks vs random codes. Blocks: no clashes, need scrambling and a small keeper service. Random: no coordination, need a conditional insert. Both are easy at 40 a second.
• Cache lifetime vs freshness. Long TTLs mean fewer database reads but slower edits and takedowns unless you delete on write. Keep TTLs long and delete explicitly.
• SQL vs key-value store. Either works at 3 TB. A key-value store matches the access pattern; SQL is fine if the team knows it and the code is the primary key.
• Exact vs approximate counts. Queue-based counts are a minute late and can double count a retried event; that is fine for marketing reports.

Interview talking points

• Open with the 100-to-1 read-to-write ratio; it justifies the cache and a single-key lookup.
• Show that storage is small (3 TB in five years), so sharding is for availability and headroom, not survival.
• Explain base 62 and why seven characters (3.5 lakh crore codes).
• Show how uniqueness is guaranteed across servers: blocks of numbers or a conditional insert.
• Separate the read path from the write path, and say which one must never fail.
• Pick 302 and say what 301 would cost.
• Keep counting off the redirect path.
• Mention abuse: phishing checks, creation limits, instant takedown.

For experienced engineers

A reversible permutation of the number space (a small Feistel network or a multiplicative inverse modulo 62⁷) gives non-sequential, clash-free codes with no uniqueness check. Caching 302s at a CDN for a few seconds absorbs extreme spikes if sampled edge-log counts are acceptable.

Follow-up questions

How do two servers never hand out the same code? Each takes its own block of numbers from the keeper, or both use random codes and let the database's "insert only if new" refuse duplicates. Uniqueness is decided in exactly one place.

Traffic grows ten times. What changes? Add link servers and cache memory; both scale out. The database barely notices because the cache absorbs extra clicks. Add shards only when storage, not traffic, demands it.

What if a shard's main machine fails? Redirects keep working from the cache and replicas. Creates for codes on that shard retry for a minute while a replica is promoted, or the server picks a code that lives on another shard.

How do expiring links work? Store expires_at, check it on every read, cap the cache TTL at the remaining lifetime, and delete expired rows in background batches.

How would you take down a harmful link fast? Set disabled in the database and purge the code from the shared cache and every local copy in the same step. Short TTLs on local copies cap the worst case at seconds.

Is a short link safe for private documents? No. Codes are dense in the space, so scanning finds live links. A short link is a shortcut, not a lock; anything private needs a login behind it.