Level 1: thiết kế URL Shortener

Được. Từ đây Bài 14 đổi thành chuỗi bài tập System Design theo level, mình tự giải luôn để bạn học theo mẫu. Mỗi bài đi theo:

Đề bài → requirements → bản đơn giản → bottleneck → scale dần
      → failure → full architecture → AWS/Azure mapping → interview

Cloud service chỉ được thêm khi có lý do. Không thuộc tên AWS/Azure trước rồi cố nhét vào architecture.

1. Đề bài và requirements

Design a URL shortening service like TinyURL.

Long URL   https://shop.com/products/iphone/123456
                 ↓
Short URL  https://short.ly/aB3x9

GET /aB3x9  →  302 Redirect  →  https://shop.com/products/iphone/123456

Functional:

1. Tạo short URL.
2. Redirect short URL → long URL.
3. short_code phải unique.
4. Đếm click cơ bản.

Scale giả định:

Create:       50 req/s
Redirect: 10,000 req/s

→ READ >>> WRITE: hệ thống read-heavy

Từ con số này lát nữa mới có lý do thêm Redis.

2. API

POST /urls
{ "url": "https://shop.com/products/iphone/123456" }
→ 201 { "shortUrl": "https://short.ly/aB3x9" }

GET /aB3x9
→ 302 Location: https://shop.com/products/iphone/123456

Dùng 302 (không cache vĩnh viễn ở browser) nếu muốn mọi click đều đi qua server để đếm. 301 giảm tải hơn nhưng mất analytics.

3. Data model

CREATE TABLE url_mapping (
    id          BIGINT PRIMARY KEY,
    short_code  VARCHAR(10) NOT NULL,
    long_url    TEXT        NOT NULL,
    created_at  TIMESTAMP   NOT NULL,
    expires_at  TIMESTAMP,
    CONSTRAINT uk_short_code UNIQUE (short_code)
);

-- lookup chính
SELECT long_url FROM url_mapping WHERE short_code = ?;

UNIQUE(short_code) vừa chặn trùng vừa tạo index cho lookup chính.

4. Architecture V1: chưa cần Redis, Kafka

Client → URL Service (Spring Boot) → Database

Create:   POST /urls → generate code → INSERT DB
Redirect: GET /aB3x9 → SELECT DB → 302

Traffic nhỏ thì xong. Giờ đi qua từng vấn đề.

5. Problem 1: tạo short code unique thế nào?

Cách dễ hiểu: lấy numeric ID unique (DB sequence) rồi encode Base62 (0-9 a-z A-Z = 62 ký tự).

id = 125839  →  Base62  →  "wJ9"  (ngắn hơn decimal)

ID unique  →  Base62(ID) unique  →  không cần random rồi check collision

public final class Base62 {
    private static final String ALPHABET =
        "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

    public static String encode(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();
    }
}

@Service
@RequiredArgsConstructor
public class UrlService {
    private final UrlRepository repo;
    private final IdGenerator idGenerator;   // DB sequence / range allocator

    @Transactional
    public String create(String longUrl) {
        long id = idGenerator.nextId();
        String code = Base62.encode(id);
        repo.save(new UrlMapping(id, code, longUrl, Instant.now()));
        return code;
    }
}

Base62 cần 6 ký tự cho 62⁶ ≈ 56 tỷ mã, 7 ký tự ≈ 3.5 nghìn tỷ.

Khi scale: một DB sequence thì dễ. Nhiều DB/shard mà mỗi cái tự tăng thì DB1 → 100, DB2 → 100 → collision. Các hướng:

Base62 của ID tuần tự thì đoán được mã kế tiếp. Nếu cần khó đoán, xáo ID (ví dụ nhân với số lẻ lớn mod 62⁷) hoặc dùng random + UNIQUE.

6. Problem 2: redirect quá nhiều, DB chịu không nổi

10,000 req/s đều đổ vào DB. Mapping short_code → long_url đọc rất nhiều, gần như không đổi: hợp để cache. Redis xuất hiện vì lý do đó, không phải vì "System Design thì phải có Redis".

GET /aB3x9
     ↓
   Redis
   /   \
 HIT    MISS
  ↓      ↓
 URL     DB → set Redis (TTL) → URL
  ↓
 302

public String resolve(String code) {
    String cached = redis.opsForValue().get("url:" + code);
    if (cached != null) return cached;

    String longUrl = repo.findLongUrl(code)
        .orElseThrow(() -> new ResponseStatusException(HttpStatus.NOT_FOUND));
    redis.opsForValue().set("url:" + code, longUrl, Duration.ofHours(24));
    return longUrl;
}

Cache hit 95%: Redis ~9,500 req/s, DB chỉ ~500 req/s. Chi tiết cache-aside xem Bài 7.2.

App cũng scale ngang: URL Service stateless, nhiều instance sau Load Balancer.

7. Problem 3: click count làm redirect chậm

Ngây thơ:
GET /aB3x9 → Redis 2ms → UPDATE clicks = clicks + 1 (20ms) → 302
10,000 redirect/s = 10,000 write/s, user chờ analytics vô ích

Click count không nằm trên critical path. Tách ra:

GET /aB3x9
     │
     ├──────────────→ 302 ngay cho user
     │
     └── URL_CLICKED{shortCode, timestamp} → Queue/Stream → Analytics consumer
                                                            (gộp batch, cộng dồn)

Nguyên tắc: việc không cần cho response hiện tại → cân nhắc async. Analytics chết thì redirect vẫn phải chạy (graceful degradation).

8. Problem 4: spam tạo URL

Attacker gọi POST /urls liên tục. Đặt rate limit ở API Gateway, ví dụ 100 create/phút/IP, vượt thì 429 Too Many Requests (xem Bài 15.4).

9. Problem 5: dataset quá lớn

Read đã có cache, DB read vẫn cao thì thêm read replica. Hàng tỷ URL thì shard:

hash(short_code) % N
        ↓
   ┌────┼────┐
Shard0 Shard1 Shard2

GET /aB3x9 → hash → biết ngay Shard1 → lookup local index

Đây là shard key đẹp: lookup key trùng shard key. So với Order "shard by user_id nhưng query by order_id" thì đơn giản hơn nhiều. Dùng consistent hashing để thêm shard ít phải di chuyển dữ liệu.

10. Failure: Redis chết

Redis 💀 → fallback DB → DB traffic tăng 20 lần → DB overload → cả hệ thống chết
                                                  (cascading failure)

Phòng: Redis có replica/Sentinel, DB pool có giới hạn, circuit breaker, monitor cache hit ratio. Metrics nên theo dõi: redirect req/s, p95/p99 latency, error rate, cache hit ratio, DB connections, queue lag.

11. Full architecture

                        Client
                          │
                     API Gateway (rate limit)
                          │
                    Load Balancer
               ┌──────────┼──────────┐
            URL S1     URL S2     URL S3   (stateless)
               └──────────┼──────────┘
                    Redis (cache)
                          │
                 Database (shard by hash(short_code))

URL Service → Queue/Stream → Analytics consumer → Analytics storage

12. Map sang AWS / Azure

Bản serverless rất hợp bài này vì access pattern gần như key → value:

AWS:   API Gateway → Lambda → DynamoDB
Azure: API Management → Azure Functions → Cosmos DB

Concept không đổi, chỉ tên product đổi.

13. Trade-off

Đúng là đọc tóm tắt thì giống học thuộc một sơ đồ. Bài này thật ra dạy quá trình sơ đồ đó hình thành: mỗi component xuất hiện vì một problem cụ thể.

Requirement
│
├─ Long URL → short URL
│   Problem: short code không được trùng
│   → Unique ID + Base62
│
├─ Redirect cực nhiều
│   Problem: DB read quá tải
│   → Cache → Redis
│
├─ Cần đếm click
│   Problem: analytics làm redirect chậm
│   → Async processing → Kafka/RabbitMQ
│
└─ Data quá lớn
    Problem: một DB không chứa nổi
    → Sharding theo hash(short_code)

Problem → Solution → Technology. Đừng học thuộc architecture, hãy nhớ chuỗi problem này. Bắt đầu luôn từ bản đơn giản nhất (Spring Boot + 1 DB) rồi mới thêm.

Không nên. Redis ở đây là cache, không phải source of truth.

• Redis giữ dữ liệu trong RAM: hàng tỷ URL rất tốn tiền.
• Persistence RDB/AOF vẫn có thể mất vài giây dữ liệu khi crash (xem Bài 7.3). Mất mapping = link của khách hỏng vĩnh viễn.
• Failover replica bất đồng bộ cũng có thể mất write cuối.

Nếu muốn một store key-value bền vững, chọn DB key-value thật như DynamoDB/Cosmos DB, rồi vẫn có thể đặt cache phía trước. Quy tắc: cache mất được, source of truth thì không.

Q1. Give me your high-level design.

🇻🇳 Tiếng Việt:

Hệ thống read-heavy vì redirect nhiều hơn tạo URL rất nhiều. Em bắt đầu với các URL service stateless sau load balancer, DB lưu mapping short code unique → URL gốc. Vì redirect nhiều và mapping hầu như không đổi, em thêm Redis cache-aside để giảm đọc DB. Click analytics không nằm trên đường redirect nên em publish event bất đồng bộ.

🇬🇧 English:

The system is read-heavy because redirects happen much more often than URL creation. I would start with stateless URL service instances behind a load balancer and a database that stores the mapping from a unique short code to the original URL. Since the mapping is read frequently but rarely changes, I would add Redis with cache-aside to reduce database reads. Click analytics is not on the critical redirect path, so I would publish click events asynchronously.

Q2. How do you generate unique short codes across many servers?

🇻🇳 Tiếng Việt:

Em tạo ID unique toàn cục rồi encode Base62. Một DB sequence là đủ lúc đầu; khi scale em cấp phát dải ID cho từng instance hoặc dùng ID kiểu Snowflake. Cột short_code vẫn có UNIQUE constraint làm chốt chặn cuối.

🇬🇧 English:

I generate a globally unique numeric ID and encode it in Base62. A database sequence is enough at first; at larger scale I would allocate ID ranges per instance or use Snowflake-style IDs. The short_code column still has a UNIQUE constraint as the final safety net.

Q3. The data no longer fits in one database. What now?

🇻🇳 Tiếng Việt:

Em shard theo hash của short code, vì đó chính là lookup key chính, nên mỗi redirect chỉ chạm đúng một shard. Dùng consistent hashing để thêm shard ít phải chuyển dữ liệu.

🇬🇧 English:

I would shard by a hash of the short code, because it is the primary lookup key, so each redirect touches exactly one shard. Consistent hashing keeps data movement small when adding shards.

Cách nhớ ngắn gọn

• Read-heavy → cache-aside Redis, app stateless + LB.
• Unique code = unique ID + Base62, UNIQUE constraint chặn cuối.
• Click count = async event, analytics chết không kéo redirect chết.
• Shard key = lookup key = short_code.