Bitly xử lý hàng tỷ click mỗi tháng. TinyURL có hơn 1 tỷ link được tạo ra. Phía sau một cái link ngắn 6 ký tự là cả một hệ thống phân tán phức tạp — và đây là bài toán kinh điển nhất trong system design interview.
Đề bài
Thiết kế hệ thống cho phép người dùng nhập URL dài và nhận lại một URL ngắn. Khi truy cập URL ngắn sẽ redirect về URL gốc. Hệ thống phải xử lý lượng truy cập lớn, độ trễ thấp và đảm bảo tính sẵn sàng cao.
Hướng tư duy:
- Làm rõ yêu cầu trước: tạo link ngắn nhanh, redirect nhanh, link không bị trùng, mở rộng được khi traffic tăng
- Functional cần có API tạo short link và API redirect. Non-functional tập trung vào scalability, high availability và low latency
- Ước lượng scale: giả sử vài trăm triệu link, đọc nhiều hơn ghi rất nhiều → read-heavy system. Điều này ảnh hưởng trực tiếp đến việc chọn cache và database
Yêu cầu hệ thống
| API | Mô tả |
|---|---|
POST /api/shorten | Nhận long URL, trả về short URL |
GET /{short_code} | Redirect về URL gốc |
Non-functional: scalability (horizontal), high availability (99.99%+), low latency cho redirect (< 50ms).
Ước lượng cho hàng triệu người dùng
Để thiết kế đúng, phải biết hệ thống cần chịu tải bao nhiêu:
1
2
3
Write QPS : 5,000,000 link/ngày ÷ 86,400s ≈ 60 QPS
Read QPS : 60 × 400 (read/write ratio) ≈ 24,000 QPS
Storage : ~9 tỷ records × 300 bytes ≈ 2.7 TB / 5 năm
Read/Write ratio lên đến 400:1 — cứ 1 lần tạo link thì có 400 lần click. Đây là lý do mọi quyết định thiết kế phải ưu tiên tối ưu read path trước.
Cache không phải nice-to-have ở đây — là bắt buộc.
Thiết kế giải pháp
High-level flow
Tạo short link: User gửi URL → API server → sinh short code → lưu DB → trả về short URL.
Khi redirect: Load balancer → app server → check cache → nếu miss mới query DB → redirect.
flowchart LR
A[User] --> B[Load Balancer]
B --> C[App Server]
C -- create --> D[(Database)]
C -- redirect --> E{Redis Cache}
E -- HIT --> F([Redirect])
E -- MISS --> D
D --> E
Thành phần chính
- Load Balancer — phân phối traffic đều giữa các app server
- App servers — xử lý logic, quan trọng là phải stateless để scale ngang dễ dàng
- Database (NoSQL — DynamoDB/Cassandra) — chỉ cần lookup theo key, không JOIN → NoSQL scale tốt hơn MySQL nhiều
- Cache (Redis) — tăng tốc redirect, giảm tải DB
- ID generator — sinh short code unique cho hàng triệu link
Cách tạo short URL
Có 2 cách phổ biến:
- Hash URL → Base62: nhanh, nhưng có thể collision → phải check DB, retry → tốn thêm round-trip
- Auto-increment ID → Base62: đơn giản, đảm bảo unique tuyệt đối ✅
Thực tế thường chọn ID generator + Base62. Chỉ 6 ký tự Base62 đã có 62⁶ ≈ 56 tỷ tổ hợp — đủ dùng cho nhiều thập kỷ.
Snowflake ID là giải pháp phổ biến nhất: cấu trúc 64-bit gồm timestamp + datacenter ID + machine ID + sequence. Mỗi server tự sinh ID độc lập, không cần lock, không cần coordinate — đây là lý do nó scale tốt trong môi trường phân tán.
Chi tiết xử lý redirect
Khi có hàng triệu người dùng click link cùng lúc, mỗi millisecond đều có giá trị:
- Check Redis cache trước
- Cache HIT → redirect ngay (~1–2ms) ✅
- Cache MISS → query DB → set cache → redirect
Kết quả: 95–99% request chỉ chạm Redis, DB hầu như không chịu tải từ read traffic. Đây là lý do hệ thống chịu được hàng chục nghìn QPS mà DB không sập.
301 hay 302? 301 (permanent) → browser cache, lần sau không qua server → nhanh hơn nhưng mất analytics. 302 (temporary) → mọi click đều qua server → đếm được đầy đủ. Bitly dùng 301 cho free tier, 302 cho paid tier. Quyết định kinh doanh ảnh hưởng trực tiếp đến kiến trúc.
Scale khi traffic tăng
- Horizontal scale app servers — vì stateless, thêm server không cần lo về shared state
- DB sharding theo consistent hashing (không shard theo ký tự đầu — dễ gây hotspot phân phối không đều)
- Redis Cluster — cache phân tán, tránh single point of failure
- CDN (Cloudflare/CloudFront) — giảm latency cho người dùng toàn cầu
Các vấn đề cần lưu ý khi scale lên hàng triệu
Collision khi generate code Chỉ xảy ra khi dùng Hash. Dùng ID generator thì không bao giờ collision — đây là lý do nên chọn cách này từ đầu.
Hot key — link viral Một link viral có thể gây hàng triệu request/giây vào cùng một Redis key. Redis đơn luồng — một hot key đủ làm nghẽn cả cluster. Giải pháp: thêm local in-memory cache tại mỗi app server (TTL ~5s). 99% request cho link viral không cần ra Redis.
Spam link Bot tạo hàng triệu link để spam. Giải pháp: rate limit theo IP bằng Redis sliding window counter.
Analytics tracking Đừng ghi click count đồng bộ trong redirect path — sẽ tăng latency trực tiếp cho người dùng. Dùng async: ghi event vào Kafka → xử lý bằng ClickHouse. Redirect path không bị ảnh hưởng.
Tóm lại
| Vấn đề | Giải pháp |
|---|---|
| Read-heavy (400:1) | Redis cache-first, 95%+ request không chạm DB |
| Unique short code | Snowflake ID + Base62, không collision |
| Scale app servers | Stateless + horizontal scale |
| Scale database | Consistent hashing sharding |
| Link viral / hot key | Local in-memory cache tại app server |
| Analytics | Async qua Kafka, không ảnh hưởng redirect |
Comments powered by Disqus.