6 thuật toán rate limit — đếm theo cửa sổ, nhớ log, xô token, xô rò và GCRA

"100 request mỗi phút" nghe như một câu rõ ràng. Thật ra nó có ít nhất bốn nghĩa khác nhau, và mỗi thuật toán chọn một nghĩa. Bài này cho cùng một luồng request đi qua cả 6 thuật toán trên một bộ mô phỏng có đồng hồ ảo (chạy lại ra đúng số cũ), để thấy chỗ mỗi thuật toán cho lọt, chặn oan, hay bắt người dùng chờ. Phần chạy trên nhiều server (Redis, race, lệch đồng hồ) nằm ở bài 3.

Thuật ngữ dùng trong bài
key (thứ được đếm riêng: user id, IP, API key, tenant) · window (cửa sổ thời gian đếm request) · fixed window (cửa sổ cố định: đếm trong khung 0–60s, 60–120s…, hết khung thì đặt lại) · sliding log (nhớ thời điểm của từng request, luôn đếm đúng 60 giây gần nhất) · sliding window counter (2 bộ đếm cửa sổ cố định + nội suy để ước lượng cửa sổ trượt) · token bucket (xô chứa token, nạp đều theo thời gian, mỗi request lấy 1 token) · leaky bucket (xô rò: đầu ra đều đặn; có 2 kiểu — hàng đợi bắt request chờ, và đồng hồ đo chỉ quyết định qua/chặn) · GCRA (Generic Cell Rate Algorithm — leaky bucket kiểu đồng hồ đo, chỉ nhớ 1 số) · TAT (theoretical arrival time — thời điểm "theo lịch" request kế tiếp mới nên tới) · burst (số request được dồn sát nhau một lúc) · boundary burst (lọt gấp đôi giới hạn ngay tại ranh giới 2 cửa sổ).

Kiểm chứng: tài liệu gốc đọc ngày 02/10/2026 — Redis docs (INCR, mục "Pattern: rate limiter"); nginx docs (ngx_http_limit_req_module: "The limitation is done using the 'leaky bucket' method"); blog Cloudflare "Counting things, a lot of different things" (07/06/2017, sliding window counter); Brandur Leach "Rate Limiting, Cells, and GCRA" (18/09/2015); README redis-cell; blog Stripe "Scaling your API with rate limiters" (Paul Tarjan, 30/03/2017, token bucket). Lab chạy thật: bộ mô phỏng Node 22.23.3 với thời gian ảo (labs/rate-limit/node/algorithms.mjs, 02-algorithms.mjs), output nguyên văn ở labs/rate-limit/out/02-algorithms.txt. Trace từng request ở mục 3: 07-trace.mjs → out/07-trace.txt; công thức limit_req đọc từ source nginx (ngx_http_limit_req_module.c, nhánh master, đọc ngày 26/10/2026). Số byte trong Redis lấy từ lab bài 3 (Redis 8.8.0, MEMORY USAGE).

Trả lời 30 giây

Có hai họ. Họ đếm theo cửa sổ định nghĩa "không quá N request trong W giây": fixed window rẻ nhất nhưng lọt gấp đôi ở ranh giới cửa sổ (lab: 199 request trong 2 giây với giới hạn 100/phút); sliding log đúng tuyệt đối nhưng tốn RAM theo N (1 000 phần tử ≈ 95 KB mỗi key); sliding window counter là thỏa hiệp 2 con số, sai vài phần trăm khi tải sát ngưỡng. Họ tốc độ + burst định nghĩa "trung bình r request/giây, dồn tối đa b": token bucket và GCRA cho kết quả giống hệt nhau (GCRA chỉ cần 1 số), luôn đảm bảo không quá b + r·T trong mọi khoảng T. Leaky bucket kiểu hàng đợi không chặn mà bắt chờ — lab cho thấy request phải chờ tới 60 giây, nên chỉ dùng để làm mượt traffic đi ra (gọi API đối tác), không dùng cho API nhận vào. Chọn thuật toán là chọn định nghĩa "quá nhanh" mà nghiệp vụ cần, rồi mới tới chuyện cài đặt.

1. Bài toán gốc và bối cảnh ra đời

Rate limit phải trả lời một câu cho mỗi request, trong vài micro-giây: "key này đã gửi quá nhanh chưa?". Muốn trả lời chính xác thì phải nhớ toàn bộ lịch sử request của key đó — quá đắt khi có hàng triệu key. Mọi thuật toán trong bài là một cách nén lịch sử thành vài con số, chấp nhận mất một phần độ chính xác.

Leaky bucket và GCRA đến từ mạng viễn thông: theo Brandur (2015), GCRA là thuật toán ATM Forum khuyến nghị cho mạng ATM (Asynchronous Transfer Mode) để kiểm soát luồng "cell" (gói dữ liệu cỡ cố định). Ở đó mục tiêu là đầu ra đều đặn.
Token bucket cũng từ mạng (traffic shaping), được Stripe dùng cho API công khai vì nó cho phép burst ngắn rồi giữ tốc độ trung bình.
Fixed window là cách ai cũng nghĩ ra đầu tiên với Redis: INCR + EXPIRE — chính docs Redis lấy làm ví dụ.
Sliding window counter được Cloudflare mô tả năm 2017 khi họ cần rate limit cho hàng triệu domain mà mỗi bộ đếm chỉ được tốn 2 con số.

Tối ưu cho: quyết định O(1), ít trạng thái, không cần job chạy nền. Không tối ưu cho: tính tiền chính xác từng request (dùng bảng đếm có transaction), công bằng giữa các key (bài 5), hay bảo vệ sức chịu tải của hệ thống (bài 4 — một con số cố định không biết server đang chậm đi).

2. Mô hình tư duy cốt lõi

Mỗi thuật toán là một định nghĩa khác nhau của "quá nhanh". Có hai họ:

flowchart LR
  Q["100 request/phút nghĩa là gì?"] --> W["Họ đếm theo cửa sổ
không quá N trong W giây"]
  Q --> R["Họ tốc độ + burst
trung bình r/giây, dồn tối đa b"]
  W --> FW["Fixed window
cửa sổ cắt theo đồng hồ"]
  W --> SL["Sliding log
cửa sổ trượt chính xác"]
  W --> SW["Sliding window counter
cửa sổ trượt ước lượng"]
  R --> TB["Token bucket
đếm token còn lại"]
  R --> GC["GCRA
nhớ TAT, kết quả như token bucket"]
  R --> LQ["Leaky bucket hàng đợi
không chặn, bắt chờ"]

Hệ quả cần nhớ: chỉ sliding log đảm bảo "không bao giờ quá N trong mọi cửa sổ W". Fixed window đảm bảo tối đa 2N. Token bucket với b = N đảm bảo tối đa b + r·T — với "100/phút" là 200 trong 60 giây (lab E bên dưới). Đó không phải lỗi; đó là định nghĩa. Nếu hợp đồng với đối tác ghi "không quá 100 request trong 60 giây bất kỳ", token bucket b = 100 là sai hợp đồng.

Hình 1 — Số liệu lab A (giới hạn 100/phút, 1 request mồi ở giây 0). Vạch xanh: request được qua; vạch đỏ: bị chặn. Fixed window "neo ở request đầu" của Laravel (cửa sổ mở ở request đầu tiên thay vì căn theo đồng hồ) cho cùng kết quả 199 — kẻ tấn công chỉ cần biết lúc cửa sổ hết hạn, và chính header X-RateLimit-Reset khi bị 429 nói cho họ biết.

3. Internals và quyết định thiết kế — từng thuật toán

Code dưới đây lấy nguyên từ labs/rate-limit/node/algorithms.mjs: mỗi hàm trả về một limiter (now) => true/false cho một key, now tính bằng mili-giây.

Cách đọc mục này. Mỗi thuật toán có đủ 4 phần: (1) code + câu nói mẫu khi phỏng vấn; (2) trực giác — thuật toán nén lịch sử thành cái gì và vì sao thiết kế như vậy; (3) một trace (dò từng request: trạng thái trước, phép so sánh, quyết định, trạng thái sau) kèm lời giải thích từng dòng và một hình động vẽ từ đúng các con số đó; (4) đánh đổi và bối cảnh dùng đúng / dùng sai. Mọi trace là output thật của labs/rate-limit/node/07-trace.mjs (lưu ở labs/rate-limit/out/07-trace.txt). Các hàm trong algorithms.mjs giấu trạng thái trong closure (biến nằm trong hàm con, bên ngoài không đọc được), nên script chép lại từng dòng code thành một bản "soi" để in được biến, và ở mọi request so quyết định của bản soi với hàm thật — dòng cuối output: Đã so 112 quyết định của bản soi với algorithms.mjs: khớp hết.

Để so được giữa các thuật toán, cả 6 dùng chung một luồng nhỏ, cố ý đặt một cụm request dồn về cuối khung đầu và một cụm ngay sau ranh giới 10 giây (ranh giới là chỗ các thuật toán khác nhau nhiều nhất):

Luồng chung: giới hạn 5 request / 10 giây; 12 request tại t = 2.0, 7.0, 8.0, 9.0, 9.5, 9.8, 10.1, 10.4, 10.7, 11.2, 15.0, 19.5 (giây)
Token bucket: b = 5, nạp 0,5 token/giây · GCRA: 5 / 10s, burst 5 (T = 2s, τ = 8s) · leaky queue: capacity 5, rò 0,5 request/giây (gap 2s)

3.1 Fixed window — 1 bộ đếm, đặt lại theo khung giờ

export function fixedWindow(limit, windowMs) {
  let win = -1, count = 0;
  return (now) => {
    const w = Math.floor(now / windowMs);          // khung hiện tại: 0, 1, 2… (trong Redis: tên key có số khung)
    if (w !== win) { win = w; count = 0; }
    return count < limit ? (count++, true) : false;
  };
}

Cách nói khi phỏng vấn: "Fixed window chia thời gian thành các khung cố định, ví dụ mỗi phút đồng hồ là một khung, và mỗi key chỉ giữ một bộ đếm cho khung hiện tại. Request tới thì tôi xem nó thuộc khung nào; nếu là khung mới thì bộ đếm về không. Bộ đếm còn dưới giới hạn thì cho qua và cộng một, đủ rồi thì chặn. Trên Redis nó chỉ là một lệnh tăng số kèm thời gian hết hạn, nên rẻ nhất trong các thuật toán. Cái giá là ngay quanh ranh giới hai khung, client có thể dồn gần gấp đôi giới hạn."

Trực giác — nén lịch sử thành gì. Fixed window nén toàn bộ lịch sử của một key thành đúng một câu: "từ đầu khung này tới giờ đã có bao nhiêu request được qua". Nó quên hẳn lúc nào trong khung các request đó tới — request ở giây 0,1 và request ở giây 9,9 của khung được đếm như nhau — và quên sạch mọi thứ của khung trước ngay khi sang khung mới. Thiết kế này có lý do: khung căn theo đồng hồ thì số khung floor(now / window) có thể ghép thẳng vào tên key Redis (rl:user42:173), key tự hết hạn bằng EXPIRE, không cần dọn dẹp, không cần đọc rồi ghi — một lệnh INCR là đủ, và INCR vốn nguyên tử. Toàn bộ cái giá nằm ở chỗ "quên lúc nào": hệ thống không phân biệt được 5 request rải đều với 5 request dồn vào nửa giây cuối khung.

Trace trên luồng chung (giới hạn 5 / 10 giây, khung 0 = [0s, 10s), khung 1 = [10s, 20s)):

=== 3.1 Fixed window (căn đồng hồ): w = floor(t / 10s), sang khung mới thì count = 0 ===
t (s)  | khung w | trước: win count | count < 5 ?      | sau: win count
   2.0 |       0 |  -1     0       | 0 < 5 ? có       |    0     1  QUA  (sang khung mới → count = 0)
   7.0 |       0 |   0     1       | 1 < 5 ? có       |    0     2  QUA 
   8.0 |       0 |   0     2       | 2 < 5 ? có       |    0     3  QUA 
   9.0 |       0 |   0     3       | 3 < 5 ? có       |    0     4  QUA 
   9.5 |       0 |   0     4       | 4 < 5 ? có       |    0     5  QUA 
   9.8 |       0 |   0     5       | 5 < 5 ? không    |    0     5  CHẶN
  10.1 |       1 |   0     5       | 0 < 5 ? có       |    1     1  QUA  (sang khung mới → count = 0)
  10.4 |       1 |   1     1       | 1 < 5 ? có       |    1     2  QUA 
  10.7 |       1 |   1     2       | 2 < 5 ? có       |    1     3  QUA 
  11.2 |       1 |   1     3       | 3 < 5 ? có       |    1     4  QUA 
  15.0 |       1 |   1     4       | 4 < 5 ? có       |    1     5  QUA 
  19.5 |       1 |   1     5       | 5 < 5 ? không    |    1     5  CHẶN

Năm request đầu (2,0 → 9,5s). Request lúc 2,0s có w = floor(2000 / 10000) = 0, khác win = −1 (giá trị khởi tạo, nghĩa là "chưa từng có khung nào"), nên bộ đếm đặt về 0 rồi so 0 < 5 → qua, count thành 1. Bốn request tiếp theo cùng khung 0, mỗi lần so 1 < 5, 2 < 5, 3 < 5, 4 < 5 đều đúng → count lên 5. Để ý: thuật toán không quan tâm bốn request này dồn trong 2,5 giây cuối khung (7,0 → 9,5s).
9,8s bị chặn. Vẫn khung 0, so 5 < 5 sai → chặn, count giữ nguyên 5. Đến đây hành vi còn "đúng": 5 request trong khung.
10,1s — chỗ hỏng. w = floor(10100 / 10000) = 1 khác win = 0 → count về 0, so 0 < 5 → qua. Chỉ 0,6 giây trước đó (9,5s) client vừa dùng hết 5 lượt của khung 0, vậy mà giờ lại có nguyên 5 lượt mới. Ba request 10,4s, 10,7s, 11,2s đi tiếp với count 1, 2, 3 → đều qua; 15,0s so 4 < 5 → qua, count = 5; 19,5s so 5 < 5 → chặn.
Kết quả đo được (bảng tổng kết ở mục 3.7): fixed window cho qua 10/12 request, và trong cửa sổ trượt 10 giây từ 7,0s tới 15,0s có 9 request được qua — gần gấp đôi giới hạn 5. Đây là phiên bản nhỏ của lab A (199 request trong 2 giây với giới hạn 100/phút).
Biến thể neo ở request đầu (cùng luồng, dòng fixed window (neo request đầu) ở mục 3.7): cửa sổ mở lúc request đầu tiên 2,0s và sống tới 12,0s, nên cụm 9,8 → 11,2s vẫn rơi vào cửa sổ đang đầy → bị chặn hết; cửa sổ mới mở lúc 15,0s. Kết quả 7 qua, tối đa 5 trong 10 giây bất kỳ — lần này đúng giới hạn, vì ranh giới của nó không nằm giữa cụm request. Lab A cho thấy ngược lại khi kẻ tấn công biết lúc cửa sổ hết hạn: vẫn 199. Ranh giới chỉ dời chỗ, không biến mất.

Hình 2 — Số liệu từ trace 3.1 (out/07-trace.txt). Vạch xanh: qua; vạch đỏ: chặn (9,8s và 19,5s). Đường bậc xanh dương là count: chạm 5 ở 9,5s, rơi thẳng về 0 ở ranh giới, rồi lại leo lên 5. Bộ đếm "đúng" trong từng khung, nhưng nhìn qua một cửa sổ trượt bất kỳ (ngoặc đỏ) thì 9 request lọt — đó là boundary burst, không phải lỗi cài đặt.

Đánh đổi và bối cảnh

Trạng thái: 1 số nguyên — trong Redis là 1 key INCR có TTL, 32 byte (MEMORY USAGE).
Đánh đổi: rẻ nhất, dễ hiểu nhất, đổi lại là boundary burst: 2N request lọt qua trong khoảng rất ngắn quanh ranh giới.
Biến thể "neo ở request đầu" (fixedWindowAnchored): cửa sổ mở khi request đầu tiên tới và sống đúng windowMs. Đây là cách Illuminate\Cache\RateLimiter của Laravel làm (key …:timer sống decaySeconds). Không căn theo đồng hồ nên mỗi key reset lệch nhau — đỡ cảnh mọi client cùng quay lại lúc giây :00 — nhưng ranh giới vẫn còn.
Đúng chỗ khi bản thân hợp đồng là "theo khung lịch": gói "10 000 request/tháng", quota theo ngày, giới hạn hiển thị cho khách "còn 37 lượt hôm nay". Ở đó fixed window không phải phép xấp xỉ — nó chính là định nghĩa nghiệp vụ, và khách hiểu "reset lúc 00:00". Cũng hợp với chặn thô chống lạm dụng ở khung dài (giờ/ngày), nơi gấp đôi trong vài giây không làm đau backend.
Sai chỗ: đăng nhập/OTP (kẻ tấn công canh ranh giới là gấp đôi số lần thử — mục 9), và bảo vệ sức chịu tải ở khung ngắn (2N dồn vào backend ngay ranh giới). Thêm một hệ quả vận hành: khi mọi client nhận cùng một X-RateLimit-Reset (khung căn đồng hồ), chúng cùng quay lại ở giây :00 — tải dồn theo nhịp đồng hồ.
Cạm bẫy cài đặt trên Redis (docs INCR, mẫu "rate limiter 2", đã tra lại qua Context7): INCR rồi mới EXPIRE ở lệnh riêng là race condition — client chạy INCR xong mà chưa kịp EXPIRE thì key "will be leaked until we'll see the same IP address again"; docs sửa bằng cách gói hai lệnh vào một Lua script chạy qua EVAL.
So với hàng xóm: thêm đúng một bộ đếm nữa là thành sliding window counter (3.3) — gần như cùng chi phí mà làm mượt ranh giới cho client bình thường; muốn bỏ hẳn ranh giới thì phải nhớ từng request (3.2) hoặc đổi định nghĩa sang tốc độ + burst (3.4, 3.6).

3.2 Sliding log — nhớ từng request

export function slidingLog(limit, windowMs) {
  const log = [];                                   // trong Redis: ZSET, score = thời điểm
  return (now) => {
    while (log.length && log[0] <= now - windowMs) log.shift();   // bỏ request cũ hơn 1 cửa sổ
    return log.length < limit ? (log.push(now), true) : false;
  };
}

Cách nói khi phỏng vấn: "Sliding log giữ nguyên danh sách thời điểm của những request đã được cho qua, trên Redis thường là một sorted set với điểm là thời gian. Mỗi lần có request, tôi xoá những phần tử cũ hơn một cửa sổ, đếm số còn lại; còn dưới giới hạn thì ghi request mới vào và cho qua. Vì nhớ đúng từng request nên đây là thuật toán duy nhất đảm bảo không bao giờ quá N trong bất kỳ cửa sổ W nào. Đổi lại bộ nhớ tăng theo N cho mỗi key, nên tôi chỉ dùng khi N nhỏ, như đăng nhập hay gửi OTP. Và nhớ chỉ ghi request được qua, ghi cả request bị chặn thì client sẽ bị khoá mãi."

Trực giác — nén lịch sử thành gì. Sliding log không nén gì cả: nó giữ đúng phần lịch sử còn liên quan — thời điểm của các request được qua trong W giây gần nhất — và vứt phần còn lại. Vì vậy nó trả lời câu "trong 10 giây vừa qua có bao nhiêu request?" chính xác tuyệt đối, ở mọi thời điểm, không có ranh giới nào để lợi dụng. Hai chi tiết thiết kế đáng để ý: (1) dọn "lười" — không có timer nào xoá phần tử khi nó hết hạn, lúc có request mới tới mới dọn, và vì dọn trước khi đếm nên kết quả vẫn đúng; (2) giới hạn N đồng thời là kích thước tối đa của log, nên chi phí RAM/CPU tỉ lệ thẳng với chính con số cấu hình — giới hạn càng rộng rãi càng đắt.

Trace trên luồng chung:

=== 3.2 Sliding log: bỏ mọi timestamp ≤ t − 10s, còn < 5 phần tử thì ghi t và cho qua ===
t (s)  | bỏ (≤ t−10s)  | log sau khi bỏ               | len < 5 ?     | log sau
   2.0 | -             | []                           | 0 < 5 ? có    | [2.0]  QUA 
   7.0 | -             | [2.0]                        | 1 < 5 ? có    | [2.0 7.0]  QUA 
   8.0 | -             | [2.0 7.0]                    | 2 < 5 ? có    | [2.0 7.0 8.0]  QUA 
   9.0 | -             | [2.0 7.0 8.0]                | 3 < 5 ? có    | [2.0 7.0 8.0 9.0]  QUA 
   9.5 | -             | [2.0 7.0 8.0 9.0]            | 4 < 5 ? có    | [2.0 7.0 8.0 9.0 9.5]  QUA 
   9.8 | -             | [2.0 7.0 8.0 9.0 9.5]        | 5 < 5 ? không | [2.0 7.0 8.0 9.0 9.5]  CHẶN
  10.1 | -             | [2.0 7.0 8.0 9.0 9.5]        | 5 < 5 ? không | [2.0 7.0 8.0 9.0 9.5]  CHẶN
  10.4 | -             | [2.0 7.0 8.0 9.0 9.5]        | 5 < 5 ? không | [2.0 7.0 8.0 9.0 9.5]  CHẶN
  10.7 | -             | [2.0 7.0 8.0 9.0 9.5]        | 5 < 5 ? không | [2.0 7.0 8.0 9.0 9.5]  CHẶN
  11.2 | -             | [2.0 7.0 8.0 9.0 9.5]        | 5 < 5 ? không | [2.0 7.0 8.0 9.0 9.5]  CHẶN
  15.0 | 2.0           | [7.0 8.0 9.0 9.5]            | 4 < 5 ? có    | [7.0 8.0 9.0 9.5 15.0]  QUA 
  19.5 | 7.0 8.0 9.0 9.5 | [15.0]                       | 1 < 5 ? có    | [15.0 19.5]  QUA

Đầy log (2,0 → 9,5s). Mỗi request thấy log ngắn hơn 5 → ghi vào. Sau 9,5s log là [2.0 7.0 8.0 9.0 9.5] — đủ 5.
Năm lần chặn liên tiếp (9,8 → 11,2s). Request 10,1s tính mốc t − 10s = 0,1s; phần tử cũ nhất 2,0 > 0,1 nên không bỏ được gì, log vẫn 5 phần tử → chặn. Tương tự tới 11,2s (mốc 1,2s). Đây là khác biệt cốt lõi với fixed window: ranh giới 10s không có nghĩa gì ở đây, vì cụm 7,0 → 9,5s vẫn nằm trong 10 giây gần nhất.
15,0s — dọn lười. Mốc là 15,0 − 10 = 5,0s; 2,0 ≤ 5,0 nên bị bỏ, còn 4 → qua, log thành [7.0 8.0 9.0 9.5 15.0]. Về mặt logic, phần tử 2,0 đã hết hạn từ giây 12,0, nhưng chẳng có request nào lúc đó nên nó nằm lại tới 15,0s mới bị dọn — không sai, vì dọn xong mới đếm.
19,5s — dấu "≤" quan trọng. Mốc là 9,5s, nên bỏ cả 7,0, 8,0, 9,0 và 9,5 (đúng 10 giây trước cũng tính là đã ra khỏi cửa sổ — cửa sổ là nửa mở (9,5s; 19,5s]). Còn [15.0] → qua.
Kết quả: 7/12 qua, tối đa 5 trong mọi cửa sổ 10 giây — chặt nhất trong 6 thuật toán (mục 3.7).
"Tiếng vọng" của burst. Mỗi chỗ trống trong log mở ra đúng W giây sau khi một request được qua. Nên cụm 7,0 → 9,5s sẽ "mở lại" thành 4 chỗ trống ở 17,0 → 19,5s, đúng hình dạng cụm cũ. Đó là lý do ở lab B (quá tải đều) sliding log cho ra cùng nhịp 34 33 33 0 0 0 như fixed window: chính xác không có nghĩa là mượt.

Biến thể sai hay gặp — ghi request vào log trước rồi mới đếm (kể cả request bị chặn):

--- 3.2b Biến thể SAI (viết riêng ở đây, không có trong algorithms.mjs): ghi cả request bị chặn vào log ("ZADD trước rồi đếm") ---
1 request mỗi giây từ t = 0 tới 14s, giới hạn 5 / 10s
đúng (chỉ ghi request được qua): ✓✓✓✓✓✗✗✗✗✗✓✓✓✓✓
sai  (ghi cả request bị chặn):   ✓✓✓✓✓✗✗✗✗✗✗✗✗✗✗   ← log luôn có 10 phần tử, không bao giờ vơi khi client còn gửi

Bản đúng cho qua lại từ giây 10 vì 5 phần tử đầu (0 → 4s) lần lượt hết hạn. Bản sai ghi luôn 5 request bị chặn ở giây 5 → 9, nên tới giây 10 trong 10 giây gần nhất vẫn có 10 phần tử ≥ 5 → chặn tiếp, và mỗi lần chặn lại ghi thêm một phần tử. Client còn gửi đều là còn bị chặn — đúng hiện tượng lab bài 3 đo trên Redis (10 0 0 0 0 0).

Hình 3 — Số liệu từ trace 3.2. Đường bậc là số request thật nằm trong 10 giây gần nhất: nó chỉ đi xuống khi một request cũ ra khỏi cửa sổ, không bao giờ "về 0" theo đồng hồ. Trong code, phần tử hết hạn chỉ bị xoá khi có request tới (2,0 bị dọn lúc 15,0s), nhưng vì dọn xong mới đếm nên quyết định vẫn đúng như đường bậc.

Đánh đổi và bối cảnh

Trạng thái: N timestamp. Redis đo được: ZSET 100 phần tử 3 225 byte (encoding listpack), 1 000 phần tử 95 704 byte, 10 000 phần tử 1 070 248 byte (encoding skiplist — ZSET quá 128 phần tử đổi sang cấu trúc tốn RAM hơn nhiều). 1 triệu client × giới hạn 1 000/phút ≈ 89 GB RAM.
Đánh đổi: đúng tuyệt đối, đổi lại RAM và CPU tăng theo N. Hợp với N nhỏ: đăng nhập, OTP, gửi SMS (vài lần/giờ).
Chỉ ghi request được qua. Cách viết "ZADD trước rồi đếm" ghi cả request bị chặn → client cứ gửi là log không bao giờ vơi → bị chặn vĩnh viễn trong lúc còn gửi (lab bài 3: 10 0 0 0 0 0 so với 10 10 10 10 10 10; trace 3.2b ở trên tái hiện cùng hiện tượng).
Đúng chỗ: N nhỏ mà mỗi lần lọt đều đắt — thử mật khẩu, OTP, đặt lại mật khẩu, gửi SMS tốn tiền; hợp đồng với đối tác ghi rõ "không quá N trong W giây bất kỳ" với N nhỏ. Có thêm lợi ích phụ: log chính là bằng chứng — support trả lời được "bạn đã gửi 5 lần lúc 2,0 / 7,0 / 8,0 / 9,0 / 9,5".
Sai chỗ: N lớn hoặc key nóng (mỗi request là xoá theo khoảng + đếm + ghi trên ZSET); và khi mục tiêu là làm mượt tải cho backend — "tiếng vọng" ở trên cho thấy nó lặp lại nguyên hình dạng burst mỗi W giây.
So với hàng xóm: sliding window counter (3.3) là bản "nén" của sliding log xuống 2 số, chấp nhận sai; token bucket/GCRA đổi hẳn câu hỏi để vừa đúng vừa rẻ. Muốn "đúng tuyệt đối theo cửa sổ trượt" thì không có đường tắt: phải nhớ từng request (mục 10).

3.3 Sliding window counter — 2 con số + nội suy

export function slidingWindowCounter(limit, windowMs) {
  let win = 0, prev = 0, curr = 0;
  return (now) => {
    const w = Math.floor(now / windowMs);
    if (w !== win) { prev = w === win + 1 ? curr : 0; curr = 0; win = w; }
    const elapsed = (now - w * windowMs) / windowMs;            // đã đi được bao nhiêu phần cửa sổ hiện tại
    return prev * (1 - elapsed) + curr < limit ? (curr++, true) : false;
  };
}

Ví dụ của Cloudflare: giới hạn 50/phút, phút trước 42 request, phút này 18 request, đang ở giây 15 → 42 × (60−15)/60 + 18 = 49,5. Giả định ngầm: request của cửa sổ trước rải đều. Khi chúng dồn về cuối cửa sổ trước, ước lượng thấp hơn thực tế và cho lọt. Lab D đo độ sai này (mục 4).

Cách nói khi phỏng vấn: "Sliding window counter chỉ giữ hai bộ đếm: số request của khung trước và của khung hiện tại. Để ước lượng số request trong một phút trượt, tôi lấy số của khung trước nhân với phần khung trước còn nằm trong cửa sổ trượt, rồi cộng số của khung hiện tại. Ví dụ đang ở giây mười lăm thì khung trước còn ba phần tư nằm trong cửa sổ, nên tính ba phần tư số request của nó. Cách này giả định request khung trước rải đều, nên khi chúng dồn về một phía thì ước lượng lệch, nhưng chỉ tốn hai con số mỗi key và hết hẳn kiểu lọt gấp đôi tức thời ở ranh giới."

Trực giác — nén lịch sử thành gì. Đây là sliding log bị nén có tổn thất: thay vì nhớ khung trước có 5 request ở đâu, nó chỉ nhớ "khung trước có 5", rồi giả vờ 5 request đó rải đều trên 10 giây. Khi cửa sổ trượt đã đi được elapsed phần của khung hiện tại, phần khung trước còn nằm trong cửa sổ là 1 − elapsed, nên "số request khung trước còn tính" là prev × (1 − elapsed) — một đường thẳng giảm dần từ prev về 0. Ước lượng đúng khi giả định rải đều đúng; sai số luôn nằm trong khoảng [−prev, +prev], và chỉ lật quyết định khi client sống sát ngưỡng (lab D). Cloudflare chọn nó vì ở quy mô hàng triệu key, 2 con số mỗi key và cộng/nhân đơn giản là thứ quyết định, còn phần lớn nguồn ở rất xa ngưỡng nên sai số không bao giờ hiện ra.

Trace trên luồng chung — cột cuối là số request thuật toán đã cho qua nằm trong 10 giây gần nhất (thứ sliding log sẽ đếm), để thấy chỗ ước lượng lệch:

--- 3.3a Luồng chung ---
t (s)  | w | prev curr | elapsed | ước lượng = prev × (1 − elapsed) + curr  | < 5 ?  | curr sau | đếm thật 10s gần nhất
   2.0 | 0 |    0    0 |    0.20 | 0 × 0.80 + 0 = 0.00                      | có     |        1 |   0  QUA 
   7.0 | 0 |    0    1 |    0.70 | 0 × 0.30 + 1 = 1.00                      | có     |        2 |   1  QUA 
   8.0 | 0 |    0    2 |    0.80 | 0 × 0.20 + 2 = 2.00                      | có     |        3 |   2  QUA 
   9.0 | 0 |    0    3 |    0.90 | 0 × 0.10 + 3 = 3.00                      | có     |        4 |   3  QUA 
   9.5 | 0 |    0    4 |    0.95 | 0 × 0.05 + 4 = 4.00                      | có     |        5 |   4  QUA 
   9.8 | 0 |    0    5 |    0.98 | 0 × 0.02 + 5 = 5.00                      | không  |        5 |   5  CHẶN
  10.1 | 1 |    5    0 |    0.01 | 5 × 0.99 + 0 = 4.95                      | có     |        1 |   5  QUA   ← cho qua SAI (đã đủ 5 trong 10s) (sang khung 1: prev = 5, curr = 0)
  10.4 | 1 |    5    1 |    0.04 | 5 × 0.96 + 1 = 5.80                      | không  |        1 |   6  CHẶN
  10.7 | 1 |    5    1 |    0.07 | 5 × 0.93 + 1 = 5.65                      | không  |        1 |   6  CHẶN
  11.2 | 1 |    5    1 |    0.12 | 5 × 0.88 + 1 = 5.40                      | không  |        1 |   6  CHẶN
  15.0 | 1 |    5    1 |    0.50 | 5 × 0.50 + 1 = 3.50                      | có     |        2 |   5  QUA   ← cho qua SAI (đã đủ 5 trong 10s)
  19.5 | 1 |    5    2 |    0.95 | 5 × 0.05 + 2 = 2.25                      | có     |        3 |   2  QUA 
→ max trong 10s trượt bất kỳ (request đã qua): 6

Khung 0 (2,0 → 9,8s): prev = 0 nên ước lượng chỉ là curr — hành vi giống hệt fixed window: qua 5, chặn 9,8s với 0 × 0,02 + 5 = 5,00, không nhỏ hơn 5.
10,1s — sang khung 1. prev nhận giá trị curr cũ là 5, curr = 0. elapsed = (10,1 − 10)/10 = 0,01, nên ước lượng 5 × 0,99 + 0 = 4,95 < 5 → qua. Thật ra trong 10 giây gần nhất (0,1s; 10,1s] đã có đủ 5 request (2,0 7,0 8,0 9,0 9,5) — đây là request thứ 6. Thuật toán "tưởng" 0,05 request của khung trước (phần rơi vào [0s; 0,1s]) đã ra khỏi cửa sổ, trong khi thực tế khoảng đó trống trơn. Sai lệch nhỏ, nhưng đúng sát vạch nên đủ để lật quyết định.
10,4 → 11,2s — vẫn làm mượt ranh giới. 10,4s: 5 × 0,96 + 1 = 5,80 → chặn; 10,7s: 5 × 0,93 + 1 = 5,65 → chặn; 11,2s: 5 × 0,88 + 1 = 5,40 → chặn. So với fixed window cho qua cả 4 request này, SWC chỉ cho qua 1 — khoản "khung trước" đè lên khung mới chính là thứ chặn boundary burst.
15,0s: 5 × 0,50 + 1 = 3,50 → qua, nhưng đếm thật lại là 5 (7,0 8,0 9,0 9,5 10,1) → lần lọt thứ hai. Giả định rải đều nói "nửa khung trước đã trôi qua thì nửa số request đã ra khỏi cửa sổ", trong khi cả 4 request 7,0 → 9,5s đều còn nằm trong (5s; 15s].
Kết quả: 8/12 qua, tối đa 6 trong 10 giây — tệ hơn sliding log 1 request, tốt hơn fixed window 3 request.

Hai kịch bản riêng cho thấy sai số đi theo cả hai chiều, tuỳ request của khung trước dồn về phía nào:

--- 3.3b Khung trước dồn về CUỐI khung (ước lượng thấp hơn thật → cho qua sai) ---
t (s)  | w | prev curr | elapsed | ước lượng = prev × (1 − elapsed) + curr  | < 5 ?  | curr sau | đếm thật 10s gần nhất
   9.0 | 0 |    0    0 |    0.90 | 0 × 0.10 + 0 = 0.00                      | có     |        1 |   0  QUA 
   9.2 | 0 |    0    1 |    0.92 | 0 × 0.08 + 1 = 1.00                      | có     |        2 |   1  QUA 
   9.4 | 0 |    0    2 |    0.94 | 0 × 0.06 + 2 = 2.00                      | có     |        3 |   2  QUA 
   9.6 | 0 |    0    3 |    0.96 | 0 × 0.04 + 3 = 3.00                      | có     |        4 |   3  QUA 
   9.8 | 0 |    0    4 |    0.98 | 0 × 0.02 + 4 = 4.00                      | có     |        5 |   4  QUA 
  12.0 | 1 |    5    0 |    0.20 | 5 × 0.80 + 0 = 4.00                      | có     |        1 |   5  QUA   ← cho qua SAI (đã đủ 5 trong 10s) (sang khung 1: prev = 5, curr = 0)
  14.0 | 1 |    5    1 |    0.40 | 5 × 0.60 + 1 = 4.00                      | có     |        2 |   6  QUA   ← cho qua SAI (đã đủ 5 trong 10s)
  15.0 | 1 |    5    2 |    0.50 | 5 × 0.50 + 2 = 4.50                      | có     |        3 |   7  QUA   ← cho qua SAI (đã đủ 5 trong 10s)
  16.0 | 1 |    5    3 |    0.60 | 5 × 0.40 + 3 = 5.00                      | không  |        3 |   8  CHẶN
  17.0 | 1 |    5    3 |    0.70 | 5 × 0.30 + 3 = 4.50                      | có     |        4 |   8  QUA   ← cho qua SAI (đã đủ 5 trong 10s)
→ max trong 10s trượt bất kỳ (request đã qua): 9

Dồn cuối khung trước → đánh giá thấp → cho qua sai. 5 request ở 9,0 → 9,8s đều còn nằm trong 10 giây gần nhất tới tận 19,0s, nhưng SWC "xả" chúng theo đường thẳng: 12,0s chỉ tính 5 × 0,80 = 4,00, 14,0s tính 5 × 0,60 + 1 = 4,00, 15,0s tính 5 × 0,50 + 2 = 4,50 — cả ba đều qua dù đếm thật đã là 5, 6, 7.
16,0s mới chặn được: 5 × 0,40 + 3 = 5,00, không nhỏ hơn 5. Nhưng 17,0s ước lượng lại tụt xuống 5 × 0,30 + 3 = 4,50 → qua lần thứ tư, đếm thật lúc đó là 8.
Hậu quả: 9 request trong 10 giây trượt với giới hạn 5 — gần 2N. Đây là trường hợp xấu nhất mà bảng mục 4 ghi "xấu nhất 2N trên cửa sổ 60s"; thực tế nó cần đúng kiểu traffic "dồn cuối khung rồi đều đặn sau đó" như lab E.

--- 3.3c Khung trước dồn về ĐẦU khung (ước lượng cao hơn thật → chặn oan) ---
t (s)  | w | prev curr | elapsed | ước lượng = prev × (1 − elapsed) + curr  | < 5 ?  | curr sau | đếm thật 10s gần nhất
   0.2 | 0 |    0    0 |    0.02 | 0 × 0.98 + 0 = 0.00                      | có     |        1 |   0  QUA 
   0.4 | 0 |    0    1 |    0.04 | 0 × 0.96 + 1 = 1.00                      | có     |        2 |   1  QUA 
   0.6 | 0 |    0    2 |    0.06 | 0 × 0.94 + 2 = 2.00                      | có     |        3 |   2  QUA 
   0.8 | 0 |    0    3 |    0.08 | 0 × 0.92 + 3 = 3.00                      | có     |        4 |   3  QUA 
   1.0 | 0 |    0    4 |    0.10 | 0 × 0.90 + 4 = 4.00                      | có     |        5 |   4  QUA 
  12.0 | 1 |    5    0 |    0.20 | 5 × 0.80 + 0 = 4.00                      | có     |        1 |   0  QUA  (sang khung 1: prev = 5, curr = 0)
  12.5 | 1 |    5    1 |    0.25 | 5 × 0.75 + 1 = 4.75                      | có     |        2 |   1  QUA 
  13.0 | 1 |    5    2 |    0.30 | 5 × 0.70 + 2 = 5.50                      | không  |        2 |   2  CHẶN  ← chặn OAN (mới 2 trong 10s)
  14.0 | 1 |    5    2 |    0.40 | 5 × 0.60 + 2 = 5.00                      | không  |        2 |   2  CHẶN  ← chặn OAN (mới 2 trong 10s)
  16.0 | 1 |    5    2 |    0.60 | 5 × 0.40 + 2 = 4.00                      | có     |        3 |   2  QUA 
→ max trong 10s trượt bất kỳ (request đã qua): 5

Dồn đầu khung trước → đánh giá cao → chặn oan. 5 request ở 0,2 → 1,0s đã ra khỏi cửa sổ từ giây 11,0, nhưng SWC vẫn tính 5 × 0,80 = 4,00 ở 12,0s và 5 × 0,70 + 2 = 5,50 ở 13,0s → chặn dù 10 giây gần nhất mới có 2 request. 14,0s: 5 × 0,60 + 2 = 5,00 → chặn oan lần nữa. Phải tới 16,0s (5 × 0,40 + 2 = 4,00) mới cho qua.
Chiều này an toàn cho backend nhưng tệ cho trải nghiệm: client làm đúng vẫn ăn 429. Lab D đo cả hai chiều trên traffic ngẫu nhiên: ở mức 1× giới hạn, 13,273% cho qua sai và 2,359% chặn sai.

Hình 4 — Số liệu từ trace 3.3a. Trong khung 0 hai đường trùng nhau (chưa có khung trước để đoán). Sang khung 1, đường vàng giảm tuyến tính với độ dốc prev / W = 0,5 request/giây — giả định "khung trước rải đều" — trong khi đường xanh chỉ giảm khi request thật hết hạn (12s, 17s, 18s, 19s). Chỗ đường vàng nằm dưới vạch 5 mà đường xanh đã ở 5 là chỗ cho qua sai. Khung xanh mờ là cửa sổ trượt 10 giây đang được ước lượng.

Đánh đổi và bối cảnh

Trạng thái: 2 số (bộ đếm khung trước, khung này); trên Redis là 2 key INCR có TTL — đọc 2, ghi 1.
Đúng chỗ: rate limit ở biên mạng/gateway cho rất nhiều key (IP, domain), nơi mục tiêu là "chặn kẻ vượt xa ngưỡng" và một vài phần trăm sai sát vạch không ai nhận ra — đúng bối cảnh Cloudflare 2017. Khi đã dùng fixed window và chỉ muốn bỏ boundary burst mà không đổi định nghĩa với khách, đây là bước nâng cấp rẻ nhất.
Sai chỗ: N nhỏ và mỗi lần lọt đều đắt (đăng nhập: trace 3.3b cho 9 lần trong khi giới hạn 5); hợp đồng "không quá N trong W bất kỳ"; tính tiền. Và đừng mô tả nó với khách là "cửa sổ trượt chính xác" — client sống sát ngưỡng sẽ thấy 429 "vô lý" (trace 3.3c).
So với hàng xóm: so với fixed window, thêm 1 số mà hết lọt 2N tức thời; so với sliding log, từ N số xuống 2 số nhưng mất tính chính xác; so với token bucket, vẫn không có núm burst riêng — burst luôn bằng chính N.

3.4 Token bucket — xô token nạp đều

export function tokenBucket(capacity, perSec) {
  let tokens = capacity, last = 0;
  return (now) => {
    tokens = Math.min(capacity, tokens + ((now - last) * perSec) / 1000);   // nạp "lười": tính bù lúc có request
    last = now;
    return tokens >= 1 ? (tokens--, true) : false;
  };
}

Cách nói khi phỏng vấn: "Token bucket coi mỗi key là một cái xô chứa tối đa b token, token được nạp đều với tốc độ r mỗi giây, mỗi request lấy một token, xô cạn thì chặn. Tôi không chạy job nạp token định kỳ mà nạp kiểu lười: khi request tới mới tính thời gian đã trôi từ lần trước nhân với tốc độ, cộng vào, nhưng không vượt sức chứa. Nên mỗi key chỉ cần hai con số là số token và thời điểm cập nhật cuối. Điểm mạnh là tách hai thứ: b quyết định được dồn bao nhiêu một lúc, r quyết định tốc độ trung bình, và nó đảm bảo trong mọi khoảng T không quá b cộng r nhân T request."

Trực giác — nén lịch sử thành gì. Token bucket nén lịch sử thành một khoản tín dụng: số token là "client còn được dồn bao nhiêu request ngay bây giờ". Request tiêu tín dụng, thời gian trả lại tín dụng với tốc độ r, và tín dụng có trần b. Chính cái trần làm thuật toán quên: một khi xô đầy, mọi lịch sử trước đó không còn ảnh hưởng gì — client im 5 phút và client im 5 ngày được đối xử như nhau. Đó là định nghĩa "tốc độ + burst" chứ không phải "đếm trong cửa sổ": thay vì hỏi "W giây qua có bao nhiêu request", nó hỏi "client có đang đi nhanh hơn r lâu đủ để dùng hết b không". Hai núm tách bạch là lý do nó hợp với API công khai (Stripe 2017 dùng token bucket): b đặt theo hành vi client thật (một lần mở trang), r đặt theo sức chịu của backend — không phải thỏa hiệp một con số N cho cả hai việc.

Trace trên luồng chung (b = 5, r = 0,5 token/giây — cùng "5 trong 10 giây" về trung bình):

=== 3.4 Token bucket (b = 5, nạp 0,5 token/giây): tokens = min(5, tokens + Δt × 0,5), còn ≥ 1 thì lấy 1 ===
t (s)  | trước: tokens last | nạp = Δt × 0,5   | sau nạp (trần 5) | ≥ 1 ?  | tokens sau
   2.0 |   5.00   0.0s      | 2.0 × 0,5 = 1.00 | 6.00 → 5.00      | có     |   4.00  QUA 
   7.0 |   4.00   2.0s      | 5.0 × 0,5 = 2.50 | 6.50 → 5.00      | có     |   4.00  QUA 
   8.0 |   4.00   7.0s      | 1.0 × 0,5 = 0.50 | 4.50             | có     |   3.50  QUA 
   9.0 |   3.50   8.0s      | 1.0 × 0,5 = 0.50 | 4.00             | có     |   3.00  QUA 
   9.5 |   3.00   9.0s      | 0.5 × 0,5 = 0.25 | 3.25             | có     |   2.25  QUA 
   9.8 |   2.25   9.5s      | 0.3 × 0,5 = 0.15 | 2.40             | có     |   1.40  QUA 
  10.1 |   1.40   9.8s      | 0.3 × 0,5 = 0.15 | 1.55             | có     |   0.55  QUA 
  10.4 |   0.55  10.1s      | 0.3 × 0,5 = 0.15 | 0.70             | không  |   0.70  CHẶN
  10.7 |   0.70  10.4s      | 0.3 × 0,5 = 0.15 | 0.85             | không  |   0.85  CHẶN
  11.2 |   0.85  10.7s      | 0.5 × 0,5 = 0.25 | 1.10             | có     |   0.10  QUA 
  15.0 |   0.10  11.2s      | 3.8 × 0,5 = 1.90 | 2.00             | có     |   1.00  QUA 
  19.5 |   1.00  15.0s      | 4.5 × 0,5 = 2.25 | 3.25             | có     |   2.25  QUA

2,0s — trần đã làm việc. Xô khởi tạo đầy (5 token, last = 0). Nạp 2,0 × 0,5 = 1,00 → 6,00, vượt trần → cắt về 5,00, lấy 1 → còn 4,00. Token "nạp thừa" bị đổ đi — đây là chỗ thuật toán quên quá khứ.
7,0s: im 5 giây → nạp 5,0 × 0,5 = 2,50 → 6,50 → cắt về 5,00 → còn 4,00. Từ 8,0 tới 10,1s request tới nhanh hơn tốc độ nạp nên xô vơi dần: 8,0s 4,00 + 0,50 = 4,50 → 3,50; 9,0s → 3,00; 9,5s 3,00 + 0,25 = 3,25 → 2,25; 9,8s 2,25 + 0,15 = 2,40 → 1,40; 10,1s 1,40 + 0,15 = 1,55 → 0,55.
9,8s và 10,1s được qua — fixed window và sliding log đều chặn 9,8s. Token bucket cho dồn 6 request trong 3,1 giây (7,0 → 10,1s) vì client đã "để dành" được tín dụng từ quãng im lặng trước đó; đó chính là ý nghĩa của b.
10,4s và 10,7s bị chặn: 0,55 + 0,15 = 0,70 rồi 0,70 + 0,15 = 0,85, đều < 1. Khi chặn, token không bị trừ nhưng last vẫn cập nhật — không mất gì, vì phần nạp đã được cộng vào tokens. Từ dòng 10,4s cũng tính được header "chờ bao lâu": còn thiếu 1 − 0,70 = 0,30 token, nạp 0,5 token/giây → 0,6 giây (tính tay từ trace, không có trong output).
11,2s: 0,85 + 0,25 = 1,10 ≥ 1 → qua, còn 0,10. Rồi 15,0s 0,10 + 1,90 = 2,00 → qua; 19,5s 1,00 + 2,25 = 3,25 → qua.
Đảm bảo: 10/12 qua, tối đa 8 trong 10 giây trượt — vượt "5 trong 10 giây" nhưng nằm trong cam kết b + r·T = 5 + 0,5 × 10 = 10. Nếu đối tác đòi "không quá 5 trong 10 giây bất kỳ" thì cấu hình này sai hợp đồng — đúng như cảnh báo ở mục 2.

Hình 5 — Token bucket không cần job nạp chạy nền: lúc request tới mới tính bù số token đã "rơi" vào xô. Burst bằng đúng sức chứa của xô; sau burst, tốc độ được phục vụ bằng tốc độ nạp. Lab C dùng đúng cơ chế này: xô b = 1 chặn 11/12 request của một lần mở trang, xô b = 20 cho qua cả 12.

Đánh đổi và bối cảnh

Hai tham số tách bạch: capacity = burst tối đa, perSec = tốc độ trung bình. Đảm bảo: trong mọi khoảng T, không quá capacity + perSec × T request.
Nạp lười (lazy refill): không có job nào "rót" token định kỳ; lúc request tới mới tính bù theo thời gian đã trôi. Nhờ vậy lưu được trong Redis bằng 1 hash 2 field (68 byte): số token và thời điểm cập nhật.
Phải đọc–tính–ghi nguyên tử: khác fixed window (một INCR), token bucket cần đọc 2 field, tính, ghi lại — trên Redis phải gói trong Lua, không thì 2 request song song cùng đọc "còn 1 token" và cùng qua (race, bài 3).
Số thực ở đúng biên: trace 3.6b cho thấy cùng luồng nhưng request thứ 10 tới lúc 11,0s thì 0,85 + 0,15 ra 0.99999999999999989 → bị chặn, trong khi về lý thuyết là đúng 1 token. Cài đặt thật nên lưu token theo đơn vị nguyên (nginx lưu "1/1000 request", xem 3.5) hoặc dùng GCRA tính bằng mili-giây nguyên. Hành vi tương tự trong các script Lua phổ biến: chưa verify.
Đúng chỗ: mặc định cho API nhận vào (public API, mobile, SPA) — burst thật của client được phục vụ ngay, tốc độ trung bình vẫn bị giữ; header "còn lại" và "chờ bao lâu" tính trực tiếp từ số token.
Sai chỗ: hợp đồng kiểu cửa sổ trượt (cần sliding log); khi cần đầu ra đều cho một hệ thống phía sau không chịu được burst (cần leaky bucket hàng đợi — 3.5); và khi đặt b = 1 cho client là trình duyệt (lab C: 11/12 request bị chặn).

3.5 Leaky bucket — hai nghĩa khác nhau

Kiểu hàng đợi (shaping): request vào hàng đợi, xô "rò" ra đều đặn. Không chặn khi còn chỗ — nhưng bắt request chờ.

export function leakyQueue(capacity, perSec) {
  const gap = 1000 / perSec;
  let nextOut = 0;                                  // thời điểm xô rò được request kế tiếp
  return (now) => {
    const out = Math.max(nextOut, now);
    if ((out - now) / gap >= capacity) return false; // hàng đợi đầy → chặn
    nextOut = out + gap;
    return out - now;                               // số ms request này phải chờ
  };
}

Cách nói khi phỏng vấn: "Leaky bucket kiểu hàng đợi nhận request vào một hàng có sức chứa giới hạn, rồi xả ra với nhịp cố định, ví dụ cứ hai giây một request. Tôi chỉ cần nhớ thời điểm sớm nhất xô có thể xả request kế tiếp; request mới tới sẽ được xếp vào lúc đó, và thời gian chờ của nó là khoảng cách từ bây giờ tới lúc đó. Nếu phía trước đã có đủ số chỗ bằng sức chứa thì chặn. Kết quả là đầu ra đều tuyệt đối, nhưng cái giá trả bằng độ trễ, nên tôi dùng nó để làm mượt traffic đi ra đối tác, không đặt trước API mà người dùng đang chờ."

Trực giác — nén lịch sử thành gì. Kiểu hàng đợi nén lịch sử thành một mốc thời gian nextOut: "xô đang bận tới lúc nào". Mọi request được nhận đều đi ra đúng nhịp gap = 1/r, nên câu hỏi không còn là "qua hay chặn" mà là "chờ bao lâu"; chỉ chặn khi hàng chờ đã dài quá capacity khoảng gap. Nó là thuật toán duy nhất trong bài đảm bảo đầu ra (thứ backend hay đối tác nhìn thấy) đều đặn — các thuật toán khác chỉ quyết định cho qua, còn những gì được qua thì cứ thế dồn vào backend. Đúng với nguồn gốc viễn thông ở mục 1: ở đó mục tiêu là đầu ra đều đặn, không phải trả lời nhanh cho người gửi.

Trace trên luồng chung (capacity 5, rò 0,5 request/giây → gap 2 giây):

=== 3.5 Leaky bucket hàng đợi (capacity 5, gap 2s): out = max(nextOut, t), chờ = out − t, chờ/gap ≥ 5 thì chặn ===
t (s)  | nextOut trước | out    | chờ = out − t | chờ/gap < 5 ?      | nextOut sau | rời xô lúc
   2.0 |          0.0s |   2.0s |          0.0s | 0.00 < 5 ? có      |        4.0s |   2.0s  NHẬN
   7.0 |          4.0s |   7.0s |          0.0s | 0.00 < 5 ? có      |        9.0s |   7.0s  NHẬN
   8.0 |          9.0s |   9.0s |          1.0s | 0.50 < 5 ? có      |       11.0s |   9.0s  NHẬN
   9.0 |         11.0s |  11.0s |          2.0s | 1.00 < 5 ? có      |       13.0s |  11.0s  NHẬN
   9.5 |         13.0s |  13.0s |          3.5s | 1.75 < 5 ? có      |       15.0s |  13.0s  NHẬN
   9.8 |         15.0s |  15.0s |          5.2s | 2.60 < 5 ? có      |       17.0s |  15.0s  NHẬN
  10.1 |         17.0s |  17.0s |          6.9s | 3.45 < 5 ? có      |       19.0s |  17.0s  NHẬN
  10.4 |         19.0s |  19.0s |          8.6s | 4.30 < 5 ? có      |       21.0s |  19.0s  NHẬN
  10.7 |         21.0s |  21.0s |         10.3s | 5.15 < 5 ? không   |       21.0s |      -  CHẶN
  11.2 |         21.0s |  21.0s |          9.8s | 4.90 < 5 ? có      |       23.0s |  21.0s  NHẬN
  15.0 |         23.0s |  23.0s |          8.0s | 4.00 < 5 ? có      |       25.0s |  23.0s  NHẬN
  19.5 |         25.0s |  25.0s |          5.5s | 2.75 < 5 ? có      |       27.0s |  25.0s  NHẬN

2,0s và 7,0s đi ngay: nextOut nằm trong quá khứ (0,0s rồi 4,0s) nên out = max(nextOut, t) = t, chờ 0. Sau mỗi request nextOut = out + 2: 4,0s, rồi 9,0s.
Hàng đợi bắt đầu dài ra (8,0 → 10,4s). 8,0s: xô bận tới 9,0s → out = 9,0, chờ 9,0 − 8,0 = 1,0s, tức 0,5 khoảng gap. 9,0s: out 11,0s, chờ 2,0s. 9,5s: out 13,0s, chờ 3,5s. 9,8s: out 15,0s, chờ 5,2s. 10,1s: out 17,0s, chờ 6,9s. 10,4s: out 19,0s, chờ 8,6s — 8,6 / 2 = 4,30 < 5 → vẫn nhận. Mỗi request tới sớm hơn nhịp 2 giây nên thời gian chờ cộng dồn.
10,7s bị chặn: out sẽ là 21,0s, chờ 21,0 − 10,7 = 10,3s → 5,15 khoảng gap ≥ 5 → hàng đầy. nextOut giữ nguyên 21,0s.
11,2s lại được nhận dù chỉ 0,5 giây sau: chờ 21,0 − 11,2 = 9,8s → 4,90 < 5. Trong 0,5 giây đó hàng đợi đã "rò" bớt 0,25 chỗ — vừa đủ để lọt dưới ngưỡng. Request này phải chờ 9,8 giây, lâu nhất trong trace.
15,0s và 19,5s: chờ 23,0 − 15,0 = 8,0s và 25,0 − 19,5 = 5,5s — dù hai request này tới thưa, chúng vẫn chịu hậu quả của cụm trước.
Kết quả: nhận 11/12 — nhiều nhất trong 6 thuật toán — và cột "rời xô lúc" là 2,0, 7,0, 9,0, 11,0, … 25,0s: từ 7,0s trở đi đúng mỗi 2 giây một request, nên đầu ra không bao giờ quá 5 trong 10 giây (tính từ cột đó). Cái giá: request chờ tới 9,8 giây. Với một API mà client timeout sau 5 giây, một nửa số request "được nhận" này là việc làm phí.

Hình 6 — Số liệu từ trace 3.5 (cột "chờ" và "rời xô lúc"). Mỗi đường xiên là một request: càng xiên càng chờ lâu. Cụm tới dồn ở hàng trên biến thành một hàng đều tăm tắp ở hàng dưới — đó là "shaping". Cùng luồng này, token bucket và GCRA không bắt ai chờ: 10,4s và 10,7s bị chặn ngay.

Kiểu đồng hồ đo (policing): không có hàng đợi, chỉ hỏi "nếu xô rò đều thì request này có làm tràn không?". Đây chính là GCRA. nginx limit_req là lai giữa hai kiểu: không có nodelay thì giữ request lại (hàng đợi), có nodelay thì cho qua ngay hoặc chặn (đồng hồ đo) — lab nginx ở bài 5.

nginx thật sự lưu gì. Đọc ngx_http_limit_req_module.c (nhánh master trên GitHub, file sửa lần cuối 28/03/2021): mỗi key là một node có đúng 2 số — last (mili-giây) và excess ("mực nước" trong xô, đơn vị 1/1000 request, comment trong code: "1 corresponds to 0.001 r/s"). Mỗi request: excess = excess_cũ − rate × ms / 1000 + 1000 (rò theo thời gian đã trôi, cộng 1 request mới), âm thì về 0; excess > burst → từ chối; còn lại thì nếu excess > delay request bị giữ (excess − delay) × 1000 / rate mili-giây bằng một timer. nodelay trong code chỉ là đặt delay thành số rất lớn. Nghĩa là nginx không có cấu trúc hàng đợi: nó là một đồng hồ đo (giống GCRA) tính ra thời gian chờ rồi hẹn giờ cho request đi tiếp. Docs (tra qua Context7) mô tả cùng hành vi bằng lời: "Excessive requests are delayed until their number exceeds the maximum burst size in which case the request is terminated with an error", và "The delay parameter (1.15.7) specifies a limit at which excessive requests become delayed. Default value is zero, i.e. all excessive requests are delayed." Script trace chép công thức đó (cột nginx-port — bản chép, không phải nginx chạy thật) và đặt cạnh hai hàm trong algorithms.mjs:

=== 3.5b So với nginx limit_req: 10 request CÙNG LÚC (t = 0), rate = 10r/s (1 request / 100ms) ===
Cột nginx-port: chép công thức trong ngx_http_limit_req_module.c (đơn vị 1/1000 request):
  excess = max(0, excess_cũ − rate × ms/1000 + 1000); excess > burst → 429; còn lại chờ (excess − delay) × 1000 / rate ms nếu excess > delay

burst=5 (không nodelay)
  nginx-port:  0ms(ex 0) 100ms(ex 1) 200ms(ex 2) 300ms(ex 3) 400ms(ex 4) 500ms(ex 5) 429(ex 6) 429(ex 6) 429(ex 6) 429(ex 6)
  leakyQueue(6, 10/s)    0ms 100ms 200ms 300ms 400ms 500ms 429 429 429 429

burst=5 nodelay
  nginx-port:  0ms(ex 0) 0ms(ex 1) 0ms(ex 2) 0ms(ex 3) 0ms(ex 4) 0ms(ex 5) 429(ex 6) 429(ex 6) 429(ex 6) 429(ex 6)
  gcra(10/s, burst 6)    0ms 0ms 0ms 0ms 0ms 0ms 429 429 429 429

burst=5 delay=3
  nginx-port:  0ms(ex 0) 0ms(ex 1) 0ms(ex 2) 0ms(ex 3) 100ms(ex 4) 200ms(ex 5) 429(ex 6) 429(ex 6) 429(ex 6) 429(ex 6)

nginx thật (bài 5, out/05-nginx.txt) cho cùng 3 cấu hình: 6 qua (1 ngay + 5 chờ 100…500ms) / 6 qua ngay / 4 qua ngay + 2 chờ 100, 200ms — 4 request còn lại 429.

Cách nói khi phỏng vấn: "Bên trong nginx, mỗi key chỉ có hai con số: lần cuối thấy request và mực nước trong xô, tính bằng số request đang vượt. Mỗi request mới, mực nước rút đi theo thời gian đã trôi nhân với tốc độ rồi cộng thêm một; vượt quá burst thì trả lỗi. Nếu còn trong burst thì không có nodelay nginx bắt request chờ đúng bằng mực nước chia cho tốc độ, có nodelay thì cho đi luôn. Nên burst bằng năm thực ra cho sáu request cùng lúc: một request đúng nhịp cộng năm request vượt."

Không nodelay = hàng đợi. Request đầu tạo node với excess = 0 → đi ngay. Request thứ 2 tới cùng mili-giây: 0 − 0 + 1000 → ex 1, chờ 1000 × 1000 / 10000 = 100ms; thứ 6: ex 5, chờ 500ms; thứ 7: ex 6 > burst 5 → 429. Dãy 0 100 200 300 400 500 429×4 trùng khớp leakyQueue(6, 10/s) và trùng nginx thật ở bài 5 (200/4ms … 200/504ms, 4 request 429).
nodelay = đồng hồ đo = GCRA. Cùng mực nước, nhưng không ai chờ: 6 qua ngay, 4 bị chặn — khớp gcra(10/s, burst 6).
delay=3 = lai. Ba request vượt đầu (ex 1..3) đi ngay, ex 4 chờ (4 − 3) × 100 = 100ms, ex 5 chờ 200ms — khớp dòng 4 của lab nginx (4 qua ngay + 2 chờ). Hai hàm trong algorithms.mjs không có bản tương đương.
Lệch một đơn vị khi đọc tham số: burst=5 của nginx tương ứng capacity/burst 6 trong bộ mô phỏng, vì nginx đếm phần vượt so với request được phép ngay. Khi viết ADR, ghi "số request được dồn cùng lúc" (ở đây là 6) thay vì chép tên tham số của từng công cụ.
Phần sau 300ms: 200 200 429 200 429 của lab nginx (bài 5) phụ thuộc thời điểm tới thật của từng request (có xê dịch vài mili-giây) nên không tái hiện bằng thời gian ảo ở đây — chưa verify bằng bản chép công thức.

Đánh đổi và bối cảnh

Trạng thái: kiểu đồng hồ đo: 1–2 số (GCRA: TAT; nginx: excess + last). Kiểu hàng đợi: thêm chính những request đang chờ — trong một server là connection đang mở, trong hệ phân tán là một queue thật và worker xả queue (bảng mục 7).
Đúng chỗ (hàng đợi): traffic đi ra tới đối tác có hạn mức cứng (gửi SMS, gọi API thanh toán, webhook), job nền, nơi không ai đang ngồi chờ response và "chậm nhưng đủ" tốt hơn "nhanh nhưng 429".
Sai chỗ (hàng đợi): trước API mà người dùng đang chờ — lab A/B cho thấy chờ tới 60 giây, trace trên chờ 9,8 giây với chỉ 12 request; client timeout từ lâu mà server vẫn giữ connection và vẫn xử lý. Cloudflare 2017 bỏ leaky bucket còn vì "two parameters (average rate and burst) that are not always easy to tune properly" — mục 9.
Với nginx: API nhận vào dùng burst=… nodelay (đồng hồ đo); chỉ bỏ nodelay khi thật sự muốn làm mượt và chấp nhận độ trễ; delay=N khi muốn burst nhỏ đi ngay còn phần vượt thêm thì bị làm chậm thay vì bị chặn.

3.6 GCRA — chỉ nhớ 1 số

export function gcra(limit, periodMs, burst) {
  const T = periodMs / limit;                       // emission interval: khoảng cách "chuẩn" giữa 2 request
  const tau = T * (burst - 1);                      // được đi sớm hơn lịch tối đa tau → burst request liền nhau
  let tat = 0;                                      // theoretical arrival time
  return (now) => {
    const t = Math.max(tat, now);
    if (t - now > tau) return false;               // đến quá sớm so với lịch
    tat = t + T;                                    // được qua: đẩy lịch lùi thêm 1 khoảng T
    return true;
  };
}

Ý tưởng: thay vì đếm token, GCRA giữ một "lịch hẹn" TAT. Mỗi request được qua đẩy lịch thêm T. Request được qua nếu lịch chưa vượt quá now + τ. Không cần job nạp, không cần hash 2 field — chỉ 1 số (32 byte trong Redis). Lab cho kết quả giống hệt token bucket ở mọi kịch bản (A: 104 vs 104; B: 399 vs 399; C: 12 vs 12), đúng như lý thuyết: hai cách nhìn của cùng một định nghĩa. redis-cell (module Redis của Brandur) cài GCRA với lệnh CL.THROTTLE <key> <max_burst> <count per period> <period>; README hiện ghi dự án ở chế độ "best effort" maintenance — lab này không cài module đó.

Cách nói khi phỏng vấn: "GCRA cho mỗi key một lịch hẹn, gọi là thời điểm tới theo lý thuyết của request kế tiếp. Mỗi request được qua đẩy lịch đó thêm một khoảng chuẩn, bằng chu kỳ chia cho giới hạn. Request được qua nếu nó không tới sớm hơn lịch quá một khoảng dung sai, và dung sai đó bằng burst trừ một nhân với khoảng chuẩn. Nếu lịch đã nằm trong quá khứ thì lấy thời điểm hiện tại làm mốc, nên client im lâu cũng không tích được quá burst. Kết quả giống hệt token bucket nhưng mỗi key chỉ cần một con số và toàn tính bằng số nguyên."

Trực giác — nén lịch sử thành gì. GCRA nén lịch sử thành một khoản nợ thời gian: TAT − now là client đang đi trước lịch bao xa. Mỗi request được qua cộng thêm nợ T; thời gian trôi tự trả nợ với tốc độ 1 giây mỗi giây; được nợ tối đa τ trước khi gửi request mới. max(TAT, now) nghĩa là không được "nợ âm" — đúng bằng cái trần của token bucket. Vì vậy hai thuật toán là một: số token chỉ là khoản nợ đo bằng đơn vị T và lật ngược. Brandur (2015) chỉ ra điểm hơn về kỹ thuật: "if we could build an algorithm without a drip, it would be fundamentally more stable" — không có thứ gì phải "nhỏ giọt" theo thời gian, chỉ có một mốc so với đồng hồ.

Trace trên luồng chung (5 / 10s, burst 5 → T = 10 / 5 = 2s, τ = 2 × (5 − 1) = 8s). Cột "token tương đương" đổi TAT ra số token, cột cuối là số token (sau nạp) của token bucket ở 3.4:

=== 3.6 GCRA (5 / 10s, burst 5 → T = 2s, τ = 8s): t' = max(TAT, now); t' − now > τ thì chặn, không thì TAT = t' + T ===
t (s)  | TAT trước | t' = max | t' − now | ≤ τ = 8.0 ?       | TAT sau | token tương đương = min(5, (now + τ + T − TAT)/T) | token bucket (3.4)
   2.0 |      0.0s |     2.0s |     0.0s | 0.0 ≤ 8.0 ? có    |    4.0s | min(5, (2.0 + 8 + 2 − 0.0)/2) = 5.00              |   5.00  QUA 
   7.0 |      4.0s |     7.0s |     0.0s | 0.0 ≤ 8.0 ? có    |    9.0s | min(5, (7.0 + 8 + 2 − 4.0)/2) = 5.00              |   5.00  QUA 
   8.0 |      9.0s |     9.0s |     1.0s | 1.0 ≤ 8.0 ? có    |   11.0s | min(5, (8.0 + 8 + 2 − 9.0)/2) = 4.50              |   4.50  QUA 
   9.0 |     11.0s |    11.0s |     2.0s | 2.0 ≤ 8.0 ? có    |   13.0s | min(5, (9.0 + 8 + 2 − 11.0)/2) = 4.00             |   4.00  QUA 
   9.5 |     13.0s |    13.0s |     3.5s | 3.5 ≤ 8.0 ? có    |   15.0s | min(5, (9.5 + 8 + 2 − 13.0)/2) = 3.25             |   3.25  QUA 
   9.8 |     15.0s |    15.0s |     5.2s | 5.2 ≤ 8.0 ? có    |   17.0s | min(5, (9.8 + 8 + 2 − 15.0)/2) = 2.40             |   2.40  QUA 
  10.1 |     17.0s |    17.0s |     6.9s | 6.9 ≤ 8.0 ? có    |   19.0s | min(5, (10.1 + 8 + 2 − 17.0)/2) = 1.55            |   1.55  QUA 
  10.4 |     19.0s |    19.0s |     8.6s | 8.6 ≤ 8.0 ? không |   19.0s | min(5, (10.4 + 8 + 2 − 19.0)/2) = 0.70            |   0.70  CHẶN
  10.7 |     19.0s |    19.0s |     8.3s | 8.3 ≤ 8.0 ? không |   19.0s | min(5, (10.7 + 8 + 2 − 19.0)/2) = 0.85            |   0.85  CHẶN
  11.2 |     19.0s |    19.0s |     7.8s | 7.8 ≤ 8.0 ? có    |   21.0s | min(5, (11.2 + 8 + 2 − 19.0)/2) = 1.10            |   1.10  QUA 
  15.0 |     21.0s |    21.0s |     6.0s | 6.0 ≤ 8.0 ? có    |   23.0s | min(5, (15.0 + 8 + 2 − 21.0)/2) = 2.00            |   2.00  QUA 
  19.5 |     23.0s |    23.0s |     3.5s | 3.5 ≤ 8.0 ? có    |   25.0s | min(5, (19.5 + 8 + 2 − 23.0)/2) = 3.25            |   3.25  QUA

2,0s: TAT ban đầu 0 nằm trong quá khứ → t' = max(0, 2,0) = 2,0, t' − now = 0 ≤ 8 → qua, TAT = 2,0 + 2 = 4,0s. 7,0s: TAT 4,0 lại nằm trong quá khứ → t' = 7,0, TAT = 9,0s. Phần thời gian im lặng 4,0 → 7,0s bị bỏ — tương đương xô đã đầy, token nạp thêm bị đổ.
8,0 → 10,1s, nợ tăng dần: 8,0s: t' = 9,0, nợ 1,0s → TAT 11,0; 9,0s: nợ 11,0 − 9,0 = 2,0 → 13,0; 9,5s: nợ 3,5 → 15,0; 9,8s: nợ 5,2 → 17,0; 10,1s: nợ 17,0 − 10,1 = 6,9 ≤ 8 → qua, TAT 19,0s.
10,4s và 10,7s bị chặn: nợ 19,0 − 10,4 = 8,6 và 19,0 − 10,7 = 8,3, đều > τ = 8. Khi chặn, TAT giữ nguyên — request bị chặn không làm nợ tăng (khác với lỗi "ghi cả request bị chặn" của sliding log).
11,2s: nợ 19,0 − 11,2 = 7,8 ≤ 8 → qua, TAT 21,0. Rồi 15,0s nợ 6,0 → TAT 23,0; 19,5s nợ 3,5 → TAT 25,0.
Vì sao bằng token bucket — đọc cột "token tương đương". Ở 10,4s: (10,4 + 8 + 2 − 19,0) / 2 = 0,70, đúng bằng 0,70 token của token bucket ở cùng thời điểm; ở 11,2s: (11,2 + 8 + 2 − 19,0) / 2 = 1,10 = 1,10. Mười hai dòng, hai cột trùng nhau từng số. Lý do đại số: token = (τ + T − (TAT − now)) / T, nên token ≥ 1 tương đương TAT − now ≤ τ — cùng một phép so sánh viết theo hai đơn vị. Quyết định ở bảng 3.7 cũng trùng hoàn toàn (10/12, max 8).

Cách nói khi phỏng vấn: "Muốn thấy GCRA là token bucket thì đổi khoản nợ ra token: lấy dung sai cộng một khoảng chuẩn, trừ đi khoảng mà lịch hẹn đang đi trước hiện tại, rồi chia cho khoảng chuẩn. Còn ít nhất một token nghĩa là lịch đi trước không quá dung sai, đúng điều kiện cho qua của GCRA. Trong trace của tôi, mười hai request, số token tính từ lịch hẹn trùng với token bucket ở mọi dòng. Khác biệt chỉ là cách lưu: một mốc thời gian thay vì hai con số."

Một kịch bản riêng cho thấy chỗ hai cách lưu khác nhau trong thực tế — số thực:

--- 3.6b Cùng luồng nhưng request thứ 10 tới lúc 11.0s (đúng biên: còn đúng 1 token / t' − now = τ) ---
t = 11.0s: token bucket thấy tokens = 0.99999999999999989 → CHẶN | GCRA thấy t' − now = 8000ms, τ = 8000ms → QUA

Về toán, lúc 11,0s cả hai đều đúng biên: còn đúng 1 token, và nợ đúng bằng τ. Token bucket cộng dồn các phần nạp 0,15 bằng số thực dấu phẩy động (IEEE 754 — không biểu diễn chính xác được 0,15) nên ra 0.99999999999999989 và chặn; GCRA làm phép trừ trên mili-giây nguyên (8000 ≤ 8000) nên cho qua. Lệch đúng một request ở đúng biên — không nguy hiểm, nhưng là loại lỗi làm test "đúng biên" chập chờn và làm hai service dùng hai cài đặt trả khác nhau.

Hình 7 — GCRA với burst 5. Không có xô, không có token — chỉ có một mốc thời gian. Muốn biết "còn bao nhiêu lượt" để trả header thì tính ngược từ (now + τ − TAT) / T. Lab cho thấy GCRA và token bucket ra cùng số ở mọi kịch bản.

Hình 8 — Số liệu từ trace 3.4 và 3.6. Đường vàng: số token của token bucket (dốc lên 0,5 token/giây, cắt ở trần 5 trong quãng 4,0 → 7,0s, rơi 1 ở mỗi request được qua; hai request bị chặn không làm rơi). Vòng xanh: số token tính ngược từ TAT của GCRA ngay trước mỗi request — trùng từng điểm. Hình 7 ở trên cho thấy cơ chế TAT; hình này cho thấy kết quả của nó.

Đánh đổi và bối cảnh

Trạng thái: 1 mốc thời gian (32 byte trong Redis). Trên Redis vẫn phải đọc–so–ghi nguyên tử (Lua, hoặc module như redis-cell), nhưng chỉ một key một giá trị và TTL đặt bằng TAT − now là đủ để key tự biến mất khi hết nợ.
Đúng chỗ: mọi nơi token bucket hợp, khi muốn trạng thái nhỏ nhất và số học nguyên: limiter dùng chung cho cả công ty (mục 8), gateway tự viết trên Redis. "Còn lại" và "chờ bao lâu" tính ngược được từ TAT; "chờ bao lâu" khi bị chặn chính là (TAT − now) − τ — ở 10,4s là 8,6 − 8 = 0,6 giây, khớp con số tính từ token bucket ở 3.4 (tính tay từ trace).
Sai chỗ: giống token bucket (hợp đồng cửa sổ trượt, cần làm mượt đầu ra). Thêm một rủi ro tổ chức: khái niệm TAT/τ khó giải thích cho support và đối tác hơn "xô token" — nên giao tiếp bằng ngôn ngữ token bucket, cài đặt bằng GCRA.
Tham số "burst" không đồng nhất giữa các công cụ: trong algorithms.mjs, burst 5 nghĩa là 5 request liền nhau (τ = 4T); trong nginx, burst=5 nghĩa là 6 (trace 3.5b). Ngữ nghĩa max_burst của redis-cell: chưa verify (chỉ đọc README, không cài).

3.7 Sáu thuật toán trên cùng một luồng

=== Tổng kết luồng chung (✓ = qua/nhận, ✗ = chặn) ===
thuật toán                      |  2.0  7.0  8.0  9.0  9.5  9.8 10.1 10.4 10.7 11.2 15.0 19.5 | qua | max/10s trượt
fixed window (căn đồng hồ)      |    ✓    ✓    ✓    ✓    ✓    ✗    ✓    ✓    ✓    ✓    ✓    ✗ |  10 |             9
fixed window (neo request đầu)  |    ✓    ✓    ✓    ✓    ✓    ✗    ✗    ✗    ✗    ✗    ✓    ✓ |   7 |             5
sliding log                     |    ✓    ✓    ✓    ✓    ✓    ✗    ✗    ✗    ✗    ✗    ✓    ✓ |   7 |             5
sliding window counter          |    ✓    ✓    ✓    ✓    ✓    ✗    ✓    ✗    ✗    ✗    ✓    ✓ |   8 |             6
token bucket (b=5, 0,5/s)       |    ✓    ✓    ✓    ✓    ✓    ✓    ✓    ✗    ✗    ✓    ✓    ✓ |  10 |             8
leaky bucket hàng đợi (5)       |    ✓    ✓    ✓    ✓    ✓    ✓    ✓    ✓    ✗    ✓    ✓    ✓ |  11 |             9  chờ lâu nhất 9.8s
GCRA (5/10s, burst 5)           |    ✓    ✓    ✓    ✓    ✓    ✓    ✓    ✗    ✗    ✓    ✓    ✓ |  10 |             8

Cùng 12 request, số được qua từ 7 tới 11 — không thuật toán nào "sai", mỗi dòng đúng với định nghĩa "quá nhanh" của nó. Cột max/10s trượt là thước đo chung: chỉ sliding log (và lần này cả fixed window neo request đầu, nhờ may mắn về vị trí ranh giới) giữ đúng 5.
Fixed window 10 qua, max 9 — nhiều request qua mà lại "lọt" nặng nhất, vì cụm sau ranh giới được nguyên hạn mức mới.
Sliding window counter 8 qua, max 6 — chặn được cụm sau ranh giới (chỉ lọt 10,1s), sai một request ở đúng chỗ giả định rải đều không đúng.
Token bucket = GCRA: 10 qua, max 8 — cho qua 9,8s và 10,1s mà các thuật toán cửa sổ chặn, vì client đã để dành tín dụng; vẫn dưới cam kết b + r·T = 10.
Leaky bucket hàng đợi 11 nhận, chờ lâu nhất 9,8s — nhận nhiều nhất nhưng trả bằng độ trễ; đầu ra ra đều mỗi 2 giây.

Cách nói khi phỏng vấn: "Tôi hay giải thích bằng một luồng mười hai request với giới hạn năm request mười giây. Fixed window cho qua mười nhưng có lúc chín request trong mười giây, vì cụm sau ranh giới được hạn mức mới. Sliding log chặt nhất, chỉ bảy. Sliding window counter ở giữa, sai một request. Token bucket và GCRA cho qua mười theo kiểu được dồn rồi giữ tốc độ, còn leaky bucket hàng đợi nhận gần hết nhưng có request phải chờ gần mười giây. Nên câu hỏi đầu tiên luôn là nghiệp vụ định nghĩa quá nhanh là gì."

4. Đảm bảo và giới hạn

Thuật toán	Trạng thái / key (Redis)	Đảm bảo trong mọi cửa sổ W	Burst	Thêm độ trễ?
Fixed window	1 số, 32 B	tối đa 2N	N ở đầu mỗi khung	Không
Sliding log	N timestamp; 100 → 3,2 KB, 1 000 → 95 KB	tối đa N (chính xác)	N	Không
Sliding window counter	2 số	≈ N; xấu nhất 2N trên cửa sổ 60s (lab E: 200), nhưng burst ngắn ở ranh giới chỉ ~N (lab E: 102/giây)	~N	Không
Token bucket	2 số, hash 68 B	tối đa b + r·W	b (tách khỏi tốc độ)	Không
GCRA	1 số, 32 B	như token bucket	như token bucket	Không
Leaky bucket hàng đợi	1 số + hàng đợi thật	đầu ra đều r	vào hàng đợi	Có — tới capacity/r giây

Lab E — trường hợp xấu nhất cho "100/phút": dồn 100 request vào 0,1 giây cuối phút đầu, rồi 10 request/giây đều trong 2 phút.

thuật toán                       | qua/1300 | max trong 60s trượt bất kỳ | max trong 1s trượt bất kỳ
fixed window (căn đồng hồ)       |     300 |                        200 |                       109
fixed window (neo request đầu)   |     201 |                        100 |                       100
sliding log                      |     201 |                        100 |                       100
sliding window counter           |     300 |                        200 |                       102
token bucket (b=100, 100/phút)   |     299 |                        199 |                       101
GCRA (100/phút, burst 100)       |     300 |                        199 |                       101
leaky bucket hàng đợi (100)      |     300 |                        200 |                       102

Đọc kỹ dòng sliding window counter: trên cửa sổ 60 giây nó cũng lọt gấp đôi như fixed window (200), nhưng ở ranh giới nó không cho dồn — chỉ 102 request trong 1 giây so với 109 của fixed window. Riêng fixed window "neo ở request đầu" lần này lại đúng 100: cửa sổ mở đúng lúc burst tới nên burst đã ăn hết cả cửa sổ. Cùng thuật toán đó ở lab A lại lọt 199 — kết quả phụ thuộc kẻ tấn công có canh được ranh giới hay không.

Lab D — sliding window counter sai bao nhiêu? 300 client × 10 phút ở mỗi mức tải, traffic Poisson (request tới ngẫu nhiên, độc lập). Thuật toán tự quyết định trên lịch sử của chính nó; tại mỗi request, so với quyết định mà bộ đếm chính xác sẽ đưa ra trên cùng lịch sử đó.

tốc độ / giới hạn  |  request | SWC cho qua | cho qua SAI | chặn SAI | sai lệch ước lượng TB | max/60s trượt (client tệ nhất)
0.5×               |   149694 |    100.000% |      0.000% |   0.000% |                  4.1% |                             82
0.9×               |   270762 |     98.261% |      6.143% |   0.684% |                  3.0% |                            118
1×                 |   300591 |     94.060% |     13.273% |   2.359% |                  2.8% |                            117
1.25×              |   375057 |     78.840% |     18.401% |   7.472% |                  2.5% |                            118
2×                 |   599541 |     49.924% |     16.129% |   9.629% |                  4.4% |                            108
4×                 |  1200609 |     24.982% |      9.710% |   8.324% |                  8.9% |                            103

Ba ý: (1) khi tải xa ngưỡng (0,5×), không sai lần nào; (2) khi tải lởn vởn quanh ngưỡng, quyết định lệch khá thường xuyên vì sai số ước lượng chỉ ~3% nhưng đủ lật quyết định của những request sát vạch; (3) độ vượt thực tế nhỏ: client tệ nhất được 118 request trong 60 giây thay vì 100. Cloudflare báo con số đẹp hơn nhiều ("0.003% of requests have been wrongly allowed or rate limited", trên 400 triệu request từ 270 000 nguồn) vì họ đo trên traffic thật, nơi phần lớn nguồn ở rất xa ngưỡng, và đo theo nguồn bị chặn chứ không theo từng request. Hai kết quả không mâu thuẫn: sai số chỉ đáng kể với những client sống sát ngưỡng.

5. Failure modes

Hỏng thế nào	Thuật toán dính	Lab	Hậu quả đo được
Dồn 2 lần giới hạn quanh ranh giới cửa sổ	Fixed window (cả 2 biến thể)	A	199 request / 2 giây với giới hạn 100/phút
Quá tải kéo dài → cho qua theo từng đợt rồi im	Fixed window, cả sliding log	B	`34 33 33 0 0 0` mỗi phút — backend nhận đợt dồn
Ước lượng sai khi traffic không đều	Sliding window counter	D	tới 118/100 trong 60 giây
Request chờ quá lâu (client đã bỏ đi)	Leaky bucket hàng đợi	A, B	chờ 60,0 giây (A), 59,7 giây (B)
Burst đặt quá nhỏ cho client thật	Token bucket, GCRA	C	b = 1: 11/12 request của 1 lần mở trang bị chặn
Log không bao giờ vơi	Sliding log "ZADD trước"	bài 3	bị chặn vĩnh viễn khi còn gửi

Hình 9 — Cột cao nhất = 34 request/10 giây. Fixed window (và cả sliding log — cùng một hàng số 34 33 33 0 0 0) dồn toàn bộ hạn mức vào nửa đầu mỗi phút: backend nhận tải gấp đôi rồi ngồi chơi. Sliding window counter làm mượt từ phút thứ hai. Token bucket cho phút đầu gần 200 vì xô đầy sẵn 100 token — đúng định nghĩa b + r·T, không phải lỗi.

6. Vận hành trong production

Chọn burst từ hành vi client thật, không từ cảm giác. Một trang SPA mở ra bắn 8–15 request cùng lúc. Lab C: giới hạn "10/giây" viết thành token bucket b = 1 (đúng như nginx rate=10r/s không có burst) chặn 11/12 request. Đo số request song song của một lần tải trang bằng DevTools/HAR rồi đặt b lớn hơn số đó.
Header "còn lại / đặt lại lúc nào" phụ thuộc thuật toán. Fixed window: reset = cuối khung. Token bucket/GCRA: "còn lại" là số token, "chờ bao lâu" là thời gian nạp đủ 1 token — không có khái niệm "reset cả xô". Draft IETF RateLimit header (bản 11, 23/05/2026) dùng ngôn ngữ trung lập q (quota), w (window), r (còn lại), t (số giây) để thuật toán nào cũng điền được — chi tiết ở bài 6.
Dung lượng Redis: nhân số key đang hoạt động với byte/key ở bảng mục 4. Fixed window/GCRA: 1 triệu key ≈ vài chục MB (cộng overhead key). Sliding log: tính theo N — đây là chỗ hay vỡ capacity.
Đổi thuật toán là đổi hợp đồng. Chuyển từ fixed window sang token bucket làm một số client đang "dồn đầu phút" bắt đầu bị 429 dù tổng số không đổi. Chạy chế độ shadow (tính nhưng không chặn) trước, so số bị chặn của hai thuật toán (bài 6).
Metric riêng của thuật toán: với leaky bucket hàng đợi, đo thời gian chờ trong hàng đợi (p99), không chỉ số bị chặn — lab B cho thấy không ai bị chặn mà mọi request đều chờ ~60 giây.

7. So sánh và ma trận quyết định

Tiêu chí	Fixed window	Sliding log	Sliding window counter	Token bucket / GCRA	Leaky bucket hàng đợi
Độ chính xác	Thấp (2× ở ranh giới)	Tuyệt đối	Khá (lệch vài %)	Đúng theo định nghĩa b + r·T	Đúng (đầu ra đều)
RAM / key	1 số	N số	2 số	2 số / 1 số	1 số + hàng đợi
Cài trên Redis	Rất dễ	Dễ, tốn RAM	Dễ	Cần Lua (tính bù token)	Cần worker xả hàng đợi
Điều khiển burst	Không	Không tách được	Không tách được	Có (b riêng, r riêng)	Có (độ dài hàng đợi)
Ai đang dùng	Laravel (neo request đầu), Envoy ratelimit service, quota giờ/ngày	Login/OTP tự viết	Cloudflare (2017)	Stripe, Envoy local rate limit; GCRA: redis-cell, thư viện throttled	nginx không `nodelay`, queue gọi API đối tác

flowchart TD
  Q1["Cần chắc chắn KHÔNG BAO GIỜ quá N
trong mọi cửa sổ W, và N nhỏ?"] -->|"có: login, OTP, SMS"| SL["Sliding log"]
  Q1 -->|"không"| Q2["Traffic đi RA ngoài
cần đều đặn: gọi API đối tác?"]
  Q2 -->|"có"| LQ["Leaky bucket hàng đợi
hoặc queue + rate limit job"]
  Q2 -->|"không, traffic đi VÀO"| Q3["Muốn cho burst ngắn
rồi giữ tốc độ trung bình?"]
  Q3 -->|"có: API, SPA"| GC["Token bucket / GCRA"]
  Q3 -->|"không, chỉ chặn thô theo giờ/ngày"| Q4["Chịu được 2 lần giới hạn
quanh ranh giới?"]
  Q4 -->|"có: quota ngày"| FW["Fixed window"]
  Q4 -->|"không"| SW["Sliding window counter"]

Dùng khi nào: token bucket/GCRA làm mặc định cho API nhận vào (có burst, ít RAM, đúng định nghĩa rõ ràng); fixed window cho quota thô theo giờ/ngày; sliding log cho thao tác nhạy cảm số lần ít; leaky bucket hàng đợi cho traffic đi ra. Tránh khi nào: fixed window cho login/OTP (kẻ tấn công nhân đôi số lần thử); sliding log khi N lớn; leaky bucket hàng đợi trước API mà client có timeout.

8. Góc nhìn tech lead: tác động tổ chức

Viết định nghĩa vào ADR, không chỉ con số: "API đối tác: 600 request/phút, burst 100, thuật toán GCRA — nghĩa là trong mọi khoảng T giây không quá 100 + 10·T request". Đối tác đọc được, support trả lời được, QA test được.
Một thư viện limiter cho cả công ty. Mỗi service tự viết một thuật toán là mỗi nơi một định nghĩa — khách gọi 3 service thấy 3 kiểu 429 khác nhau. Bọc sau một interface nhỏ allow(key, cost) → {ok, remaining, retryAfter}.
Exit strategy: giữ interface đó thì đổi thuật toán (fixed window → GCRA) hay đổi nơi chạy (app → gateway) không đụng code nghiệp vụ. Đừng để code nghiệp vụ đọc thẳng key Redis của limiter.
Onboarding: một trang nội bộ có bảng ở mục 7 + lab A (199/100) giải thích nhanh hơn mọi buổi họp.

9. Anti-patterns và bài học thực tế

Fixed window cho đăng nhập/OTP. Lab A: kẻ tấn công canh ranh giới là gấp đôi số lần thử. Với OTP 6 số thì vẫn khó, với mật khẩu yếu thì gấp đôi tốc độ dò.
Sliding log cho giới hạn lớn. 1 triệu client × 1 000/phút ≈ 89 GB RAM Redis (lab bài 3).
Leaky bucket hàng đợi trước API nhận vào. Lab A/B: chờ tới 60 giây — client timeout từ lâu, server vẫn phải xử lý (xem bài 4: việc làm phí).
Burst = 1 cho client là trình duyệt. Lab C: 11/12 request của một lần mở trang bị chặn.
Coi sliding window counter là chính xác. Lab D: tới 118/100 khi traffic không đều.
Chọn thuật toán trước khi hỏi định nghĩa. "100/phút" của đối tác là fixed window theo phút đồng hồ hay 60 giây trượt? Hỏi trước, không thì client của bạn bị 429 dù "đã tính đúng".

Nguồn đáng đọc: Redis docs INCR (2 mẫu rate limiter và race condition của chúng); Cloudflare 2017 — họ bỏ leaky bucket vì "two parameters (average rate and burst) that are not always easy to tune properly" và vì cần nhiều thao tác không làm nguyên tử được; Brandur 2015 về GCRA ("if we could build an algorithm without a drip, it would be fundamentally more stable"); Stripe 2017 (token bucket trên Redis).

10. Câu hỏi phụ interviewer hay hỏi tiếp

Token bucket khác leaky bucket thế nào?: Token bucket cho dồn tới b rồi giữ tốc độ r, không bắt chờ. Leaky bucket kiểu hàng đợi làm đầu ra đều, bắt request chờ. Leaky bucket kiểu đồng hồ đo (GCRA) thì tương đương token bucket — lab ra cùng số.
Vì sao fixed window lọt gấp đôi?: Bộ đếm đặt lại ở ranh giới: N request cuối khung này + N request đầu khung sau nằm trong vài giây. Lab: 199 trong 2 giây với giới hạn 100/phút.
GCRA lưu gì?: Một số TAT. Request qua nếu TAT − now ≤ τ, qua rồi thì TAT = max(TAT, now) + T. Không job nền, 32 byte/key.
Sliding window counter sai bao nhiêu?: Ước lượng lệch ~3% khi tải sát ngưỡng, đủ để lệch quyết định ở những request sát vạch; client tệ nhất được 118/100. Xa ngưỡng thì không sai.
Burst nên đặt bao nhiêu?: Lớn hơn số request song song của một thao tác thật (một lần mở trang, một lần đồng bộ của app). Đo từ HAR/log, không đoán.
nginx và Laravel dùng thuật toán gì?: nginx limit_req: leaky bucket (docs ghi rõ), có/không nodelay quyết định chặn hay bắt chờ. Laravel throttle: fixed window neo ở request đầu (Illuminate\Cache\RateLimiter), bản Redis cũng là fixed window viết bằng Lua (DurationLimiter).
Muốn đúng tuyệt đối mà RAM ít thì sao?: Không có bữa trưa miễn phí: đúng tuyệt đối theo cửa sổ trượt cần nhớ từng request. Đổi định nghĩa sang "tốc độ + burst" (GCRA) thì vừa đúng vừa rẻ.

Phụ lục: lab đã chạy

Môi trường: Node 22.23.3 trong container node:22-bookworm-slim, không mạng; thời gian ảo nên kết quả lặp lại y hệt (lab D dùng PRNG có seed 20261002). Số byte Redis: Redis 8.8.0 (lab bài 3).

cd labs/rate-limit/node
./run.sh 02-algorithms.mjs     # A: ranh giới | B: quá tải đều | C: mở trang 12 request | D: sai số SWC | E: xấu nhất
                              # → ../out/02-algorithms.txt
./run.sh 07-trace.mjs          # trace từng request, trạng thái trước/sau (mục 3.1–3.7) → ../out/07-trace.txt

Phần trong `07-trace.mjs`	Kịch bản	Dùng ở
Luồng chung	5 request / 10s; 12 request tại 2,0 7,0 8,0 9,0 9,5 9,8 10,1 10,4 10,7 11,2 15,0 19,5s qua cả 6 thuật toán (+ fixed window neo request đầu)	3.1–3.6, bảng 3.7
3.2b	Sliding log ghi cả request bị chặn (biến thể sai, viết riêng trong script) — 1 request/giây, 0 → 14s	3.2
3.3b, 3.3c	Sliding window counter khi khung trước dồn về cuối / về đầu khung	3.3
3.5b	10 request cùng lúc, 10r/s: bản chép công thức `limit_req` (burst=5, nodelay, delay=3) so với `leakyQueue`/`gcra`	3.5
3.6b	Request thứ 10 tới đúng biên 11,0s: token bucket số thực so với GCRA mili-giây nguyên	3.4, 3.6

07-trace.mjs chạy ngày 26/10/2026 cùng image node:22-bookworm-slim (Node 22.23.3), --network none; chạy 2 lần, output giống hệt. Script so mọi quyết định của bản "soi" với hàm thật trong algorithms.mjs (112/112 khớp) — không sửa algorithms.mjs, không chạy lại 02-algorithms.

Chưa verify: module redis-cell (chỉ đọc README); số liệu sản xuất của Cloudflare (trích từ blog 2017, có thể đã đổi); thuật toán nội bộ hiện tại của Stripe và Cloudflare; cột nginx-port ở 3.5b là bản chép công thức từ source, không phải nginx chạy thật (3 cấu hình khớp lab nginx bài 5, phần "sau 300ms" chưa tái hiện); lỗi số thực ở biên (3.6b) trong các script Lua token bucket phổ biến; ngữ nghĩa max_burst của redis-cell.