Track 10 · Case Study 01Alex Xu Ch. 8

Design a URL Shortener (TinyURL)

The canonical system design interview problem: back-of-the-envelope capacity estimations for 100M URLs/day, Base62 encoding vs. Key Generation Services (KGS), 301 vs. 302 HTTP redirect mechanics, and low-latency Redis caching.

⏱️ Estimated Reading: 30 mins•Prerequisites: Tracks 1–9 Foundational Blocks•Interactive Lab: Base62 & URL Shortener Lab

📐 STEP 1 · REQUIREMENTS & CAPACITY ESTIMATION

1. Requirements & Back-of-the-Envelope Estimation

Let's establish the core scope and system scale for a planetary-level URL shortening service like Bitly or TinyURL:

Functional Requirements

Given a long URL, return a short unique alias (e.g. https://tiny.url/7bX9q1).
Redirect short links to the original long URL with sub-10ms latency.
Allow users to specify optional custom aliases (e.g. /my-cool-link).
Links can optionally expire after a configurable TTL.

Non-Functional Requirements

High Availability (99.99%): Redirections must never go down.
Ultra-Low Latency: P99 redirect latency < 10ms.
Read-Heavy: 10:1 Read-to-Write ratio.
Non-Predictable: Short IDs should not be sequentially guessable.

📊 Back-of-the-Envelope Math (5-Year Horizon):

Traffic Estimation

• Write Rate: 100M URLs / day → 1,160 writes/sec

• Read Rate (10:1): 1B reads / day → 11,600 reads/sec

• Peak Read QPS: ~25,000 RPS

Storage & Memory

• 5-Year URLs: 100M × 365 × 5 = 182.5 Billion

• Row Size: 550 Bytes → 5-Year Storage: ~100 Terabytes

• Daily 20% Cache (80/20 rule): ~110 Gigabytes RAM

🔀 STEP 2 · HTTP REDIRECT PROTOCOLS

2. 301 Permanent vs. 302/307 Temporary Redirects

When a user visits https://tiny.url/7bX9q1, which HTTP status code should the server return? This is a classic interview trade-off question:

HTTP 301 Moved Permanently

The browser caches the redirection permanently on the user's local device. Subsequent visits bypass our backend entirely!

• Pro: Near-zero server load on repeat visits.

• Con: We cannot track analytics, click counts, or referrer data!

HTTP 302 / 307 Temporary Redirect

The browser sends every single request to our server, and we respond with Location: https://target.com.

• Pro: 100% accurate click analytics, bot detection, and geolocation tracking.

• Con: Higher traffic on server (solved using Redis cache).

🔢 STEP 3 · SHORTENING ALGORITHMS

3. Base62 Encoding & The Key Generation Service (KGS)

Why Base62? Base62 uses [0-9, a-z, A-Z] (62 characters total), which is URL-safe and avoids special characters like + or / found in Base64:

How Many Characters Do We Need?

• 6 Characters: 62^6 = 56,800,235,584 (~56.8 Billion URLs — Not enough for 182B 5-yr scale)

• 7 Characters: 62^7 = 3,521,614,606,208 (~3.52 Trillion URLs — Massive headroom!)

Method 1: MD5 / SHA-256 Hash + Truncate

Compute MD5(long_url) and take first 7 characters.

⚠️ Collision Hazard: If two different URLs produce the same 7 chars, you must append salt and retry in a loop until collision is resolved.

Method 2: 64-bit Unique ID → Base62 (Gold Standard)

Generate a 64-bit unique integer (via Snowflake or ZooKeeper token range), then convert the integer directly to Base62.

✅ Zero Collisions: Pure mathematical 1-to-1 bijection. Impossible to collide.

🏗️ STEP 4 · HIGH-LEVEL ARCHITECTURE

4. End-to-End System Architecture

TinyURL Planetary Architecture Diagram

🧪 LIVE SHORTENER LAB

5. Interactive Base62 & URL Shortener Lab

Type a long URL or unique 64-bit integer. Observe real-time Base62 conversion, simulated Redis cache hits, and 301 vs 302 redirection telemetry.

ENTER LONG URL:

SIMULATED 64-BIT INTEGER ID:

HTTP REDIRECT STRATEGY:

GENERATED SHORT URL:

https://tiny.url/7bX9q1

Base62 Encoding of ID: 1115712284912 → 7bX9q1

EXECUTION TELEMETRY:

• Cache Status: HIT (Redis RAM in 0.8ms)
• HTTP Status: 302 Found
• Analytics: Click event dispatched to Kafka

💻 PRODUCTION PATTERNS · CODE TEMPLATES

6. Base62 Shortening Service in 5 Languages

base62_url_shortener

class Base62Codec:
    ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
    BASE = len(ALPHABET)

    @classmethod
    def encode(cls, num: int) -> str:
        if num == 0:
            return cls.ALPHABET[0]
        digits = []
        while num > 0:
            digits.append(cls.ALPHABET[num % cls.BASE])
            num //= cls.BASE
        return ''.join(reversed(digits))

    @classmethod
    def decode(cls, s: str) -> int:
        num = 0
        for char in s:
            num = num * cls.BASE + cls.ALPHABET.index(char)
        return num

class UrlShortenerService:
    def __init__(self, id_generator, redis_client, db_client):
        self.id_gen = id_generator
        self.redis = redis_client
        self.db = db_client

    def shorten_url(self, long_url: str) -> str:
        # 1. Get globally unique 64-bit ID
        unique_id = self.id_gen.generate_id()
        # 2. Encode to Base62
        short_code = Base62Codec.encode(unique_id)
        # 3. Store mapping in DB and warm Redis cache
        self.db.save(short_code, long_url)
        self.redis.set(f"url:{short_code}", long_url, ex=86400)
        return f"https://tiny.url/{short_code}"

const ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
const BASE = BigInt(62);

export class Base62Codec {
  static encode(id: bigint): string {
    if (id === 0n) return ALPHABET[0];
    let num = id;
    let result = "";
    while (num > 0n) {
      result = ALPHABET[Number(num % BASE)] + result;
      num = num / BASE;
    }
    return result;
  }

  static decode(str: string): bigint {
    let num = 0n;
    for (const char of str) {
      num = num * BASE + BigInt(ALPHABET.indexOf(char));
    }
    return num;
  }
}

package main

import (
	"strings"
)

const Alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
const Base = uint64(len(Alphabet))

func EncodeBase62(num uint64) string {
	if num == 0 {
		return string(Alphabet[0])
	}
	var sb strings.Builder
	for num > 0 {
		rem := num % Base
		sb.WriteByte(Alphabet[rem])
		num /= Base
	}
	// Reverse string
	runes := []rune(sb.String())
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	return string(runes)
}

public class Base62Codec {
    private static final String ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    private static final int BASE = ALPHABET.length();

    public static String encode(long num) {
        if (num == 0) return String.valueOf(ALPHABET.charAt(0));
        StringBuilder sb = new StringBuilder();
        while (num > 0) {
            sb.append(ALPHABET.charAt((int)(num % BASE)));
            num /= BASE;
        }
        return sb.reverse().toString();
    }

    public static long decode(String str) {
        long num = 0;
        for (char c : str.toCharArray()) {
            num = num * BASE + ALPHABET.indexOf(c);
        }
        return num;
    }
}

#include <string>
#include <algorithm>

const std::string ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

std::string encode_base62(uint64_t num) {
    if (num == 0) return std::string(1, ALPHABET[0]);
    std::string result = "";
    while (num > 0) {
        result += ALPHABET[num % 62];
        num /= 62;
    }
    std::reverse(result.begin(), result.end());
    return result;
}

🎯 INTERVIEW SCENARIOS

7. URL Shortener Scenario Quizzes

Scenario 1: A marketing team demands that short URLs return HTTP 301 Permanent Redirects to reduce server load. Why would the analytics team strongly object to this?

Scenario 2: Two concurrent users attempt to claim the same custom short alias 'my-brand' at the exact same millisecond. How should the database layer handle this race condition?

🎓 CAPSTONE CHALLENGE · HANDS-ON STUDIO

Ready to Build? Draw & AI-Validate the TinyURL Architecture

You've mastered the 100M writes/day capacity math, Base62 token ranges, 301 vs 302 redirect mechanics, and Redis cache stampede mitigations. Put your knowledge to the test on the interactive canvas and get instant AI grading!

Interactive Architecture Studio✨ Evaluate Using AI

Draw on the Whiteboard Canvas → Instant 1-Click AI critique checks your SPOFs, caching tiers, and bottleneck risks.

🚀 Launch Architecture Studio →

Full Deep-Dive Locked