Design it yourself · Chapter 20

Design a URL shortener

Design a bit.ly-style URL shortener from scratch: requirements, estimates, short-code generation, a cached redirect path, 301 vs 302, and how it fails at scale.

BeginnerInterview priority: High50 min
On this page
  1. The problem: a tiny service with a huge read path
  2. Step 1: pin down the requirements
  3. Step 2: quick estimates
  4. Step 3: the API and the one table
  5. Step 4: generating short codes
  6. Step 5: the redirect path
  7. Step 6: scale and keep it running
  8. Where this breaks
  9. What not to build
  10. In the interview
  11. Where to go next
  12. Quiz

The problem: a tiny service with a huge read path

A URL shortener turns https://shop.example.com/collections/summer-sale?utm_source=newsletter&ref=a81f into byte.ly/jU. Anyone who opens the short link is sent on to the long one. It sounds like a weekend project, and the first version is: one web server, one table, a few lines of code.

Then a celebrity shares one of your links with five million followers. Thousands of people click the same link in the same second, every click runs a database query, and the one server falls over. Links that were promised to work "forever" now return errors.

A long link becomes a short one, and the numbers behind it

  1. Time to design a real system: a URL shortener, like bit.ly. Paste a long link, get a short one; anyone who opens the short link is redirected to the original.
  2. Start every design with requirements. Must have: create a short link, redirect fast, links never break. Nice to have: custom names and click counts. And a quick estimate: say 200 new links a second, but 8,000 redirects a second.

This lesson is a first design: it applies caching, scaling out and redundancy to one small, complete system. It is the most common warm-up interview question because it fits in 30 minutes and still has real decisions in it.

Step 1: pin down the requirements

Never start drawing boxes. Start by agreeing what the system must do and how well.

KindRequirementWhy it matters for the design
FunctionalCreate a short link from a long URLThe write path
FunctionalOpening a short link redirects to the long URLThe read path: this is most of the traffic
Functional (nice to have)Custom aliases (byte.ly/summer-sale), expiry dates, click countsEach adds a small twist
Non-functionalRedirect in under 25 ms at the serverRules out a database query on every click at scale
Non-functionalRedirects available 99.99% of the timeA broken link is broken for everyone who has it
Non-functionalLinks never break and codes are never reusedStorage only grows; codes must be unique forever

Out of scope: user accounts and dashboards, link previews, editing a link's destination (we revisit this in a try box).

Step 2: quick estimates

Suppose the service creates 200 links a second and serves 8,000 redirects a second on average. Those two numbers drive everything.

QuantityWorkingResult
Read-to-write ratio8,000 ÷ 20040 : 1, read-heavy
Links per year200 × 86,400 × 365≈ 6.3 billion
Bytes per link7-char code + ~150-byte URL + timestamps, index and row overhead≈ 300 bytes
Storage per year6.3 B × 300 B≈ 2 TB (about 20 TB after 10 years, ×3 with replication)
Peak redirects8,000 × 3≈ 24,000 / s
Redirect bandwidth8,000 × ~500-byte response≈ 4 MB/s: negligible
Hot set to cachethe 20 M most-clicked links × ~400 B with Redis overhead≈ 8 GB: one Redis node plus a replica

Two conclusions. The system is read-heavy, so design effort goes into the redirect path. And the load is modest (one database takes 200 writes a second easily), but storage grows forever, which is what eventually forces you to split the data.

Your turn: how long must the code be?

Codes use the 62 characters 0-9, a-z, A-Z. At 6.3 billion new links a year, how many years do 6-character codes last? And 7-character codes? Which would you pick, and why not just use 10?

Compare with our answer
  • 62⁶ ≈ 56.8 billion codes: about 9 years at 6.3 B a year. Too tight for "links never break".
  • 62⁷ ≈ 3.5 trillion codes: over 500 years. Plenty.
  • Shorter is the whole point of the product, so don't pay for characters you don't need; but leave room for growth and for random codes, which need a sparse space to avoid collisions.

A strong answer mentions: 62ⁿ as the size of the space · links per year from the write rate · 6 chars running out within a decade · 7 chars as the sensible choice · spare space if codes are random rather than sequential.

Step 3: the API and the one table

The whole public API is two calls.

POST /v1/links
Content-Type: application/json

{"long_url": "https://shop.example.com/collections/summer-sale?ref=a81f",
 "custom_alias": null, "expires_at": null}

201 Created
{"code": "jU", "short_url": "https://byte.ly/jU"}
GET /jU

302 Found
Location: https://shop.example.com/collections/summer-sale?ref=a81f

The data model is a single table, and every read is a lookup by its primary key:

CREATE TABLE links (
    code        VARCHAR(16)  PRIMARY KEY,      -- generated code or custom alias
    long_url    TEXT         NOT NULL,
    created_at  TIMESTAMPTZ  NOT NULL DEFAULT now(),
    expires_at  TIMESTAMPTZ                    -- NULL = never expires
);

The core: one table from short code to long URL

  1. The core is tiny. A table maps each short code to its long URL. To create a code, take a unique counter value and write it in base 62, using digits plus lower and upper case letters. Seven characters give over three trillion codes.

Because every query is "get the row with this key", almost any database works: Postgres or MySQL for the first few years, or a key-value store such as DynamoDB or Cassandra if you want sharding handled for you. The PRIMARY KEY constraint matters more than the brand: it is what finally guarantees that no two links ever share a code. See SQL vs NoSQL for the general trade-off.

Step 4: generating short codes

This is the decision interviewers most want to hear you reason about. A code must be short, unique forever, and ideally not guessable.

OptionHowGood atWeak at
Counter + base 62Take the next number from a counter, write it in base 62Never collides; codes are as short as possibleSequential codes are guessable; the counter must be shared safely
Random code + insert-if-absentPick 7 random characters; insert, and retry on a duplicate keyNo coordination at all; not guessableCollisions grow as the space fills; each retry is another write
Hash of the long URLMD5 or SHA-256 of the URL, keep the first 7 base-62 charactersThe same URL always gets the same codeTruncated hashes collide often (see below); handling that turns it into option 2
Pre-generated key poolA background job fills a table of unused random codes; creates take oneFast, no collisions at create timeOne more service to run; must hand out each key exactly once

Base 62 is just counting with 62 symbols instead of 10. The number 1,234 is 19 × 62 + 56; symbol 19 is j and symbol 56 is U, so 1,234 becomes jU.

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def encode(n: int) -> str:
    if n == 0:
        return ALPHABET[0]
    digits = []
    while n > 0:
        n, r = divmod(n, 62)
        digits.append(ALPHABET[r])
    return "".join(reversed(digits))

def decode(code: str) -> int:
    n = 0
    for ch in code:
        n = n * 62 + ALPHABET.index(ch)
    return n

assert encode(1234) == "jU" and decode("jU") == 1234

Choice: a counter, handed out in blocks. If every create asked one shared counter for the next number, the counter would sit on every write and become a single point of failure. Instead, each app server reserves a block of numbers and spends them from memory.

Handing out IDs in blocks, so the counter is rarely touched

The counter can be a database row (UPDATE counters SET next = next + 1000 RETURNING next) or a key in ZooKeeper or etcd. At 200 creates a second and blocks of 1,000, it is touched every five seconds. A crashed server loses the rest of its block, which only leaves a harmless gap.

Why not just hash the URL?

A 7-character base-62 code holds about 41.7 bits. By the birthday paradox, after roughly √(62⁷) ≈ 1.9 million codes the chance that some two URLs share a truncated hash is already about 40%; at 6 billion links collisions are constant. You must check on insert and re-hash with a salt, which is a random-code scheme with extra steps. And "same URL, same code" is often unwanted: two users may want separate expiry dates and click counts.

Step 5: the redirect path

A redirect is a read: look up the code, reply with the long URL in a Location header. At 8,000 a second, with a few links far more popular than the rest, this is the textbook case for cache-aside: look in Redis first, and only on a miss read the database and fill the cache.

Most redirects are answered from the cache

  1. A redirect is a read: look up the code, reply with a redirect to the long URL. Because it’s so read-heavy, put a cache in front of the database. Popular links get clicked again and again, so most redirects never touch the database.
from datetime import datetime, timezone

@app.get("/<code>")
def follow(code: str):
    key = f"link:{code}"
    cached = redis.get(key)                         # 1. try the cache (~0.5 ms)
    if cached == b"":                               # a remembered "not found"
        abort(404)
    if cached is not None:
        return redirect(cached.decode(), code=302)

    row = db.fetch_one(                             # 2. miss: primary-key read (~1-5 ms)
        "SELECT long_url, expires_at FROM links WHERE code = %s", (code,))
    now = datetime.now(timezone.utc)
    if row is None or (row.expires_at is not None and row.expires_at <= now):
        redis.set(key, "", ex=60)                   # negative cache: stops scanners hammering the DB
        abort(404)

    ttl = 86_400                                    # keep popular links for a day...
    if row.expires_at is not None:                  # ...but never past the link's own expiry
        ttl = max(1, min(ttl, int((row.expires_at - now).total_seconds())))
    redis.set(key, row.long_url, ex=ttl)            # 3. fill the cache
    return redirect(row.long_url, code=302)

With a 90% hit ratio, the database sees about 800 reads a second plus 200 writes: comfortable for one primary. The average redirect costs roughly 0.9 × 0.5 ms + 0.1 × 5.5 ms ≈ 1 ms of lookup time, well inside the 25 ms target.

301 or 302?

The HTTP status code you redirect with is a real design decision, and a favourite follow-up question.

StatusMeaning to the browserGood atWeak atUse when
301 Moved Permanently"Remember this; go straight there next time"Repeat clicks from the same browser never reach you: less loadYou stop seeing those clicks, and you cannot change or disable the link for anyone who has cached itLinks are permanent and you don't count clicks
302 Found (or 307)"Go there this time; ask me again next time"Every click reaches you: counts, expiry and abuse takedowns all workEvery click costs you a requestClick counts, expiry or takedowns matter (the usual case)

Choice: 302. Click counts are on the wish list, links can expire, and a shortener will be used for phishing, so you need the power to switch a link off. The extra traffic is what the cache is for. You can still let a CDN hold a 302 for a short time with Cache-Control: max-age=60 to absorb a viral spike, trading up to a minute of delay on a takedown.

Step 6: scale and keep it running

Enough app servers for the peak, plus a spare

  1. Eight thousand redirects a second needs several app servers behind the load balancer. Add one spare, so a crash doesn’t hurt. The database barely notices, thanks to the cache.

The finished design, piece by piece:

  1. Load balancer in front, with a health check, so a dead app server stops receiving traffic within seconds.
  2. Stateless app servers. Plan conservatively at 1,000–2,000 redirects a second each, so the 24,000 / s peak needs 12–24 servers, plus one spare (N+1). They hold no state except an ID block they can afford to lose.
  3. Redis with a replica for the hot links. If it fails, redirects get slower but stay correct, because cache-aside falls back to the database.
  4. The database with a replica in another zone for failover; redirects may read from replicas, since a link a second late to appear is fine.
  5. Later, sharding. Load never forces it, but 20 TB after ten years does. Shard by a hash of code: every lookup carries the code, so each request goes to exactly one shard (sharding). This is where a key-value store such as DynamoDB or Cassandra earns its place, since it shards and replicates for you; with Postgres or MySQL you split the data yourself.

Click counts without slowing redirects

Never write to the database on every redirect: that turns 8,000 cheap reads a second into 8,000 writes. Instead, the app server emits a small click event (code, time, country) to a log or message queue such as Kafka and returns the redirect immediately. A separate consumer aggregates counts per link per hour and writes them in batches. Counts become a few seconds late, which nobody minds.

Where this breaks

Two smaller traps worth naming:

  • Custom aliases can collide with generated codes. If someone reserves abc, a counter will eventually produce abc too. Either the generator retries when the insert fails, or aliases live in a separate space the generator never produces (for example, aliases must be at least 8 characters, or contain a -).
  • Abuse. Shorteners hide phishing links. Rate-limit creates, check new URLs against a blocklist such as Google Safe Browsing, and keep the power to disable a code (another reason for 302).

What not to build

Resist adding every box from the course. No queue on the create path: a create is one 300-byte insert, so do it synchronously and return the code at once. No sharding on day one: 2 TB a year fits one database for several years; choose the shard key now, shard later. No microservices: one stateless service with two endpoints is the right size.

In the interview

Your turn: spot the bugs

A candidate proposes: "Codes are the first 7 characters of MD5(long URL). We insert with INSERT ... ON CONFLICT DO UPDATE SET long_url = EXCLUDED.long_url. Redirects return 301 with no expiry. Each redirect runs UPDATE links SET clicks = clicks + 1." List every problem.

Compare with our answer
  • Truncated MD5 collides within a few million links, and ON CONFLICT DO UPDATE silently overwrites someone else's link. Use DO NOTHING, detect the conflict, pick a new code.
  • 301 with no expiry: browsers cache it, so clicks go uncounted and a phishing link can't be fully disabled.
  • A write per redirect turns 8,000 reads a second into 8,000 updates, and a viral link makes them all fight over one row lock. Queue click events and aggregate in batches.
  • No cache on the redirect path.

A strong answer mentions: hash collisions at this scale · overwrite on conflict loses data · 301 caching defeats counting and takedowns · per-click writes create a hot row · an async click pipeline · a cache in front of the database.

Your turn: the requirement changes

Marketing now wants two things: links whose destination can be edited after creation, and a dashboard of clicks per link per hour by country. What changes in your design?

Compare with our answer
  • 302, not 301: a cached 301 keeps sending old visitors to the old destination.
  • On edit, update the row, then delete the cache key and purge the CDN; keep a TTL as a safety net against a racing reader.
  • Clicks: emit {code, ts, country} events to Kafka; a consumer aggregates per (code, hour, country); the dashboard reads only aggregates.
  • Ownership: edits need accounts and an owner_id column.

A strong answer mentions: 302 not 301 · delete the cache key on edit · CDN purge · TTL as a safety net · asynchronous click events · pre-aggregated counts per hour.

Where to go next

For the same recipe at full interview length on a close cousin (a Pastebin, which stores text and so adds object storage), read The design interview recipe. Next in this module: design a chat app.

URL shortener on one page
  • Requirements: create, redirect (< 25 ms, 99.99%), never break or reuse a code; nice to have: aliases, expiry, click counts.
  • Numbers: 200 creates/s vs 8,000 redirects/s (40:1); 6.3 B links/year ≈ 2 TB; hot set ≈ 8 GB.
  • Codes: 62⁷ ≈ 3.5 T; counter handed out in blocks of 1,000, scrambled so codes aren't sequential; or random codes with insert-if-absent.
  • Never truncate a hash without a collision check; the PRIMARY KEY on code is the final guarantee.
  • Redirect path: cache-aside in Redis, TTL capped at link expiry, negative caching for unknown codes.
  • 302 over 301 when you count clicks, expire links or need takedowns; a CDN can still cache the 302 briefly.
  • Clicks: async events → queue → batch aggregation; never a write per redirect.
  • Scale: stateless app servers N+1 behind a load balancer; replicas for failover; shard by hash of code when storage demands it.
Interactive labBuild it yourself on the design boardOpens in the ByteAtlas lab. Your progress is saved in this browser.
Check what stuck

1. A shortener serves 8,000 redirects and 200 creates per second. Where should most of the design effort go?

2. A team generates codes from the first 7 base-62 characters of MD5(long URL), with no duplicate check. What happens as the service grows?

3. Why do app servers reserve blocks of 1,000 IDs from the counter instead of one ID per create?

4. The product needs click counts and the ability to disable phishing links. Which redirect status fits?

5. Bots request millions of random codes that were never created. Each one misses Redis and queries the database. What helps most?

6. How long should a cached redirect live in Redis for a link that expires in 10 minutes?

7. After ten years the links table holds about 20 TB. How should it be split?

Score 60% or more and the lesson is marked complete.

Passing the quiz also marks it complete. Progress is saved in this browser only.