Thiết kế URL Shortener quy mô tỷ click 2026 - Snowflake ID, Base62, Bloom Filter và Cache đa tầng cho Production

Posted on: 4/16/2026 7:10:03 PM

1. Vì sao URL Shortener vẫn là bài system design đáng đào sâu nhất 2026

URL shortener là bài toán quen thuộc tới mức nhiều kỹ sư bỏ qua, nhưng nếu lật đáy lên bạn sẽ thấy nó là phòng thí nghiệm thu nhỏ của gần như mọi chủ đề system design: sinh ID phân tán, encoding gọn, cache đa tầng, Bloom Filter, phân tách read/write, kiểm soát hotspot, analytics phi đồng bộ, chống abuse. Một dịch vụ như Bitly xử lý hơn 10 tỷ click mỗi tháng, nghĩa là ~3.800 click/s trung bình và có thể vọt lên 30k+ click/s khi một link viral trong đêm — những con số buộc kiến trúc phải chính xác từng quyết định nhỏ.

Bài này không giới thiệu lại "cách băm URL thành 6 ký tự", mà là phân tích các quyết định kiến trúc trade-off nhau khi bạn thật sự phải ship một dịch vụ shortener sẵn sàng cho hàng tỷ click: sinh ID bằng gì, độ dài short-code bao nhiêu là đủ, cache ở đâu, xử lý cache-miss như thế nào, đẩy analytics ra sao, và chặn abuse bằng cơ chế gì. Toàn bộ blueprint cuối bài dùng .NET 10 Minimal API, PostgreSQL 18 và Redis làm cache — những thứ đã viết cụ thể trong các bài trước của anhtu.dev.

2. Yêu cầu chức năng và capacity planning

Trước khi vẽ bất cứ mũi tên nào, cần đóng đinh bốn con số: traffic đỉnh, kích thước cơ sở dữ liệu sau 5 năm, bandwidth, và tỉ lệ read/write. Con số quyết định toàn bộ lựa chọn downstream.

Từ bảng này có ba kết luận: (1) workload cực kỳ read-heavy — toàn bộ thiết kế phải tối ưu cho read path; (2) dung lượng 3TB không phải con số lớn, một instance PostgreSQL 18 là dư sức — không cần Cassandra/DynamoDB ngay từ đầu; (3) 7 ký tự Base62 là sweet spot, 6 quá chật khi có scan sequential, 8 thì dài thừa.

3. Kiến trúc tổng quan: ba tầng tách bạch

Kiến trúc production chia rõ ba path: write path (ngắn URL mới), read path (redirect), và analytics path (ghi click event). Điểm then chốt: analytics phải ra khỏi critical path của redirect, nếu không một spike click viral sẽ làm sập cả dịch vụ shorten.

flowchart LR
    U1(["User tạo URL"]) --> API["API Gateway"]
    API --> WS["Shorten Service"]
    WS --> IDG["ID Generator
Snowflake"]
    WS --> DB[("PostgreSQL
primary")]
    U2(["User click URL ngắn"]) --> CDN["CDN Edge"]
    CDN -. "miss" .-> LB["L7 LB"]
    LB --> RS["Redirect Service"]
    RS --> BF{"Bloom Filter"}
    BF -- "maybe" --> RC[("Redis Cache")]
    BF -- "no" --> E404(["404 nhanh"])
    RC -- "miss" --> RO[("PostgreSQL
read replica")]
    RS -. "fire and forget" .-> Q[("Kafka
click-events")]
    Q --> AN["Analytics Consumer"]
    AN --> CH[("ClickHouse")]

Hình 1: Ba path tách bạch, Bloom Filter đặt trước cache, analytics đẩy ra queue

Ba nguyên tắc rút ra từ sơ đồ:

• CDN là tầng cache đầu tiên. Redirect cho short-code phổ biến thậm chí không chạm tới server gốc. Cloudflare, Fastly hỗ trợ cache 301/302 theo TTL.
• Bloom Filter trước Redis. Khi có ai đó quét short-code ngẫu nhiên (kẻ xấu hoặc bot), 99% là code không tồn tại — Bloom Filter cắt ngay, không đánh cache, không đánh DB.
• Analytics tách sync. Mọi click event được đẩy sang Kafka rồi consumer xử lý ra ClickHouse. Redirect service không bao giờ đợi ghi analytics.

4. Sinh ID phân tán: Auto-increment vs Snowflake vs Hash

Lõi bài toán shortener là ánh xạ URL gốc → một short-code. Cách sinh short-code này thay đổi hoàn toàn hiệu năng và kiến trúc xuống dưới. Có ba trường phái phổ biến và mỗi cái có trade-off rõ rệt:

Với bài toán 39 write/s, auto-increment là đủ. Nhưng khi scale lên >10k write/s, hoặc chạy multi-region active-active, nên chuyển sang Snowflake rút gọn: 41-bit timestamp (69 năm) + 10-bit machine ID + 12-bit sequence = 63-bit, encode Base62 ra ~11 ký tự. Nếu muốn short-code 7 ký tự, có thể dùng trick: giữ Snowflake 64-bit làm primary key, nhưng sinh short-code bằng cách tăng counter Redis INCR url:counter rồi Base62 encode — counter này có thể pre-allocate batch 10.000 bằng INCRBY để service không phải hỏi Redis từng click.

5. Base62 encoding: vì sao không phải Base64

Base62 dùng 62 ký tự [0-9a-zA-Z] — bỏ khỏi Base64 bộ + / vì chúng gây rối trong URL. Một số dịch vụ chọn Base58 (bỏ thêm 0 O I l gây nhầm lẫn mắt thường), nhưng đổi lại tốn thêm một ký tự. Quyết định tùy use case: Base62 cho dịch vụ web, Base58 cho mã chia sẻ đọc được bằng miệng (tương tự Bitcoin address).

// encode counter (long) thành short-code Base62
public static string Base62Encode(long value)
{
    const string Alphabet =
        "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    if (value == 0) return "0";
    var sb = new StringBuilder(11);
    while (value > 0)
    {
        sb.Insert(0, Alphabet[(int)(value % 62)]);
        value /= 62;
    }
    return sb.ToString();
}

Với 7 ký tự Base62 ta có không gian 62⁷ = 3.52×10¹² tổ hợp. Nếu dịch vụ sinh 100M code mỗi tháng, sau 100 năm vẫn chưa dùng hết 0.4% không gian — đủ cho mọi mục đích thương mại. Tăng lên 8 ký tự chỉ khi bạn thực sự có nhu cầu thâm nhập enterprise B2B mà mỗi khách hàng muốn namespace riêng.

6. Write path: ghi an toàn, idempotent và chống collision

Write path đơn giản hơn read path nhiều, nhưng có ba cái bẫy. Cái đầu: nếu cùng một URL được shorten nhiều lần, trả về cùng short-code hay cấp mã mới? Quyết định này ảnh hưởng lớn tới khối lượng database. Hầu hết dịch vụ chọn trả mã mới cho API gọi ẩn danh (để track analytics tách biệt), và trả mã cũ cho user đã đăng nhập (để lịch sử người dùng gọn).

sequenceDiagram
    participant C as Client
    participant API as Shorten API
    participant KG as ID Counter
    participant DB as PostgreSQL
    participant BF as Bloom Filter
    C->>API: POST /shorten url
    API->>API: Validate URL schema, TLD
    API->>KG: INCR url:counter batch=1000
    KG-->>API: id=15237
    API->>API: Base62Encode 15237 = abc12
    API->>DB: INSERT ON CONFLICT do nothing
    DB-->>API: ok
    API->>BF: Add abc12 to filter
    API-->>C: short=anhtu.dev/abc12

Hình 2: Write path — batch counter, insert idempotent, update Bloom Filter

Ba điểm cần ngắm trong code thực tế:

• Validate URL sớm. Chặn schema không phải http/https, chặn TLD nội bộ (localhost, *.local), chặn URL rỗng hoặc quá dài (>2048 ký tự). Check này miễn phí và loại 80% input xấu.
• Insert idempotent. Dùng INSERT ... ON CONFLICT (short_code) DO NOTHING của PostgreSQL. Khi có race condition ở counter (ít xảy ra nhưng có), insert lần 2 sẽ no-op và service retry với ID tiếp theo.
• Thêm ngay vào Bloom Filter. Sau khi insert OK, push short-code sang Bloom Filter (dùng RedisBloom module hoặc in-memory shared). Nếu thiếu bước này, request đầu tiên tới code vừa tạo sẽ bị Bloom Filter chặn 404.

7. Read path: ba tầng cache và ngân sách 30ms

Read path là nơi mọi đồng tiền đầu tư vào hệ thống đổ về. 99% redirect phải trả lời dưới 30ms p99, có nghĩa không được đánh database ở 99% request. Kiến trúc cache ba tầng là cách chuẩn mực:

flowchart LR
    U(["Click /abc12"]) --> CDN{"CDN edge
cache 301?"}
    CDN -- "hit" --> R301(["301 ngay
tại edge"])
    CDN -- "miss" --> RS["Redirect Service"]
    RS --> L1{"L1 in-process
LRU 10k"}
    L1 -- "hit" --> OUT1(["trả 301"])
    L1 -- "miss" --> BF{"Bloom Filter"}
    BF -- "no" --> E404(["404"])
    BF -- "maybe" --> L2{"L2 Redis"}
    L2 -- "hit" --> OUT2(["trả 301 + warm L1"])
    L2 -- "miss" --> DB[("PostgreSQL
read replica")]
    DB --> OUT3(["trả 301 + warm L1 + L2"])

Hình 3: Tầng cache — CDN → L1 in-process → Bloom Filter → L2 Redis → DB replica

7.1. CDN layer: cache 301 ở biên

CDN (Cloudflare, Fastly, CloudFront) có thể cache cả HTTP 301/302 response nếu service gửi đúng header Cache-Control: public, max-age=3600. Điều này đặc biệt mạnh cho các short-code viral — một link được share trên Twitter có thể có 99.9% request được CDN xử lý, server gốc không hề biết tới. Lưu ý: nếu short-code có thể bị xóa, cần bind với stale-while-revalidate hoặc dùng TTL ngắn (60–300s) để không serve stale sau khi user disable link.

7.2. L1 in-process: LRU 10.000 entry

Mỗi instance service giữ một LRU cache 10.000 entry (≈1MB memory). Cache này xử lý các short-code "hyper-hot" trong vài phút gần nhất và tiết kiệm round-trip Redis. Microsoft.Extensions.Caching.Memory với SizeLimit=10_000 và CompactionPercentage=0.2 là đủ.

7.3. Bloom Filter: cắt request "vô danh"

Bloom Filter là một cấu trúc probabilistic: có thể nói chắc "không tồn tại" nhưng chỉ nói được "có thể tồn tại". Đặc tính false-negative = 0 này là điều kiện đủ để dùng làm gate trước cache: nếu Bloom nói "không", ta trả 404 ngay, không đánh Redis/DB. Với 100M short-code và tỉ lệ false-positive 1%, Bloom Filter cần ~120MB memory — nhỏ so với lợi ích.

# Redis BF create (sau khi enable module RedisBloom)
BF.RESERVE url:bf 0.01 100000000

# add khi insert
BF.ADD url:bf abc12

# check khi redirect
BF.EXISTS url:bf xyz99

Khi counter đã sinh >50% capacity ban đầu, rebuild Bloom lớn hơn (scalable Bloom Filter có sẵn trong RedisBloom qua BF.RESERVE ... EXPANSION 2). Một scheduled job mỗi ngày ghi toàn bộ short-code vào file rồi rebuild từ scratch là biện pháp dự phòng chống drift nếu insert bỏ sót.

7.4. L2 Redis: cache tập nóng

Redis là cache chính. Key pattern url:c:{short} → value là URL gốc. TTL 7 ngày — short-code không đổi nên không có vấn đề invalidation ngoại trừ khi user xóa link. Khi xóa, service vừa DEL url:c:{short} vừa push một sự kiện invalidate cho CDN qua Cloudflare API.

Với 99% read cache hit, một instance Redis 16GB nén string đủ chứa 200M key. Nếu vượt qua, dùng Redis Cluster hoặc phân mảnh theo hash short-code đầu. Một mẹo tối ưu bandwidth Redis nữa: dùng MGET batch khi một page redirect nhiều URL cùng lúc (ví dụ API bulk lookup cho partner).

7.5. Read replica PostgreSQL

DB miss là case hiếm sau khi đi qua Bloom + cache. Nhưng khi miss thật sự, nên đánh vào read replica thay vì primary — primary đang bận xử lý write. PostgreSQL 18 streaming replication có lag rất thấp (<100ms), chấp nhận được cho use case này; nếu user vừa tạo và redirect ngay trong replicated-lag window, client có thể thấy 404 tạm thời, lần refresh sau sẽ thấy. Có thể vá bằng cách cho request "very recent" đi thẳng primary nếu tạo-trong-5-giây.

8. Hotspot problem: một link viral cũng không được sập

Một tweet viral có thể đẩy một short-code lên 50.000 click/s trong vài phút. Nếu kiến trúc không chuẩn bị cho kịch bản này, key Redis đó trở thành single hot key — mọi request hashing tới cùng một shard, saturate bandwidth một node. Ba lớp phòng thủ:

1. CDN edge. Đã nói ở trên — 99% hotspot xử lý xong ở edge, không chạm tới kiến trúc backend.
2. L1 in-process. Chặn hậu bão. Sau khi CDN miss vì TTL hết, request đầu tiên tới mỗi instance load Redis rồi L1 giữ 60s; các request tiếp theo không chạm Redis nữa.
3. Redis client-side caching. Redis 7+ hỗ trợ tracking — client subscribe để nhận thông báo invalidate, tự giữ cache cục bộ. Tốt hơn LRU thuần vì tự động đồng bộ khi DEL.

9. Analytics path: đếm click mà không sập redirect

Yêu cầu analytics rất khác yêu cầu redirect. Redirect cần tốc độ và tất cả-hoặc-không-có (trả 301 hay 404). Analytics cần hoàn cảnh: geo, user-agent, referrer, thời điểm — và có thể chấp nhận mất 0.1% event. Do vậy, analytics phải tách sang một pipeline riêng ngay từ redirect service.

flowchart LR
    RS["Redirect Service"] -- "fire and forget
enrichment" --> RINGBUF["Ring buffer
in-process"]
    RINGBUF -- "batch 100
hoặc 200ms" --> KP["Kafka Producer"]
    KP --> KAFKA[("topic click-events")]
    KAFKA --> CON["Analytics Consumer"]
    CON --> ENRICH["Enrich
IP to Geo"]
    ENRICH --> CH[("ClickHouse
events_daily")]
    CH --> DASH(["Grafana / Superset
dashboard"])

Hình 4: Click event ra ring buffer in-process, batch-flush vào Kafka, analytics đi đường riêng

Chi tiết kỹ thuật quan trọng:

• Ring buffer in-process. Redirect service KHÔNG gọi Kafka synchronous. Nó push event vào một ring buffer bounded (ví dụ Channel<T> .NET với BoundedChannelOptions) rồi trả response ngay. Một background task đọc buffer, batch 100 event hoặc 200ms, gửi Kafka. Nếu buffer full (Kafka chậm), drop oldest để redirect không bao giờ chậm theo analytics.
• Trả 301 trước, ghi sau. Thứ tự là: ghi event vào buffer → trả 301 → worker flush buffer. Client nhận redirect trong 5ms, trong khi event đi qua Kafka rồi ClickHouse mất vài giây.
• ClickHouse làm OLAP, không phải OLTP. ClickHouse được chọn riêng cho phần analytics (column-store, compress cao, aggregate nhanh). PostgreSQL vẫn là source of truth cho URL metadata; ClickHouse chỉ giữ event để query "top URLs today", "clicks per hour" — thứ PostgreSQL sẽ khóc khi phải quét billion row.

// enqueue phi chặn trong Redirect handler
app.MapGet("/{code}", async (string code, UrlCache cache, EventQueue eq,
                             HttpContext ctx) =>
{
    var target = await cache.TryGetAsync(code);
    if (target is null) return Results.NotFound();
    eq.TryEnqueue(new ClickEvent(
        code, DateTimeOffset.UtcNow,
        ctx.Connection.RemoteIpAddress?.ToString(),
        ctx.Request.Headers.UserAgent.ToString(),
        ctx.Request.Headers.Referer.ToString()
    ));
    ctx.Response.Headers.CacheControl = "public, max-age=3600";
    return Results.Redirect(target, permanent: true);
});

10. Chống abuse: spam, malware và enumeration

URL shortener công khai là mồi ngon cho kẻ xấu. Ba rủi ro chính phải xử lý từ đầu, không để thành nợ kỹ thuật:

Với malware scan, thiết kế bất đồng bộ là tối ưu: khi insert, short-code được bật ngay nhưng có cờ scan_status=pending. Một worker background pull URL qua Safe Browsing; nếu malicious, cập nhật flag blocked=true và đẩy DEL cache + CDN purge. Trade-off: trong vài phút đầu, link có thể serve cho user trước khi bị chặn. Để an toàn hơn, với user anonymous có thể block đến khi scan xong (chậm ~500ms nhưng an toàn), user có API key tin cậy thì bật ngay.

11. Blueprint implement với .NET 10 Minimal API

Kiến trúc code theo clean layering, gói nhỏ:

UrlShortener/
  Program.cs           minimal API endpoints + DI
  Domain/
    ShortUrl.cs        entity
    IShortUrlStore.cs  port
  Infra/
    PgShortUrlStore.cs Npgsql 8.x
    RedisCache.cs      StackExchange.Redis 3.x
    BloomFilter.cs     wrap RedisBloom BF.* commands
    KafkaEventQueue.cs Channel to Kafka bridge
  Application/
    ShortenCommand.cs  validate + id + insert
    RedirectQuery.cs   multi-tier cache lookup

// Program.cs minimal API
var builder = WebApplication.CreateBuilder(args);
builder.Services.AddSingleton<UrlCache>();
builder.Services.AddSingleton<BloomFilter>();
builder.Services.AddSingleton<EventQueue>();
builder.Services.AddNpgsqlDataSource(builder.Configuration.GetConnectionString("Pg"));
builder.Services.AddStackExchangeRedisCache(o => o.Configuration = "redis:6379");
builder.Services.AddHostedService<ClickEventFlusher>();

var app = builder.Build();

app.MapPost("/shorten", async (
    ShortenRequest req, IShortenHandler h, CancellationToken ct) =>
        await h.HandleAsync(req, ct));

app.MapGet("/{code:length(4,12)}", async (
    string code, IRedirectHandler h, HttpContext ctx) =>
        await h.HandleAsync(code, ctx));

app.Run();

Vài lưu ý thực chiến:

• Pooling Npgsql. Mặc định min=0 max=100. Với workload miss-rate 1%, pool 30–50 là đủ. Quan trọng hơn: bật Multiplexing=true (Npgsql 8+) để tái sử dụng một physical connection cho nhiều request.
• HTTP/2 cho redirect. Bật Kestrel HTTP/2 + keep-alive, cache response bytes tĩnh để giảm CPU serialization.
• Graceful shutdown. ClickEventFlusher phải flush buffer còn sót trước khi stop. Dùng IHostApplicationLifetime.ApplicationStopping token.
• Native AOT. Redirect service là ứng viên vàng cho Native AOT — ít dependency, hot path nhỏ; compile AOT cắt startup xuống <50ms và memory footprint xuống 30MB mỗi instance.

12. Schema PostgreSQL và index

CREATE TABLE short_urls (
    id              bigint PRIMARY KEY,
    short_code      varchar(12) NOT NULL UNIQUE,
    target_url      text NOT NULL,
    created_at      timestamptz NOT NULL DEFAULT now(),
    created_by      bigint,
    expires_at      timestamptz,
    is_blocked      boolean NOT NULL DEFAULT false,
    scan_status     smallint NOT NULL DEFAULT 0,
    click_count     bigint NOT NULL DEFAULT 0
);
CREATE INDEX idx_short_urls_created_by ON short_urls(created_by) WHERE created_by IS NOT NULL;
CREATE INDEX idx_short_urls_expires_at ON short_urls(expires_at) WHERE expires_at IS NOT NULL;

Ba quyết định quan trọng:

• short_code UNIQUE. Đây là key truy vấn chính. UNIQUE tạo btree; lookup O(log n) nhanh đủ, không cần hash index (PostgreSQL hash index vẫn không replicate chuẩn trước 16).
• click_count trong bảng chính chỉ là denormalized. Đếm chính xác nằm ở ClickHouse. Counter PostgreSQL cập nhật batch mỗi phút từ aggregation job, chấp nhận lệch vài giây cho UI hiển thị.
• Partial index. Đa số record không có expires_at hay created_by — partial index chỉ đánh dấu subset nhỏ, tiết kiệm disk.

13. Topology triển khai cho 30k QPS

flowchart TB
    subgraph EDGE["Edge"]
        CF["Cloudflare CDN
99% cache hit"]
    end
    subgraph RGN_A["Region ap-southeast-1"]
        LB_A["L7 LB"]
        RS_A1["Redirect Svc x8"]
        RS_A2["Shorten Svc x2"]
        RD_A[("Redis Cluster
3 shards")]
        PG_A_P[("PG primary")]
        PG_A_R[("PG replica x2")]
    end
    subgraph RGN_B["Region us-east-1"]
        LB_B["L7 LB"]
        RS_B1["Redirect Svc x6"]
        RD_B[("Redis")]
        PG_B_R[("PG replica x2")]
    end
    CF --> LB_A
    CF --> LB_B
    LB_A --> RS_A1
    LB_A --> RS_A2
    RS_A1 --> RD_A
    RS_A2 --> RD_A
    RS_A1 --> PG_A_R
    RS_A2 --> PG_A_P
    PG_A_P -. "logical replication" .-> PG_B_R
    LB_B --> RS_B1
    RS_B1 --> RD_B
    RS_B1 --> PG_B_R

Hình 5: Topology 2-region, read-only replica ở region thứ hai, write pin về primary

Ghi chú triển khai:

• Write pin region. Mọi shorten request đi về region chứa primary (ap-southeast-1). Redirect phân tán đều theo GeoDNS. Trade-off đơn giản, không cần multi-master.
• Sizing ước lượng. 14 redirect service instance (8+6), mỗi 2 vCPU/2GB, tổng ~28 vCPU. Redis 1 cluster 3 shard (3× 16GB). PostgreSQL 1 primary + 4 replica (8 vCPU/32GB mỗi). Chi phí cloud ~2.500–3.500 USD/tháng với on-demand, hoặc 1.500–2.000 USD với reserved 1 year.
• Auto-scaling. Scale redirect service theo CPU hoặc incoming RPS. Không scale PostgreSQL theo RPS vì đa số request không chạm DB; chỉ scale replica khi p95 replica lag vượt ngưỡng.

14. Failure mode và runbook

15. Tối ưu chi phí khi scale

Khi dịch vụ chạm 10B click/tháng, chi phí có thể phình nhanh nếu không tỉnh. Ba đòn bẩy tiết kiệm hiệu quả nhất:

16. Kết luận

URL shortener nhìn giản đơn nhưng tập trung đầy đủ các chủ đề quan trọng của system design: sinh ID phân tán, encoding, cache đa tầng, Bloom Filter, tách write/read, analytics pipeline, chống abuse, và tối ưu chi phí. Một blueprint đúng cho bài này dạy nhiều hơn mười bài lý thuyết về "scalability" chung chung, vì mọi quyết định đều có con số thực (30ms p99, 99% cache-hit, 3.52×10¹² không gian code).

Bài học rút ra áp dụng được cho rất nhiều hệ tương tự — từ feature flag service, short link analytics, tracking pixel, QR code service, đến deep-link cho mobile. Nếu bạn ship một dịch vụ mới và thấy nó "giống giống shortener" (lookup theo key ngắn, read-heavy, cần cache dày, analytics phi đồng bộ), blueprint ở đây gần như plug-and-play.

17. Nguồn tham khảo

• ASP.NET Core Minimal APIs - Microsoft Docs
• RedisBloom - Bloom Filter Documentation
• PostgreSQL 18 Documentation
• ClickHouse MergeTree Engine
• Twitter Snowflake - Distributed ID Generation
• Cloudflare Cache Rules và Cache-Control
• .NET Native AOT Deployment - Microsoft
• Google Safe Browsing API v4