Thiết kế URL shortener: ước lượng tải, cấp mã và chọn redirect Trung cấp

Vấn đề

Người dùng dán URL dài, nhận https://sho.rt/ab3. Ai mở link ngắn được chuyển sang URL gốc. Bản demo Map làm được trong 20 dòng. Khó ở chỗ khác:

• Hai instance có cấp trùng code không?
• Link bị thu hồi thì browser và CDN có còn giữ đích cũ không?
• Một link viral nhận nhiều traffic hơn cả phần còn lại thì database chịu ra sao?

Hai luồng có yêu cầu trái ngược. Ghi (tạo link): ít, cần validation và code duy nhất. Đọc (mở link): rất nhiều, cần lookup nhanh và redirect đúng.

Quyết định chính trong một bảng

Câu hỏi	Mặc định đề xuất	Đổi khi nào
Độ dài code	6-7 ký tự base62	Cần 100 tỷ link trở lên, hoặc cần code khó đoán hơn
Cấp code	ID range allocation + base62 (+ hoán vị nếu cần chống đoán)	Cần code không thể đoán: random 7+ ký tự + UNIQUE + retry
Lưu mapping	PostgreSQL, code UNIQUE	Ghi vượt khả năng một primary: shard theo code
Redirect	302 hoặc 307 + Cache-Control ngắn	Link không bao giờ đổi, cần SEO: 301/308
Đếm click	Event async ra queue	Cần số chính xác để tính tiền: định nghĩa lại “click” trước

Ước lượng tải (giả định nêu rõ, tự tính lại được)

Đây là giả định của bài, không phải số đo từ hệ thống thật. Đổi giả định thì đổi kết quả.

Giả định	Giá trị
Link mới mỗi tháng	100 triệu
Tỷ lệ đọc : ghi	100 : 1
Hệ số đỉnh so với trung bình	10 lần
Thời gian lưu	5 năm, không xóa
Kích thước một dòng (code, URL, metadata, index)	~500 byte
Kích thước một response redirect	~300 byte

Một tháng = 30 × 86.400 = 2.592.000 giây.

Đại lượng	Phép tính	Kết quả
Ghi trung bình	100.000.000 / 2.592.000	~39 req/s
Đọc trung bình	38,58 × 100	~3.900 req/s (3.858)
Đọc đỉnh	3.858 × 10	~38.600 req/s
Số link sau 5 năm	100 triệu × 12 × 5	6 tỷ
Dung lượng sau 5 năm	6 × 10^9 × 500 byte	~3 TB
Băng thông đỉnh	38.580 × 300 byte	~11,6 MB/s
Cache nóng (giả định 10 triệu link)	10^7 × ~200 byte	~2 GB

Kết luận có ích: ghi chỉ ~39 req/s, một primary PostgreSQL thừa sức. Đọc đỉnh ~38.600 req/s là thứ cần cache. 3 TB không thuộc loại phải shard ngay, nhưng cần kế hoạch partition hoặc archive.

Base62 và độ dài code

62 ký tự 0-9a-zA-Z, nên k ký tự cho 62^k giá trị.

k	62^k	Đủ cho
5	916.132.832 (~0,9 tỷ)	~9 tháng ở 100 triệu link/tháng
6	56.800.235.584 (~56,8 tỷ)	6 tỷ link (5 năm) với dư địa gấp ~9 lần
7	3.521.614.606.208 (~3,5 nghìn tỷ)	Dư cho random code, collision rất thấp

Với bộ đếm tăng dần, 5 năm chỉ cần 6 ký tự. Với random code thì 6 ký tự quá chật: 6 tỷ link chiếm 6×10^9 / 5,68×10^10 = 10,6% không gian, nên 1 trong 10 lần thử đầu đã trùng. Dùng 7 ký tự.

Bốn cách cấp code

Cách	Cơ chế	Ưu	Nhược
Counter / sequence	base62(nextval)	Không bao giờ trùng, code ngắn nhất	Đoán được, lộ quy mô, một điểm phối hợp
ID range allocation	Mỗi instance xin một dải (ví dụ 1.000 ID), tự đếm trong RAM	Giữ ưu điểm của counter, allocator gần như không bị gọi	Crash làm mất phần dải chưa dùng (chấp nhận được), code không tăng đơn điệu giữa instance
Random	7 ký tự ngẫu nhiên (CSPRNG) + UNIQUE + retry	Khó đoán, không cần phối hợp	Có retry; xác suất trùng tăng theo độ đầy
Hash truncation	Cắt hash(URL) còn 7 ký tự	Cùng URL ra cùng code (dedupe tự nhiên)	Birthday bound thấp, xem dưới; vẫn cần retry với salt

Range allocation là cách PostgreSQL tự làm với CREATE SEQUENCE ... CACHE n: mỗi session giữ sẵn n số, số chưa dùng mất khi session kết thúc, và các session chỉ được đảm bảo nhận giá trị khác nhau, không đảm bảo đúng thứ tự. Sequence cũng không rollback, nên gap xảy ra cả khi CACHE 1. Với shortener gap không sao.

Birthday bound: vì sao hash truncation nguy hiểm

Không gian N = 62^7 ≈ 3,52 × 10^12 (khoảng 41,7 bit). Với n link, xác suất có ít nhất một cặp trùng ≈ 1 − e^(−n² / 2N).

n link	Xác suất có cặp trùng bất kỳ
1 triệu	~13%
~2,2 triệu	~50% (n ≈ 1,18 × √N)
10 triệu	~100%

Nghĩa là cắt hash xuống 7 ký tự thì va chạm xuất hiện rất sớm, chỉ vài triệu link. Với random code thì hỏi khác: xác suất một insert mới trúng code đã có là n / N, ở 6 tỷ link là 6×10^9 / 3,52×10^12 ≈ 0,17%, retry rẻ. Cả hai đều cần UNIQUE constraint làm trọng tài.

Muốn dùng counter nhưng không để lộ thứ tự: ánh xạ ID qua một hoán vị song ánh trên [0, 62^7) (ví dụ Feistel network có khóa) rồi mới base62. Giữ nguyên tính không trùng, code trông ngẫu nhiên.

Redirect: 301, 302, 307 hay 308?

Theo RFC 9110, mục 15.4:

Status	Ý nghĩa	Cache mặc định	Đổi method POST thành GET	SEO / analytics
301	Đích mới vĩnh viễn	Heuristically cacheable	Client được phép đổi	Google coi là tín hiệu đích canonical; browser/CDN có thể giữ lâu, request sau không về origin, mất click, khó đổi đích
302	Đích tạm thời	Chỉ cache khi có header cache tường minh	Client được phép đổi	Google không coi là canonical, URL ngắn vẫn là URL được index; mọi click về origin nếu không cache
307	Đích tạm thời	Như 302	Cấm đổi method	Như 302
308	Đích mới vĩnh viễn	Heuristically cacheable	Cấm đổi method	Như 301; ít client cũ không nhận ra

Các điểm cần nhớ:

• “Heuristically cacheable” nghĩa là cache được phép tự suy ra thời hạn giữ (RFC 9111). Đừng dựa vào hành vi đó: luôn gửi Cache-Control rõ ràng.
• Shortener chỉ phục vụ GET/HEAD nên khác biệt giữa 301 và 308 (hoặc 302 và 307) chỉ còn là phần lịch sử; chọn cặp mới (307/308) nếu muốn ngữ nghĩa chặt.
• Mặc định nên dùng 302 hoặc 307 kèm Cache-Control: private, max-age=60 (hoặc public nếu cho CDN cache): vừa đo được click, vừa đổi/thu hồi trong vài chục giây.
• Dùng 301/308 khi link không bao giờ đổi và bạn chấp nhận không đếm được phần lớn click lặp.

Cách hoạt động

Luồng ghi cấp code duy nhất, luồng đọc đi qua CDN rồi cache rồi store

Phóng to sơ đồ

Client tạo link → Write APIPOST target

◀ Trước▶ PhátTiếp ▶↺ Từ đầuBước 1/6

Ghi: Write API validate URL (scheme, độ dài, blocklist) rồi cần một code duy nhất.

Điểm đáng nhìn trong sơ đồ:

1. Allocator ít bị gọi: ở ~39 ghi/giây với dải 1.000 ID, toàn hệ thống chỉ xin dải khoảng 0,04 lần mỗi giây (39 / 1.000).
2. Đọc có ba tầng chặn: CDN, Redis, rồi mới đến store. Phần lớn 38.600 req/s đỉnh không bao giờ chạm database.
3. Chính sách cache của redirect quyết định tầng nào chặn được: max-age dài thì CDN chặn nhiều, nhưng thu hồi chậm.

Chi tiết cần xử lý khi hiện thực:

• Link không tồn tại trả 404; link đã gỡ hoặc hết hạn có thể trả 410 Gone. Negative caching chỉ nên vài giây để không giữ 404 cho code vừa tạo.
• Link hot cùng hết cache một lúc gây stampede: xem cache stampede.
• Khi thu hồi link độc hại, phải xóa cả Redis lẫn purge CDN; redirect đã cache ở browser thì chỉ chờ hết max-age.
• Server tự fetch URL đích (để lấy preview) mở ra SSRF: xem SSRF.

Ví dụ thực tế

Link chiến dịch SMS: 2 triệu tin trong 10 phút

Chiến dịch gửi 2 triệu SMS, mỗi tin một link ngắn riêng. Giả sử 20% người nhận mở link trong 10 phút đầu: 400.000 click / 600 giây ≈ 670 req/s, thấp hơn nhiều so với đỉnh 38.600 ở trên.

Nhưng nếu cùng một link được gửi cho tất cả, 670 req/s dồn vào một key. Redis chịu được, store thì không nên bị chạm: cache-aside với TTL và request coalescing là bắt buộc.

Đội dùng 302 với max-age=60. Khi phát hiện link đích lỗi, họ sửa đích và xóa cache; tối đa 60 giây sau mọi người dùng thấy đích mới. Nếu họ dùng 301, người đã mở link có thể còn giữ đích cũ trong browser.

Demo cấp mã và validation

npx --prefix examples ts-node examples/src/url-shortener/shortener-demo.ts

Output thật:

{ code: '1', target: 'https://example.org/articles/42' }
{ missing: '404' }

Demo chỉ kiểm tra base62, validation (https: và không có credential) và lookup trong một process. Hai instance chạy riêng đều bắt đầu nextId = 1, nên trùng code: đó là lý do cần allocator và UNIQUE ở storage chung. Chuỗi 404 là do demo tự in, không phải HTTP response.

Bảng tối thiểu trong PostgreSQL:

CREATE TABLE link (
  id          bigint PRIMARY KEY,
  code        text   NOT NULL UNIQUE,
  target_url  text   NOT NULL,
  owner_id    bigint NOT NULL,
  created_at  timestamptz NOT NULL DEFAULT now(),
  expires_at  timestamptz,
  disabled_at timestamptz
);

Index UNIQUE trên code phục vụ lookup (xem B-tree index). Chỉ thêm (owner_id, created_at) khi có trang quản lý link cần nó. Đừng tái sử dụng code đã hết hạn: link cũ sẽ trỏ sang đích mới.

🎮 Thử tay

• Scale Lab: đề URL shortener: 4 vòng từ MVP tới link viral và bot spam.
• Dựng URL shortener: một màn kéo thả trong ngân sách.

Checklist production

1. Code unique bằng UNIQUE constraint; bắt lỗi trùng và cấp lại (random) hoặc xin dải mới (allocator).
2. Độ dài code tính từ số link dự kiến, có dư địa 10 lần.
3. Chọn status redirect theo yêu cầu đổi/thu hồi, và luôn đặt Cache-Control tường minh.
4. Cache-aside cho lookup, TTL hữu hạn, negative cache chỉ vài giây, có cách purge khi thu hồi.
5. Rate limit theo IP cho code không tồn tại (chống dò), giới hạn độ dài code.
6. Validation URL đích: scheme cho phép, không credential, blocklist phishing; không tự fetch URL nếu chưa chặn SSRF.
7. Analytics qua queue bất đồng bộ; định nghĩa “click” (request, lọc bot, hay session) trước khi báo cáo.
8. Quy trình gỡ link độc hại, kể cả cache và CDN.

Khi nào dùng / không dùng thiết kế này

• Dùng: tải đọc nhiều hơn ghi hàng chục lần, link ít khi bị sửa, chấp nhận eventual consistency vài chục giây khi thu hồi.
• Không đủ: cần thu hồi tức thì toàn cầu (dùng Cache-Control: no-store và chấp nhận mọi click về origin), hoặc cần đếm click chính xác theo từng người (cần tracking riêng, không suy ra từ redirect).

Sai lầm thường gặp

Sai lầm thường gặp

Chỉ kiểm tra trùng code ở application. Hai instance cùng thấy “chưa có” rồi cùng insert. UNIQUE hoặc allocator phải phân xử.

Sai lầm thường gặp

Chọn 301 rồi kỳ vọng đổi đích có hiệu lực ngay. 301/308 có thể được cache lâu, kể cả khi bạn không đặt max-age. Nếu cần sửa hoặc thu hồi nhanh, dùng 302/307 với max-age ngắn.

Sai lầm thường gặp

Cắt hash còn 7 ký tự và không xử lý va chạm. Birthday bound cho thấy xác suất có cặp trùng đã ~13% ở 1 triệu link.

Sai lầm thường gặp

Đếm mọi redirect như một người dùng. Bot, prefetch và cache làm số request khác số người thật.

Tóm tắt

Tóm tắt

• Ước lượng trước: với giả định đã nêu, ghi ~39 req/s, đọc đỉnh ~38.600 req/s, 3 TB sau 5 năm; ghi dễ, đọc cần cache.
• 6 ký tự base62 (56,8 tỷ) đủ cho counter; random code dùng 7 ký tự.
• Hash truncation 7 ký tự trùng ở ~2,2 triệu link (birthday bound); mọi cách cấp code đều cần UNIQUE.
• 302/307 + Cache-Control ngắn là mặc định an toàn; 301/308 chỉ khi link bất biến.
• Định nghĩa analytics và quy trình thu hồi là yêu cầu của thiết kế, không phải phần phụ.

Tự kiểm tra: (1) Tự tính lại QPS đọc đỉnh nếu tỷ lệ đọc : ghi là 500 : 1. (2) Với 8 ký tự base62, hash truncation đạt xác suất trùng 50% ở khoảng bao nhiêu link (gợi ý: 1,18 × √(62^8))? (3) Shortener chỉ phục vụ GET, vậy chọn 301 hay 302 khác nhau ở điểm nào (cache, analytics, SEO)?

Tham khảo

• RFC 9110, mục 15.4 — Redirection 3xx
• RFC 9111 — Heuristic freshness
• Redirects and Google Search
• CREATE SEQUENCE — PostgreSQL 17
• Unique Indexes — PostgreSQL 17
• URL API — Node.js