Review: System Design Interview (Day 70) | FE Master

🎯 Mục tiêu bài học

Tổng hợp kiến thức Network + DB để giải quyết bài toán triệu user.

Challenge: Design TinyURL (bit.ly)

Yêu cầu: Nhập URL dài -> Ra URL ngắn (vd: bit.ly/aBc12). Click URL ngắn -> Redirect về URL dài.

1. Capacity Planning (Tính toán dung lượng)

Traffic: 100 triệu link mới/tháng.
- QPS (Query Per Second) = 100M / (30 ngày * 24h * 3600s) ≈ 40 writes/s.
- Read:Write ratio 100:1 -> Read QPS = 4000 reads/s.
Storage (5 năm):
- 1 bản ghi = 500 bytes.
- Tổng link = 100M * 12 tháng * 5 năm = 6 tỷ link.
- Tổng dung lượng = 6 tỷ * 500 bytes = 3TB.
Bandwidth:
- Ingress (Upload): 40 * 500B = 20KB/s.
- Egress (Download): 4000 * 500B = 2MB/s.

💡 Mẹo phỏng vấn:

Luôn bắt đầu bằng con số. Đừng code ngay. Vẽ ra con số để chứng minh mình hiểu quy mô hệ thống.

2. Database Choice

Cần quan hệ phức tạp không? Không.
Cần tốc độ đọc nhanh? Có.
Chọn: NoSQL (Cassandra/DynamoDB) hoặc SQL đều được. (Vì Key-Value đơn giản).

🚀 Optimization: Bloom Filter

Vấn đề: Hacker spam 1 triệu URL không tồn tại -> DB bị quá tải vì phải check từng cái.

Giải pháp: Dùng Bloom Filter (Cấu trúc dữ liệu xác suất).

Nó là một mảng Bit cực nhẹ (vài MB chứa được tỷ record).
Nếu Bloom Filter bảo "KHÔNG CÓ" -> Chắc chắn 100% không có -> Trả về 404 ngay (Không cần hỏi DB).
Nếu Bloom Filter bảo "CÓ" -> Có thể có hoặc không (xác suất nhỏ) -> Mới check DB.

3. Thuật toán sinh Hash (Cốt lõi)

Cách 1: MD5(URL_gốc). MD5 ra 128 bit (32 hex chars). Quá dài. Cần cắt lấy 6-7 ký tự đầu. Vấn đề: Trùng lặp (Collision).
Cách 2: Base62(Auto_Increment_ID).
- ID = 1 -> a.
- ID = 12345 -> xYz1.
- Base62 (a-z, A-Z, 0-9) có 62 ký tự. Với 7 ký tự -> $62^7 = 3.5$ nghìn tỷ link. Đủ dùng.
- Vấn đề: Cần bộ đếm ID tập trung (Centralized Counter) -> Dùng Redis INCR hoặc Zookeeper.

4. High Level Design

graph LR User --> LB(Load Balancer) LB --> WebS(Web Servers) WebS --> Cache(Redis Cache) Cache -.-> DB(Database) WebS --> DB

Cache (Redis): Lưu 20% các link hot nhất. Giúp giảm 90% tải cho DB.
301 vs 302 Redirect:
- 301 (Permanent): Browser cache lại. Server không biết user click lần 2. (Tiết kiệm server, nhưng mất Analytics).
- 302 (Temporary): Mỗi lần click đều hỏi Server -> Server đếm được Analytics. (Tốn tài nguyên hơn). -> Chọn 302 để bán dữ liệu Analytics.

🎯 Mục tiêu bài học

Tổng hợp kiến thức Network + DB để giải quyết bài toán triệu user.

Challenge: Design TinyURL (bit.ly)

Yêu cầu: Nhập URL dài -> Ra URL ngắn (vd: bit.ly/aBc12). Click URL ngắn -> Redirect về URL dài.

1. Capacity Planning (Tính toán dung lượng)

Traffic: 100 triệu link mới/tháng.
- QPS (Query Per Second) = 100M / (30 ngày * 24h * 3600s) ≈ 40 writes/s.
- Read:Write ratio 100:1 -> Read QPS = 4000 reads/s.
Storage (5 năm):
- 1 bản ghi = 500 bytes.
- Tổng link = 100M * 12 tháng * 5 năm = 6 tỷ link.
- Tổng dung lượng = 6 tỷ * 500 bytes = 3TB.
Bandwidth:
- Ingress (Upload): 40 * 500B = 20KB/s.
- Egress (Download): 4000 * 500B = 2MB/s.

💡 Mẹo phỏng vấn:

Luôn bắt đầu bằng con số. Đừng code ngay. Vẽ ra con số để chứng minh mình hiểu quy mô hệ thống.

2. Database Choice

Cần quan hệ phức tạp không? Không.
Cần tốc độ đọc nhanh? Có.
Chọn: NoSQL (Cassandra/DynamoDB) hoặc SQL đều được. (Vì Key-Value đơn giản).

🚀 Optimization: Bloom Filter

Vấn đề: Hacker spam 1 triệu URL không tồn tại -> DB bị quá tải vì phải check từng cái.

Giải pháp: Dùng Bloom Filter (Cấu trúc dữ liệu xác suất).

Nó là một mảng Bit cực nhẹ (vài MB chứa được tỷ record).
Nếu Bloom Filter bảo "KHÔNG CÓ" -> Chắc chắn 100% không có -> Trả về 404 ngay (Không cần hỏi DB).
Nếu Bloom Filter bảo "CÓ" -> Có thể có hoặc không (xác suất nhỏ) -> Mới check DB.

3. Thuật toán sinh Hash (Cốt lõi)

Cách 1: MD5(URL_gốc). MD5 ra 128 bit (32 hex chars). Quá dài. Cần cắt lấy 6-7 ký tự đầu. Vấn đề: Trùng lặp (Collision).
Cách 2: Base62(Auto_Increment_ID).
- ID = 1 -> a.
- ID = 12345 -> xYz1.
- Base62 (a-z, A-Z, 0-9) có 62 ký tự. Với 7 ký tự -> $62^7 = 3.5$ nghìn tỷ link. Đủ dùng.
- Vấn đề: Cần bộ đếm ID tập trung (Centralized Counter) -> Dùng Redis INCR hoặc Zookeeper.

4. High Level Design

graph LR User --> LB(Load Balancer) LB --> WebS(Web Servers) WebS --> Cache(Redis Cache) Cache -.-> DB(Database) WebS --> DB

Cache (Redis): Lưu 20% các link hot nhất. Giúp giảm 90% tải cho DB.
301 vs 302 Redirect:
- 301 (Permanent): Browser cache lại. Server không biết user click lần 2. (Tiết kiệm server, nhưng mất Analytics).
- 302 (Temporary): Mỗi lần click đều hỏi Server -> Server đếm được Analytics. (Tốn tài nguyên hơn). -> Chọn 302 để bán dữ liệu Analytics.

Review: System Design Interverview

lesson.content.title

🎯 Mục tiêu bài học

Challenge: Design TinyURL (bit.ly)

1. Capacity Planning (Tính toán dung lượng)

💡 Mẹo phỏng vấn:

2. Database Choice

🚀 Optimization: Bloom Filter

3. Thuật toán sinh Hash (Cốt lõi)

4. High Level Design

Review: System Design Interverview

lesson.content.title

🎯 Mục tiêu bài học

Challenge: Design TinyURL (bit.ly)

1. Capacity Planning (Tính toán dung lượng)

💡 Mẹo phỏng vấn:

2. Database Choice

🚀 Optimization: Bloom Filter

3. Thuật toán sinh Hash (Cốt lõi)

4. High Level Design