Phỏng vấn 5: cache, rate limiter và search

Giới thiệu

Bạn luyện thiết kế hệ thống mini. Luôn hỏi tải trước khi vẽ.

Kiến thức cần nhớ

Khung trình bày 5 bước

• Bước 1: hỏi rõ tải và độ trễ cam kết.
• Bước 2: ước lượng bộ nhớ và băng thông.
• Bước 3: vẽ thành phần và luồng request.
• Ví dụ đời thường: giống hỏi số khách trước khi vẽ quán.
• Bước 4 và 5: đào sâu điểm khó rồi chốt đánh đổi.

Cache và rate limiter

• Cache LRU LFU giảm tải cho backend.
• Rate limiter chặn khi gọi quá nhanh.
• Ví dụ đời thường: limiter như bảo vệ đếm khách vào.
• Token bucket cho bùng nổ ngắn hạn có giới hạn.

Search mini

• Trie gợi ý tiền tố, Bloom lọc nhanh.
• Xếp hạng đơn giản bằng độ mới và khớp từ.
• Ví dụ đời thường: giống mục lục cộng danh sách đen.
• Mọi con số ước lượng phải ghi giả định.

# thùng token đơn giản
class ThungToken:  # giới hạn tốc độ gọi
    def __init__(self, suc):
        self.token = suc  # số lượt còn lại
    def goi(self):
        if self.token > 0:  # còn lượt
            self.token -= 1  # trừ một lượt
            return True  # cho qua
        return False  # chặn lại

Ví dụ

• Tải và tỉ lệ trúng cho trước -> tính tải còn lại cho backend.
• 100 request dồn một giây -> limiter cho qua đúng cam kết.

💻 Bài tập

Luyện phỏng vấn thiết kế hệ thống, mỗi đề 45 phút, viết ra giấy hoặc Markdown có sơ đồ. Nộp vào day-165/.

Mỗi đề đi đủ 5 bước: (1) hỏi rõ yêu cầu và tải, (2) ước lượng số liệu, (3) sơ đồ thành phần và luồng request, (4) đào sâu 2 điểm khó, (5) đánh đổi và cách mở rộng.

Bài 1: Thiết kế rate limiter cho API gateway

• 10^6 user, mỗi user 100 request/phút, 50 máy gateway.
• Ước lượng: bộ nhớ cho trạng thái limiter, số lần gọi Redis mỗi giây.
• Đào sâu: chọn thuật toán nào (lý do), giới hạn toàn cục khi nhiều gateway, Redis sập thì sao (fail open hay fail close).

Bài 2: Thiết kế autocomplete cho ô tìm kiếm

• 10^7 truy vấn/ngày, trả lời dưới 50 ms, cập nhật từ khóa hot mỗi giờ.
• Ước lượng: kích thước trie cho 10^7 cụm từ, số máy.
• Đào sâu: cập nhật trie không gián đoạn, cache ở tầng nào, cá nhân hóa.

Bài 3: Thiết kế cache phân tán và dịch vụ tìm kiếm (nâng cao)

1. Cache phân tán 1 TB trên 20 máy: consistent hashing (vẽ vòng băm, giải thích thêm/bớt máy), nhân bản, xử lý key nóng.
2. Tìm kiếm cho 10^8 tài liệu: chia shard chỉ mục ngược, gộp kết quả top-k từ các shard, Bloom filter ở đâu.
3. Nhờ 1 người đóng vai người phỏng vấn cho 1 đề, hoặc tự ghi âm. Ghi lại câu hỏi bị bí.

✅ Tiêu chí hoàn thành

• 4 đề đủ 5 bước, có sơ đồ.
• Mỗi đề có phép ước lượng với số cụ thể.
• Mỗi đề nêu ít nhất 2 đánh đổi.
• Có ghi chú buổi phỏng vấn thử.

❓ Câu hỏi ôn tập

1. Bước đầu tiên khi thiết kế là gì?
2. Cache giảm tải cho ai?
3. Token bucket cho phép gì?
4. Vì sao ghi giả định cho mọi số?

🌕 Bạn đã hoàn thành ngày 165. Làm hết bài tập phía trên rồi sang ngày tiếp theo.