Đến nội dung chính
notes.vinhnq.com

Tìm kiếm

System DesignMid19 phút đọc

Thiết kế URL shortener: sinh mã ngắn, Base62, token range và chuyển hướng

Ôn 12 thẻ
Trong bài này

URL shortener là đề system design “nhập môn” nhưng đủ chỗ để thể hiện độ sâu: sinh mã không trùng, không đoán được, đọc nhiều gấp trăm lần ghi. Bài này đi đủ các bước như một buổi phỏng vấn, kèm phép tính và các chỗ slide gốc nói chưa đúng. Cuối bài có kế hoạch trình bày 45 phút và vài quy ước vẽ sơ đồ.

1. Hỏi yêu cầu

Ý chính: chốt chức năng cốt lõi (rút gọn, chuyển hướng) và bốn con số: số ghi mỗi ngày, tỉ lệ đọc/ghi, độ dài mã, thời gian lưu.

Chức năng:

  • Rút gọn một long URL thành short URL, như Bitly hay TinyURL.
  • Cùng một long URL có thể nhận nhiều short URL khác nhau (mỗi chiến dịch một link riêng để đo).
  • Mã không trùng (collision-free) và không đoán được (không lần ra link của người khác bằng cách tăng mã).
  • Người dùng tự chọn mã (custom alias), link thân thiện với SEO, có thống kê click.

Câu hỏi về quy mô và câu trả lời trong đề:

Câu hỏi Trả lời
Bao nhiêu link mới mỗi ngày? 10 triệu
Tỉ lệ đọc : ghi? 100 : 1
Mã dài tối đa? 8 ký tự
Lưu bao lâu? 4 năm

Phi chức năng: availability cao (link chết là hỏng chiến dịch của khách), latency chuyển hướng thấp (p99 dưới ~50 ms phía server), mở rộng được, bền dữ liệu.

2. Ước lượng

Ý chính: ghi ~116/giây, đọc ~12K/giây, 14,6 tỷ bản ghi trong 4 năm, vài chục TB kể cả replica; cache cho link nóng chỉ vài GB.

Mẹo: một ngày có 86.400 giây, làm tròn 10⁵ cho nhẩm nhanh. Các con số cần thuộc và mẹo nhân lũy thừa 10 nằm ở Ước lượng back-of-the-envelope.

  • Ghi: 10⁷ / 10⁵ = 100/giây (chính xác ~116). Đỉnh ×3 ≈ 350/giây.
  • Đọc: 100 × 116 ≈ 12K/giây, đỉnh ≈ 35K/giây.
  • Số bản ghi 4 năm: 10⁷ × 365 × 4 ≈ 1,46 × 10¹⁰.
  • Dung lượng: một bản ghi ~500 byte (mã, long URL trung bình ~200 byte, user, thời điểm tạo và hết hạn, overhead) → 1,46 × 10¹⁰ × 500 B ≈ 7,3 TB; replication factor 3 → ~22 TB. Slide ra 17,6 TB và 52,8 TB, tức ngầm giả định ~1,2 KB mỗi bản ghi. Điều quan trọng là nói rõ giả định.
  • Cache: giữ link tạo trong một ngày (link mới được click nhiều nhất): 10⁷ × ~220 B ≈ 2,2 GB, một node Redis là đủ.
  • Không gian mã: 62⁶ ≈ 5,7 × 10¹⁰, 62⁷ ≈ 3,5 × 10¹², 62⁸ ≈ 2,2 × 10¹⁴. Cần 1,46 × 10¹⁰ nên 6 ký tự đã đủ; chọn 7 để dư ~240 lần.

3. API

Ý chính: hai đường chính: tạo link (POST, ghi) và chuyển hướng (GET /{code}, đọc nóng). Thống kê và quản lý là phụ.

POST /api/v1/urls
{ "longUrl": "https://shop.example/sale?utm=fb", "customAlias": "sale-tet", "expiresAt": "2027-02-01T00:00:00Z" }
→ 201 { "code": "sale-tet", "shortUrl": "https://sho.rt/sale-tet" }

GET /{code}
→ 302 Location: https://shop.example/sale?utm=fb      (404 nếu không có, 410 nếu đã hết hạn)

GET /api/v1/urls/{code}/stats?from=2026-11-01&to=2026-11-18
→ 200 { "clicks": 18234, "byCountry": { ... } }

POST cần idempotency key nếu client có thể retry, để một lần bấm không tạo hai link (xem idempotency). Rate limit theo API key và theo IP để chặn spam.

4. Sinh mã: bốn cách và lựa chọn

Ý chính: tách bài toán làm hai: sinh một số nguyên duy nhất, rồi mã hoá Base62 cho ngắn và hợp URL. Trong bốn cách sinh số, token range thắng nhờ không trùng, ngắn và không cần phối hợp mỗi lần ghi.

Vì sao Base62. Base36 (a-z0-9) cho mã dài hơn; Base64 có + và / phải escape trong URL. Base62 (a-zA-Z0-9) là bảng chữ lớn nhất an toàn với URL. Một số 7 chữ số Base62 chứa tối đa 3,5 nghìn tỷ giá trị.

Cách Ý tưởng Trùng? Độ dài Đoán được? Kết luận
Ngẫu nhiên (UUID, CSPRNG) chọn ngẫu nhiên trong 62⁸ rồi Base62 có, theo nghịch lý ngày sinh, phải kiểm tra khi ghi 8 không dùng được nếu chấp nhận ghi có điều kiện
Hash (MD5/SHA của long URL, cắt 7 ký tự) băm rồi cắt có, và cắt càng ngắn càng dễ 7 cùng URL ra cùng mã trái yêu cầu “một URL nhiều mã”
Snowflake (64 bit: thời gian + máy + sequence) ID phân tán không 11 có, theo thời gian quá dài
Token range (bộ đếm chia khoảng) mỗi instance giữ một khoảng số không 7 có, nếu không xáo chọn, kèm xáo

Token range hoạt động thế nào

Một bộ điều phối cấp khoảng số không chồng nhau; mỗi instance Token Service giữ khoảng của mình trong RAM và cấp số bằng một AtomicLong. Hết khoảng thì xin khoảng mới.

flowchart LR
  C[(ZooKeeper hoặc PostgreSQL: next_start)] -->|xin khoảng 1M số| T1["Token service 1: 1 - 1M"]
  C --> T2["Token service 2: 1M - 2M"]
  T1 -->|next++ trong RAM| S[Shortener]
  T2 --> S
  S -->|xáo + Base62| K[mã 7 ký tự]
  • Bộ điều phối có thể là ZooKeeper (như slide) hay đơn giản hơn: một dòng PostgreSQL UPDATE id_alloc SET next_start = next_start + 1000000 RETURNING next_start. Câu UPDATE tự khoá dòng nên hai instance không nhận trùng khoảng.
  • Ở 116 ghi/giây, một khoảng 1 triệu số dùng được ~2,4 giờ; bộ điều phối gần như không bị gọi.
  • Instance chết thì phần còn lại của khoảng bị bỏ phí. Không sao: 3,5 nghìn tỷ mã, phí vài triệu không đáng kể.

Không đoán được: xáo số trước khi mã hoá

Token range cho số tuần tự, nên aB3xK9p và mã kế tiếp chỉ khác chữ cuối. Ai đó có thể quét hết link của người khác. Slide liệt kê “đoán được” là nhược điểm nhưng vẫn chọn, trái với yêu cầu “không đoán được”.

Cách sửa: trước khi Base62, đưa số qua một phép hoán vị có khoá bí mật trên miền cố định, ví dụ mạng Feistel 42 bit. Hoán vị nghĩa là hai số khác nhau luôn ra hai số khác nhau, nên vẫn không trùng; nhưng nhìn mã thì không suy ra mã kế tiếp.

Code Java: Feistel 42 bit và Base62
final class CodeGenerator {
    private static final String ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    private static final int HALF = 21;                       // 2 nửa × 21 bit = 42 bit
    private static final long MASK = (1L << HALF) - 1;
    private final long[] roundKeys;                           // khoá bí mật, nạp từ secret store

    CodeGenerator(long[] roundKeys) { this.roundKeys = roundKeys; }

    String encode(long counter) {                             // counter < 2^42 ≈ 4,4 nghìn tỷ
        long l = (counter >>> HALF) & MASK, r = counter & MASK;
        for (long k : roundKeys) {                            // 4 vòng là đủ để xáo
            long f = (mix(r ^ k)) & MASK;
            long next = l ^ f;
            l = r; r = next;
        }
        return base62((l << HALF) | r);
    }

    private static long mix(long x) {                         // hàm trộn bất kỳ, không cần khả nghịch
        x *= 0x9E3779B97F4A7C15L; x ^= (x >>> 29); return x;
    }

    private static String base62(long n) {
        StringBuilder sb = new StringBuilder();
        do { sb.append(ALPHABET.charAt((int) (n % 62))); n /= 62; } while (n > 0);
        return sb.reverse().toString();
    }
}

Feistel luôn khả nghịch dù hàm mix không khả nghịch, nên đây là hoán vị trên [0, 2⁴²). Kết quả < 2⁴² ≈ 4,4 × 10¹² nên vừa 8 ký tự Base62 (thường 7). Muốn ép đúng 7 ký tự thì dùng cycle-walking: nếu kết quả ≥ 62⁷ thì mã hoá tiếp tới khi lọt vào miền.

Đây không phải mã hoá chống người có tài nguyên lớn, chỉ đủ để mã không đoán được bằng cách tăng dần. Thư viện Sqids (trước là Hashids) làm việc tương tự.

5. Lưu trữ và data model

Ý chính: bảng URL là key-value thuần (tra theo mã, không join), hàng chục tỷ dòng: hợp với wide-column như ScyllaDB/Cassandra, partition key là chính mã. Bảng user và gói cước có quan hệ, cần ACID: PostgreSQL.

-- ScyllaDB (CQL)
CREATE TABLE urls (
  code        text PRIMARY KEY,      -- partition key, phân tán bằng hash
  long_url    text,
  user_id     bigint,
  created_at  timestamp,
  expires_at  timestamp
);  -- ghi với USING TTL nếu link có hạn

CREATE TABLE url_by_hash (           -- chỉ cần khi có yêu cầu "một long URL một mã"
  long_url_hash blob PRIMARY KEY,    -- SHA-256(long_url chuẩn hoá)
  code          text
);

Vì sao không PostgreSQL cho bảng URL? 14,6 tỷ dòng, 22 TB: PostgreSQL làm được nhưng phải tự shard (Citus hoặc chia theo hash ở app). ScyllaDB có sẵn phân vùng theo hash, replication và thêm node trực tuyến. Mình đã viết về partition và sharding.

Yêu cầu thêm: một long URL chỉ một mã

Ý chính: cần tra “long URL này đã có mã chưa” rồi mới tạo. Đừng index cả chuỗi URL dài; index hash(long_url) và dùng ghi có điều kiện để hai request đồng thời không tạo hai mã.

Slide đưa hai phương án:

  • Bloom filter: nói “chắc chắn chưa có” rất rẻ; “có thể có” thì phải hỏi DB. Slide loại vì false positive, nhưng false positive chỉ tốn thêm một lần đọc. Vấn đề thật: phải đồng bộ filter giữa các instance, không xoá được, và vẫn cần DB để biết mã cũ là gì.
  • Global secondary index trên hash(long_url): trong suốt với app. Nhưng GSI của ScyllaDB là materialized view, cập nhật bất đồng bộ.

6. Chuyển hướng, cache và analytics

Ý chính: đường đọc là cache-aside: Redis trước, ScyllaDB khi miss. Dùng 302 để mỗi click về server và đẩy sự kiện click vào Kafka bất đồng bộ; không bao giờ để analytics làm chậm chuyển hướng.

flowchart LR
  U[Người dùng] --> CDN[CDN]
  CDN --> GW[API gateway + rate limit]
  GW -->|POST| SH[Shortener]
  GW -->|GET code| TR[URL translator]
  SH --> TS[Token service]
  SH --> DB[(ScyllaDB)]
  SH --> RC[(Redis)]
  TR --> RC
  TR -->|miss| DB
  TR -.->|click event| K[Kafka]
  K -.-> AN[(Analytics: ClickHouse)]

Vài chi tiết đường đọc:

  • Cache-aside với TTL 1 ngày cho link thường, link sắp hết hạn thì TTL = thời gian còn lại (xem cache-aside và invalidation).
  • Mã không tồn tại (bot quét mã ngẫu nhiên) xuyên qua cache vào DB: cache kết quả rỗng TTL ngắn, hoặc Bloom filter của mọi mã đã cấp. Ở đây Bloom filter rất hợp (xem cache penetration).
  • Link viral (một mã chiếm 30% lượt đọc) làm nóng một node Redis: thêm cache trong tiến trình (Caffeine, TTL vài giây) ở translator.
  • Analytics: translator gửi {code, ts, ip, ua, referer} vào Kafka không chờ ack đồng bộ; một consumer tổng hợp theo phút vào ClickHouse. Mất một vài click khi sự cố là chấp nhận được.

7. Lỗi, mở rộng và các chỗ hay bị hỏi

Ý chính: mỗi thành phần chết thì hệ thống còn làm được gì: ZooKeeper chết vẫn tạo link tới hết khoảng; Redis chết thì đọc thẳng ScyllaDB (12K/giây vẫn chịu được); một node ScyllaDB chết thì replica khác phục vụ.

  • Custom alias: ghi có điều kiện IF NOT EXISTS. Tránh đụng mã tự sinh tương lai: alias phải dài ≥ 8 ký tự hoặc chứa -, còn mã tự sinh luôn 7 ký tự Base62.
  • Hết hạn và dọn dẹp: TTL của ScyllaDB tự xoá; mã đã hết hạn không tái sử dụng (người cũ vẫn có link in trên giấy).
  • Lạm dụng: quét long URL qua dịch vụ kiểm tra mã độc trước khi kích hoạt, chặn domain xấu, rate limit theo user.
  • Nhiều vùng địa lý: đọc ở vùng gần nhất (ScyllaDB multi-DC, consistency LOCAL_ONE cho đọc), mỗi vùng có token range riêng nên ghi không cần phối hợp liên vùng.

8. Trình bày trong 45 phút

Ý chính: đi từ trên xuống: vấn đề → ý tưởng → thiết kế tổng thể → chi tiết → edge case → xử lý lỗi, và chốt lại ở cuối. Dành nhiều thời gian nhất cho phần khó thật: sinh mã.

Phút Việc Nói gì
0–5 Yêu cầu chức năng, 4 con số, “không đoán được” và “một URL nhiều mã”
5–10 Ước lượng 116 ghi/giây, 12K đọc/giây, 14,6 tỷ bản ghi, 7 ký tự đủ
10–15 API + data model POST, GET /{code}, bảng urls partition theo mã
15–20 Sơ đồ tổng thể gateway, shortener, translator, cache, DB
20–35 Đào sâu bốn cách sinh mã, token range, xáo Feistel, 301/302, dedupe
35–42 Lỗi và mở rộng thành phần nào chết thì sao, link viral, multi-region
42–45 Tóm tắt ba quyết định chính và điều sẽ làm tiếp
Quy ước vẽ sơ đồ và mẹo trình bày

Vẽ sơ đồ (dùng UML sequence/activity, C4 hay tự do đều được, miễn nhất quán; xem thêm C4):

  • Mọi hộp và mũi tên đều có nhãn. Mũi tên từ bên gọi tới bên được gọi.
  • Đồng bộ là nét liền, bất đồng bộ là nét đứt.
  • Hình: service là chữ nhật, database là hình trụ đứng, message queue là hình trụ nằm.
  • Màu có nghĩa và không quá 5 màu: đỏ cho thành phần chính hoặc chỗ dễ vỡ, xanh lá cho đã an toàn/xong, vàng cho cảnh báo, xám cho thứ đã tắt.
  • Thuộc phím tắt của công cụ, nhóm các phần tử liên quan, dùng lớp nền để khoanh vùng (ví dụ “đường ghi”, “đường đọc”).

Trình bày:

  • Từ trên xuống: trừu tượng → chi tiết → trừu tượng. Mỗi lần đi sâu, nói rõ mình đang ở đâu trên sơ đồ.
  • Quy tắc ba: gom thành ba ý chính (“ba quyết định của tôi là…”), nhắc lại ý quan trọng ba lần.
  • Hai kênh: lời nói và hình vẽ. Đừng nhồi chữ lên bảng; vẽ ít, nói nhiều.
  • Mở đầu bằng vấn đề hoặc nỗi đau của người dùng, kết bằng phần tóm tắt.

Ghi nhớ

  • Tính được nhanh số ghi/đọc mỗi giây, số bản ghi 4 năm và vì sao 7 ký tự Base62 là đủ.
  • So sánh được bốn cách sinh mã, và chỉ ra chỗ slide sai về Snowflake và ID ngẫu nhiên.
  • Giải thích được token range và cách làm cho mã không đoán được mà vẫn không trùng.
  • Biết khi nào chọn 301, khi nào 302, và analytics đi đường nào.
  • Biết vì sao “tra index rồi ghi” tạo trùng, và sửa bằng ghi có điều kiện.

Câu hỏi phỏng vấn

Junior

Vì sao dùng Base62 chứ không phải Base64 cho mã ngắn?

Base62 (a-zA-Z0-9) là bảng chữ lớn nhất không cần escape trong URL; Base64 có + và / phải mã hoá lại.

Bảng chữ càng lớn thì mã càng ngắn: 7 ký tự Base62 chứa ~3,5 nghìn tỷ giá trị, còn Base36 cần 8 ký tự cho cùng lượng đó.

Mid

So sánh bốn cách sinh mã ngắn và chọn một.

Ngẫu nhiên (trùng, cần ghi có điều kiện), hash (trùng khi cắt ngắn, cùng URL ra cùng mã), Snowflake (không trùng nhưng 11 ký tự và đoán được), token range (không trùng, 7 ký tự, không cần phối hợp mỗi lần ghi). Chọn token range và xáo số trước khi Base62.

Nêu thêm cái giá: cần bộ điều phối cấp khoảng và chấp nhận phí số khi instance chết.

Đường đọc chịu 35K request/giây lúc đỉnh. Bạn thiết kế cache thế nào?

Cache-aside trên Redis, TTL ~1 ngày; cache cả kết quả rỗng hoặc dùng Bloom filter cho mã không tồn tại; thêm cache trong tiến trình cho link viral.

Bộ nhớ cho link nóng chỉ vài GB. Redis chết thì đọc thẳng ScyllaDB, vẫn chịu được tải này.

Senior

Token range cho số tuần tự, nên mã đoán được. Sửa thế nào mà vẫn không trùng?

Đưa số qua một phép hoán vị có khoá bí mật trên miền cố định (ví dụ mạng Feistel 42 bit) rồi mới Base62; hoán vị là song ánh nên không trùng, nhưng không suy ra được mã kế tiếp.

Cần ép đúng 7 ký tự thì dùng cycle-walking. Thư viện Sqids làm việc tương tự.

Yêu cầu mới: mỗi long URL chỉ có một mã. Làm sao để hai request đồng thời không tạo hai mã?

Dùng bảng url_by_hash với INSERT ... IF NOT EXISTS theo SHA-256 của URL đã chuẩn hoá; bên thua đọc lại mã đã có.

Không dựa vào secondary index (ở ScyllaDB cập nhật bất đồng bộ), và không dựa vào Bloom filter để quyết định (chỉ dùng để bỏ qua lần đọc khi chắc chắn chưa có).

ZooKeeper cấp token range bị sập 30 phút. Chuyện gì xảy ra?

Gần như không gì: mỗi instance còn khoảng số trong RAM, ở 116 ghi/giây một khoảng 1 triệu dùng được hơn 2 giờ. Chỉ instance mới khởi động hoặc vừa hết khoảng mới không tạo được link.

Muốn an toàn hơn thì xin khoảng mới khi khoảng hiện tại còn 20%, và cho phép đọc (chuyển hướng) hoàn toàn không phụ thuộc ZooKeeper.

Từ vựng tiếng Anh

Term Phát âm Nghĩa Ví dụ câu tiếng Anh dùng trong phỏng vấn
back-of-the-envelope /ˌbæk əv ði ˈen.və.loʊp/ ước lượng nhanh “A quick back-of-the-envelope estimate gives about 116 writes per second.”
keyspace /ˈkiː.speɪs/ không gian mã “Seven Base62 characters give a keyspace of 3.5 trillion.”
collision /kəˈlɪʒ.ən/ trùng mã “Random IDs will collide, so every insert must be conditional.”
token range /ˈtoʊ.kən reɪndʒ/ khoảng số được cấp sẵn “Each instance leases a token range and hands out IDs from memory.”
predictable /prɪˈdɪk.tə.bəl/ đoán được “Sequential codes are predictable, so I permute them first.”
permutation /ˌpɝː.mjəˈteɪ.ʃən/ hoán vị “A keyed permutation keeps codes unique but unguessable.”
redirect /ˌriː.dəˈrekt/ chuyển hướng “I’d use a 302 redirect so every click reaches us.”
conditional write /kənˈdɪʃ.ən.əl raɪt/ ghi có điều kiện “A conditional write with IF NOT EXISTS prevents duplicates.”
hot key /hɑːt kiː/ key bị truy cập dồn “A viral link becomes a hot key, so I add an in-process cache.”
read-heavy /ˈriːd ˌhev.i/ đọc nhiều hơn ghi “The system is read-heavy, a hundred reads per write.”

Ghi chép dựa trên khoá System Design (Ronin Engineer), viết lại theo cách hiểu của mình.