Bài 13: Rate Limiting & Backpressure

Bài 12 kết thúc bằng bốn cách để một hệ bất đồng bộ nói không, và hẹn rằng cách cuối cùng — giảm tốc chính người gửi — là nội dung của bài này. Rate limiting là cơ chế để hệ thống từ chối có kiểm soát, thay vì nhận hết rồi vỡ, hoặc nhận hết rồi hứa một tồn đọng sáu tiếng.

Lab của bài này chạy cả bốn thuật toán rate limit thật trên Redis, mỗi thuật toán là một script Lua. Ba phép đo đáng chú ý. Thứ nhất, với cùng hạn mức 100 request/giây, fixed window cho lọt 200 request trong một giây ở đúng mốc giao cửa sổ — gấp đôi hạn mức, và con số này lặp lại y hệt qua cả ba lần chạy. Thứ hai, viết limiter bằng INCR rồi EXPIRE ở hai lệnh riêng làm 20 trên 200 khoá mắc kẹt không có TTL — tức 20 người dùng bị chặn vĩnh viễn. Thứ ba, bốn thuật toán chênh nhau không đáng kể về tốc độ (p50 đều quanh 0,08 ms), nhưng chênh nhau hơn 10 lần về bộ nhớ.

13.1 Rate limit bảo vệ bạn khỏi ai

Câu trả lời quen thuộc là "khỏi kẻ tấn công". Câu trả lời đó không sai nhưng nó dẫn người ta đặt rate limit sai chỗ. Trong phần lớn sự cố thật, thứ đánh sập hệ thống không phải người lạ mà là chính client của bạn: một ứng dụng di động vừa ra bản mới có vòng retry không jitter, một job cron của đội khác chạy lúc 0 giờ, hoặc một service nội bộ đang thử lại điên cuồng vì service phía sau nó chậm. Người lạ thì bị chặn ở tầng khác (WAF — web application firewall, tường lửa lọc lưu lượng độc hại trước khi nó vào tới app — và chống DDoS); còn client của chính bạn thì có khoá API hợp lệ và đi thẳng vào đường chính.

Ba khái niệm hay bị gộp làm một, trong khi chúng phục vụ ba mục đích khác hẳn nhau và thường được cài ở ba chỗ khác nhau:

Khác biệt đáng nhớ nhất nằm ở cột cuối. Rate limit nói không; throttle nói chờ. Throttle nghe tử tế hơn, và đó chính là cái bẫy: mỗi request bị làm chậm vẫn đang chiếm một kết nối, một luồng, một chỗ trong hàng đợi. Ở Bài 1 ta đã thấy điều gì xảy ra khi hàng đợi dâng — throttle không xoá tải, nó chỉ đổi tải thành độ trễ. Khi thật sự quá tải, từ chối nhanh là hành động tử tế hơn.

13.2 Bốn thuật toán, và cái giá thật của từng cái

Bốn thuật toán dưới đây trả lời cùng một câu hỏi — "request này có được đi qua không" — nhưng chúng định nghĩa chữ "một giây" theo bốn cách khác nhau, và toàn bộ khác biệt nằm ở đó.

Điểm yếu của fixed window được nhắc tới ở khắp nơi, nhưng gần như luôn dưới dạng lời kể. Lab của bài này dựng đúng kịch bản đó và đếm: hạn mức 100 request mỗi 1000 ms, bắn 100 request ngay trước mốc giao cửa sổ rồi 100 request ngay sau mốc đó, và đo con số duy nhất mà server phía sau thật sự quan tâm — số request lọt qua nhiều nhất trong một cửa sổ trượt 1 giây bất kỳ.

Con số 200% của fixed window không phải trường hợp xấu hiếm gặp — nó xảy ra mỗi lần lưu lượng dồn quanh mốc giao cửa sổ, và mốc đó là một thời điểm cố định trong ngày nên rất dễ bị dồn: các job cron đều hẹn giờ tròn, các client retry đều làm tròn về giây. Điều tệ hơn là không có tham số nào chỉnh được: 2× là hệ quả trực tiếp của việc bộ đếm reset đột ngột.

Điểm cần nói cho đúng: token bucket cũng cho burst — 119% trong phép đo trên, chứ không phải 100%. Nhiều bài viết trình bày token bucket như thể nó "không có vấn đề burst", điều đó không đúng. Khác biệt thật nằm ở chỗ burst của token bucket có chặn trên và chỉnh được: nó tối đa bằng sức chứa của xô, nên nếu bạn cần đầu ra phẳng thì hạ sức chứa xuống dưới tốc độ rót. Còn burst của fixed window là 2× bất kể bạn cấu hình thế nào.

Vậy tại sao không dùng sliding window log cho mọi thứ, khi nó chính xác tuyệt đối? Câu trả lời không nằm ở tốc độ mà nằm ở bộ nhớ. Đo 20.000 lời gọi cho mỗi thuật toán, cả bốn cho ra thời gian gần như y hệt nhau — vì thứ tốn thời gian là vòng mạng tới Redis chứ không phải phép tính bên trong:

Bốn cột đầu gần như không phân biệt được; cột cuối chênh nhau hơn 10 lần. Đó là vì sliding window log phải nhớ dấu thời gian của từng request còn hiệu lực, nên bộ nhớ của nó tỉ lệ với hạn mức chứ không phải với số người dùng: hạn mức 100 tốn 1.499 byte mỗi người, hạn mức 10.000 sẽ tốn gấp trăm lần. Với một triệu người dùng hoạt động, đó là khác biệt giữa vài trăm megabyte và vài chục gigabyte — tức khác biệt giữa "một node Redis" và "một cụm Redis phải vận hành".

13.3 Trong hệ phân tán, bộ đếm phải là nguyên tử

Bài 3 đã cho hệ thống ba app replica, và điều đó làm hỏng ngay cách viết limiter tự nhiên nhất: giữ bộ đếm trong bộ nhớ tiến trình. Với ba replica, mỗi replica đếm riêng, và hạn mức thật trở thành ba lần hạn mức bạn cấu hình. Bộ đếm phải nằm ở chỗ dùng chung — nhưng chỉ dùng chung thôi chưa đủ.

Đây là cách viết limiter phổ biến nhất trên mạng, và nó có một lỗi nghiêm trọng:

// WRONG: two separate commands, with a gap in between
const n = await redis.incr(key);
if (n === 1) {
  await redis.expire(key, 60);   // (!) if the process dies BEFORE this line...
}
if (n > limit) return deny();

Khoảng trống giữa INCR và EXPIRE nhỏ, nhưng nó có thật. Nếu tiến trình chết đúng lúc ấy — deploy, OOM kill, container bị siết CPU rồi bị thanh lý — thì khoá đó tồn tại vĩnh viễn không có TTL. Bộ đếm không bao giờ reset, và người dùng đó bị chặn mãi mãi cho tới khi có người vào xoá khoá bằng tay. Lab tái tạo đúng chuyện này với 200 người dùng, "chết" ở 1 trên 10 lần:

{
  "role": "nonatomic",
  "crashEvery": 10,
  "report": [
    { "mode": "two-commands", "keyCount": 200, "keysWithoutTtl": 20,
      "consequence": "20 users blocked FOREVER" },
    { "mode": "lua", "keyCount": 200, "keysWithoutTtl": 0,
      "consequence": "no keys stuck" }
  ]
}

Cách sửa là gộp toàn bộ "đọc — quyết định — ghi" vào một script Lua. Redis chạy trọn một script như một lệnh đơn, nên hoặc cả hai lệnh cùng chạy, hoặc không lệnh nào chạy. Đây là bản token bucket thật đang chạy trong lab:

-- A bucket of capacity `cap`, refilled steadily at `cap` per `win`.
-- There are no window boundaries at all, so there is no cliff to exploit. Bursts are
-- ALLOWED but capped by exactly the bucket capacity — the difference from fixed window.
--
-- The time comes from redis.call('TIME'), NOT from the client: many app instances call
-- the same limiter and their clocks differ. If the client sent `now`, a machine running
-- 200 ms fast would move itself into the next window early.
local cap  = tonumber(ARGV[1])
local win  = tonumber(ARGV[2])
local k    = KEYS[1]
local t    = redis.call('TIME')
local now  = t[1] * 1000 + math.floor(t[2] / 1000)
local d    = redis.call('HMGET', k, 'tokens', 'ts')
local tokens = tonumber(d[1])
local ts     = tonumber(d[2])
if tokens == nil then
  tokens = cap
  ts = now
end
local delta = now - ts
if delta < 0 then delta = 0 end
tokens = math.min(cap, tokens + delta * cap / win)
local ttl = win * 2
if tokens < 1 then
  redis.call('HSET', k, 'tokens', tokens, 'ts', now)
  redis.call('PEXPIRE', k, ttl)
  return '0|0|' .. math.ceil((1 - tokens) * win / cap)
end
tokens = tokens - 1
redis.call('HSET', k, 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', k, ttl)
return '1|' .. math.floor(tokens) .. '|0'

Bản này chạy trên cả ba app replica cùng lúc trong lab, sau load balancer, với hạn mức 500 request/giây toàn cục. Bắn 20 kết nối trong 10 giây:

Sai lệch 7 trên 5.500 — tức 0,13%. Đó là bằng chứng đo được rằng bộ đếm nguyên tử dùng chung thật sự giữ được hạn mức toàn cục, chứ không phải hạn mức nhân với số replica.

Còn một quyết định nữa quan trọng không kém thuật toán: giới hạn theo chiều nào. Theo người dùng đã đăng nhập là chính xác nhất nhưng không bảo vệ được endpoint đăng nhập (lúc đó chưa có người dùng nào). Theo IP thì bảo vệ được endpoint công khai nhưng đụng NAT. Theo endpoint thì bảo vệ được đúng chỗ đắt tiền. Thực tế bạn cần vài chiều cùng lúc, và mỗi chiều là một khoá Redis riêng.

13.4 Từ chối cho đúng cách

Từ chối là một hành động giao tiếp. Client bị từ chối sẽ làm gì đó, và cái nó làm phụ thuộc hoàn toàn vào những gì bạn nói với nó. Đây là phản hồi thật của lab khi xô đã cạn:

$ curl -si "localhost:3001/limited?user=drain2"

HTTP/1.1 429 Too Many Requests
X-RateLimit-Limit: 500          # your quota
X-RateLimit-Remaining: 0        # how much is left
X-RateLimit-Reset: 1            # how long until it refills (seconds)
Retry-After: 1                  # WAIT EXACTLY THIS MANY SECONDS
Content-Type: application/json; charset=utf-8

{"error":"rate_limited","retryAfterMs":2}

Bốn header đó là hợp đồng. Retry-After nói cho client biết chính xác khi nào quay lại — không có nó, client chỉ còn cách đoán, và cách đoán phổ biến nhất là thử lại ngay lập tức, đúng thứ bạn đang cố ngăn. Ba header X-RateLimit-* còn cho phép client tự điều tiết trước khi chạm hạn mức: một SDK tử tế thấy Remaining: 3 thì tự chậm lại thay vì lao vào tường.

Phản hồi thật ở trên phơi bày một chi tiết đáng chú ý: thời gian chờ thật là 2 mili giây (token bucket rót 500 token mỗi giây nên token kế tiếp có sau 2 ms), nhưng Retry-After tính bằng giây nên giá trị nhỏ nhất nó nói được là 1 — chậm hơn 500 lần so với sự thật. Đó là lý do phần thân phản hồi kèm thêm retryAfterMs: header giữ đúng chuẩn HTTP cho client phổ thông, còn client hiểu API của bạn thì đọc con số chính xác. Nếu chỉ có header, mọi client bị từ chối sẽ cùng chờ tròn 1 giây rồi cùng quay lại một lúc — bạn vừa tự tạo ra một đợt đồng bộ hoá, đúng vấn đề mà jitter ở Bài 17 sinh ra để giải.

Một câu hỏi thường bị bỏ qua: limiter tốn bao nhiêu? Nó nằm trên đường đi của mọi request, kể cả request được cho qua, nên chi phí của nó cộng thẳng vào p99 của toàn hệ thống. Đo bằng cách so cùng một endpoint có và không có limiter, đặt hạn mức cao đến mức không request nào bị từ chối (bốn cặp lần chạy, 20 kết nối, 10 giây mỗi lần):

p50 tăng khoảng 0,04 ms — đúng bằng một vòng mạng tới Redis, không có gì bất ngờ. Điều bất ngờ là p95 và p99 lại thấp hơn một cách nhất quán, ở cả bốn cặp lần chạy. Giải thích khả dĩ: /fast trả lời hoàn toàn đồng bộ nên nhiều request được xử lý dồn thành cụm trong một lượt event loop, còn /limited có một điểm nhường (await chờ Redis) chia nhỏ các cụm đó ra. Đây là giả thuyết chứ không phải kết luận đã chứng minh — lab này không đo trực tiếp độ trễ event loop, nên mình ghi lại đúng những gì đo được.

13.5 Load shedding: khi từ chối phải có chọn lọc

Rate limit trả lời câu hỏi "client này đã dùng quá phần của mình chưa". Load shedding trả lời một câu hỏi khác hẳn: "hệ thống đang quá tải, giờ bỏ cái gì". Câu thứ hai chỉ xuất hiện khi mọi client đều trong hạn mức mà tổng vẫn vượt năng lực — và lúc đó rate limit không giúp được gì, vì không ai vi phạm cả.

Số liệu từ phép đo toàn cục ở mục 13.3 cho thấy điều đầu tiên cần biết về từ chối: nó không miễn phí, nhưng nó rẻ hơn rất nhiều so với phục vụ. Trong 10 giây, lab phục vụ 5.493 request và từ chối 185.660 — tức nó xử lý được khoảng 18.500 lần từ chối mỗi giây, gấp 34 lần số request nó thật sự phục vụ. Đó là lý do "từ chối nhanh" là một chiến lược sống được: bạn vẫn trả một cái giá, nhưng cái giá đó nhỏ hơn một bậc độ lớn.

Nhưng cái giá đó chỉ nhỏ khi từ chối xảy ra sớm. Từ chối sau khi đã truy vấn database để kiểm tra hạn mức thì bạn đã trả gần hết chi phí rồi mới nói không. Nguyên tắc: limiter phải nằm trước mọi thứ đắt tiền — trước xác thực nếu có thể, chắc chắn là trước database.

Chi tiết dễ bỏ sót nhất trong hình trên là dòng đầu: health check. Nếu load shedding bỏ cả health check thì load balancer kết luận node đã chết và rút nó ra khỏi vòng phục vụ (Bài 3), dồn tải sang các node còn lại, khiến chúng cũng bắt đầu shed, cũng trượt health check, cũng bị rút ra. Cơ chế sinh ra để cứu hệ thống trở thành cơ chế giết hệ thống. Đây là dạng cascade failure sẽ được mổ xẻ đầy đủ ở Bài 17.

Tự làm lại các phép đo

cd blog/sysdesign/sysdesign-lab

# --- Window boundary: same 100/s limit, count the worst 1-second window ---
./tools/ratelimit-test.sh boundary    # fixed=200 · log=100 · counter=105 · token=119

# --- Time vs memory: the 4 algorithms are near-identical in speed... ---
./tools/ratelimit-test.sh bench       # p50 all ~0.08ms (empty GET baseline: 0.073ms)
# --- ...but differ more than 10-fold in memory ---
./tools/ratelimit-test.sh memory      # log 1499 B/user vs 121-171 B/user

# --- INCR + EXPIRE as two commands: keys stuck forever ---
./tools/ratelimit-test.sh nonatomic   # two-commands: 20/200 keys with no TTL · lua: 0/200

# --- What the limiter adds to every request ---
./tools/ratelimit-test.sh overhead    # /fast vs /limited: p50 +0.04ms

# --- 3 replicas behind the LB, a GLOBAL 500/s limit, 10 seconds ---
./tools/ratelimit-test.sh e2e 500     # 5493 allowed (expected 5500) · 185,660 x 429

Tóm lại

Rate limit chủ yếu bảo vệ bạn khỏi chính client của mình, không phải khỏi kẻ tấn công — nên đặt nó chỉ ở biên là bỏ trống đúng chỗ cascade failure bắt đầu.

Về thuật toán, phép đo cho một kết luận gọn: chọn thuật toán không phải chuyện tốc độ. Cả bốn đều cho p50 quanh 0,08 ms vì thứ tốn thời gian là vòng mạng chứ không phải phép tính. Khác biệt thật nằm ở hai chỗ khác — hành vi ở mốc giao cửa sổ (fixed window cho lọt 200% và không cấu hình nào sửa được) và bộ nhớ (sliding window log tốn 1.499 byte mỗi người dùng, gấp hơn 10 lần ba cái còn lại). Token bucket cũng cho burst, 119% chứ không phải 100% — nhưng burst của nó có chặn trên và chỉnh được, và đó mới là điểm khác biệt đáng nói.

Về cài đặt, một điều gần như không có ngoại lệ: gộp toàn bộ quyết định vào một script Lua. Bản INCR rồi EXPIRE tách rời làm 20 trên 200 khoá mắc kẹt không TTL trong phép đo — tức 20 người dùng bị chặn vĩnh viễn bởi chính cơ chế bảo vệ họ. Bù lại, bộ đếm nguyên tử dùng chung giữ được hạn mức toàn cục rất sát: 5.493 trên kỳ vọng 5.500 với ba replica không hề nói chuyện với nhau.

Và về cách từ chối: 429 kèm Retry-After, không bao giờ 5xx. Từ chối rẻ hơn phục vụ khoảng 34 lần trong lab này — nhưng chỉ khi nó xảy ra sớm, và chỉ khi nó có chọn lọc. Shed đồng đều là cách chắc chắn để phá SLO của nhóm quan trọng nhất.

Bài 14 đổi hướng: thay vì lưu trạng thái hiện tại rồi ghi đè liên tục, ta lưu chuỗi sự kiện đã xảy ra và tính lại trạng thái từ đó. Nó mở ra khả năng tua lại lịch sử để tìm lỗi — và đòi hỏi một thứ đã học ở Bài 11 làm điều kiện bắt buộc: tính idempotent.