System Design · Lesson 5 of 5

Case Study: URL Shortener

Design a URL shortening service end to end.

• Advanced
• 18 min read
• 3 objectives

Before this lessonLesson 4: Queues, APIs and Reliability

Let us apply everything by designing a URL shortener (like bit.ly): users submit a long URL and get a short one; visiting the short link redirects to the original. It is small enough to finish in one lesson yet touches every core idea.

1. Requirements

• Functional: create a short URL, redirect, optional custom alias and expiry, basic click counts.
• Non-functional: very low redirect latency, high availability, links should not be guessable in order, and reads far outnumber writes.

2. Estimates

new_urls_per_day = 100_000_000 / 30          # assume 100M new URLs per month
writes_per_sec = new_urls_per_day / 86_400     # ~40/s
read_write_ratio = 100
reads_per_sec = writes_per_sec * read_write_ratio   # ~4,000/s

records_5_years = 100_000_000 * 12 * 5          # 6 billion
bytes_per_record = 500
storage_tb = records_5_years * bytes_per_record / 1e12
print(round(writes_per_sec), round(reads_per_sec), round(storage_tb, 1))

39 3858 3.0

Roughly 40 writes per second and 4,000 reads per second is modest; 3 TB over five years fits comfortably in a database. The design is read-heavy, so caching is the big lever.

3. API and data model

POST /api/v1/urls       { long_url, custom_alias?, expires_at? } -> { short_url }
GET  /{code}             -> 301/302 redirect to the long URL

table urls(
  code        VARCHAR(10) PRIMARY KEY,
  long_url    TEXT NOT NULL,
  created_at  TIMESTAMP,
  expires_at  TIMESTAMP NULL,
  user_id     BIGINT NULL
)

4. Generating the short code

Seven characters of base62 (a-z, A-Z, 0-9) give 62 to the power 7, about 3.5 trillion codes, far more than the 6 billion needed. Options:

• Hash the URL (MD5 or SHA-256) and take the first 7 characters. Simple, but collisions must be detected and handled.
• Counter + base62: an auto-incrementing id encoded in base62. No collisions, but sequential codes are guessable, and one counter is a bottleneck. Fix by allocating id ranges to each app server, and by adding a shuffle or salt so codes look random.
• Random code with a uniqueness check on insert, retrying on the rare collision.

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

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

print(base62(125), base62(3_500_000_000))

21 3lbTzk

5. High-level design

• Clients hit a load balancer, which spreads requests over stateless app servers.
• Redirect path: check Redis for code; on a miss read the database and fill the cache (cache-aside, long TTL, LRU eviction). The hottest links stay in memory, so most reads never touch the database.
• Write path: validate the URL, allocate a code, insert into the database.
• Database: PostgreSQL with a primary and read replicas; shard by code hash only if it outgrows one cluster. A key-value store such as DynamoDB also fits well, since access is always by key.
• Analytics: publish a click event to a queue; workers aggregate counts asynchronously so redirects stay fast.

6. Trade-offs and edge cases

• 301 vs 302: 301 (permanent) lets browsers cache the redirect, reducing load but hiding later clicks from analytics. 302 keeps every click visible.
• Abuse: rate limit creation, block malicious domains, and scan for phishing.
• Expiry: a background job deletes expired rows; check expires_at on read too.
• Custom aliases need a uniqueness check and reserved words (api, admin).
• Availability: multiple regions with replicated data and DNS failover if global uptime matters.

// Write your solution here