第 24 課：案例研究 - 設計 URL 縮短器

系統架構：從零到英雄

第 7 部分：系統設計案例研究

亞洲開發網

簡介

URL Shortener 是面試中最常見的系統設計問題。雖然簡單，但它涵蓋了許多概念：哈希、資料庫、快取、擴充、分析。

---

1. 要求

1.1 功能

- Tạo short URL từ long URL
- Redirect short URL → long URL
- Custom alias (optional)
- Expiration time (optional)
- Analytics: click count, referrer, location

1.2 非功能性

- Read-heavy (100:1 read/write ratio)
- Low latency redirect (< 50ms)
- High availability (99.99%)
- Short URL không đoán được

1.3 估計

Assumptions:
  100M URLs created / month
  Read:Write = 100:1 → 10B redirects / month

QPS:
  Write: 100M / (30 × 24 × 3600) ≈ 40 URLs/s
  Read:  40 × 100 = 4,000 redirects/s

Storage (5 years):
  100M × 12 × 5 = 6B URLs
  Each URL: ~500 bytes (short + long + metadata)
  Total: 6B × 500B = 3TB

Cache (20% hot URLs):
  4,000 QPS, cache 20% requests
  Cache size: 4,000 × 86,400 × 20% × 500B ≈ 35GB
  → Fits in 1 Redis instance

---

2. 短URL生成

2.1 策略：Base62編碼

Base62: [0-9a-zA-Z] = 62 characters
7 characters: 62^7 = 3.5 trillion combinations

ID = 123456789
Base62 = "8M0kX" (5 chars)

Approach 1: Auto-increment ID → Base62
  Pros: Simple, no collision
  Cons: Predictable (sequential), single point (ID generator)

Approach 2: Hash (MD5/SHA256) → Take first 7 chars
  MD5("https://example.com/long-url") = "a1b2c3d4..."
  Short = "a1b2c3d"
  Pros: Deterministic
  Cons: Collision possible → need collision handling

Approach 3: Pre-generate random IDs
  Generate millions of unique IDs offline
  App picks unused ID from pool
  Pros: No collision, fast
  Cons: Complexity of ID pool management

2.2 分散式系統的 ID 生成

Snowflake-like ID:
  ┌─────────┬──────────┬──────────┬───────────┐
  │ 1 bit   │ 41 bits  │ 10 bits  │ 12 bits   │
  │ sign    │timestamp │machine ID│ sequence  │
  └─────────┴──────────┴──────────┴───────────┘

  → Unique across servers
  → Sortable by time
  → 64-bit → Base62 = 11 chars (take 7)

---

3. 架構

┌──────────────────────────────────────────────────────┐
│                                                       │
│  Client                                               │
│    │                                                   │
│    ▼                                                   │
│  ┌──────────────┐                                     │
│  │ Load Balancer│                                     │
│  └──────┬───────┘                                     │
│         │                                             │
│  ┌──────▼───────┐    ┌──────────────┐                 │
│  │ API Servers  │───►│ Redis Cache  │                 │
│  │ (Stateless)  │    │ (hot URLs)   │                 │
│  └──────┬───────┘    └──────────────┘                 │
│         │                                             │
│  ┌──────▼───────┐    ┌──────────────┐                 │
│  │ Database     │    │ Analytics    │                 │
│  │ (URL mapping)│    │ (Kafka →     │                 │
│  │              │    │  ClickHouse) │                 │
│  └──────────────┘    └──────────────┘                 │
│                                                       │
└──────────────────────────────────────────────────────┘

---

4. 資料庫設計

CREATE TABLE urls (
  id         BIGINT PRIMARY KEY,     -- Snowflake ID
  short_code VARCHAR(7) UNIQUE,      -- Base62 encoded
  long_url   TEXT NOT NULL,
  user_id    BIGINT,                 -- creator
  created_at TIMESTAMP DEFAULT NOW(),
  expires_at TIMESTAMP,
  click_count BIGINT DEFAULT 0
);

-- Index for redirect lookup (hot path)
CREATE INDEX idx_short_code ON urls(short_code);

Database Choice:
  Write path: PostgreSQL (ACID, reliable)
  Read path:  Redis cache (fast lookup)
  Analytics:  ClickHouse (aggregate queries)

---

5.API設計

Create Short URL:
  POST /api/shorten
  {
    "long_url": "https://example.com/very/long/path",
    "custom_alias": "mylink",     // optional
    "expires_at": "2025-01-01"    // optional
  }
  Response: { "short_url": "https://xdev.vn/a1b2c3d" }

Redirect:
  GET /a1b2c3d
  → 301 Redirect to https://example.com/very/long/path

  301 (Permanent): Browser caches, ít analytics
  302 (Temporary): Browser không cache, nhiều analytics hơn
  → Chọn 302 nếu cần analytics chính xác

Analytics:
  GET /api/stats/a1b2c3d
  Response: { "clicks": 15234, "created": "...", ... }

---

6. 重定向流程

User clicks: https://xdev.vn/a1b2c3d

1. Request → Load Balancer → API Server
2. Check Redis: GET "url:a1b2c3d"
   Hit?  → Return long_url (fast!)
   Miss? → Query Database, cache result
3. Return 302 Redirect: Location: {long_url}
4. Async: Publish click event → Kafka
   → Analytics consumer: aggregate clicks

Cache Strategy:
  Write: Create URL → Write DB + Cache
  Read:  Lookup → Cache first → DB if miss
  Eviction: LRU, TTL = 24 hours

---

7. 擴展考慮因素

Database Scaling:
  Read-heavy → Read replicas
  10B+ URLs → Shard by short_code hash
  Partition by created_at (archive old URLs)

Cache Scaling:
  Single Redis thường đủ (35GB fits)
  Nếu cần: Redis Cluster

API Scaling:
  Stateless → Horizontal scaling
  Auto-scale based on QPS

Rate Limiting:
  Prevent abuse: Max 100 URLs/hour per user
  Prevent redirect abuse: Max 1000 redirects/min per IP

---

總結

組件	技術	目的
應用程式介面	Node.js/Go	無狀態、快速
資料庫	PostgreSQL	URL 映射 ACID
快取	Redis	熱門網址查找
分析	卡夫卡+ ClickHouse	點選追蹤
ID 產生	雪花	分散式唯一ID

---

練習

1. 如果需要支援 1M URL/秒（100x 規模），如何更改架構？

2. 設計自訂別名功能：驗證、衝突處理、保留高階名稱。

3.設計URL過期：自動清理，處理過期URL重定向。