Token bucket vs sliding window: chọn kiểu rate limit cho API

Một tình huống thường gặp khi bật rate limit cho API lần đầu: ngày đầu êm ru. Ngày thứ hai, team mobile báo: “App khách hàng VIP bị 429 liên tục, họ gọi support rồi.” Hoá ra dùng fixed window counter với limit 100 request/phút, và client gửi batch 80 request mỗi lần sync, vào đúng ranh giới hai cửa sổ liền nhau thì vẫn qua, nhưng chỉ cần lệch vài giây là chạm trần. Rate limit đúng thuật toán nhưng sai mục tiêu.

Bài học: rate limit không phải “chọn một con số rồi cắm vào middleware”. Nó là quyết định sản phẩm, bạn đang nói với client “được phép làm gì, với tốc độ nào”. Chọn thuật toán sai, ngưỡng sai, hoặc thiếu header phản hồi rõ ràng đều ảnh hưởng trực tiếp đến trải nghiệm người dùng.

Mục tiêu trước, thuật toán sau

Trước khi nhảy vào token bucket hay sliding window, cần trả lời một câu hỏi: bạn rate limit để làm gì?

Bảo vệ tài nguyên khan hiếm (database connection, CPU cho route nặng, quota SMS bên thứ ba) thì cần giới hạn chặt. Đảm bảo công bằng giữa các tenant trong SaaS thì cần limit theo tenant, không phải theo IP. Chống brute force login thì cần sliding window chính xác, vì kẻ tấn công sẽ canh biên cửa sổ. Shape traffic để downstream dễ chịu thì cần leaky bucket cho luồng ra đều.

Không có “thuật toán rate limit tốt nhất”, chỉ có thuật toán phù hợp với mục tiêu cụ thể.

Token bucket, cho phép burst, kiểm soát trung bình

Ý tưởng đơn giản: một cái xô chứa tối đa B token. Mỗi giây, r token được thêm vào (nhưng không vượt quá B). Mỗi request tiêu 1 token (hoặc nhiều hơn cho endpoint đắt). Hết token thì reject.

Tính chất hay nhất của token bucket: nó cho phép burst ngắn. Nếu client im lặng một lúc, xô đầy lên B token, rồi gửi liền B request vẫn qua. Nhưng trung bình theo thời gian, tốc độ không vượt r. Phù hợp khi bạn muốn nói: “trung bình 10 req/s, nhưng cho phép burst 30 nếu trước đó idle.”

Triển khai in-process khá đơn giản:

import time

class TokenBucket:
    def __init__(self, rate, capacity):
        self.rate = rate         # tokens per second
        self.capacity = capacity
        self.tokens = capacity
        self.last = time.monotonic()

    def allow(self, cost=1):
        now = time.monotonic()
        elapsed = now - self.last
        self.tokens = min(self.capacity, self.tokens + elapsed * self.rate)
        self.last = now
        if self.tokens >= cost:
            self.tokens -= cost
            return True
        return False

Nhưng khi có nhiều instance app, trạng thái phải ở store chung. Redis + script Lua là lựa chọn phổ biến nhất vì đảm bảo atomic, không sợ race condition giữa hai instance cùng trừ token:

-- KEYS[1]: bucket key, e.g. "rl:user:42"
-- ARGV: now (float seconds), rate, capacity, cost
local now = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local cap  = tonumber(ARGV[3])
local cost = tonumber(ARGV[4])

local state = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(state[1]) or cap
local ts = tonumber(state[2]) or now

local elapsed = math.max(0, now - ts)
tokens = math.min(cap, tokens + elapsed * rate)

local allowed = 0
if tokens >= cost then
  tokens = tokens - cost
  allowed = 1
end

redis.call('HMSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('EXPIRE', KEYS[1], math.ceil(cap / rate) + 10)
return { allowed, tokens }

Gọi từ app bằng EVALSHA (load script một lần, sau đó chỉ gửi hash), overhead rất nhỏ.

Leaky bucket là họ hàng gần: thay vì kiểm soát đầu vào, nó kiểm soát đầu ra đều đặn. Nếu request đến nhanh hơn tốc độ xả, xô đầy thì drop. Dùng khi cần shape traffic ra downstream theo nhịp cố định, ví dụ gọi API đối tác có hard limit.

Fixed window counter, đơn giản nhưng có bug biên

Chia thời gian thành ô cố định (ví dụ mỗi phút). Đếm request mỗi key trong ô hiện tại. Vượt ngưỡng thì reject. Triển khai Redis chỉ cần INCR + EXPIRE:

key = "rl:user:42:2026-04-09T12:03"
INCR key
EXPIRE key 120
nếu counter > 100 thì reject

Ưu điểm lớn nhất là đơn giản và tốn ít bộ nhớ, chỉ một counter mỗi ô. Nhưng nó có nhược điểm kinh điển: burst tại biên. Giới hạn 100/phút, client gửi 100 ở giây 59 và 100 ở giây 60, hai ô khác nhau, đều hợp lệ, nhưng 200 request trong 2 giây. Với endpoint nhẹ thì không sao, nhưng với database migration hay payment API thì đủ gây sự cố.

Fixed window phù hợp cho quota daily/monthly đơn giản (1000 request/ngày cho free tier), ở quy mô ngày thì bug biên không đáng kể.

Sliding window, chính xác nhưng tốn hơn

Sliding window log

Lưu timestamp từng request trong Redis ZSET (sorted set, score = timestamp). Khi request mới đến, xoá các entry cũ hơn cửa sổ, đếm còn lại, nếu dưới limit thì thêm vào và cho qua:

now = ...ms
ZREMRANGEBYSCORE key -inf (now - 60000)
count = ZCARD key
if count < 100:
   ZADD key now now
   EXPIRE key 120
   allow
else:
   reject

Chính xác tuyệt đối: “không quá N request trong bất kỳ cửa sổ T giây nào”. Không có bug biên. Nhưng bộ nhớ tỷ lệ với số request gần đây, QPS cao sẽ tốn đáng kể.

Sliding window counter (xấp xỉ)

Giữ hai counter: ô hiện tại và ô trước. Ước lượng bằng cách pha trộn theo vị trí trong ô:

estimated = count_current + count_previous * (1 - elapsed_in_current / window_size)

Ít bộ nhớ như fixed window, nhưng chính xác hơn nhiều vì không có bug biên rõ rệt. Đây là lựa chọn “sweet spot” phổ biến nhất trong thực tế, đủ chính xác cho hầu hết trường hợp mà không tốn RAM như log.

Khi nào cần sliding

Khi chính sách phải nghiêm theo thời gian, “không vượt 5 lần OTP trong bất kỳ 10 phút nào”. Khi cần phát hiện burst bất thường (abuse detection). Khi endpoint quan trọng (login, payment), thà tốn bộ nhớ còn hơn bị bypass bằng cách canh biên.

So sánh nhanh

Mục tiêu	Gợi ý thuật toán
Cho burst hợp lý, trung bình về rate	Token bucket
Shape traffic ra đều cho downstream	Leaky bucket
Không quá N trong T (nghiêm)	Sliding window (log hoặc counter tuỳ RAM)
Quota daily/monthly đơn giản	Fixed window (chấp nhận bug biên nhỏ)

Đặt rate limiter ở đâu trong kiến trúc

Câu trả lời không phải “một chỗ” mà là nhiều lớp phối hợp.

Ở edge (CDN, WAF), chặn IP abuse nặng, DDoS cơ bản. Lớp này ít biết về user identity, chỉ dựa trên IP và pattern traffic. Cloudflare, AWS WAF, hay nginx limit_req nằm ở đây.

Ở API gateway (Envoy, Kong, Traefik), giới hạn theo API key, route, method. Đây là nơi áp policy chung: free tier 100 req/phút, premium 1000.

Ở application layer, middleware trong service. Biết user, tenant, role, có thể làm chính sách tinh vi: limit khác nhau cho đọc vs ghi, cho admin vs regular user, cho endpoint payment vs search.

Ở database / downstream, connection pool size, circuit breaker. Không phải rate limit cổ điển nhưng cùng mục tiêu bảo vệ. Khi Postgres chỉ có 100 connection, đó chính là hard limit tự nhiên.

Pattern thực tế: edge chặn abuse thô, gateway áp policy tổng, app xử lý logic nghiệp vụ. Ba lớp này bổ sung cho nhau, không thay thế.

Chọn key limit theo ai

IP là lựa chọn đầu tiên nhiều người nghĩ tới, nhưng NAT khiến nhiều user chung một IP (toàn bộ văn phòng 200 người sau một IP), còn mobile thì IP đổi liên tục. Chỉ dùng IP cho lớp edge ngoài cùng.

Sau khi auth, user ID hoặc API key là key chính xác nhất. Với SaaS, tenant ID tách quota giữa các khách hàng, công bằng và dễ nâng gói. Khi chưa login, dùng session hoặc device fingerprint, kém chính xác nhưng có còn hơn không.

Tổ hợp key cũng rất hữu ích: (user, endpoint) để limit riêng từng endpoint. User A có thể search 100 lần/phút nhưng chỉ được POST payment 5 lần/phút.

Một tip nhỏ: hash key nhạy cảm (API key) trước khi làm Redis key, và đặt prefix rõ ràng (rl:v1:user:…) để version hoá, khi đổi thuật toán hoặc ngưỡng, bạn có thể dùng prefix v2 mà không conflict.

Header HTTP nên trả về

Client cần biết mình đang ở đâu so với limit để tự điều chỉnh. Trả header theo chuẩn đang được IETF chuẩn hoá:

RateLimit-Limit: 100
RateLimit-Remaining: 42
RateLimit-Reset: 37

Khi reject, trả 429 Too Many Requests kèm Retry-After (tính bằng giây):

HTTP/1.1 429 Too Many Requests
Retry-After: 37
Content-Type: application/json

{"error": "rate_limit_exceeded", "retry_after_seconds": 37}

Client tốt sẽ đọc Retry-After và exponential backoff. Bạn nên viết client SDK của chính mình theo quy ước này, không phải tất cả dev đều đọc header, nên trả luôn trong body JSON nữa cho chắc.

Những cạm bẫy thường gặp

Limit chung cho đọc và ghi. Ghi thường đắt hơn đọc gấp nhiều lần (insert payment vs list products). Gộp chung một limit thì hoặc đọc bị kìm vô lý, hoặc ghi được thả lỏng nguy hiểm. Tách policy theo method hoặc endpoint là tối thiểu.

Client retry storm sau 429. Sau khi bị reject, tất cả client đồng loạt retry cùng lúc tạo thundering herd. Gợi ý: trả Retry-After với jitter nhẹ (cộng random 0-5 giây) hoặc document rõ cho client dùng exponential backoff + jitter.

Nhầm 429 với 503. 429 là “client gửi quá nhiều”, lỗi của client. 503 là “server quá tải”, lỗi phía server. Dùng đúng status code để monitoring phân biệt được, và client cũng hành xử khác nhau (429 thì backoff, 503 thì có thể retry ngay nếu server khác).

Redis down thì sao? Nếu rate limiter phụ thuộc Redis hoàn toàn và Redis chết, app fail-open (cho qua hết) hay fail-closed (chặn hết)? Fail-open an toàn hơn cho UX nhưng mất bảo vệ. Thực tế nên dùng fail-open kèm alert + fallback local (token bucket in-memory với ngưỡng lỏng hơn), ít nhất có bảo vệ tối thiểu.

Không test integration. Unit test thuật toán không đủ. Cần test end-to-end: spam N request, xác nhận 429 sau ngưỡng, đợi T giây, xác nhận lại cho qua. Nhiều team bỏ qua bước này rồi phát hiện limit không hoạt động khi lên production.

Đo lường sau khi bật

Bật rate limit mà không đo thì không biết có đang chặn nhầm user hợp lệ. Vài metric cần theo dõi:

Tỷ lệ 429 theo endpoint và user segment, nếu free tier bị 429 nhiều nhưng premium thì không, có thể ngưỡng free quá thấp. Latency P95/P99 so với baseline, overhead của limiter (thường rất nhỏ nhưng nên confirm). Ratio 429 từ bot vs client thật, nếu chặn nhầm nhiều crawler SEO hợp lệ hay monitoring của đối tác, nới rule hoặc whitelist.

Nên set alert khi tỷ lệ 429 vượt 5% request trong 5 phút, đủ sớm để phát hiện vấn đề mà không quá nhạy với spike tự nhiên.

Tóm tắt

Token bucket đơn giản, cho burst, dễ Redis hoá bằng Lua, phù hợp cho hầu hết API. Sliding window chính xác hơn theo thời gian, phù hợp endpoint nhạy cảm. Fixed window rẻ nhất nhưng có bug biên. Đặt rate limit ở nhiều lớp, mỗi lớp có trách nhiệm khác nhau. Trả header RateLimit-* và Retry-After, đừng để client phải đoán.

Và quan trọng nhất: chọn ngưỡng dựa trên số liệu thật (baseline traffic, peak, p99 latency) chứ không phải “100 req/phút nghe hợp lý”. Bật, đo, điều chỉnh, rate limit là quy trình sống, không phải config một lần rồi quên.