Rate limiting cho API: chọn thuật toán, lưu trạng thái ở đâu và trả lỗi thế nào Trung cấp

Vấn đề

API tìm kiếm chịu được khoảng 1.000 request/giây. Một khách hàng chạy script đồng bộ dữ liệu, bắn 3.000 request/giây trong 5 phút. Database bão hoà, p99 của mọi khách hàng khác tăng vọt.

Rate limiting trả lời ba câu hỏi riêng biệt:

1. Đếm thế nào? Thuật toán quyết định burst nào được qua.
2. Đếm ở đâu? Trong RAM mỗi instance hay ở store chung như Redis.
3. Từ chối thế nào? Status code, header và body để client biết khi nào thử lại.

Làm đúng một câu mà sai hai câu còn lại vẫn hỏng: thuật toán chuẩn nhưng mỗi Pod đếm riêng thì limit thực tế nhân theo số Pod.

Chọn nhanh

Thuật toán	Bộ nhớ mỗi key	Burst	Độ chính xác	Độ phức tạp
Fixed window	1 counter + window id	Tới 2× limit quanh ranh giới cửa sổ	Thấp ở ranh giới	Rất thấp (INCR + EXPIRE)
Sliding window log	1 timestamp mỗi request trong cửa sổ, O(limit)	Không vượt limit trong bất kỳ cửa sổ trượt nào	Chính xác	Trung bình; tốn RAM khi limit lớn
Sliding window counter	2 counter (cửa sổ hiện tại và trước)	Gần đúng, xấp xỉ limit	Xấp xỉ, giả định request rải đều	Thấp
Token bucket	2 số: token còn lại + thời điểm cập nhật	Cho burst tới capacity, sau đó ép về tốc độ refill	Chính xác theo mô hình	Thấp
Leaky bucket	Hàng đợi hoặc 1 mốc thời gian	Làm phẳng: đầu ra đều, burst bị xếp hàng hoặc từ chối	Chính xác theo mô hình	Thấp đến trung bình (nếu có hàng đợi)

Mặc định cho API công khai: token bucket (hoặc GCRA, một biến thể chỉ lưu một mốc thời gian). Nó cho client burst hợp lý, giới hạn tốc độ dài hạn, và chỉ cần hai con số mỗi key.

Năm thuật toán

Fixed window: rẻ nhưng hở ở ranh giới

Chia thời gian thành ô cố định (ví dụ mỗi phút), đếm request trong ô, vượt limit thì từ chối. Sang ô mới thì counter về 0.

Lỗ hổng ranh giới với limit 100 request/phút:

Thời điểm	Request	Cửa sổ	Kết quả
00:59.5	100	phút 0 (đếm 0 → 100)	cho qua hết
01:00.0	100	phút 1 (đếm lại từ 0)	cho qua hết

Kết quả: 200 request trong khoảng 0,5 giây, gấp đôi limit mỗi phút, mà không vi phạm luật nào của thuật toán.

Sliding window log: chính xác nhưng tốn RAM

Lưu timestamp của từng request (thường là sorted set). Mỗi request mới: xoá timestamp cũ hơn now - window, đếm phần còn lại, so với limit.

Chính xác tuyệt đối, nhưng limit 10.000 request/giờ nghĩa là tới 10.000 phần tử cho mỗi key. Hợp với limit nhỏ và nhạy cảm (đăng nhập, gửi OTP), không hợp với quota lớn.

Sliding window counter: xấp xỉ rẻ

Giữ counter của cửa sổ hiện tại và cửa sổ trước, ước lượng theo tỉ lệ thời gian đã trôi:

rate ≈ previous_count × (window − elapsed) / window + current_count

Ví dụ của Cloudflare với limit 50/phút: phút trước 42 request, phút này đã qua 15 giây với 18 request → 42 × 45/60 + 18 = 49,5. Request tiếp theo sẽ bị chặn.

Giả định request phút trước rải đều nên là xấp xỉ. Cloudflare báo cáo trên 400 triệu request: khoảng 0,003% request bị cho qua hoặc chặn sai.

Token bucket: burst có kiểm soát

Bucket chứa tối đa capacity token, được nạp đều rate token/giây. Mỗi request lấy 1 token (hoặc nhiều hơn nếu request đắt); hết token thì từ chối.

Không cần timer nạp token: lúc xử lý request, tính tokens = min(capacity, tokens + elapsed × rate). Hai tham số tách bạch hai câu hỏi: burst tối đa (capacity) và tốc độ dài hạn (rate).

Token bucket capacity 10, refill 10/giây chặn burst thứ hai

Phóng to sơ đồ

Token bucket

◀ Trước▶ PhátTiếp ▶↺ Từ đầuBước 1/5

Client im lặng một lúc nên bucket đã đầy: 10 token. Đây chính là burst tối đa được phép.

Leaky bucket: làm phẳng đầu ra

Request vào một “xô” và rò ra với tốc độ cố định; xô đầy thì tràn (từ chối). Có hai cách hiểu: hàng đợi (request bị trì hoãn rồi mới xử lý) hoặc meter (chỉ đo, tương đương token bucket nhìn ngược).

NGINX limit_req dùng phương pháp leaky bucket: request vượt rate bị trì hoãn cho tới khi vượt burst thì bị từ chối; thêm nodelay để xử lý ngay phần trong burst. Lưu ý: status mặc định khi từ chối của limit_req_status là 503, nên đổi sang 429 nếu muốn client phân biệt quá tải với vượt quota.

Demo: cùng một burst, hai thuật toán

Mô phỏng với đồng hồ giả, không cần Redis. Limit 10 request/giây cho cả hai: fixed window 1.000 ms, token bucket capacity 10, refill 10/giây. Client bắn 10 request ở 990 ms, 10 ở 1.000 ms, 10 ở 1.500 ms.

npx --prefix examples ts-node examples/src/rate-limiting/burst-demo.ts

limit: 10 req/s | fixed window 1000 ms | token bucket capacity 10, refill 10/s
t(ms)  sent  fixed-window  token-bucket  tokens-left
  990    10    10 allowed    10 allowed          0.0
 1000    10    10 allowed     0 allowed          0.1
 1500    10     0 allowed     5 allowed          0.1
accepted in 990..1000 ms (10 ms): fixed-window=20, token-bucket=10
total accepted out of 30: fixed-window=20, token-bucket=15

Đọc kết quả:

• Fixed window cho 20 request qua trong 10 ms, gấp đôi limit, vì 1.000 ms là ranh giới cửa sổ.
• Token bucket không bao giờ cho quá capacity trong một burst, nhưng sau 500 ms lại cho 5 request qua: không phạt client lâu hơn mức cần.
• Fixed window chặn hết lượt 1.500 ms dù client đã chờ nửa giây; token bucket phân phối công bằng hơn theo thời gian.

Trạng thái ở đâu: từng instance hay Redis chung

Cách lưu	Ưu	Nhược	Dùng khi
RAM từng instance	Không thêm network hop, không phụ thuộc store	Limit thực tế ≈ limit × số instance; reset khi Pod restart; lệch khi load balancer phân phối không đều	Chống quá tải cục bộ (bảo vệ chính instance đó)
Redis chung	Một nguồn sự thật cho mọi instance	+1 round-trip mỗi request; Redis thành dependency của đường nóng	Quota theo user/API key, limit bán theo gói
Gateway / edge (NGINX, API gateway, CDN)	Chặn trước khi tốn tài nguyên ứng dụng	Không biết ngữ cảnh nghiệp vụ (tenant, cost)	Lớp thô theo IP, chống flood

Atomic: đọc-tính-ghi phải là một bước

Cách làm sai hay gặp: GET token, tính trong app, rồi SET. Hai instance cùng đọc “còn 1 token” và cùng cho qua.

• INCR + EXPIRE đủ cho fixed window, vì INCR tự atomic.
• MULTI/EXEC gom lệnh thành khối, nhưng không cho bạn đọc kết quả giữa chừng để quyết định; phải ghép WATCH và retry khi xung đột. Redis cũng không rollback lệnh đã chạy trong transaction.
• Lua script là lựa chọn gọn nhất: Redis đảm bảo script chạy atomic, chặn mọi hoạt động khác của server trong lúc chạy.

Phác thảo token bucket bằng Lua. Đã chạy thử trên Redis 7.4 với capacity 10, refill 10 token/giây: 12 request gửi liền nhau thì 10 được nhận, 2 bị từ chối với retry_ms = 99. Vẫn cần test tải và test failover trong hệ thống của bạn trước khi dùng:

-- KEYS[1] = khoá bucket, ví dụ rl:{apikey:abc}
-- ARGV[1] = capacity, ARGV[2] = refill token/giây, ARGV[3] = cost của request
local capacity = tonumber(ARGV[1])
local rate     = tonumber(ARGV[2])
local cost     = tonumber(ARGV[3])

-- cost lớn hơn capacity thì không bao giờ đủ token: trả -1 để app báo lỗi thay vì 429 + Retry-After
if cost > capacity then
  return { 0, 0, -1 }
end

local t   = redis.call('TIME')                      -- đồng hồ của Redis, không phải của app
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)

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

tokens = math.min(capacity, tokens + math.max(0, now - ts) / 1000 * rate)

local allowed, retry_ms = 0, 0
if tokens >= cost then
  tokens  = tokens - cost
  allowed = 1
else
  retry_ms = math.ceil((cost - tokens) / rate * 1000)
end

redis.call('HSET', KEYS[1], 'tokens', tostring(tokens), 'ts', tostring(now))
redis.call('PEXPIRE', KEYS[1], math.ceil(capacity / rate * 1000) + 1000)
return { allowed, math.floor(tokens), retry_ms }

Những điểm cố ý trong phác thảo:

• Tên key đi qua KEYS, không ghép chuỗi trong script; Redis yêu cầu vậy để script chạy đúng cả trên Cluster.
• TIME trong script an toàn vì từ Redis 5.0 script được replicate theo effects (Redis 7.0 bỏ hẳn chế độ verbatim), nên replica nhận lệnh HSET với giá trị đã tính, không chạy lại script.
• PEXPIRE để key của client không hoạt động tự biến mất sau khi bucket đã đầy lại.
• retry_ms dùng để điền Retry-After. Giá trị -1 nghĩa là cost vượt capacity: request này không bao giờ qua được dù chờ bao lâu, nên trả lỗi cấu hình hoặc 4xx khác thay vì 429, nếu không client sẽ retry mãi. Vì vậy capacity phải lớn hơn hoặc bằng cost lớn nhất (ví dụ export trừ 50 token thì capacity tối thiểu 50).
• Gọi bằng EVALSHA; script cache không bền qua restart/failover, client library thường tự nạp lại khi gặp NOSCRIPT.

Script chặn cả server trong lúc chạy, nên giữ nó ngắn và O(1); một script chậm làm mọi client Redis khác chờ (Redis single-threaded).

Đồng hồ: chọn một nguồn

• Dùng đồng hồ của Redis (TIME) thay vì Date.now() của từng instance. Lệch đồng hồ giữa các Pod làm elapsed âm hoặc phình, nạp sai token. math.max(0, ...) ở trên chặn trường hợp âm.
• Đồng hồ trong RAM local: dùng đồng hồ đơn điệu (performance.now() hoặc process.hrtime.bigint() trong Node), không dùng wall clock có thể bị NTP chỉnh lùi.
• Redis sập thì sao? Chọn trước: fail open (cho qua, giữ availability, thêm limit local làm lưới an toàn) hay fail closed (từ chối, cho endpoint nhạy cảm như đăng nhập). Đặt timeout ngắn cho lệnh Redis để rate limiter không thành nguồn latency.

Trả lỗi thế nào: 429, Retry-After và RateLimit header

HTTP/1.1 429 Too Many Requests
Content-Type: application/problem+json
Retry-After: 2
RateLimit-Policy: "burst";q=10;w=1
RateLimit: "burst";r=0;t=2

{
  "type": "https://api.example.com/problems/rate-limited",
  "title": "Too many requests",
  "status": 429,
  "detail": "API key abc đã dùng hết 10 request trong cửa sổ hiện tại."
}

Thành phần	Nguồn	Điểm cần nhớ
429 Too Many Requests	RFC 6585 §4	Client gửi quá nhiều request trong một khoảng thời gian. RFC không quy định cách nhận diện user hay cách đếm. Response 429 MUST NOT được cache lưu.
Retry-After	RFC 9110 §10.2.3	Giá trị là HTTP-date hoặc số giây không âm (Retry-After: 120). RFC 6585 nói 429 MAY kèm header này.
Body	RFC 9457	Dùng application/problem+json với type riêng cho rate limit để client không phải parse detail.
RateLimit, RateLimit-Policy	IETF draft	Chưa phải RFC, xem bên dưới.

Trạng thái IETF draft (kiểm tra 2026-10-18): draft-ietf-httpapi-ratelimit-headers-11 (23/05/2026) của nhóm HTTPAPI vẫn là Internet-Draft, hết hạn 24/11/2026. Draft định nghĩa hai field:

• RateLimit-Policy: chính sách, tham số q (quota), w (cửa sổ, giây), qu (đơn vị quota, mặc định request), pk (partition key).
• RateLimit: trạng thái hiện tại, tham số r (quota còn lại), t (cửa sổ hiệu lực, giây), pk.

Các header X-RateLimit-Limit/-Remaining/-Reset phổ biến nhưng không chuẩn; mỗi nhà cung cấp hiểu Reset một kiểu (giây còn lại hay epoch). Nếu dùng draft, ghi rõ trong tài liệu API là đang theo draft và có thể đổi. Khi có cả hai, draft quy định Retry-After được ưu tiên.

Client nhận 429 nên chờ theo Retry-After, thêm jitter, và không retry vô hạn: xem retry, backoff và jitter.

Đếm theo cái gì

Key	Ưu	Bẫy
User id / tenant	Công bằng theo khách hàng, gắn với gói dịch vụ	Chỉ có sau khi xác thực; endpoint ẩn danh cần key khác
API key / client id	Rõ ràng cho B2B, dễ bán quota theo gói	Một khách hàng có nhiều key → cộng dồn theo tenant
IP	Có ngay ở edge, chặn flood ẩn danh	NAT: cả công ty hay mạng di động dùng chung IP, chặn một người là chặn hàng trăm người. IPv6: một subnet thường là /64, kẻ tấn công xoay địa chỉ tuỳ ý; nên gom theo prefix. Sau proxy, phải lấy IP từ header do proxy tin cậy gắn, không tin X-Forwarded-For client tự gửi.

Rate limit không thay authorization. Kẻ dò ID theo kiểu BOLA/IDOR chỉ bị làm chậm, dữ liệu vẫn lộ nếu thiếu kiểm tra quyền.

Nhiều lớp, mỗi lớp một việc

Đang tải diagram…

• Gateway: chống flood theo IP, limit rộng tay để không chặn nhầm NAT.
• Service: quota theo user/API key/tenant, có ngữ cảnh nghiệp vụ.
• Endpoint đắt: giới hạn số request đang chạy đồng thời, không chỉ số request/giây.

Limit theo chi phí

Không phải request nào cũng tốn như nhau. GET /orders/42 và POST /reports/export trên 1 năm dữ liệu không nên trừ cùng 1 token.

• Gán cost cho từng loại request (ví dụ export trừ 50 token), dùng ARGV[3] trong script.
• GraphQL: tính cost từ độ sâu và kích thước truy vấn trước khi thực thi.
• Draft RateLimit hỗ trợ việc này qua tham số qu (đơn vị quota khác “requests”).

Bảo vệ endpoint đăng nhập

Đăng nhập cần luật riêng vì kẻ tấn công chủ động né limit:

1. Đếm lần thất bại theo tài khoản, không chỉ theo IP: OWASP lưu ý đếm theo IP thì kẻ tấn công chỉ cần rải qua nhiều địa chỉ.
2. Thêm limit theo IP để chặn password spraying (một IP thử nhiều tài khoản).
3. Lockout có thể bị lạm dụng để khoá tài khoản người khác: dùng độ trễ tăng dần thay vì khoá cứng, và vẫn cho reset mật khẩu.
4. CAPTCHA chỉ là lớp phòng thủ bổ sung; MFA mới là biện pháp chính.
5. Trả cùng một thông báo lỗi cho “sai mật khẩu” và “không có tài khoản”.

Quota theo Pod làm khách hàng nhận gấp 6 lần

Một API B2B bán gói 600 request/phút cho mỗi API key, đếm bằng token bucket trong RAM. Lúc ít tải chạy 2 Pod, khách hàng tính ra được 1.200/phút; sau đợt autoscale lên 6 Pod thì được khoảng 3.600/phút và job đồng bộ của họ đè database.

Cách sửa:

1. Chuyển bucket theo API key sang Redis, mỗi request một lệnh EVALSHA atomic.
2. Giữ limit local theo instance làm lưới an toàn khi Redis lỗi (fail open có giới hạn).
3. Trả 429 kèm Retry-After và problem+json; SDK của họ đọc header thay vì retry ngay.
4. Đặt cost 20 cho endpoint export.

Các con số trong ví dụ là kịch bản minh hoạ để thấy phép nhân, không phải số đo.

Khi nào dùng, khi nào không

Dùng	Không dùng / không đủ
API công khai, B2B có quota theo gói	Thay cho authorization hay validation
Endpoint đắt (export, search, AI)	Cơ chế duy nhất chống quá tải: cần thêm timeout, concurrency limit, load shedding
Đăng nhập, OTP, reset mật khẩu	Traffic nội bộ giữa service đã có backpressure riêng
Bảo vệ downstream có quota (SMS, payment)	Khi limit local theo Pod được bán như quota toàn cục

Lợi ích

• Một khách hàng không kéo sập trải nghiệm của mọi người.
• Chi phí downstream (database, nhà cung cấp tính tiền) có trần dự đoán được.
• Làm chậm brute force và scraping.

Chi phí

• Store chung thêm một round-trip và một dependency trên đường nóng.
• Chặn nhầm người dùng hợp lệ sau NAT nếu limit theo IP quá chặt.
• Phải vận hành: cấu hình theo gói, dashboard, ngoại lệ cho khách hàng lớn.

🎮 Thử tay

• Scale Lab: đề URL shortener, vòng 4: botnet spam API tạo link.
• Scale Lab: bán vé concert, vòng 3: bot phe vé tranh row lock với người thật.

Checklist production

1. Mỗi limit ghi rõ key (user, API key, tenant, IP/prefix), thuật toán và tham số (capacity, rate, window).
2. Quota toàn cục dùng store chung với thao tác atomic (Lua/INCR); limit local chỉ dùng để tự bảo vệ instance.
3. Từ chối bằng 429 + Retry-After + problem+json; nếu dùng NGINX limit_req, đổi limit_req_status khỏi 503 mặc định.
4. Quyết định trước fail open hay fail closed khi Redis lỗi, có timeout ngắn cho lệnh Redis.
5. IP lấy từ proxy tin cậy; IPv6 gom theo prefix; limit IP đủ rộng cho NAT.
6. Endpoint đăng nhập/OTP có limit theo tài khoản và theo IP, độ trễ tăng dần thay vì khoá cứng.
7. Metric: số request bị chặn theo key/route, top key gần chạm limit, latency của rate limiter; alert khi tỉ lệ 429 tăng đột biến.
8. Test với burst ở ranh giới cửa sổ và với nhiều instance chạy song song.

Sai lầm thường gặp

Sai lầm thường gặp

Đếm trong RAM rồi bán như quota toàn cục. Limit thật nhân theo số Pod và đổi mỗi lần autoscale. Quota hợp đồng phải ở store chung.

Sai lầm thường gặp

GET rồi SET từ ứng dụng. Hai instance đọc cùng giá trị và cùng cho qua. Gói đọc-tính-ghi vào một Lua script hoặc dùng lệnh atomic như INCR.

Sai lầm thường gặp

Trả 200 hoặc 503 khi vượt quota. Client không phân biệt được “bạn gửi quá nhiều” với “server đang hỏng”, và retry sai cách. Dùng 429 kèm Retry-After.

Sai lầm thường gặp

Tin X-Forwarded-For do client gửi. Kẻ tấn công đổi header mỗi request là có limit mới. Chỉ đọc IP do proxy tin cậy của bạn gắn vào.

Tóm tắt

Tóm tắt

• Fixed window cho tới 2× limit quanh ranh giới; demo đo được 20 request trong 10 ms với limit 10/giây.
• Token bucket là mặc định tốt: capacity quyết định burst, rate quyết định tốc độ dài hạn, chỉ cần 2 số mỗi key.
• Quota toàn cục cần store chung và thao tác atomic; Lua script trên Redis với TIME của Redis là cách gọn.
• Từ chối bằng 429 (RFC 6585) + Retry-After (RFC 9110); RateLimit header vẫn là IETF draft.
• Chọn key cẩn thận: NAT, IPv6 và X-Forwarded-For giả làm limit theo IP sai cả hai chiều.

Tự kiểm tra: (1) Với limit 100/phút theo fixed window, tối đa bao nhiêu request lọt qua trong 1 giây? (2) Vì sao token bucket trong RAM của 4 Pod không phải là limit 100/phút cho một API key? (3) Endpoint đăng nhập nên đếm thất bại theo IP hay theo tài khoản, và vì sao cần cả hai?

Tham khảo

• RFC 6585 §4 — 429 Too Many Requests
• RFC 9110 §10.2.3 — Retry-After
• draft-ietf-httpapi-ratelimit-headers — IETF Datatracker
• Scripting with Lua — Redis
• Transactions — Redis
• ngx_http_limit_req_module — NGINX
• Authentication Cheat Sheet — OWASP
• Counting things, a lot of different things — Cloudflare