Phase 5 · Chapter 1

System Design: URL Shortener

Constraints → Bottlenecks → Solutions. From a toy problem to a distributed system.

What this chapter does to you: The URL Shortener is the "Hello World" of system design interviews. Most candidates treat it as a simple problem and give a shallow answer. You will not do that. Every decision — the short code algorithm, the DB schema, the cache strategy, the redirect type — has a reason grounded in physics and tradeoffs. After this chapter, you will know how to approach ANY system design problem from scratch, because the method is always the same.

The Method — How to Approach Every System Design Problem

Before we touch the URL Shortener, understand the method. Every system design problem follows this exact sequence:

Step 1: Clarify requirements       What are we actually building?
Step 2: Estimate scale             How big is the problem?
Step 3: Define the data model      What do we store and how?
Step 4: Design the API             What operations exist?
Step 5: Design the components      What does the architecture look like?
Step 6: Identify bottlenecks       Where will it break?
Step 7: Solve the bottlenecks      How do we scale each component?

You never skip to Step 5. Engineers who draw boxes first don't understand what they're drawing. The requirements and scale estimation are what make the architecture obvious — not the other way around.

Step 1: Clarify Requirements

An interviewer says "design a URL shortener." Before drawing anything, ask:

Functional requirements — what must the system do?

• User submits a long URL → gets a short URL back
• User visits the short URL → gets redirected to the long URL
• Optional: custom aliases (bit.ly/my-brand instead of bit.ly/x7k2p)
• Optional: expiration dates on short URLs
• Optional: analytics — how many times was a URL clicked?

Non-functional requirements — what qualities must it have?

• High availability: redirects must work even during partial outages
• Low latency: redirects should be fast — users notice > 200ms
• Durability: a created short URL must work forever (unless it expires)
• Consistency: is it okay if a newly created URL takes 1-2 seconds to work globally?

Out of scope (confirm in interview):

• User accounts and authentication
• Link preview cards
• Geo-targeting (same short URL → different long URL per country)

The requirements already tell you the architecture. High read volume + low latency + high availability = caching is mandatory. Durability = a DB that doesn't lose data. Eventual consistency acceptable = we can use replication without strict consistency.

Step 2: Estimate Scale

Write volume:

• 100 million new URLs created per day
• 100M / 86,400 seconds = ~1,160 writes/second
• Peak (2× average) = ~2,500 writes/second

Read volume:

• Read:write ratio for URL shorteners is approximately 100:1 (one URL is created, clicked many times)
• 100M × 100 = 10 billion redirects per day
• 10B / 86,400 = ~115,000 reads/second
• Peak = ~230,000 reads/second

Storage:

• Each URL record: short_code (7 bytes) + long_url (avg 200 bytes) + metadata (~100 bytes) ≈ 300 bytes
• 100M new URLs/day × 365 days × 5 years = 182.5 billion URLs
• 182.5B × 300 bytes ≈ 54 TB over 5 years

This estimation immediately tells you three things:

1. Reads massively dominate writes (100:1). Optimize for reads.
2. 230,000 reads/second from a single Postgres → impossible. Need caching.
3. 54 TB → won't fit in RAM. DB on disk is the source of truth, cache the hot subset.

Back-of-envelope estimation is not busywork. It's the calculation that tells you which components you need before you've drawn a single box.

Rerun this estimate yourself. Predict the peak write rate, then drag the inputs and see how quickly reads become the problem.

Step 3: The Short Code — The Core Algorithm

How do you generate a 7-character short code that:

• Is unique for every URL
• Is short and URL-safe
• Can be generated at high throughput

You have three options. Each has distinct tradeoffs.

Option 1: Hash-Based

short_code = MD5(long_url)[0:7]

Take the MD5 hash of the long URL, use the first 7 characters.

Problem 1 — Collisions: Two different long URLs can produce the same 7-character prefix. MD5 produces 128 bits. Truncated to 7 base-16 chars = 28 bits = ~268 million values. With 182 billion URLs over 5 years, birthday paradox guarantees collisions.

Fix: On collision, append a counter and rehash. MD5(url + "1")[0:7]. But now reads must handle this — the DB needs to store the original URL to verify the hash, and generation becomes a loop.

Problem 2 — Duplicate detection: Two users shorten the same URL. Do they get the same short code? With hashing, yes — same input = same hash. This might be desirable (deduplication) or undesirable (user A can see user B's URL via the same short code).

When to use hash-based: When you want deterministic codes and deduplication. Content-addressed storage (same URL = same code) is a feature, not a bug.

Option 2: Auto-Increment ID + Base62 Encoding

This is what most production shorteners use. Let's understand it completely.

Base62 encoding:

Our alphabet: 0-9 (10 chars) + a-z (26 chars) + A-Z (26 chars) = 62 characters. URL-safe. Human-readable. 62^7 = 3.5 trillion unique codes — more than enough.

Database auto-increments an ID:
  ID = 1       → base62 → "1"
  ID = 62      → base62 → "10"
  ID = 3844    → base62 → "100"
  ID = 125,000 → base62 → "W7e"

The algorithm:

const CHARS = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'

function toBase62(num) {
  if (num === 0) return '0'
  let result = ''
  while (num > 0) {
    result = CHARS[num % 62] + result
    num = Math.floor(num / 62)
  }
  return result
}

toBase62(1)         → "1"
toBase62(62)        → "10"
toBase62(100000000) → "6LAze"   // 7 chars at ~100 million

The flow:

Advantages:

• Guaranteed uniqueness — DB auto-increment is monotonically increasing
• No collision detection needed
• Short codes are predictable in length as ID grows

Disadvantage — Sequential predictability: IDs are sequential. 6LAzk → next one is 6LAzl. A competitor or attacker can enumerate your entire URL database. For a public shortener this matters. For an internal tool it doesn't.

Fix for predictability: Don't expose the raw sequential ID. Use a counter but XOR it with a random mask, or use a random shuffle of the base62 alphabet per deployment.

Option 3: Random Code Generation

function generateCode(length = 7) {
  const chars = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
  let code = ''
  for (let i = 0; i < length; i++) {
    code += chars[Math.floor(Math.random() * 62)]
  }
  return code
}

Problem: Random means collisions are possible. 62^7 = 3.5 trillion. At 182 billion URLs, birthday paradox gives a collision probability of ~1 in 19. Not trivial. Must check DB on every generation.

Mitigation: Generate in batches, pre-check uniqueness, maintain a pool. Or accept the retry loop:

let code
do {
  code = generateCode()
} while (await urlExists(code))   // check DB until unique

At low collision probability, this loop almost never runs twice.

The production choice for this design: Auto-increment + base62. Guaranteed uniqueness, high throughput, no retry loop. Mitigate predictability with ID shuffling if needed.

Step 4: Data Model

The core table:

CREATE TABLE urls (
  id           BIGSERIAL PRIMARY KEY,
  short_code   VARCHAR(10) NOT NULL UNIQUE,
  long_url     TEXT NOT NULL,
  user_id      UUID,                           -- null if anonymous
  created_at   TIMESTAMP DEFAULT NOW(),
  expires_at   TIMESTAMP,                      -- null = never expires
  click_count  BIGINT DEFAULT 0               -- denormalized for fast reads
);

CREATE UNIQUE INDEX idx_short_code ON urls(short_code);
CREATE INDEX idx_user_id ON urls(user_id);     -- for "my links" dashboard
CREATE INDEX idx_expires_at ON urls(expires_at) WHERE expires_at IS NOT NULL;

The analytics table (separate):

CREATE TABLE clicks (
  id           BIGSERIAL PRIMARY KEY,
  short_code   VARCHAR(10) NOT NULL,
  clicked_at   TIMESTAMP DEFAULT NOW(),
  ip_hash      VARCHAR(64),                    -- hashed for privacy
  country      VARCHAR(2),                     -- from IP geolocation
  referrer     TEXT,
  user_agent   TEXT
);

CREATE INDEX idx_clicks_short_code ON clicks(short_code, clicked_at DESC);

Why separate tables?

The urls table is read on every redirect — it must be fast. The clicks table is write-heavy — every redirect inserts a row. Mixing them means a high-write analytics table slows down your fast-read redirect table. Separation keeps each table's access pattern clean.

The click_count denormalization:

COUNT(*) FROM clicks WHERE short_code = 'xyz' on a busy URL could mean scanning millions of rows. We keep a click_count on the urls table — an approximate count, updated with a background job or write-behind cache. Display this. Run the exact COUNT(*) only for detailed analytics dashboards.

Step 5: API Design

POST /api/urls
Body: { longUrl: "https://...", customAlias?: "my-brand", expiresAt?: "2025-01-01" }
Response: { shortUrl: "https://short.ly/6LAzk", shortCode: "6LAzk" }
Status: 201 Created

GET /{shortCode}
Response: 301/302 redirect to longUrl
Status: 301 (permanent) or 302 (temporary) — this choice matters enormously

GET /api/urls/{shortCode}/stats
Response: { clicks: 14200, countries: {...}, referrers: {...} }
Status: 200

DELETE /api/urls/{shortCode}
Response: 204 No Content
Status: 204

301 vs 302 — This Is Not a Trivial Choice

301 Moved Permanently: Browser caches the redirect. Next time the user visits short.ly/6LAzk, the browser redirects locally — no request ever reaches your server.

Consequence: you lose all analytics after the first visit. Consequence: if you ever need to change where 6LAzk points, you can't — browsers cached it.

302 Found (Temporary Redirect): Browser does not cache. Every visit hits your server.

Consequence: you capture every click for analytics. Consequence: more load on your servers. Consequence: you can change the destination at any time.

The correct choice depends on your product: If analytics matter → 302. If your URLs never change and you want maximum performance → 301. Most shorteners use 302 because analytics are core to the value proposition.

There's a middle ground: 301 with a Cache-Control: max-age=300 header. Browsers cache for 5 minutes. Reduces server load while keeping analytics reasonably fresh.

Step 6: The Architecture — First Pass

This is the naive architecture. It works until you identify the bottlenecks.

Step 7: Identify the Bottlenecks

Bottleneck 1: The redirect path is hot

230,000 reads/second. The redirect path is:

GET /6LAzk
→ SELECT long_url FROM urls WHERE short_code = '6LAzk'
→ 302 Redirect

Postgres with a proper index can do ~10,000-50,000 reads/second on a single machine. 230,000 reads/second → Postgres melts. Even with read replicas you need 5-10 replicas.

The fix: Cache the redirect

async function redirect(shortCode) {
  // 1. Check cache — sub-millisecond
  const cached = await redis.get(`url:${shortCode}`)
  if (cached) {
    return redirect(cached)   // 99% of requests end here
  }

  // 2. Cache miss — hit DB (~1% of requests)
  const url = await db.query(
    'SELECT long_url, expires_at FROM urls WHERE short_code = $1',
    [shortCode]
  )

  if (!url) return 404

  // 3. Check expiry
  if (url.expires_at && url.expires_at < new Date()) {
    return 410  // Gone
  }

  // 4. Cache it — TTL based on expiry or default
  const ttl = url.expires_at
    ? Math.floor((url.expires_at - Date.now()) / 1000)
    : 86400  // 24 hours for non-expiring URLs

  await redis.set(`url:${shortCode}`, url.long_url, 'EX', ttl)

  return redirect(url.long_url)
}

With caching: 99% of reads serve from Redis (<1ms). Postgres only sees ~1% of traffic. 230,000 reads/second → 2,300 Postgres reads/second. Easily handled.

Redis can handle 100,000+ operations/second. But 230,000? You need Redis Cluster or multiple Redis instances. One Redis instance per region.

Bottleneck 2: Write contention on auto-increment

2,500 writes/second. Auto-increment in Postgres: the table has a sequence (a counter). Every INSERT locks the sequence, increments, releases.

2,500 concurrent inserts fighting over one sequence = lock contention.

The fix: ID generation service

Don't generate IDs in Postgres. Pre-generate blocks of IDs:

class IdGenerator {
  constructor() {
    this.current = 0
    this.max = 0
  }

  async nextId() {
    if (this.current >= this.max) {
      // Fetch next block of 1000 IDs from DB
      const result = await db.query(`
        UPDATE id_counter
        SET current_val = current_val + 1000
        RETURNING current_val - 1000 AS start, current_val AS end
      `)
      this.current = result.start
      this.max = result.end
    }
    return this.current++
  }
}

Each app server grabs a block of 1,000 IDs at once. 2,500 writes/second across 3 app servers = ~833 writes/server/second. Each server only hits the sequence every ~1.2 seconds. Lock contention eliminated.

Bottleneck 3: Analytics writes are high volume

230,000 redirects/second → 230,000 INSERT INTO clicks per second. No single Postgres can handle this.

The fix: Queue the analytics writes

// In the redirect handler — don't write to DB synchronously
async function redirect(shortCode, req) {
  const longUrl = await getLongUrl(shortCode)  // cached

  // Fire and forget analytics
  await analyticsQueue.add('recordClick', {
    shortCode,
    ip: req.ip,
    referrer: req.headers.referer,
    userAgent: req.headers['user-agent'],
    timestamp: Date.now()
  })

  // Return redirect immediately — don't wait for analytics
  return longUrl
}

The redirect is instant. Analytics are written asynchronously via BullMQ. Workers batch-insert clicks into Postgres in groups of 1,000:

worker = new Worker('analytics', async (job) => {
  // Process 1000 clicks as a single bulk insert
  await db.query(`
    INSERT INTO clicks (short_code, clicked_at, ip_hash, referrer, user_agent)
    SELECT * FROM UNNEST($1::text[], $2::timestamp[], $3::text[], $4::text[], $5::text[])
  `, [codes, timestamps, ips, referrers, agents])
})

Batch inserts are dramatically more efficient than individual inserts. 1,000 rows in one INSERT vs 1,000 separate INSERTs = ~100× throughput.

Bottleneck 4: Single DB is a single point of failure

One Postgres → one crash = site down.

The fix: Postgres replication

Write creation to primary. Read redirects from replicas (via read replica pool). Replication lag is typically <1 second — acceptable for URL redirects.

If primary fails: promote a replica. Down for ~30 seconds during failover. Tools: Patroni, AWS RDS Multi-AZ, Heroku Postgres.

Step 8: The Complete Architecture

The data flow for a redirect:

The data flow for URL creation:

Step 9: Custom Aliases

POST /api/urls
{ longUrl: "...", customAlias: "my-campaign" }

Custom aliases must:

• Be unique (DB constraint + pre-check)
• Not conflict with reserved words (api, admin, health, robots.txt)
• Be rate-limited (prevent namespace squatting)

const RESERVED = new Set(['api', 'admin', 'health', 'login', 'register', 'static'])

async function createUrl(longUrl, customAlias) {
  if (customAlias) {
    if (RESERVED.has(customAlias.toLowerCase())) {
      throw new Error('This alias is reserved')
    }
    const exists = await db.query('SELECT id FROM urls WHERE short_code = $1', [customAlias])
    if (exists) throw new Error('Alias taken')
    return insert(longUrl, customAlias)
  }
  // Auto-generate
  const id = await idGenerator.nextId()
  const shortCode = toBase62(id)
  return insert(longUrl, shortCode)
}

Step 10: The Expiry Problem — Cleaning Up Dead URLs

URLs with expires_at in the past should return 410 Gone. But they still exist in the DB and cache.

In the cache: Set TTL = expires_at - now. Cache auto-expires. ✅

In the DB: Expired rows accumulate forever if you don't clean them.

The fix: Background cleanup job

// BullMQ scheduled job, runs daily
queue.add('cleanExpiredUrls', {}, {
  repeat: { cron: '0 3 * * *' }   // 3am every day
})

worker = new Worker('cleanExpiredUrls', async () => {
  await db.query(`
    DELETE FROM urls
    WHERE expires_at < NOW() - INTERVAL '7 days'
    LIMIT 10000
  `)
  // Limit 10000 per run to avoid long lock duration
  // Re-queue if more exist
})

Why - INTERVAL '7 days'? Give yourself a week buffer before hard deletion. Analytics for a recently expired URL might still be useful. And a user might have a browser tab open with the URL — graceful degradation.

The partial index from Chapter 3:

CREATE INDEX idx_expires_at ON urls(expires_at)
WHERE expires_at IS NOT NULL

This index only covers rows that have an expiry date — not the majority of URLs that never expire. Small, fast, efficient.

Step 11: What We Learned — The General Method Applied

Look at how the method worked:

None of these were arbitrary choices. Each one was forced by the scale estimates and the constraints we clarified in Step 1.

This is system design thinking. Not patterns memorized — constraints followed to conclusions.

Practice Problems

Problem 1 (Scale Estimation): You're building the URL shortener for India only. Initial scale:

• 5 million new URLs/day
• 50:1 read:write ratio
• Average long URL: 150 bytes

Calculate: writes/second, reads/second, storage after 3 years. Based on these numbers, do you need Redis caching from day 1? At what scale does single Postgres become the bottleneck?

Problem 2 (Algorithm Design): Your CTO wants the short codes to be non-sequential for security. But you also need guaranteed uniqueness without a retry loop.

Design an ID generation approach that:

• Guarantees uniqueness without DB collision checks
• Produces non-sequential codes (not predictably incrementing)
• Handles 2,500 writes/second

(Hint: what if you shuffle the base62 alphabet differently per ID range? Or XOR the integer ID with a fixed secret before encoding?)

Problem 3 (Failure Analysis): Your Redis cluster goes down completely. The DB is healthy.

For each of these operations, what happens?

• A user visits a short URL for the first time
• A user visits a short URL they visited yesterday (cached)
• A user creates a new short URL
• Your analytics queue

For each: does the system degrade gracefully or fail completely? What would you change in the architecture to improve resilience?

Problem 4 (Deep Design): A customer asks for "branded domains" — their short URLs should use their own domain. go.yourcorp.com/6LAzk instead of short.ly/6LAzk.

How does this change your architecture?

• How does a request to go.yourcorp.com/6LAzk reach your servers?
• How do you know which customer owns go.yourcorp.com?
• What changes in your DB schema?
• What changes in your cache key design?

Problem 5 (Connect to Previous Chapters): Your URL shortener is getting DDoS'd. Someone is hitting the redirect endpoint with 500,000 requests/second for a single short code abc123.

Even with Redis caching, 500,000 requests/second hitting your app servers is causing CPU spikes. Each request still has Node.js overhead: parse HTTP, check rate limit (Redis), read cache (Redis), send response.

Design a complete mitigation strategy using tools from:

• Chapter 2 (Rate Limiting): how and where to limit
• Chapter 1 of Phase 4 (Caching): what extra caching layer stops this at the edge
• Phase 1 Chapter 2 (Network): which layer can absorb this before it reaches your app

What's Coming in Chapter 2 of Phase 5

Chapter 1 was the URL Shortener — a read-heavy system with a simple data model.

Chapter 2 is Twitter's Feed — a write-heavy system with a complex fan-out problem.

The core question: when user A posts a tweet and has 10 million followers, how do you update 10 million feeds in real time without melting your infrastructure?

The answer involves a technique called fan-out on write vs fan-out on read — one of the most important system design tradeoffs in social systems. It connects directly to what you know about queues (Phase 4), caching (Phase 4), and database reads at scale (Phase 2).

End of Phase 5, Chapter 1. Estimated reading time: 75-90 minutes. Practice problems: 60-90 minutes. Do not proceed to Chapter 2 until you can do Problem 3 fully — the Redis failure analysis. A system that can't survive its cache going down is not a production system. Knowing exactly what degrades and what fails is the difference between a system you built and a system you understand.