System Design Interview Framework

// Example: "Design a URL shortener"
// Questions to ask:
// - Should users be able to customize short URLs?
// - Do short URLs expire?
// - Do we need analytics (click counts, geographic data)?
// - Is there authentication or can anyone create URLs?
// - What is the expected format of short URLs?

interface FunctionalRequirements {
  core: string[];     // Must have
  secondary: string[]; // Nice to have, time permitting
  outOfScope: string[]; // Explicitly excluded
}

const urlShortenerRequirements: FunctionalRequirements = {
  core: [
    "Create short URL from long URL",
    "Redirect short URL to original URL",
    "Short URLs should be unique and non-guessable",
  ],
  secondary: [
    "Custom aliases",
    "URL expiration",
    "Click analytics",
  ],
  outOfScope: [
    "User authentication",
    "Rate limiting UI",
    "Admin dashboard",
  ],
};

interface NonFunctionalRequirements {
  scale: {
    dailyActiveUsers: number;
    readWriteRatio: number;
    peakMultiplier: number;
  };
  performance: {
    readLatency: string;   // e.g., "< 50ms for 99th percentile"
    writeLatency: string;  // e.g., "< 200ms"
  };
  availability: string;    // e.g., "99.99%"
  consistency: string;     // "strong" or "eventual"
  durability: string;      // "zero data loss"
}

// Key questions:
// - How many users? DAU/MAU?
// - What is the read/write ratio?
// - What are the latency requirements?
// - What consistency level is needed?
// - What are the availability requirements?
// - Is there geographic distribution?

// Example: URL shortener estimation
// Given: 100M URLs created per month

// Write QPS
const urlsPerMonth = 100_000_000;
const writeQPS = urlsPerMonth / (30 * 24 * 3600); // ~40 writes/sec

// Read QPS (assuming 100:1 read:write ratio)
const readQPS = writeQPS * 100; // ~4,000 reads/sec
const peakReadQPS = readQPS * 3; // ~12,000 reads/sec at peak

// Storage (5-year horizon)
const urlsIn5Years = urlsPerMonth * 12 * 5; // 6 billion URLs
const avgRecordSize = 500; // bytes (short URL + long URL + metadata)
const totalStorage = urlsIn5Years * avgRecordSize; // 3 TB

// Bandwidth
const readBandwidth = readQPS * avgRecordSize; // ~2 MB/s (trivial)

// Conclusions:
// - QPS is manageable with a single database + caching
// - 3 TB fits on a single machine but sharding is reasonable
// - Caching hot URLs in Redis will handle most reads

// High-level components for URL shortener
// 
// Client -> Load Balancer -> API Servers -> Database
//                                       -> Cache (Redis)
//
// Write flow:
// 1. Client sends POST /shorten { url: "https://long-url.com" }
// 2. API server generates short code
// 3. Store mapping in database
// 4. Return short URL to client
//
// Read flow:
// 1. Client sends GET /{shortCode}
// 2. Check Redis cache first
// 3. If cache miss, query database
// 4. Cache the result in Redis
// 5. Return 301/302 redirect to original URL

// Component decisions to state and justify:
const architectureDecisions = {
  loadBalancer: "AWS ALB - distributes traffic, SSL termination",
  apiServers: "Node.js - handles HTTP, stateless, horizontally scalable",
  database: "PostgreSQL - reliable, handles 40 writes/sec easily",
  cache: "Redis - in-memory, sub-ms reads for hot URLs",
  idGeneration: "Base62 encoding of auto-increment ID or pre-generated IDs",
};

// Deep dive: Short URL generation strategy

// Option 1: Hash-based (MD5/SHA256 + truncate)
function hashBased(longUrl: string): string {
  const hash = md5(longUrl);
  return base62Encode(hash.substring(0, 7));
  // Problem: collisions possible, need to check and retry
}

// Option 2: Counter-based (auto-increment + base62)
function counterBased(counter: bigint): string {
  return base62Encode(counter);
  // Problem: predictable, sequential
  // Solution: Use a distributed ID generator (Snowflake)
}

// Option 3: Pre-generated key service
class KeyGenerationService {
  // Pre-generate millions of unique keys
  // Store in a database table
  // API servers fetch keys in batches (e.g., 1000 at a time)
  // Mark keys as used

  private localKeys: string[] = [];

  async getKey(): Promise<string> {
    if (this.localKeys.length === 0) {
      // Fetch a batch from the key database
      this.localKeys = await this.fetchKeyBatch(1000);
    }
    return this.localKeys.pop()!;
  }
}

// Decision: Option 3 (pre-generated keys) because:
// - No collision handling needed
// - Keys are not sequential (better security)
// - Scales well (batch fetching reduces DB calls)
// - Trade-off: need to manage the key pool