System Design — Thiết Kế URL Shortener Từ A Đến Z • blog.dopana

Thiết kế URL shortener là bài toán kinh điển trong phỏng vấn system design. Nó tưởng đơn giản — nhưng ẩn chứa nhiều vấn đề thú vị: làm sao sinh short code duy nhất? Làm sao handle 10 tỷ URL? Cache thế nào? Redirect loại nào?

Bài này thiết kế một URL shortener từ yêu cầu đến implementation.

Yêu Cầu#

Functional#

Tạo short URL từ long URL
Redirect short URL → long URL
Optional: custom alias, expiry, analytics

Non-Functional#

Highly available: Không downtime
Low latency: Redirect < 10ms
Scale: 100M URLs/month, 10K writes/sec, 100K reads/sec

Estimations#

Metric	Value
Writes	100M / tháng ≈ 38 / sec
Reads	100× writes ≈ 3800 / sec → peak 10K / sec
Storage	100M × 500 bytes ≈ 50 GB / năm
Bandwidth	Write: 38 × 500B ≈ 19 KB/s, Read: 3800 × 500B ≈ 1.9 MB/s

Thiết Kế#

                          ┌─────────────┐
                          │   Client     │
                          └──────┬──────┘
                                 │
                          ┌──────┴──────┐
                          │  Load Balancer │
                          └──────┬──────┘
                                 │
                    ┌────────────┴────────────┐
                    │    Web Server (stateless) │
                    └────────────┬────────────┘
                                 │
              ┌──────────────────┼──────────────────┐
              │                  │                   │
         ┌────┴────┐      ┌────┴────┐       ┌──────┴──────┐
         │  Redis   │      │  DB     │       │  Analytics   │
         │  Cache   │      │Primary  │       │  (async)     │
         └─────────┘      └────┬────┘       └─────────────┘
                               │
                         ┌────┴────┐
                         │  DB     │
                         │Replicas │
                         └─────────┘

plaintext

Base62 — Short Code#

Short code cần: duy nhất, ngắn, URL-safe. Giải pháp: Base62 (a-z, A-Z, 0-9).

Số ký tự	Số lượng URL
6	62⁶ ≈ 56 tỷ
7	62⁷ ≈ 3,500 tỷ
8	62⁸ ≈ 218,000 tỷ

7 ký tự đủ cho hầu hết hệ thống.

Cách 1: Hash + Collision#

Hash MD5 long URL, lấy 7 ký tự đầu, check collision.

import hashlib, base62

def generate_short_code(long_url: str) -> str:
    hash_bytes = hashlib.md5(long_url.encode()).digest()
    return base62.encode(int.from_bytes(hash_bytes[:7], 'big'))

python

Ưu: deterministic (cùng URL → cùng code), không cần DB để sinh. Nhược: collision rate cao khi scale.

Cách 2: Distributed ID + Base62#

Sinh unique ID từ distributed ID generator (Snowflake, Redis incr, PostgreSQL sequence), chuyển sang Base62.

import base62

def generate_short_code(db):
    # Redis INCR hoặc database sequence
    next_id = db.incr('url_counter')
    return base62.encode(next_id)

python

# Chuyển ID → Base62
BASE62 = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def encode_base62(num: int) -> str:
    if num == 0: return BASE62[0]
    chars = []
    while num > 0:
        num, rem = divmod(num, 62)
        chars.append(BASE62[rem])
    return ''.join(reversed(chars))

# encode_base62(123456789) → "8m0Kx" (6 ký tự)

python

Ưu: không collision, đơn giản. Nhược: cần central ID generator.

Database Schema#

CREATE TABLE urls (
    id BIGSERIAL PRIMARY KEY,
    short_code VARCHAR(10) UNIQUE NOT NULL,
    long_url TEXT NOT NULL,
    user_id BIGINT,
    custom_alias VARCHAR(20),
    expires_at TIMESTAMP,
    created_at TIMESTAMP DEFAULT NOW(),
    updated_at TIMESTAMP DEFAULT NOW()
);

CREATE INDEX idx_short_code ON urls(short_code);

-- Analytics (separate DB hoặc Kafka → ClickHouse)
CREATE TABLE clicks (
    id BIGSERIAL PRIMARY KEY,
    short_code VARCHAR(10) NOT NULL,
    clicked_at TIMESTAMP DEFAULT NOW(),
    ip_address INET,
    user_agent TEXT,
    referer TEXT,
    country VARCHAR(2)
);

CREATE INDEX idx_clicks_code ON clicks(short_code, clicked_at);

sql

API Design#

Create short URL#

POST /api/shorten
Content-Type: application/json

{
  "long_url": "https://example.com/very/long/url",
  "custom_alias": "",      // optional
  "expires_in_days": 30    // optional
}

Response: 201
{
  "short_url": "https://short.ly/abc1234",
  "short_code": "abc1234",
  "expires_at": "2026-07-31T10:00:00Z"
}

http

Redirect#

GET /abc1234

Response: 301 (permanent) hoặc 302 (temporary)
Location: https://example.com/very/long/url

http

301 vs 302#

Status	Ý nghĩa	Cache	Khi nào dùng
301	Moved Permanently	Browser cache	Long URL cố định, không cần analytics
302	Found	Không cache	Cần analytics (bitly pattern)

Bitly dùng 302 để track mỗi lần click. Nếu dùng 301, browser cache redirect → không gọi server → mất analytics.

Caching#

Cache Strategy#

Read:   GET short_code → check Redis → nếu miss → query DB → set Redis → redirect
Write:  POST long_url → sinh code → insert DB → set Redis

plaintext

import redis

r = redis.Redis(host='localhost', port=6379, decode_responses=True)

def get_long_url(short_code: str) -> str | None:
    # Check cache
    long_url = r.get(f"url:{short_code}")
    if long_url:
        return long_url
    
    # Cache miss → query DB
    row = db.query("SELECT long_url FROM urls WHERE short_code = %s", short_code)
    if row:
        r.setex(f"url:{short_code}", 86400, row['long_url'])  # TTL 24h
        return row['long_url']
    
    return None

python

Cache TTL#

Hot URLs: TTL dài (7 ngày), refresh mỗi lần access
Cold URLs: TTL ngắn (1 giờ)
LRU eviction khi đầy

Cache Estimations#

10K reads/sec, 80% cache hit → 8000 từ cache, 2000 từ DB. Với Redis cluster 3 node, mỗi node ~10GB RAM, chịu được ~50M entries.

Database Sharding#

Khi URLs > 1 tỷ, cần shard.

Shard key: short_code (hash modulo N shards)

def get_shard(short_code: str) -> int:
    return murmurhash(short_code) % NUM_SHARDS

python

Vấn đề: thêm shard cần rebalance → consistent hashing.

Rate Limiting#

Prevent abuse — giới hạn tạo URL mới:

# Token bucket: 100 URLs/hour/user
def can_create_url(user_id: str) -> bool:
    key = f"rate:{user_id}:{datetime.now().hour}"
    count = r.incr(key)
    if count == 1:
        r.expire(key, 3600)  # TTL 1 giờ
    return count <= 100

python

Implementation Đơn Giản (Flask + Redis + PostgreSQL)#

from flask import Flask, request, redirect, jsonify
import redis, base62, psycopg2

app = Flask(__name__)
r = redis.Redis(decode_responses=True)

@app.route('/shorten', methods=['POST'])
def shorten():
    data = request.json
    long_url = data['long_url']
    
    # Sinh short code
    next_id = r.incr('global_counter')
    short_code = base62.encode(next_id)
    
    # Lưu DB
    cur = db.cursor()
    cur.execute(
        "INSERT INTO urls (short_code, long_url) VALUES (%s, %s)",
        (short_code, long_url)
    )
    db.commit()
    
    # Cache
    r.setex(f"url:{short_code}", 86400, long_url)
    
    return jsonify({'short_url': f'https://short.ly/{short_code}'})

@app.route('/<short_code>')
def redirect_url(short_code):
    # Check cache
    long_url = r.get(f"url:{short_code}")
    
    if not long_url:
        cur = db.cursor()
        cur.execute("SELECT long_url FROM urls WHERE short_code = %s", (short_code,))
        row = cur.fetchone()
        if not row:
            return "Not found", 404
        long_url = row[0]
        r.setex(f"url:{short_code}", 86400, long_url)
    
    # Analytics async (Kafka hoặc queue)
    send_click_event(short_code, request)
    
    return redirect(long_url, code=302)

python

Evolution#

V1: PostgreSQL + Redis (1M URLs/month)
    └── Đơn giản, đủ dùng cho MVP

V2: Add sharding + read replicas (100M URLs/month)
    └── Scale DB, cache cluster

V3: Add Kafka + ClickHouse (1B URLs/month)
    └── Analytics riêng, không ảnh hưởng redirect path

V4: Global load balancer + multi-region (10B+ URLs/month)
    └── Geo-routing, global Redis, active-active DB

plaintext

Bắt đầu đơn giản, scale dần. Không cần Kafka và ClickHouse từ ngày đầu.

Tổng Kết#

URL shortener tưởng đơn giản nhưng dạy nhiều concept quan trọng:

Base62 encoding — sinh short code
Caching — Redis, TTL, LRU
Database sharding — consistent hashing
HTTP redirect — 301 vs 302
Rate limiting — token bucket
Analytics — async processing
Evolution — từ simple đến global scale

System Design — Thiết Kế URL Shortener Từ A Đến Z

Yêu Cầu#

Functional#

Non-Functional#

Estimations#

Thiết Kế#

Base62 — Short Code#

Cách 1: Hash + Collision#

Cách 2: Distributed ID + Base62#

Database Schema#

API Design#

Create short URL#

Redirect#

301 vs 302#

Caching#

Cache Strategy#

Cache TTL#

Cache Estimations#

Database Sharding#

Rate Limiting#

Implementation Đơn Giản (Flask + Redis + PostgreSQL)#

Evolution#

Tổng Kết#

Tài liệu tham khảo#