System Design — Bài 16: Thiết kế URL Shortener: sinh mã, cache và ánh xạ 1-1

Rút gọn URL có giao diện nhỏ nhưng chứa nhiều quyết định thú vị: mã ngắn có được đoán không, cùng URL có được tạo nhiều mã không, và một click có nhất thiết về origin để đếm analytics không? Ta lần theo từng yêu cầu để xây kiến trúc và xử lý các trường hợp đồng thời.

Khóa học System Design: mục lục 21 bài — bạn đang đọc bài 16.

Các con số dưới đây là giả định phục vụ học thiết kế, không phải số liệu hay kiến trúc nội bộ của sản phẩm được nhắc tên. Dung lượng dùng đơn vị thập phân; capacity thực tế phải đo theo workload và mục tiêu chất lượng.

Yêu cầu & ước lượng

Trong phiên bản đầu, một long URL có thể có nhiều mã ngắn. Mã phải không trùng trong phạm vi hệ thống, dài tối đa tám ký tự và khó đoán theo mục tiêu đã thống nhất. Có thể hỗ trợ alias tùy chọn, hết hạn và analytics, nhưng phải chọn phần nào đào sâu trong thời gian có hạn.

Với 10 triệu lượt tạo mỗi ngày và đọc gấp 100 lần, ta có khoảng 100 lượt ghi và 10.000 lượt đọc mỗi giây theo cách làm tròn. Dữ liệu giữ bốn năm khoảng 17,6 terabyte trước replica và overhead. Đọc nhiều thúc đẩy thiết kế cache và đường lookup ngắn.

Hai phẩy hai gigabyte cache là giả định hot set cụ thể của bài, không phải toàn bộ URL còn hiệu lực. Trước khi chọn shard hay sản phẩm, cần so tải, dung lượng và tăng trưởng với benchmark phù hợp.

Sinh mã ngắn — bốn phương án

Base62 dùng chữ và số để biểu diễn giá trị gọn hơn số thập phân. Với tám ký tự có khoảng 218 nghìn tỷ tổ hợp. Nhưng không gian lớn không có nghĩa sinh ngẫu nhiên sẽ không bao giờ trùng; cần unique constraint hoặc ghi có điều kiện và retry khi collision.

ID tuần tự hoặc token range giúp phân phối cấp ID không chồng lấn, nhưng encode Base62 vẫn dễ đoán. Hash URL có thể trùng và cũng không tự đáp ứng yêu cầu khó đoán. Một ID 64 bit có thể cần tới mười một ký tự Base62, nên không mặc định vừa giới hạn tám ký tự.

Nếu chọn random token, dùng nguồn ngẫu nhiên phù hợp mục tiêu chống đoán, kết hợp kiểm tra trùng và rate limit. Mã khó đoán vẫn không thay authorization cho tài nguyên nhạy cảm. Nếu chọn token range, hãy nói rõ đây là phương án cấp uniqueness, cần cơ chế bổ sung để đáp ứng entropy.

Lưu ở đâu, phân mảnh thế nào

Bản ghi chính gồm short code, long URL, thời điểm tạo, hết hạn và thông tin chủ sở hữu khi cần. Luồng redirect tra theo short code nên đây là ứng viên tự nhiên cho khóa truy cập và hash partition.

Một phương án là chọn kho phù hợp lookup theo key cho mapping, còn user và subscription dùng kho quan hệ. Đây là lựa chọn minh họa theo giả định quy mô, không phải yêu cầu rằng URL shortener luôn cần hai database. Nếu một database hiện tại đáp ứng capacity và chức năng, có thể khởi đầu đơn giản hơn.

Redis giữ mapping nóng. Khi miss, service đọc nguồn bền rồi nạp cache. Link hết hạn hoặc bị khóa do lạm dụng phải có chính sách invalidation; cache lâu mà không kiểm tra điều kiện có thể tiếp tục phục vụ link đã bị thu hồi.

Yêu cầu mới: ánh xạ 1-1

Bây giờ khách muốn cùng một long URL luôn trả cùng short URL. Ta phải làm rõ “cùng” trong toàn hệ hay trong từng tài khoản, và URL được so nguyên văn hay sau chuẩn hóa. Tự bỏ query parameter có thể làm hai tài nguyên khác nhau bị gộp nhầm.

Cần lookup từ long URL sang short code, có thể dùng hash để hỗ trợ nhưng vẫn kiểm tra URL gốc khi hash collision. Bloom filter chỉ giảm số lượt lookup trong điều kiện phù hợp; nó không thay nguồn dữ liệu xác nhận.

Hai request đồng thời có thể cùng thấy chưa tồn tại rồi đều tạo. Vì vậy cần unique constraint, ghi có điều kiện hoặc cơ chế phối hợp với consistency phù hợp trên khóa canonical đã chọn. Nếu hai mapping nằm ở các shard khác nhau, phải thiết kế rõ cách giữ bất biến khi một bước thất bại.

Sơ đồ cuối & chi tiết ăn điểm

Ở đường tạo, gateway kiểm tra quyền và hạn mức, service sinh mã theo phương án đã chọn, ghi mapping có bảo đảm chống trùng rồi trả URL ngắn. Retry của client cần được xem xét nếu người dùng mong một yêu cầu chỉ tạo một kết quả.

Ở đường đọc, translator tìm mapping qua cache rồi nguồn bền khi miss, kiểm tra hiệu lực và trả redirect. Analytics có thể phát bất đồng bộ để không kéo dài đường chuyển hướng; nếu chấp nhận mất một phần sự kiện cần nói rõ mức bảo đảm.

301 diễn đạt chuyển hướng lâu dài, còn 302 là chuyển hướng tạm thời. Khả năng cache còn phụ thuộc header và client; 302 không tự bảo đảm mọi click đều về origin. Nếu cần analytics tại origin, thiết kế cache policy rõ. Khi cache phục vụ ở edge hoặc trình duyệt, cần cách đo khác phù hợp.

Đường tạo và đường chuyển hướng

POST /links {url, idempotency_key}
  -> xác thực/hạn mức
  -> random token phù hợp mục tiêu entropy
  -> INSERT với UNIQUE(code), retry khi collision
  -> trả short URL sau commit

GET /{code}
  -> cache -> miss: đọc mapping từ DB
  -> kiểm tra hết hạn/thu hồi -> redirect
  -> analytics bất đồng bộ theo mức bảo đảm đã chốt

62^8 = 218.340.105.584.896 mã có thể biểu diễn

Không gian mã lớn không loại bỏ birthday collision và không thay authorization. Khi yêu cầu ánh xạ 1-1, cần một ràng buộc riêng cho URL đã chuẩn hóa trong phạm vi xác định, cùng cơ chế xử lý hai request tạo đồng thời.

Thuật ngữ cần nhớ

URL — Uniform Resource Locator: Địa chỉ định vị tài nguyên. Case URL Shortener lưu ánh xạ mã ngắn tới địa chỉ đích và xử lý chuyển hướng.
TTL — Time To Live: Thời gian sống còn hiệu lực của dữ liệu, bản ghi tên miền hoặc lease. Hết hạn không tự thực hiện nghiệp vụ như hoàn tồn kho; cần luồng xử lý tương ứng.
CSPRNG — Cryptographically Secure Pseudorandom Number Generator: Bộ sinh số giả ngẫu nhiên an toàn mật mã, dùng tạo token khó dự đoán; vẫn cần đủ entropy, ràng buộc duy nhất và giới hạn thử đoán.
HTTP — Hypertext Transfer Protocol: Giao thức trao đổi request/response của web. HTTP/1.1 và HTTP/2 là các phiên bản với cách truyền và ghép luồng khác nhau.

Bài tập tự thực hành

Hai request cùng long URL tới đồng thời trong chế độ 1-1.

Gợi ý kiểm tra lời giải

Lookup riêng chưa đủ; cần primitive giữ uniqueness theo phạm vi, xử lý hash collision và retry.

Tự kiểm tra sau bài học

Base62 là encoding, không phải cơ chế bảo mật.
Read path kiểm tra cả cache stale, link hết hạn và thu hồi.
Cache policy của redirect phù hợp yêu cầu analytics.

Đọc thêm từ tài liệu gốc

RFC 9111: HTTP Caching

Tiếp tục lộ trình

Bài trước — Framework phỏng vấn System Design trong 40 phút

Bài tiếp — Thiết kế News Feed: push, pull và mô hình hybrid

Xem toàn bộ khóa học System Design 21 bài