Rate Limiting Ở Quy Mô Lớn: Thuật Toán, Redis Pattern, và Phối Hợp Phân Tán

Tại Sao Rate Limiting Là Bài Toán Hệ Thống

Hầu hết hướng dẫn rate limiting chỉ cho bạn cách thêm middleware vào một server. Điều đó hoạt động cho đến khi bạn có nhiều hơn một server. Với nhiều instance, mỗi cái duy trì counter của riêng mình, client có thể gửi N request đến mỗi M server và vượt quá giới hạn dự định M lần. Rate limiting chỉ hiệu quả khi counter được chia sẻ.

Các Thuật Toán

Fixed Window

Chia thời gian thành các window rời rạc. Đếm request trong window hiện tại. Nếu vượt giới hạn, từ chối request.

Đơn giản. Có vấn đề. Client có thể gửi 100 request lúc 12:00:59 và 100 request lúc 12:01:01 — 200 request trong hai giây, gấp đôi giới hạn mỗi phút.

Sliding Window Counter

Sử dụng hai fixed window counter (window hiện tại và trước) và tính count có trọng số:

count = (current_window_count) + (previous_window_count × tỷ_lệ_còn_lại)

Xấp xỉ nhưng thực tế. Rẻ hơn nhiều so với sliding window log. Sai số có giới hạn và chấp nhận được cho hầu hết trường hợp.

Token Bucket

Mỗi client có bucket với dung lượng tối đa N token. Token nạp lại với tốc độ cố định. Mỗi request tiêu thụ một token. Nếu bucket rỗng, request bị từ chối.

Cho phép burst đến dung lượng bucket, sau đó thực thi tốc độ steady-state.

Triển Khai Với Redis

INCR + EXPIRE (Fixed Window)

key = "rate:{client_id}:{window}"
count = INCR key
if count == 1:
    EXPIRE key window_size_seconds
if count > limit:
    reject

Sorted Set (Sliding Window Log)

key = "rate:{client_id}"
ZREMRANGEBYSCORE key 0 window_start
count = ZCARD key
if count < limit:
    ZADD key now now
    EXPIRE key window_seconds
else:
    reject

Lua Script cho Atomicity

Bọc chúng trong Lua script để Redis thực thi nguyên tử:

local key = KEYS[1]
local limit = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local now = tonumber(ARGV[3])

redis.call('ZREMRANGEBYSCORE', key, 0, now - window)
local count = redis.call('ZCARD', key)
if count < limit then
    redis.call('ZADD', key, now, now)
    redis.call('EXPIRE', key, math.ceil(window / 1000))
    return 1
end
return 0

Nơi Thực Thi

Tại edge (API gateway / load balancer): rẻ nhất — request không bao giờ chạm đến application code. Tốt nhất cho bảo vệ DoS và traffic chưa xác thực.

Tại service: cần thiết cho giới hạn per-user hay per-tenant yêu cầu authentication context.

Cả hai: dùng giới hạn thô ở edge (IP-based) và giới hạn tinh ở service (per-user). Defense in depth.

Trả Về Header Đúng

HTTP/1.1 429 Too Many Requests
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1714500060
Retry-After: 47

Client hành xử tốt sẽ back off. Client hành xử kém sẽ retry ngay lập tức — đó là lý do tại sao thực thi ở edge quan trọng.