Rate Limiting: Sliding Window, Token Bucket Và Các Thuật Toán Giới Hạn Lưu Lượng

⏳ Tóm tắt cho người bận rộn (TL;DR)

• Sliding Window (Cửa sổ trượt): Khắc phục lỗi "dồn traffic ở ranh giới thời gian" của Fixed Window bằng cách trượt khung thời gian đếm lùi liên tục theo từng request mới nhất.
• Burst Limit (Giới hạn đột biến): Cho phép một lượng lớn request vượt qua giới hạn trong một chớp mắt (burst) để đảm bảo trải nghiệm người dùng không bị gián đoạn, nhưng vẫn giữ được tốc độ trung bình an toàn.
• Token Bucket (Thùng Token): Thuật toán cấp token (đồng xu) đều đặn vào một cái xô. Request tới phải lấy được token để đi tiếp. Khi xô đầy, nó cho phép xử lý một đợt Burst bằng đúng sức chứa của xô.
• Leaky Bucket (Thùng rò rỉ): Xô bị lủng đáy. Đầu vào có thể ồ ạt, nhưng đầu ra chảy xuống server xử lý luôn ở tốc độ cố định. Dùng để "làm phẳng" traffic, không cho phép Burst.

---

📖 BÀI VIẾT CHI TIẾT

1. Tại sao cần Sliding Window (Cửa sổ trượt)?

Để hiểu sự ưu việt của cửa sổ trượt, ta cần biết lỗ hổng của Cửa sổ cố định (Fixed Window). Giả sử hệ thống quy định: Cho phép 100 request / 1 phút. Cửa sổ cố định sẽ chia thời gian thành các mốc cứng: 08:00 - 08:01, 08:01 - 08:02...

• Lỗ hổng (Edge-case): Hacker gửi 100 request ở giây 08:00:59 (cuối phút đầu) và 100 request nữa ở giây 08:01:00 (đầu phút sau). Về lý thuyết, hacker không vi phạm luật của phút nào, nhưng Server của bạn phải gánh 200 request chỉ trong 2 giây, dẫn tới nguy cơ sập cục bộ.

Giải pháp: Sliding Window Thuật toán này không đóng khung cứng nhắc, mà khung thời gian sẽ trượt liên tục theo thời gian thực. Khi một request đến vào lúc 08:01:30, hệ thống đếm ngược lại đúng 60 giây (từ 08:00:30). Nhờ vậy, nó triệt tiêu hoàn toàn rủi ro dồn traffic ở ranh giới thời gian, mang lại sự kiểm soát chuẩn xác nhất.

2. Burst Limit là gì và Thuật toán Token Bucket

Burst là hiện tượng người dùng gửi lượng lớn request trong một thời gian cực ngắn (vài mili-giây). Trong thực tế, trình duyệt thường tải nhiều tài nguyên cùng lúc. Nếu API giới hạn quá khắt khe (chặn ngay lập tức nếu vượt ngưỡng 1 request/giây), người dùng sẽ liên tục bị lỗi.

Chúng ta cần Burst Limit (Dung sai đột biến). Thuật toán xử lý việc này hoàn hảo nhất là Token Bucket:

1. Tốc độ nạp (Refill Rate): Mỗi giây, hệ thống tự động bỏ 10 đồng xu vào một cái xô (sức chứa tối đa 100 đồng xu).
2. Quy tắc xử lý: Một request muốn đi qua API Gateway phải bốc được 1 đồng xu khỏi xô. Hết xu thì bị từ chối (HTTP 429).
3. Cơ chế cho phép Burst: Giả sử xô đang đầy (100 xu) và có đợt sóng 100 request ập đến cùng lúc. Hệ thống cấp phát ngay 100 xu và xử lý trót lọt toàn bộ (đây chính là Burst Limit). Sau đợt bứt tốc này xô cạn sạch, các request tiếp theo phải ngoan ngoãn chờ từng đồng xu nạp thêm mỗi giây.

3. Thuật toán Leaky Bucket (Làm phẳng lưu lượng)

Nếu Token Bucket chiều chuộng trải nghiệm người dùng, thì Leaky Bucket (Thùng rò rỉ) là người bảo vệ kỷ luật. Thuật toán này KHÔNG cho phép Burst.

• Hãy tưởng tượng một cái xô bị thủng một lỗ nhỏ ở đáy. Nước (Request) từ client có thể đổ vào xô một cách ồ ạt và lộn xộn.
• Tuy nhiên, nước chảy ra từ đáy xô để đi vào Server luôn duy trì một tốc độ cố định (ví dụ: đúng 10 giọt/giây). Nếu đổ nước quá nhanh làm đầy xô, nước tràn ra ngoài (Request bị drop).
• Ứng dụng: Thuật toán này giúp "làm phẳng" (smoothing) lưu lượng. Nó là lựa chọn số 1 cho các hệ thống cần sự ổn định tuyệt đối như Message Queue (RabbitMQ, Kafka), xử lý giao dịch tài chính, hoặc các tác vụ chạy ngầm.

🎯 Tổng kết: Lựa chọn thuật toán nào?