Phân tích bài toán thiết kế hệ thống rút gọn URL (TinyURL) chịu tải 100 triệu request mỗi ngày

Đề bài kinh điển của các vòng phỏng vấn FAANG / Big Tech#

Thiết kế một dịch vụ rút gọn liên kết (tương tự như TinyURL hoặc Bitly):

• Nhận vào một URL dài (Long URL) $\rightarrow$ Trả về một URL ngắn gọn có 7 ký tự (Short URL: topdev.vn/x7K9pQ).
• Khi người dùng truy cập link ngắn $\rightarrow$ Chuyển hướng HTTP 301 hoặc 302 về link gốc.
• Hệ thống cần phục vụ 100 triệu lượt click/ngày với độ trễ chuyển hướng dưới 20ms.

1. Ước lượng quy mô sơ bộ (Calculations)#

• Quy mô Request/giây (QPS): 100 triệu request / 86.400 giây $\approx$ 1.200 QPS trung bình, lúc cao điểm có thể lên tới 3.000 QPS.
• Tỷ lệ Đọc/Ghi (Read-to-Write): Tỷ lệ là 100:1 (Hệ thống nặng về ĐỌC, tạo link ít nhưng click xem link thì cực nhiều).
• Dung lượng lưu trữ: 1 triệu link mới/ngày $\times$ 500 bytes $\times$ 365 ngày $\approx$ 180 GB/năm $\rightarrow$ Dung lượng rất nhỏ, hoàn toàn có thể lưu trong PostgreSQL hoặc NoSQL Key-Value store.

2. Thuật toán sinh mã ngắn: Base62 vs MD5 Hash#

Nếu dùng 7 ký tự gồm: [a-z] (26 ký tự) + [A-Z] (26 ký tự) + [0-9] (10 ký tự) = 62 ký tự. Số lượng URL duy nhất có thể sinh ra là: $$62^7 \approx 3.5 \text{ nghìn tỷ URL}$$ Con số này đủ dùng cho nhân loại trong hàng trăm năm!

const BASE62_ALPHABET = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';

export function encodeBase62(uniqueId: bigint): string {
  let result = '';
  let n = uniqueId;
  while (n > 0n) {
    result = BASE62_ALPHABET[Number(n % 62n)] + result;
    n = n / 62n;
  }
  return result.padStart(7, '0');
}

3. Kiến trúc chịu tải cao: HTTP 301 vs 302 và Caching#

• HTTP 301 (Permanent Redirect): Trình duyệt của người dùng sẽ tự động cache lại URL đích vĩnh viễn. Lần click tiếp theo trình duyệt tự nhảy về trang đích mà không cần gọi tới máy chủ của bạn (Giảm tải tuyệt đối cho server!).
• HTTP 302 (Found / Temporary Redirect): Bắt buộc mọi lượt click phải đi qua máy chủ của bạn $\rightarrow$ Dùng khi bạn cần Đếm chính xác Analytics lượt click và thông tin thiết bị/địa lý của người dùng.
• Tầng Caching: Lưu 20% các link hot nhất vào cụm Redis Cluster. 80% lưu lượng truy cập sẽ trúng Cache với độ trễ chỉ 1-2ms.

Góc thảo luận#

Nếu bạn là kiến trúc sư trưởng của hệ thống này, bạn sẽ sinh mã số ID duy nhất bằng Snowflake ID, Sequence của Database hay dịch vụ KGS (Key Generation Service) riêng biệt?

Xem thêm nội dung liên quan:

• Lộ trình Thiết kế Hệ thống Phân tán
• Bộ câu hỏi trắc nghiệm System Design