Thiết kế dịch vụ rút gọn link (URL shortener) chịu tải lớn

1. Tổng quan

Rút gọn link là bài toán thiết kế hệ thống quen thuộc. Logic chỉ gồm việc map một mã ngắn sang một URL dài. Phần khó nằm ở quy mô: hàng chục nghìn lượt redirect mỗi giây, link “viral” bất chợt, và yêu cầu không bao giờ sinh trùng mã.

Bài này đi qua toàn bộ quy trình: chốt yêu cầu, ước lượng tải, mô hình dữ liệu, API, cách sinh mã, cache và các điểm khó. Đọc xong, bạn có một khung thiết kế kèm code Spring Boot 3 để tự dựng hoặc mang đi phỏng vấn.

2. Yêu cầu bài toán

2.1. Yêu cầu chức năng

• Tạo link ngắn từ URL dài. Người dùng có thể tự đặt alias, ví dụ /sale-2026.
• Truy cập link ngắn thì được redirect sang URL gốc.
• Link có thể có hạn dùng (expires_at) và có thể bị chủ sở hữu vô hiệu hoá.
• Thống kê lượt click theo link. Số liệu chấp nhận trễ vài giây.

2.2. Quy mô

Giả định 100 triệu link mới mỗi tháng và tỉ lệ đọc/ghi là 100:1.

Ghi:   100M / (30 * 86400s)  ≈ 40 link/s   (đỉnh ×10 ≈ 400/s)
Đọc:   40 × 100              ≈ 4.000 rps  (đỉnh ×10 ≈ 40.000 rps)
Lưu trữ 5 năm: 6 tỉ link × ~500 byte ≈ 3 TB
Không gian mã 7 ký tự base62: 62^7 ≈ 3,5 nghìn tỉ  (dư sức cho 6 tỉ)

Từ các con số này rút ra hai kết luận. Thứ nhất, hệ thống thiên về đọc, nên cache là trung tâm của thiết kế. Thứ hai, tải ghi thấp, nên một PostgreSQL primary là đủ, chưa cần sharding ngay.

2.3. Ràng buộc

• Redirect có p99 < 20 ms.
• Mã ngắn không trùng và không đoán được theo thứ tự, để người khác không dò được link riêng tư.
• Hệ thống tiếp tục redirect được khi analytics hoặc Kafka gặp sự cố.

3. Mô hình dữ liệu và API

Dependency cần dùng (version do Spring Boot quản lý):

<dependencies>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-web</artifactId>
    </dependency>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-jdbc</artifactId>
    </dependency>
    <dependency>
        <groupId>org.postgresql</groupId>
        <artifactId>postgresql</artifactId>
        <scope>runtime</scope>
    </dependency>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-data-redis</artifactId>
    </dependency>
    <dependency>
        <groupId>org.springframework.kafka</groupId>
        <artifactId>spring-kafka</artifactId>
    </dependency>
    <dependency>
        <groupId>com.github.ben-manes.caffeine</groupId>
        <artifactId>caffeine</artifactId>
    </dependency>
</dependencies>

Schema PostgreSQL:

CREATE TABLE links (
    code        VARCHAR(16) PRIMARY KEY,
    long_url    TEXT        NOT NULL,
    owner_id    BIGINT,
    created_at  TIMESTAMPTZ NOT NULL DEFAULT now(),
    expires_at  TIMESTAMPTZ,
    disabled    BOOLEAN     NOT NULL DEFAULT false
);
CREATE INDEX idx_links_owner ON links (owner_id, created_at DESC);

CREATE SEQUENCE link_id_seq START 1 INCREMENT BY 1000;

Giải thích các quyết định chính:

• code là khoá chính. Truy vấn nóng nhất là WHERE code = ?, nên nó đi thẳng vào index của primary key.
• idx_links_owner phục vụ màn hình “link của tôi”.
• link_id_seq tăng mỗi lần 1000 đơn vị. Mỗi lần gọi nextval, ứng dụng nhận về cả một khối ID (mục 4.2).

Hai API chính:

POST /api/links          {"url": "https://shop.vn/...", "alias": null}
  -> 201 {"code": "0bX3kQz", "shortUrl": "https://nonla.ly/0bX3kQz"}
  -> 409 nếu alias đã tồn tại

GET  /{code}
  -> 302 Location: https://shop.vn/...
  -> 404 nếu không tồn tại / hết hạn / bị vô hiệu hoá

Lưu ý: Nên dùng 302, không dùng 301. Trình duyệt cache 301 vĩnh viễn. Khi đó bạn mất số liệu click và không thể vô hiệu hoá link đã lan truyền.

4. Sinh mã ngắn

4.1. Chọn chiến lược

Cách	Ưu	Nhược
Hash URL (MD5 rồi cắt 7 ký tự)	Không cần trạng thái	Có thể trùng, phải kiểm tra và thử lại
Random 7 ký tự	Đơn giản	Càng nhiều link càng dễ trùng, mỗi lần tạo phải kiểm tra DB
Bộ đếm + base62	Không bao giờ trùng	Lộ thứ tự, cần một nguồn ID tập trung

Bài này chọn cách thứ ba và khắc phục hai nhược điểm của nó. Để không lộ thứ tự, ta xáo trộn ID bằng một song ánh (bijection). Để giảm phụ thuộc vào nguồn ID tập trung, ta cấp ID theo khối.

import java.math.BigInteger;

public final class ShortCode {
    private static final String ALPHABET =
            "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    private static final int LENGTH = 7;
    private static final BigInteger SPACE = BigInteger.valueOf(62).pow(LENGTH);
    // Số lẻ, không chia hết cho 31 => nguyên tố cùng nhau với 62^7
    private static final BigInteger MULTIPLIER = BigInteger.valueOf(1_580_030_173L);

    private ShortCode() {}

    public static String of(long id) {
        if (id < 0 || id >= SPACE.longValue()) {
            throw new IllegalArgumentException("id ngoài không gian mã: " + id);
        }
        long mixed = BigInteger.valueOf(id).multiply(MULTIPLIER).mod(SPACE).longValue();
        char[] out = new char[LENGTH];
        for (int i = LENGTH - 1; i >= 0; i--) {
            out[i] = ALPHABET.charAt((int) (mixed % 62));
            mixed /= 62;
        }
        return new String(out);
    }
}

Cách hoạt động:

• Phép nhân modulo id × MULTIPLIER mod 62^7 là một song ánh, vì MULTIPLIER nguyên tố cùng nhau với 62^7. Mỗi ID cho ra đúng một mã, và hai ID khác nhau không bao giờ cho cùng một mã.
• Vòng lặp đổi số sang base62 và đệm số 0 bên trái, nên mã luôn dài đúng 7 ký tự.
• ID 1 và ID 2 cho ra hai mã khác nhau ngay từ ký tự thứ hai, nên người ngoài khó đoán link kế tiếp.
• BigInteger tránh tràn long khi nhân. Ở tải 400 ghi/s, chi phí này không đáng kể.

Cách này chỉ làm mã khó đoán, không phải mã hoá. Ai biết MULTIPLIER vẫn đảo ngược được. Link thật sự riêng tư cần thêm cơ chế xác thực.

4.2. Cấp ID theo khối

Gọi DB cho từng ID thì primary thành nút cổ chai. Thay vào đó, mỗi instance lấy một khối 1000 ID rồi tự phát dần trong bộ nhớ:

import java.util.concurrent.locks.ReentrantLock;
import org.springframework.jdbc.core.JdbcTemplate;
import org.springframework.stereotype.Component;

@Component
public class IdBlockAllocator {
    private static final int BLOCK_SIZE = 1000; // phải khớp INCREMENT BY
    private final JdbcTemplate jdbc;
    private final ReentrantLock lock = new ReentrantLock();
    private long next;
    private long end;

    public IdBlockAllocator(JdbcTemplate jdbc) {
        this.jdbc = jdbc;
    }

    public long nextId() {
        lock.lock();
        try {
            if (next >= end) {
                Long start = jdbc.queryForObject("SELECT nextval('link_id_seq')", Long.class);
                next = start;
                end = start + BLOCK_SIZE;
            }
            return next++;
        } finally {
            lock.unlock();
        }
    }
}

Điểm cần chú ý:

• nextval là thao tác atomic. Hai instance không bao giờ nhận cùng một khối, nên không cần khoá phân tán.
• Với 400 ghi/s, mỗi instance chỉ chạm DB vài giây một lần.
• Code dùng ReentrantLock thay vì synchronized. Trên Java 21, virtual thread bị “pin” vào carrier thread khi chờ I/O bên trong khối synchronized.
• Instance restart sẽ bỏ phí phần còn lại của khối. Không gian mã có 3,5 nghìn tỉ giá trị, nên việc này chấp nhận được.

5. Luồng tạo link

import java.net.URI;
import java.time.Duration;
import org.springframework.dao.DuplicateKeyException;
import org.springframework.data.redis.core.StringRedisTemplate;
import org.springframework.jdbc.core.JdbcTemplate;
import org.springframework.stereotype.Service;

@Service
public class LinkWriteService {
    static final String KEY = "link:";
    private final JdbcTemplate jdbc;
    private final StringRedisTemplate redis;
    private final IdBlockAllocator allocator;

    public LinkWriteService(JdbcTemplate jdbc, StringRedisTemplate redis, IdBlockAllocator allocator) {
        this.jdbc = jdbc;
        this.redis = redis;
        this.allocator = allocator;
    }

    public String create(String longUrl, String alias, Long ownerId) {
        String scheme = URI.create(longUrl).getScheme();
        if (!"http".equals(scheme) && !"https".equals(scheme)) {
            throw new IllegalArgumentException("Chỉ chấp nhận http/https");
        }
        String code = (alias != null) ? alias : ShortCode.of(allocator.nextId());
        try {
            jdbc.update("INSERT INTO links(code, long_url, owner_id) VALUES (?, ?, ?)",
                    code, longUrl, ownerId);
        } catch (DuplicateKeyException e) {
            throw new AliasTakenException(code);
        }
        redis.opsForValue().set(KEY + code, longUrl, Duration.ofHours(24));
        return code;
    }
}

class AliasTakenException extends RuntimeException {
    AliasTakenException(String code) { super("Alias đã tồn tại: " + code); }
}

Luồng xử lý gồm bốn bước:

1. Kiểm tra scheme để chặn javascript: hoặc file:. Nếu bỏ bước này, dịch vụ của bạn thành công cụ phát tán link độc hại.
2. Lấy mã: dùng alias tự đặt, hoặc sinh mã từ ID.
3. INSERT. Ràng buộc primary key là lớp bảo vệ cuối cùng chống trùng mã.
4. Ghi luôn vào Redis (write-through), để lần redirect đầu tiên không phải xuống DB.

Trong production, alias tự đặt nên dùng ký tự hoặc độ dài khác với mã sinh tự động, ví dụ bắt buộc có dấu - hoặc dài từ 8 ký tự. Nếu không, alias của người dùng có thể “chiếm” trước một mã mà bộ sinh sẽ tạo ra sau này. Khi đó bộ sinh gặp DuplicateKeyException, trong khi mục đích của nó là không bao giờ trùng.

6. Luồng redirect và cache nhiều tầng

Ở 40.000 rps lúc cao điểm, hầu hết request phải được trả về mà không chạm DB. Ta dùng ba tầng: Caffeine trong JVM, Redis dùng chung, rồi mới tới PostgreSQL.

import com.github.benmanes.caffeine.cache.Cache;
import com.github.benmanes.caffeine.cache.Caffeine;
import java.time.Duration;
import java.util.List;
import java.util.Optional;
import org.springframework.data.redis.core.StringRedisTemplate;
import org.springframework.jdbc.core.JdbcTemplate;
import org.springframework.stereotype.Service;

@Service
public class LinkReadService {
    private static final String NOT_FOUND = ""; // sentinel cho negative cache
    private final Cache<String, String> local = Caffeine.newBuilder()
            .maximumSize(100_000)
            .expireAfterWrite(Duration.ofSeconds(30))
            .build();
    private final JdbcTemplate jdbc;
    private final StringRedisTemplate redis;

    public LinkReadService(JdbcTemplate jdbc, StringRedisTemplate redis) {
        this.jdbc = jdbc;
        this.redis = redis;
    }

    public Optional<String> resolve(String code) {
        String url = local.get(code, this::loadFromRedisOrDb);
        return url.isEmpty() ? Optional.empty() : Optional.of(url);
    }

    private String loadFromRedisOrDb(String code) {
        String key = LinkWriteService.KEY + code;
        String cached = redis.opsForValue().get(key);
        if (cached != null) return cached;

        List<String> rows = jdbc.queryForList("""
                SELECT long_url FROM links
                WHERE code = ? AND NOT disabled
                  AND (expires_at IS NULL OR expires_at > now())""", String.class, code);
        String url = rows.isEmpty() ? NOT_FOUND : rows.getFirst();
        redis.opsForValue().set(key, url, url.isEmpty() ? Duration.ofMinutes(5) : Duration.ofHours(24));
        return url;
    }
}

Các điểm quan trọng:

• local.get(code, loader) của Caffeine gộp các lần load đồng thời cho cùng một key. Nếu 5.000 request cùng hỏi một mã chưa có trong cache, chỉ một thread xuống Redis/DB. Các thread còn lại chờ kết quả đó. Đây chính là cách chống cache stampede trong phạm vi một instance.
• Negative caching: mã không tồn tại cũng được cache dưới dạng chuỗi rỗng trong 5 phút. Nhờ vậy, bot dò mã ngẫu nhiên không đánh sập được DB.
• Caffeine không cache giá trị null, nên code dùng sentinel "" thay cho null.

Controller trả 302 và đẩy sự kiện click sang Kafka:

import java.net.URI;
import java.util.Map;
import org.springframework.http.HttpStatus;
import org.springframework.http.ResponseEntity;
import org.springframework.kafka.core.KafkaTemplate;
import org.springframework.web.bind.annotation.*;

@RestController
public class LinkController {
    private final LinkWriteService writer;
    private final LinkReadService reader;
    private final KafkaTemplate<String, String> kafka;

    public LinkController(LinkWriteService writer, LinkReadService reader,
                          KafkaTemplate<String, String> kafka) {
        this.writer = writer;
        this.reader = reader;
        this.kafka = kafka;
    }

    public record CreateLinkRequest(String url, String alias) {}

    @PostMapping("/api/links")
    public ResponseEntity<Map<String, String>> create(@RequestBody CreateLinkRequest req) {
        String code = writer.create(req.url(), req.alias(), null);
        return ResponseEntity.status(HttpStatus.CREATED)
                .body(Map.of("code", code, "shortUrl", "https://nonla.ly/" + code));
    }

    @GetMapping("/{code:[0-9a-zA-Z-]{1,16}}")
    public ResponseEntity<Void> redirect(@PathVariable String code) {
        return reader.resolve(code)
                .map(url -> {
                    kafka.send("link-clicks", code, String.valueOf(System.currentTimeMillis()));
                    return ResponseEntity.status(HttpStatus.FOUND).location(URI.create(url)).<Void>build();
                })
                .orElse(ResponseEntity.notFound().build());
    }

    @ExceptionHandler(AliasTakenException.class)
    ResponseEntity<String> conflict(AliasTakenException e) {
        return ResponseEntity.status(HttpStatus.CONFLICT).body(e.getMessage());
    }
}

kafka.send là bất đồng bộ, nên redirect không phải chờ broker. Một consumer riêng gom các sự kiện theo code mỗi vài giây rồi ghi batch vào bảng thống kê. Cấu hình producer ưu tiên độ trễ thấp:

spring.kafka.producer.acks=1
spring.kafka.producer.properties.linger.ms=20
spring.kafka.producer.properties.max.block.ms=50

max.block.ms=50 ngăn thread redirect bị treo lâu khi broker sập, đúng với ràng buộc “analytics lỗi thì redirect vẫn chạy”. Chấp nhận mất một ít sự kiện click trong trường hợp đó.

7. Các điểm khó và cách giải

7.1. Tranh chấp

• Hai người cùng đặt một alias: đừng SELECT rồi mới INSERT. Hai request có thể cùng thấy “chưa tồn tại” rồi cùng ghi. Hãy để ràng buộc unique của DB quyết định và bắt DuplicateKeyException như ở mục 5.
• Nhiều instance cùng sinh mã: sequence cấp khối riêng cho từng instance, nên không có tranh chấp.

7.2. Nhất quán

• Đọc ngay sau khi tạo: nếu đọc từ read replica, độ trễ replication có thể khiến link mới tạo trả 404. Ghi vào Redis ngay lúc tạo (write-through) đã che được khoảng trễ này.
• Vô hiệu hoá link: cập nhật DB rồi xoá key Redis. Caffeine vẫn giữ bản cũ tối đa 30 giây trên mỗi instance. Nếu cần chặn tức thì, ví dụ link lừa đảo, hãy publish sự kiện invalidate qua Redis Pub/Sub hoặc Kafka để các instance xoá cache cục bộ.
• Hết hạn: TTL của cache nên là min(24h, expires_at - now). Nếu không, link đã hết hạn vẫn redirect thêm tối đa 24 giờ.

7.3. Tải đột biến

• Hot key: một link viral dồn toàn bộ lưu lượng vào một shard Redis. Caffeine cục bộ hấp thụ phần lớn tải này. Mỗi instance chỉ hỏi Redis khoảng một lần mỗi 30 giây cho mỗi key.
• Cold start: instance mới chưa có gì trong Caffeine, nhưng tính năng gộp load ở mục 6 giữ cho Redis không bị dội request.
• Spam tạo link: giới hạn tốc độ theo API key hoặc IP, ví dụ dùng token bucket trên Redis, trước khi gọi LinkWriteService.

8. Kiểm thử hành vi sinh mã

Tính chất quan trọng nhất của hệ thống là mã không trùng, có độ dài cố định và không lộ thứ tự:

import static java.util.stream.Collectors.toSet;
import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

import java.util.Set;
import java.util.stream.LongStream;
import org.junit.jupiter.api.Test;

class ShortCodeTest {

    @Test
    void sinhMaDungDoDaiVaBangChuCai() {
        assertThat(ShortCode.of(1)).hasSize(7).matches("[0-9a-zA-Z]{7}");
    }

    @Test
    void khongTrungTrongMotTramNghinIdLienTiep() {
        Set<String> codes = LongStream.range(0, 100_000).mapToObj(ShortCode::of).collect(toSet());
        assertThat(codes).hasSize(100_000);
    }

    @Test
    void idLienTiepKhongChoMaLienTiep() {
        assertThat(ShortCode.of(1).substring(0, 5)).isNotEqualTo(ShortCode.of(2).substring(0, 5));
    }

    @Test
    void tuChoiIdNgoaiKhongGianMa() {
        assertThatThrownBy(() -> ShortCode.of(-1)).isInstanceOf(IllegalArgumentException.class);
    }
}

Test thứ hai kiểm tra trên một mẫu, không chứng minh được tính song ánh. Tính song ánh đến từ toán học (gcd bằng 1). Test chỉ bảo vệ bạn khỏi việc ai đó vô tình đổi MULTIPLIER thành số chẵn.

9. Lỗi hay gặp và khi nào không nên làm phức tạp

Lưu ý: Đổi MULTIPLIER hoặc ALPHABET sau khi đã phát hành sẽ khiến ID mới sinh ra mã trùng với mã cũ. Hãy coi chúng là hằng số vĩnh viễn.

• Ghi từng click thẳng vào bảng links (UPDATE ... SET clicks = clicks + 1) tạo row lock nóng đúng ở link viral. Hãy gom qua Kafka.
• Không giới hạn kích thước Caffeine dẫn tới OutOfMemoryError khi bị dò mã ngẫu nhiên với số lượng lớn.
• Với sản phẩm nội bộ chỉ vài trăm link mỗi ngày, một bảng PostgreSQL và một controller là đủ. Redis, Kafka và cấp ID theo khối chỉ đáng công khi tải thực sự đòi hỏi.

10. Kết luận

Thiết kế URL shortener chịu tải lớn xoay quanh ba quyết định. Sinh mã bằng bộ đếm cấp theo khối kết hợp song ánh, để mã không trùng mà vẫn khó đoán. Dùng cache nhiều tầng có negative caching và gộp load, để chịu được hot key và bot dò mã. Đẩy mọi việc không bắt buộc, như thống kê click, ra khỏi đường redirect qua Kafka.

Hãy bắt đầu từ ước lượng quy mô. Chính các con số ở mục 2 cho bạn biết khi nào cần thêm từng tầng, thay vì dựng đủ mọi thứ ngay từ ngày đầu.