Thiết kế Rate Limiter phân tán: So sánh Token Bucket, Leaky Bucket và Sliding Window Log

Bảo vệ hệ thống trước bão Request#

Rate Limiter là thành phần chốt chặn không thể thiếu của bất kỳ API Gateway nào:

Ngăn chặn người dùng spam hoặc bot DDOS.
Giới hạn hạn ngạch sử dụng theo gói dịch vụ (Free: 100 req/ngày, Pro: 10.000 req/ngày).

Dưới đây là phân tích 3 thuật toán giới hạn tần suất kinh điển nhất.

Một chiếc xô có sức chứa tối đa $B$ tokens. Cứ mỗi giây, hệ thống tự động rót thêm $R$ tokens vào xô.
Mỗi khi có request đến: Nếu trong xô còn token $\rightarrow$ Lấy 1 token và cho qua. Nếu xô rỗng $\rightarrow$ Từ chối với mã HTTP 429.
Ưu điểm: Cho phép xử lý lưu lượng tăng đột biến trong thời gian ngắn (Traffic Burst) miễn là trong xô còn đủ token tích lũy.

Request đổ vào xô như nước. Ở đáy xô có một lỗ rò rỉ xả nước ra với tốc độ cố định $R$ request/giây.
Ưu điểm: Làm phẳng lưu lượng (Traffic Smoothing), bảo vệ backend không bao giờ bị quá tải đột ngột.
Nhược điểm: Các request đột biến hợp lệ vẫn bị xếp hàng chậm trễ.

Lưu timestamp của từng request vào một Redis Sorted Set (ZADD).
Khi có request mới: Xóa toàn bộ timestamp cũ hơn 1 phút trước (ZREMRANGEBYSCORE), sau đó đếm số lượng phần tử còn lại (ZCARD).
Ưu điểm: Chính xác tuyệt đối 100%, không bị lỗi biên (Boundary issues).
Nhược điểm: Tốn rất nhiều bộ nhớ RAM nếu lượng request lớn.

Kết hợp giữa Fixed Window và Sliding Window: Tính toán tỷ lệ trọng số của cửa sổ trước đó và cửa sổ hiện tại.

CODE

Số request ước tính = (Request cửa sổ hiện tại) + (Request cửa sổ trước) × (Tỷ lệ thời gian còn lại)

Vừa chính xác cao, vừa chỉ tốn đúng 2 keys số nguyên trong Redis!

Hệ thống của bạn đang sử dụng thuật toán Rate Limit nào? Bạn triển khai bằng Redis, Envoy Proxy hay Kong Gateway?

Xem thêm nội dung liên quan: