- Với bảng chữ cái Base62 gồm 62 ký tự (
0-9,a-z,A-Z), một chuỗi ngắn dài 7 ký tự biểu diễn được \(62^7 = 3{,}521{,}614{,}606{,}208\) (\(\approx 3.52\text{ nghìn tỷ}\)) liên kết duy nhất — dư sức phục vụ \(100\text{ triệu}\) link tạo mới mỗi ngày trong suốt gần \(100\text{ năm}\). - Phương pháp sinh ID số nguyên 64-bit duy nhất rồi đổi sang Base62 vượt trội hơn việc cắt ngắn mã băm MD5/SHA-256 vì đảm bảo song ánh 1-1 tuyệt đối, không bao giờ xảy ra đụng độ (Collision) và không cần truy vấn cơ sở dữ liệu để kiểm tra trùng lặp trước khi ghi.
- Cần phân biệt rõ mã phản hồi chuyển hướng: HTTP 301 (Moved Permanently) giúp giảm tải máy chủ tối đa nhờ trình duyệt tự lưu cache, trong khi HTTP 302 (Found) buộc mọi lượt nhấp đều đi qua máy chủ để thu thập số liệu thống kê (Click Analytics).
- Tỷ lệ đọc/ghi thực tế của hệ thống rút gọn link thường ở mức \(100:1\); việc đặt tầng đệm Redis Cache theo quy luật 80/20 giúp xử lý trên \(90\%\) lượt chuyển hướng ngay trong bộ nhớ RAM với độ trễ dưới \(5\text{ ms}\).
Bước 1: Làm rõ yêu cầu và Ước lượng quy mô hệ thống
Áp dụng khung tư duy 4 bước từ bài nhập môn System Design cho lập trình viên, trước tiên ta chốt phạm vi bài toán cùng người phỏng vấn:
Yêu cầu chức năng và phi chức năng
- Rút gọn liên kết (
shortenURL): Nhận vào một đường dẫn dài (long_url, tối đa \(2{,}048\text{ ký tự}\)) và tùy chọn bí danh tự đặt (custom_alias), trả về một đường dẫn ngắn có dạnghttps://sho.rt/{short_code}với phần mã ngắn không quá 7–8 ký tự. - Chuyển hướng (
redirect): Khi người dùng truy cậphttps://sho.rt/{short_code}, hệ thống chuyển hướng trình duyệt về đúnglong_urlban đầu; nếu mã không tồn tại hoặc đã hết hạn, trả về404 Not Found. - Đặc tính phi chức năng: Độ sẵn sàng cực cao (nếu dịch vụ ngừng hoạt động, hàng triệu liên kết chia sẻ trên mạng xã hội sẽ bị gãy), độ trễ chuyển hướng \(\text{p99} \lt 20\text{ ms}\), và thời gian lưu trữ mặc định là \(10\text{ năm}\).
Ước lượng thông số Back-of-the-Envelope
Giả sử hệ thống cần đáp ứng quy mô lớn như sau:
- Lượng tạo link mới (Write): \(100\text{ triệu}\) URL mới mỗi tháng \(\approx \frac{10^8}{30 \times 86{,}400} \approx \mathbf{40\text{ Write QPS}}\) (Đỉnh tải \(\approx 100\text{ Write QPS}\)).
- Lượng nhấp vào link (Read): Với tỷ lệ đọc/ghi là \(100:1\), hệ thống nhận \(10\text{ tỷ}\) lượt chuyển hướng mỗi tháng \(\approx \mathbf{4{,}000\text{ Read QPS}}\) (Đỉnh tải \(\approx 10{,}000\text{ Read QPS}\)).
- Tổng số bản ghi trong 10 năm: \(10^8\text{ link/tháng} \times 12\text{ tháng} \times 10\text{ năm} = \mathbf{1.2 \times 10^{10}}\) (\(12\text{ tỷ}\) liên kết).
- Dung lượng lưu trữ 10 năm: Mỗi bản ghi gồm
id (8B),short_code (8B),long_url (~500B),created_at (8B),expires_at (8B)\(\approx 550\text{ bytes}\). Tổng dung lượng đĩa cứng cần thiết là \(12 \times 10^9 \times 550\text{ B} \approx \mathbf{6.6\text{ TB}}\).
Chọn độ dài short_code bằng toán học tổ hợp
Nếu dùng bảng chữ cái Base62 gồm 0-9 (10 ký tự), a-z (26 ký tự) và A-Z (26 ký tự), số lượng chuỗi tạo được theo độ dài \(L\) là \(62^L\):
- Với \(L = 6\): \(62^6 = 56{,}800{,}235{,}584 \approx 56.8\text{ tỷ}\) chuỗi (đủ cho quy mô \(12\text{ tỷ}\) link).
- Với \(L = 7\): \(62^7 = 3{,}521{,}614{,}606{,}208 \approx \mathbf{3.52\text{ nghìn tỷ}}\) chuỗi.
Trong phỏng vấn, chọn \(L = 7\text{ ký tự Base62}\) là con số tiêu chuẩn ngành vì cung cấp không gian địa chỉ rộng gấp gần \(300\text{ lần}\) nhu cầu 10 năm mà độ dài đường dẫn vẫn cực kỳ ngắn gọn.
Bước 2: Thiết kế API và Quyết định giữa HTTP 301 với HTTP 302
Hệ thống chỉ cần hai điểm cuối REST API cốt lõi:
- Tạo liên kết rút gọn:
POST /api/v1/urls- Thân yêu cầu (Request Body):
{ "long_url": "https://bigocoding.com/courses/...", "custom_alias": "dsa2026", "ttl_days": 365 } - Phản hồi
201 Created:{ "short_url": "https://sho.rt/dsa2026" }(không gửicustom_aliasthì hệ thống tự sinh mã, ví dụhttps://sho.rt/FXsk)
- Truy cập liên kết rút gọn:
GET /{short_code}- Phản hồi chuyển hướng kèm trường Header
Location: https://bigocoding.com/courses/...
Câu hỏi phỏng vấn kinh điển: Trả về mã HTTP 301 hay HTTP 302?
Người phỏng vấn hầu như luôn hỏi bạn sự khác biệt giữa hai mã trạng thái này:
| Tiêu chí so sánh | HTTP 301 Moved Permanently |
HTTP 302 Found (Chuyển hướng tạm thời) |
|---|---|---|
| Hành vi của Trình duyệt | Lưu kết quả ánh xạ short_url -> long_url vào bộ nhớ đệm cục bộ của trình duyệt. Ở các lần nhấp sau, trình duyệt nhảy thẳng tới long_url mà không hỏi lại máy chủ rút gọn link. |
Không lưu cache chuyển hướng vĩnh viễn. Mọi lượt nhấp chuột của người dùng đều gửi yêu cầu tới máy chủ URL Shortener trước. |
| Ưu điểm lớn nhất | Giảm tải cực mạnh cho cụm máy chủ đọc (Read QPS) và giảm độ trễ cho người dùng ở các lần truy cập lặp lại. | Cho phép hệ thống đếm chính xác từng lượt click, thống kê nguồn truy cập (Referer, Quốc gia, Thiết bị) và cho phép chủ sở hữu đổi đích đến của link ngắn bất cứ lúc nào. |
| Khi nào nên chọn? | Khi mục tiêu số một là tiết kiệm chi phí băng thông/máy chủ và không cần thống kê thời gian thực. | Khi sản phẩm kinh doanh dựa trên Click Analytics hoặc hỗ trợ tính năng Dynamic Link (như Bitly). |
Bước 3: Đi sâu vào thuật toán lõi — Băm cắt ngắn hay Sinh ID + Base62?
Làm thế nào để biến một long_url thành chuỗi 7 ký tự? Có hai hướng tiếp cận chính mà bạn cần đặt lên bàn cân:
Hướng 1: Băm MD5 / SHA-256 rồi lấy 7 ký tự đầu (Và lý do không nên dùng đơn lẻ)
Nếu băm chuỗi URL bằng hàm MD5 (128-bit) rồi mã hóa Base62, ta thu được một chuỗi dài hơn 21 ký tự. Nếu chỉ cắt lấy 7 ký tự đầu tiên, theo Nghịch lý Ngày sinh (Birthday Paradox), xác suất hai URL khác nhau sinh ra cùng một chuỗi 7 ký tự đầu tiên sẽ tăng lên rất nhanh khi số bản ghi đạt hàng trăm triệu.
Để xử lý đụng độ, mỗi lần tạo link mới bạn buộc phải truy vấn Database xem mã 7 ký tự đó đã tồn tại chưa; nếu trùng thì phải nối thêm chuỗi muối (Salt) rồi băm lại và kiểm tra tiếp (hoặc dùng bộ lọc Bloom Filter). Việc phải đọc Database trước mỗi lần ghi làm tăng gấp đôi độ trễ của thao tác POST.
Hướng 2: Sinh ID số nguyên 64-bit duy nhất rồi đổi sang Base62 (Khuyên dùng)
Thay vì băm nội dung URL, mỗi khi có yêu cầu rút gọn link mới, hệ thống cấp cho bản ghi đó một số nguyên dương 64-bit duy nhất \(\text{ID} \in [1, 62^7 - 1]\), sau đó chuyển số nguyên này từ hệ thập phân (cơ số 10) sang hệ cơ số 62.
Vì hàm chuyển cơ số là một song ánh toán học (Bijection):
- Hai số \(\text{ID}_1 \neq \text{ID}_2\) chắc chắn 100% sinh ra hai chuỗi
short_codekhác nhau — hoàn toàn không có đụng độ! - Khi người dùng truy cập
GET /{short_code}, máy chủ thậm chí có thể giải mã ngược chuỗi Base62 về lại con số \(\text{ID}\) 64-bit trong thời gian \(\mathcal{O}(1)\) để tra cứu trực tiếp trên khóa chính (Clustered Primary Key) của cơ sở dữ liệu mà không cần đánh thêm một chỉ mục chuỗi thứ cấp tốn bộ nhớ.
Chạy tay (Dry-run) thuật toán chuyển đổi Base62 hai chiều
Quy ước bảng chữ cái 62 ký tự theo chỉ số từ \(0\) đến \(61\):
- Chỉ số \(0 \dots 9\): Ký tự
'0'đến'9' - Chỉ số \(10 \dots 35\): Ký tự
'a'đến'z' - Chỉ số \(36 \dots 61\): Ký tự
'A'đến'Z'
Thứ tự này là quy ước của bài (trang Wikipedia về Base62 xếp A-Z trước a-z); bên mã hóa và bên giải mã chỉ cần dùng cùng một bảng.
Xét ví dụ cần mã hóa định danh \(\text{ID} = 10{,}000{,}000\) sang chuỗi Base62:
| Bước chia | Phép chia lấy thương (\(\text{ID} \div 62\)) | Số dư (\(\text{ID} \bmod 62\)) | Ký tự tra bảng tại chỉ số dư | Chuỗi tích lũy (chưa đảo) |
|---|---|---|---|---|
| 1 | \(10{,}000{,}000 \div 62 = 161{,}290\) | \(20\) | 'k' (vì \(10 + 10 = 20\)) |
"k" |
| 2 | \(161{,}290 \div 62 = 2{,}601\) | \(28\) | 's' (vì \(10 + 18 = 28\)) |
"ks" |
| 3 | \(2{,}601 \div 62 = 41\) | \(59\) | 'X' (vì \(36 + 23 = 59\)) |
"ksX" |
| 4 | \(41 \div 62 = 0\) (Dừng vòng lặp) | \(41\) | 'F' (vì \(36 + 5 = 41\)) |
"ksXF" |
Đảo ngược chuỗi phần dư từ dưới lên trên, ta thu được mã rút gọn là "FXsk".
Khi giải mã ngược chuỗi "FXsk" theo lược đồ Horner:
\[\text{ID} = ((41 \times 62 + 59) \times 62 + 28) \times 62 + 20 = 10{,}000{,}000\]
Cài đặt hoàn chỉnh bộ mã hóa và giải mã Base62 tốc độ cao bằng C++17, Python và Java 21:
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const string ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
string encode_base62(long long id) {
if (id == 0) return "0";
string res;
while (id > 0) {
res.push_back(ALPHABET[id % 62]);
id /= 62;
}
reverse(res.begin(), res.end());
return res;
}
long long decode_base62(const string& code) {
long long id = 0;
for (char c : code) {
int val = 0;
if (c >= '0' && c <= '9') val = c - '0';
else if (c >= 'a' && c <= 'z') val = 10 + (c - 'a');
else val = 36 + (c - 'A');
id = id * 62 + val;
}
return id;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
if (!(cin >> q)) {
vector<long long> ids = {125, 10000000, 3521614606207LL};
for (size_t i = 0; i < ids.size(); ++i) {
string code = encode_base62(ids[i]);
long long back = decode_base62(code);
if (i) cout << " ";
cout << code << ":" << back;
}
cout << "\n";
return 0;
}
for (int i = 0; i < q; ++i) {
long long id;
cin >> id;
string code = encode_base62(id);
long long back = decode_base62(code);
if (i) cout << " ";
cout << code << ":" << back;
}
cout << "\n";
return 0;
}
import sys
ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
def encode_base62(num: int) -> str:
if num == 0:
return "0"
chars = []
while num > 0:
chars.append(ALPHABET[num % 62])
num //= 62
return "".join(reversed(chars))
def decode_base62(code: str) -> int:
val = 0
for c in code:
if "0" <= c <= "9":
d = ord(c) - ord("0")
elif "a" <= c <= "z":
d = 10 + ord(c) - ord("a")
else:
d = 36 + ord(c) - ord("A")
val = val * 62 + d
return val
def main() -> None:
data = sys.stdin.read().split()
if not data:
ids = [125, 10000000, 3521614606207]
else:
q = int(data[0])
ids = [int(x) for x in data[1 : 1 + q]]
out = []
for x in ids:
c = encode_base62(x)
out.append(f"{c}:{decode_base62(c)}")
print(" ".join(out))
if __name__ == "__main__":
main()
import java.util.*;
public class Main {
static final String ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
static String encodeBase62(long id) {
if (id == 0) return "0";
StringBuilder sb = new StringBuilder();
while (id > 0) {
sb.append(ALPHABET.charAt((int) (id % 62)));
id /= 62;
}
return sb.reverse().toString();
}
static long decodeBase62(String code) {
long id = 0;
for (int i = 0; i < code.length(); i++) {
char c = code.charAt(i);
int d;
if (c >= '0' && c <= '9') d = c - '0';
else if (c >= 'a' && c <= 'z') d = 10 + (c - 'a');
else d = 36 + (c - 'A');
id = id * 62 + d;
}
return id;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long[] ids;
if (!sc.hasNextInt()) {
ids = new long[]{125L, 10000000L, 3521614606207L};
} else {
int q = sc.nextInt();
ids = new long[q];
for (int i = 0; i < q; i++) ids[i] = sc.nextLong();
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < ids.length; i++) {
if (i > 0) sb.append(" ");
String code = encodeBase62(ids[i]);
sb.append(code).append(":").append(decodeBase62(code));
}
System.out.println(sb.toString());
}
}
Độ phức tạp thuật toán:
- Thời gian (Time Complexity): Số bước chia hoặc nhân bằng đúng độ dài chuỗi mã hóa \(L = \lfloor \log_{62}(\text{ID}) \rfloor + 1 \le 11\) với mọi số nguyên 64-bit, tức \(\mathcal{O}(\log_{62} \text{ID}) = \mathcal{O}(1)\).
- Không gian (Space Complexity): \(\mathcal{O}(1)\) bộ nhớ phụ.
Bước 4: Sinh ID phân tán không nghẽn và Mẹo bảo mật thực tế
Nếu chỉ dùng AUTO_INCREMENT trên một máy chủ cơ sở dữ liệu duy nhất, máy chủ đó sẽ trở thành nút thắt cổ chai khi mở rộng quy mô. Trong hệ thống phân tán, có hai phương án chuẩn để cấp ID:
- Bộ sinh ID Twitter Snowflake (64-bit): Chia 64 bit thành:
1 bit dấu (0)+41 bit dấu thời gian mili-giây+10 bit mã máy chủ (Machine ID)+12 bit số thứ tự tự tăng trong cùng mili-giây. Mỗi máy chủ API tự sinh được tới \(4{,}096\text{ ID/ms}\) mà không cần giao tiếp mạng với nhau. - Dịch vụ cấp phát dải số (Range Allocator / ZooKeeper / etcd): Một cụm điều phối trung tâm chia không gian số thành các lô (ví dụ mỗi lô \(100{,}000\) số). Máy chủ API số 1 nhận dải \([1{,}000{,}001 \dots 1{,}100{,}000]\) và giữ trong RAM để cấp dần bằng biến đếm nguyên tử (
AtomicLong). Chỉ khi dùng hết lô hiện tại máy chủ mới xin lô tiếp theo, giảm \(99.999\%\) lượt gọi mạng.
Xử lý lỗ hổng đoán trước liên kết (Sequential ID Enumeration)
Một điểm cộng rất lớn trong buổi phỏng vấn là khi bạn chủ động chỉ ra: "Nếu ID tăng tuần tự \(1000, 1001, 1002\), kẻ tấn công có thể cộng thêm 1 vào mã Base62 để quét toàn bộ kho liên kết của hệ thống."
Cách khắc phục cực kỳ thanh lịch mà vẫn giữ nguyên tính song ánh 1-1 là thực hiện một phép hoán vị bit tuyến tính (Feistel Cipher trên 42 bit) hoặc nhân mô-đulo với một số nguyên tố lớn cùng nhau với \(62^7\) trước khi đưa vào hàm encodeBase62(id). Khi đó, hai ID liên tiếp sẽ tạo ra hai chuỗi 7 ký tự khác biệt hoàn toàn về mặt thị giác.
Luyện ngay trên Big-O Coding
Kỹ thuật xử lý chuỗi ký tự tại chỗ và tìm kiếm phần tử còn thiếu trong không gian số nguyên chính là nền tảng trực tiếp của bộ mã hóa URL và bộ cấp phát định danh; hãy thử sức ngay với 2 bài toán dưới đây:
Nếu hai người dùng khác nhau cùng rút gọn một long_url giống hệt nhau thì nên trả về cùng một short_code hay hai mã khác nhau?
Trong thực tế sản phẩm (như Bitly), hệ thống thường cấp hai short_code riêng biệt cho hai người dùng khác nhau dù chung một URL đích. Lý do là mỗi người dùng muốn theo dõi thống kê lượt click (Analytics) của riêng chiến dịch tiếp thị mà họ chia sẻ, và nếu người dùng A xóa hoặc sửa link ngắn của họ thì không được làm hỏng link của người dùng B.
Người dùng muốn tự đặt mã rút gọn riêng (custom_alias, ví dụ sho.rt/bigo-contest) thì thiết kế cơ sở dữ liệu thay đổi thế nào?
Với các liên kết tự đặt custom_alias, chuỗi này không được sinh từ bộ đếm Base62 tự động nên bạn không thể giải mã ngược về ID số nguyên. Giải pháp chuẩn là lưu cột short_code VARCHAR(16) có đánh chỉ mục duy nhất (UNIQUE INDEX) và kiểm tra sự tồn tại trên Redis/Database khi tạo mới. Ngoài ra, bộ sinh Base62 tự động cần tránh các từ khóa nhạy cảm hoặc đã được đặt trước.
Làm thế nào để dọn dẹp các liên kết đã hết hạn (expires_at) mà không làm treo cơ sở dữ liệu?
Không nên chạy một tiến trình quét xóa (DELETE FROM urls WHERE expires_at < NOW()) liên tục vào giờ cao điểm vì sẽ gây khóa bảng và tốn I/O đĩa. Thay vào đó, hãy kết hợp Xóa lười (Lazy Expiration): khi người dùng truy cập một link mà kiểm tra thấy expires_at < NOW(), hệ thống trả về lỗi 410 Gone / 404 và đánh dấu xóa ngay lúc đó; đồng thời chạy một tác vụ nền (Cron Job) vào lúc 3 giờ sáng để dọn dẹp theo từng lô nhỏ (Batch Delete 1,000 dòng mỗi lần) đối với các link hết hạn chưa từng được truy cập lại.
Luyện LeetCode thực chiến theo pattern, giải bài trong 45 phút và mock interview cùng AI. 16 buổi online, lớp 7–12 học viên, chọn C++, Java hoặc Python.


