App: rate limiter bằng cache và hàng đợi

Giới thiệu

Bài này xây bộ chặn spam request quá đà. Quá quota thì trả lỗi 429 chờ sau.

Kiến thức cần nhớ

3 thuật toán giới hạn

• Fixed window: đếm request trong cửa sổ cố định như mỗi phút.
• Sliding window: lưu timestamp từng request, tỉa cái cũ.
• Token bucket: thùng nạp token đều, có token mới cho qua.
• Ví dụ đời thường: quán chỉ cho 5 khách vào mỗi 10 phút.

Lưu trạng thái bằng cache

• Mỗi key user hoặc IP có 1 bản ghi đếm riêng.
• Key im lặng lâu tự bay nhờ TTL nên RAM không phình.
• Khóa theo key để đếm đúng khi nhiều luồng cùng tới.
• Ví dụ đời thường: mỗi khách có 1 thẻ đếm riêng, lâu không tới thì hủy thẻ.

Chọn thuật toán theo endpoint

• Đăng nhập dùng sliding window cho nghiêm chống dò mật khẩu.
• API đọc dùng token bucket cho thoáng, cho burst nhẹ.
• Bị chặn trả 429 kèm Retry-After và header còn lại.
• Nạp token kiểu lazy: tới lúc có request mới tính token mới.

Ví dụ

• Input: rule 5 request mỗi phút, gửi 10 request dồn dập. Output: 5 qua, 5 bị chặn 429.
• Giải thích: hết quota trong cửa sổ nên phải chờ.
• Input: 50 luồng cùng key với quota 100. Output: đúng 100 request qua, không hơn.
• Giải thích: khóa theo key giúp đếm không lệch khi chen nhau.

💻 Bài tập

Ngôn ngữ: Python 3 (có asyncio) hoặc Go. Nộp vào day-128-ratelimiter/.

Bài 1: Ba thuật toán giới hạn

class RateLimiter(Protocol):
    def allow(self, key: str, now: float) -> tuple[bool, float]:
        """Trả (cho phép?, số giây phải chờ nếu bị chặn)."""

now được truyền vào để test bằng đồng hồ giả.

FixedWindow(5, 60): 5 request lúc t=59, 5 request lúc t=60 -> 10 request trong 2 giây đều qua (điểm yếu biên cửa sổ)
SlidingLog(5, 60): cùng kịch bản -> 5 request sau bị chặn
TokenBucket(10, 1/s): 10 request dồn cùng lúc qua hết, request 11 bị chặn, chờ 1 giây

Bài 2: Middleware và dọn dẹp

1. Viết HTTP server nhỏ (aiohttp hoặc http.server) với 2 route: /login dùng SlidingLog(5, 60) theo IP, /api/* dùng TokenBucket(20, 5/s) theo API key.
2. Bị chặn trả 429 với header Retry-After, X-RateLimit-Limit, X-RateLimit-Remaining.
3. Key im lặng quá 10 phút bị xóa (TTL). Chạy 1 triệu key ngẫu nhiên, kiểm tra bộ nhớ không phình mãi.
4. An toàn khi nhiều request đồng thời cùng key: dùng khóa theo key.

Bài 3: Đo và giới hạn phân tán (nâng cao)

1. Dùng wrk, hey hoặc script asyncio bắn 5000 request/giây. Đo số request bị chặn đúng theo lý thuyết và độ trễ thêm do limiter.
2. Chạy 2 tiến trình server sau 1 load balancer giả (round robin). Chỉ ra limiter trong bộ nhớ bị vượt gấp đôi.
3. Chuyển trạng thái sang Redis (INCR + EXPIRE cho fixed window, hoặc Lua script cho token bucket). Kiểm tra giới hạn đúng trên cả 2 tiến trình.

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

• Test 3 thuật toán bằng đồng hồ giả pass, có test điểm yếu biên cửa sổ.
• Response 429 đủ 3 header.
• Bộ nhớ ổn định với 1 triệu key.
• Bài 3 cho thấy lỗi limiter cục bộ và bản Redis sửa được.

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

• 3 thuật toán giới hạn khác nhau ở điểm gì?
• Vì sao cần khóa theo key?
• TTL giúp cache limiter thế nào?
• Khi nào dùng token bucket thay sliding window?

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