System Design: URL Shortener about 100 million tps

1. Khởi nguồn của rắc rối: Khi những đường link trở nên "bất trị"

Bạn đã bao giờ thử copy một đường link trên Amazon hay Google Maps để gửi cho bạn bè, và nhận ra nó dài đến mức chiếm trọn cả một khung chat? Những URL chứa hàng tá tham số truy vấn (query parameters) không chỉ vỡ giao diện hiển thị mà còn gây ức chế tột độ khi gõ lại bằng tay. Tệ hơn nữa, ở thời kỳ đầu của Twitter (khi nền tảng này giới hạn mỗi tweet chỉ có 140 ký tự), một đường link dài có thể ngốn sạch toàn bộ dung lượng của một bài đăng.

Đó là lúc thế giới cần một "phép màu" biến một URL dài 100-200 ký tự thành một chuỗi chỉ khoảng 7 ký tự (như tinyurl.com/zn9edcu). Bài toán đặt ra có vẻ đơn giản: Dữ liệu vào là một link dài, dữ liệu ra là một link ngắn, và khi người dùng gõ link ngắn, họ phải được chuyển hướng (redirect) về đích đến ban đầu.

Nhưng khi bạn phải phục vụ hàng trăm triệu người dùng với con số 100 triệu URL được tạo mới mỗi ngày, bài toán "có vẻ đơn giản" đó sẽ biến thành một cơn ác mộng về khả năng mở rộng (scalability) và hiệu năng.

2. Hành trình đi tìm giải pháp: Giải phẫu kiến trúc của một cú Click

Để hệ thống hoạt động, chúng ta cần giải quyết hai luồng chính: Tạo link ngắn và Chuyển hướng (Redirect).

Khi người dùng click vào link ngắn, trình duyệt gửi một HTTP GET request lên server của chúng ta. Thay vì trả về một trang web, server sẽ trả về một mã trạng thái (status code) và một Header tên là Location chứa link gốc. Trình duyệt nhận được mã này sẽ tự động "bay" đến link gốc. Ở đây, các kỹ sư đứng trước ngã ba đường: Dùng 301 Redirect hay 302 Redirect?

• 301 (Permanent Redirect): Trình duyệt hiểu là link này đã "chuyển nhà vĩnh viễn". Nó sẽ tự động cache lại kết quả. Lần sau bạn click vào link ngắn đó, trình duyệt sẽ lao thẳng đến trang đích mà không thèm gọi lên server của chúng ta nữa. Rất tiết kiệm tài nguyên hệ thống (Server Load).
• 302 (Temporary Redirect): Trình duyệt bị ép phải luôn đi qua server của chúng ta trước khi tới đích. Cách này ngốn tài nguyên, nhưng lại là "con gà đẻ trứng vàng" nếu bạn muốn làm Analytics (đếm số lượt click, theo dõi thiết bị, vị trí địa lý của người dùng).

Xong phần Redirect, bài toán hóc búa nhất xuất hiện: Làm sao để sinh ra chuỗi 7 ký tự? Chúng ta có 62 ký tự khả dụng (a-z, A-Z, 0-9). Với độ dài 7, ta có $62^7 \approx 3.5$ nghìn tỷ tổ hợp – quá đủ để dùng trong hàng chục năm. Có hai trường phái thiết kế để đạt được con số này:

Trường phái 1: Băm dữ liệu (Hash + Collision Resolution) Ý tưởng đầu tiên là ném URL dài vào một hàm băm chuẩn như MD5 hay SHA-1. Nhưng MD5 trả về tới 32 ký tự. Lấy 7 ký tự đầu ư? Sự đụng độ (Collision) chắc chắn sẽ xảy ra: hai URL khác nhau bị băm ra cùng một chuỗi 7 ký tự. Để xử lý, mỗi khi băm xong, server phải chọc xuống Database xem chuỗi đó đã tồn tại chưa. Nếu có rồi, nó sẽ nối thêm một chuỗi ngẫu nhiên vào URL gốc và băm lại từ đầu. Quá trình lặp này tạo ra độ trễ cực lớn và bòn rút sức mạnh của Database.

Trường phái 2: Đổi cơ số (Base 62 Conversion) – Ánh sáng cuối đường hầm Thay vì băm chuỗi, hãy bám vào những con số. Hệ thống sẽ nhờ một dịch vụ trung tâm (Distributed ID Generator) cấp cho mỗi URL mới một số nguyên định danh (ID) duy nhất, ví dụ: 2009215674938. Sau đó, chúng ta chia liên tục con số này cho 62 để chuyển nó từ hệ thập phân (Base 10) sang hệ cơ số 62 (Base 62). ID 2009215674938 sau khi đổi cơ số và ánh xạ sang bảng chữ cái sẽ biến thành chuỗi zn9edcu. Không bao giờ có đụng độ (vì ID là duy nhất). Không cần check Database lặp đi lặp lại. Đây chính là "chén thánh" của kiến trúc URL Shortener.

3. Câu chuyện thực chiến: Khi hệ thống đối mặt với 100 triệu URL mỗi ngày

Hãy tưởng tượng bạn đang thiết kế hệ thống này cho một công ty toàn cầu. Lưu lượng đổ về là 100 triệu URL mới tạo mỗi ngày, tương đương tốc độ tạo mới khoảng 1.160 requests/giây. Lượng click (Read) thường gấp 10 lần lượng tạo (Write), tức là khoảng 11.600 reads/giây.

Ban đầu, bạn nhét toàn bộ các cặp <shortURL, longURL> vào một cái Hash Table trên RAM để tốc độ cực nhanh. Nhưng chỉ sau vài tháng, kỹ sư Ops chạy đến báo cáo rằng RAM đã cạn kiệt. Nếu hệ thống sống 10 năm, bạn sẽ có 365 tỷ bản ghi. Mỗi bản ghi (ID, shortURL, longURL) nặng khoảng 100 Bytes. Tổng dung lượng cần lưu trữ lên tới 36.5 Terabytes (TB). Không có con server nào chứa nổi lượng RAM đó.

Bạn quyết định dời dữ liệu xuống một Relational Database với 3 cột đơn giản: id (Primary Key), shortURL, và longURL. Tuy nhiên, Database lại không thể đáp ứng tốc độ 11.600 reads/s một cách mượt mà.

Giải pháp đưa ra: Đưa Cache vào cuộc. Bạn đặt Redis chặn trước Database. Mỗi khi có luồng Redirect, hệ thống sẽ chọc vào Redis hỏi: "Mày có biết link gốc của zn9edcu là gì không?".

• Nếu có (Cache Hit), trả về ngay lập tức.
• Nếu không (Cache Miss), truy vấn Database, cập nhật ngược lại vào Redis rồi mới trả kết quả.

Nhờ vậy, Database được giải phóng khỏi gánh nặng truy vấn liên tục, hệ thống mượt mà đáp ứng lượng traffic khổng lồ.

4. Những góc khuất và điểm nghẽn trí mạng (Trade-offs)

Mọi lựa chọn kiến trúc đều có cái giá của nó. Nếu bạn chọn hướng Base 62 Conversion, hệ thống cực nhanh và không có đụng độ. Nhưng nó chứa một lỗ hổng bảo mật ngầm: Nếu các ID được sinh ra tăng dần đều (1, 2, 3...), kẻ tấn công có thể dễ dàng đoán được các short URL tiếp theo (bằng cách lấy ID tiếp theo đổi sang Base 62). Chúng có thể cào (crawl) sạch dữ liệu của hệ thống hoặc xả rác vào các ID bị lộ.

Ngược lại, nếu bạn vẫn kiên quyết dùng hướng Hash + Collision Resolution để các chuỗi trông ngẫu nhiên hơn, bạn phải đối mặt với chi phí chọc xuống DB liên tục để kiểm tra đụng độ. Để cứu vãn hiệu năng, các kỹ sư phải dùng đến Bloom Filter – một cấu trúc dữ liệu xác suất trên RAM siêu tiết kiệm không gian. Bloom Filter có thể trả lời "Chuỗi này chắc chắn CHƯA tồn tại trong DB" hoặc "Chuỗi này CÓ THỂ đã tồn tại". Nó giúp ta lọc được 99% các truy vấn vô ích xuống Database.

5. So sánh & Câu hỏi xoáy

Trong thực tế, khi xây dựng URL Shortener, các kiến trúc sư còn phải đau đầu với vô vàn bài toán phụ trợ:

• Rate Limiting: Làm sao để chặn một gã rảnh rỗi viết script tạo 1 triệu URL ngắn trong 1 phút?
• High Availability (HA): Nếu Web Server sập thì sao? Nếu Database sập thì sao? Bạn phải set up Load Balancer, tách Stateless Web Tier và thiết lập Database Replication/Sharding.

Một câu hỏi xoáy thường gặp khi bàn luận về hệ thống này: "Nếu bạn sử dụng Distributed ID Generator như Twitter Snowflake để cấp ID cho Base 62, làm sao bạn đảm bảo ID sinh ra liên tục không tạo thành chuỗi URL quá dễ đoán mà vẫn giữ được tính Time-sortable?"

Đó là lúc các kỹ sư phải đưa vào một lớp Xáo trộn (Shuffle/Obfuscation). Đây là một "màng lọc" toán học có thể đảo ngược nhằm che giấu tính tuần tự của ID gốc (giúp chống lại việc bị "vét" - scraping dữ liệu) trước khi mang đi đổi sang Base 62.

Cấu trúc một Snowflake ID (64-bit) điển hình:

1. Timestamp (41 bits): Thời gian tính bằng milisecond. Đây là phần tạo nên tính Time-sortable.
2. Worker ID (10 bits): Định danh của máy chủ sinh ID.
3. Sequence (12 bits): Số thứ tự tăng dần trong cùng một milisecond.

Nếu ta lấy ID sinh ra liên tiếp (ví dụ: $1001$ và $1002$) chuyển thẳng sang Base 62, kết quả có thể là g9 và ga. Một kẻ tấn công chỉ cần thay ga thành gb là đoán được ID tiếp theo! Do đó, quy trình xáo trộn sẽ diễn ra như sau:

Bước 1: Áp dụng Bit-Reversal hoặc Bit-Permutation Thay vì giữ nguyên, ta hoán vị vị trí các bit trong phần Sequence và một phần của Worker ID (ví dụ: bit 0 đổi chỗ với bit 5, bit 1 với bit 2). Hai ID kề nhau (như ...0001 và ...0010) sẽ trở nên khác biệt hoàn toàn sau khi hoán vị.

Bước 2: Sử dụng phép toán XOR với một "Secret Mask" Đây là cách nhanh nhất để làm ID trông ngẫu nhiên.

• Thực hiện: Shuffled_ID = Original_ID ^ Secret_Mask (ví dụ Mask là 0x55555555).
• Tính chất: Phép XOR có tính thuận nghịch. Khi cần, hệ thống chỉ việc XOR kết quả với Secret_Mask một lần nữa để lấy lại ID gốc.

(Lưu ý: Với các hệ thống yêu cầu bảo mật cực cao, kỹ sư có thể dùng Mạng Feistel (Feistel Network) tạo hàm băm đảo ngược Format-Preserving Encryption để đảm bảo ID sinh ra hoàn toàn xáo trộn nhưng vẫn nằm gọn trong 64-bit và không bao giờ đụng độ).

Bài toán khó nhất: Làm sao để bảo mật nhưng vẫn giữ tính "Time-sortable"? Có hai chiến lược phổ biến:

• Chiến lược A (Ưu tiên Sắp xếp): Chỉ xáo trộn phần Worker ID và Sequence, giữ nguyên phần Timestamp ở đầu.
  • Điểm cộng: ID vẫn tăng dần theo thời gian.
  • Điểm trừ: Phần đầu của URL Base62 vẫn sẽ giống nhau trong một khoảng thời gian ngắn, bot vẫn có thể đoán được phạm vi.
• Chiến lược B (Ưu tiên Bảo mật - Khuyên dùng): Xáo trộn toàn bộ 64-bit trước khi biến thành Base 62.
  • Cách vận hành: Khi người dùng truy cập domain.com/Abc123, server sẽ làm bước "Un-shuffle" (giải mã ngược) để tìm lại Snowflake ID gốc.
  • Hiệu năng: Mọi thao tác lưu trữ, đánh index và tìm kiếm trong Database vẫn thực hiện trên ID gốc (có tính Time-sortable và truy xuất siêu tốc), còn cái URL rối rắm kia chỉ đóng vai trò là "lớp áo" ngụy trang bên ngoài. Không hề gây tốn kém thêm chi phí xử lý đáng kể.