Đến nội dung chính
notes.vinhnq.com

Tìm kiếm

System DesignSenior12 phút đọc

Rate limiting: năm thuật toán, token bucket trên Redis và thiết kế bộ giới hạn phân tán

Ôn 9 thẻ
Trong bài này

Cụm bài Cache trong system design: 1. Cache nhiều tầng và bộ đếm · 2. Rate limiting

Rate limiting giới hạn số request một “chủ thể” (user, API key, IP) được gửi trong một khoảng thời gian, để chống lạm dụng và bảo vệ hệ thống phía sau. Bài này so năm thuật toán trên cùng một ví dụ, cài token bucket phân tán bằng Redis, và trả lời câu hỏi “chọn thuật toán nào”.

1. Đặt rate limiter ở đâu, giới hạn theo gì

Ý chính: đặt càng gần biên càng rẻ (API gateway, Nginx), nhưng giới hạn theo nghiệp vụ (gói cước, loại API) thì cần ở gateway hoặc trong service.

  • Theo chủ thể: API key, user id, IP (cho request chưa đăng nhập), hoặc tổ hợp (user + endpoint).
  • Theo tầng: Nginx limit_req chặn thô theo IP; gateway (Spring Cloud Gateway, Kong) theo API key và gói; trong service cho thao tác đắt (gửi OTP: 3 lần/10 phút).
  • Phản hồi: 429 Too Many Requests kèm Retry-After, và nên có header cho biết hạn mức còn lại (RateLimit-Limit, RateLimit-Remaining, RateLimit-Reset) để client tự điều tiết.

Ví dụ chạy suốt bài: giới hạn 10 request/phút cho mỗi API key.

2. Năm thuật toán

Ý chính: các thuật toán khác nhau ở ba điểm: xử lý burst ở ranh giới thế nào, tốn bao nhiêu bộ nhớ mỗi key, và có làm request phải chờ không.

2.1. Fixed window counter

Mỗi phút một bộ đếm rl:{key}:{phút}; INCR, nếu > 10 thì từ chối; key hết hạn sau 60 s. Rẻ và dễ, nhưng client gửi 10 request lúc 00:59 và 10 request lúc 01:00 là lọt 20 request trong 2 giây.

2.2. Sliding window log

Lưu timestamp mọi request trong ZSET; mỗi request xoá các mục cũ hơn 60 s rồi đếm. Chính xác tuyệt đối, nhưng tốn bộ nhớ theo số request (10 timestamp/key, với giới hạn 10.000/phút là 10.000 phần tử/key).

2.3. Sliding window counter

Giữ bộ đếm phút trước và phút này, ước lượng:

ước lượng = đếm_phút_này + đếm_phút_trước × (phần còn lại của phút trước trong cửa sổ)

Đang ở giây thứ 18 của phút này (30% phút), phút trước có 8 request, phút này 3: ước lượng = 3 + 8 × 0,7 = 8,6 < 10 → cho qua. Chính xác hơn fixed window, vẫn chỉ hai số. Sai số đến từ giả định request phút trước rải đều; Cloudflare báo sai lệch rất nhỏ trên traffic thật.

2.4. Leaky bucket

Request vào một hàng đợi dung lượng cố định; một worker lấy ra với tốc độ cố định (10/phút). Hàng đầy thì từ chối. Đầu ra rất đều, hợp khi phía sau chỉ chịu nổi tốc độ cố định (ví dụ API bên thứ ba). Nhược: request phải chờ trong hàng, độ trễ tăng; cài bằng message queue là tự nhiên.

2.5. Token bucket

Một “xô” chứa tối đa capacity token, được nạp rate token mỗi giây. Mỗi request lấy một token; hết token thì từ chối. Chỉ cần lưu hai số: số token còn lại và thời điểm nạp gần nhất; lúc có request mới tính bù token theo thời gian đã trôi.

Fixed window Sliding log Sliding counter Leaky bucket Token bucket
Bộ nhớ / key 1 số N timestamp 2 số hàng đợi 2 số
Burst ở ranh giới lọt ×2 không ít không có, tới capacity
Request phải chờ không không không có không
Đầu ra đều không không không rất đều trung bình đều

3. Token bucket phân tán trên Redis

Ý chính: nhiều instance gateway phải chia chung một xô, nên trạng thái nằm ở Redis. Đọc, tính và ghi phải nằm trong một Lua script để không có race.

Nếu client GET số token, tính trong Java rồi SET, hai instance cùng đọc “còn 1 token” và cả hai cho qua. Lua chạy atomic trên Redis (Redis thực thi lệnh tuần tự) nên giải quyết được. WATCH/MULTI (optimistic lock của Redis) cũng làm được nhưng phải retry khi xung đột; Lua đơn giản và nhanh hơn.

-- KEYS[1] = rl:{apiKey}   ARGV: rate (token/s), capacity, now_ms, requested
local rate, cap, now, req = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3]), tonumber(ARGV[4])
local s = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(s[1]) or cap
local ts = tonumber(s[2]) or now
tokens = math.min(cap, tokens + (now - ts) / 1000 * rate)   -- nạp bù
local allowed = tokens >= req
if allowed then tokens = tokens - req end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(cap / rate * 1000) + 1000)
return { allowed and 1 or 0, tostring(tokens) }

Lưu ý: now nên lấy từ Redis (redis.call('TIME')) thay vì từ máy gọi, để đồng hồ lệch giữa các instance không làm sai phép tính.

Ước lượng bộ nhớ: mỗi key là một hash nhỏ ~100 byte. 10 triệu API key hoạt động ≈ 1 GB, vừa một Redis. Tải: 200K request/s qua gateway là 200K lần gọi script/s, vượt một node (~50–80K lệnh/s), nên dùng Redis Cluster; key theo API key nên chia đều slot.

Lấy token theo lô và giới hạn cục bộ

Mỗi request một round-trip tới Redis thêm ~0,5–2 ms và tải Redis bằng đúng tải gateway. Cách giảm:

  • Lấy theo lô: instance gọi script với requested = 20, giữ 20 token trong bộ nhớ, phục vụ 20 request mà không gọi Redis. Hết thì lấy lô mới. Đổi lại: một instance có thể giữ token không dùng tới (giới hạn tổng thể lệch một chút), nên lô nhỏ so với capacity và có hạn dùng ngắn.
  • Giới hạn cục bộ chia đều: N instance, mỗi instance giới hạn limit / N bằng Guava hay Bucket4j trong bộ nhớ. Không cần Redis, nhưng sai khi load balancer phân phối lệch hay khi số instance thay đổi.
  • Hai tầng: cục bộ chặn thô (chống DDoS rẻ), Redis chặn chính xác cho hạn mức theo gói.

Thư viện Java: Bucket4j (token bucket, có backend Redis/Hazelcast/JCache), Resilience4j RateLimiter (giới hạn theo chu kỳ, trong một JVM), Guava RateLimiter (token bucket mượt, trong một JVM; acquire() chặn chờ nên giống leaky bucket nếu dùng sai). Spring Cloud Gateway có sẵn RequestRateLimiter dùng Redis + Lua token bucket.

4. Thiết kế trong phỏng vấn

Ý chính: trình bày theo thứ tự: yêu cầu (giới hạn theo gì, chính xác tới đâu), thuật toán, nơi lưu trạng thái, đường đi của request, và lỗi.

flowchart LR
  C[Client] --> G[API Gateway]
  G -->|Lua script| R[(Redis Cluster)]
  G -->|cho qua| S[Service]
  G -->|429 + Retry-After| C
  P[(Bảng gói cước)] -.->|cache cấu hình| G

Các câu nên chủ động nói:

  • Cấu hình hạn mức theo gói lưu ở DB, cache trong gateway, đổi không cần deploy.
  • Nhiều vùng (multi-region): mỗi vùng một Redis, chia hạn mức theo vùng hoặc chấp nhận lệch; đồng bộ toàn cầu mỗi request quá chậm.
  • Log và metric: số request bị chặn theo key và endpoint, để phát hiện client lỗi hay bị tấn công.
  • Client nên retry với exponential backoff + jitter khi nhận 429, tôn trọng Retry-After.

Bài tập

Bài 1: Rate limit cho API công khai nhiều gói

Đề: API có 3 gói: Free 60 request/phút, Pro 1.000/phút, Enterprise 10.000/phút và burst 2.000. Có 5 triệu API key, peak 150K request/s qua 30 instance gateway. Chọn thuật toán, tham số, nơi lưu, và xử lý khi Redis chậm.

Lời giải Bài 1
  • Thuật toán: token bucket cho mọi gói. Free: rate = 1/s, capacity = 60. Pro: rate ≈ 16,7/s, capacity = 1.000. Enterprise: rate ≈ 167/s, capacity = 2.000 (burst theo hợp đồng).
  • Lưu: Redis Cluster, key rl:{apiKey}. Bộ nhớ: 5M × ~100 B ≈ 500 MB. Tải 150K lệnh/s → 3–4 master (mỗi master ~50K script/s), mỗi master một replica.
  • Giảm tải: Enterprise gọi rất nhiều → lấy token theo lô 50 mỗi instance; Free/Pro gọi script mỗi request (ít request mỗi key).
  • Khi Redis chậm: timeout 10 ms, circuit breaker mở khi > 50% lỗi trong 10 s; lúc mở dùng Bucket4j cục bộ với hạn mức limit / 30. Fail-open cho đọc, fail-closed cho endpoint tốn tiền (gửi SMS).
  • Phản hồi: 429, Retry-After tính từ thời gian cần để có đủ 1 token, cùng các header hạn mức.

Ghi nhớ

  • Giải thích được vì sao fixed window lọt gấp đôi ở ranh giới, và sliding window counter ước lượng thế nào.
  • So sánh được leaky bucket và token bucket: cái nào bắt request chờ, cái nào cho burst.
  • Viết được ý chính của Lua script token bucket và giải thích vì sao phải chạy trong Redis.
  • Biết hai cách giảm round-trip tới Redis và cái giá của chúng.
  • Quyết định được fail-open hay fail-closed cho từng loại endpoint.

Câu hỏi phỏng vấn

Mid

Fixed window có vấn đề gì?

Burst ở ranh giới: client dồn request cuối cửa sổ này và đầu cửa sổ sau, lọt gần gấp đôi giới hạn trong thời gian rất ngắn.

Sliding window counter hoặc token bucket giảm vấn đề này mà vẫn chỉ cần vài số mỗi key.

Token bucket và leaky bucket khác nhau thế nào?

Token bucket giới hạn tốc độ trung bình nhưng cho burst tới capacity và không bắt request chờ; leaky bucket xếp request vào hàng và xả ở tốc độ cố định, đầu ra đều nhưng tăng độ trễ.

Token bucket hợp với API người dùng. Leaky bucket hợp khi phía sau chỉ chịu tốc độ cố định, ví dụ gọi đối tác giới hạn 100 request/s.

Vì sao cài rate limiter bằng GET rồi SET trên Redis là sai?

Hai instance cùng đọc giá trị cũ, cùng quyết định cho qua và cùng ghi, nên số request lọt vượt giới hạn (race condition read-modify-write).

Dùng một lệnh atomic (INCR cho fixed window) hoặc Lua script cho thuật toán nhiều bước; WATCH/MULTI cũng được nhưng phải retry.

Senior

Thiết kế rate limiter phân tán cho API gateway 200K request/s.

Token bucket theo API key, trạng thái ở Redis Cluster, đọc-tính-ghi trong một Lua script; thêm lô token và giới hạn cục bộ để giảm phụ thuộc Redis.

Ước lượng: 200K script/s cần 3–4 master. Cấu hình hạn mức cache ở gateway. Redis lỗi: timeout ngắn, circuit breaker, rơi về giới hạn cục bộ; chọn fail-open/closed theo endpoint. Trả 429 với Retry-After, đo số request bị chặn.

Rate limit nhiều region thì làm sao?

Không đồng bộ mỗi request qua các vùng (quá chậm); chia hạn mức theo vùng hoặc mỗi vùng giới hạn riêng rồi đồng bộ bộ đếm bất đồng bộ, chấp nhận lệch nhỏ.

Nếu hạn mức là hợp đồng tính tiền, đối soát chính xác bằng log sử dụng sau đó, không bằng limiter thời gian thực.

Redis rate limiter bị chậm làm tăng p99 của toàn bộ API. Bạn xử lý thế nào?

Giảm số lần gọi và giới hạn thời gian chờ: lấy token theo lô, timeout vài ms, circuit breaker, và giới hạn cục bộ khi Redis không trả lời kịp.

Kiểm tra thêm: key nóng (một API key chiếm phần lớn tải dồn vào một slot), script nặng, mạng giữa gateway và Redis. Key nóng thì cho key đó giới hạn cục bộ hoặc chia nhỏ xô.

Từ vựng tiếng Anh

Term Phát âm Nghĩa Ví dụ câu tiếng Anh dùng trong phỏng vấn
rate limiting /reɪt ˈlɪm.ɪ.tɪŋ/ giới hạn tần suất “Rate limiting protects downstream services from abusive clients.”
token bucket /ˈtoʊ.kən ˈbʌk.ɪt/ xô token “A token bucket allows short bursts up to its capacity.”
leaky bucket /ˈliː.ki ˈbʌk.ɪt/ xô rò “A leaky bucket smooths output to a constant rate.”
burst /bɝːst/ dồn dập “Fixed windows let through a burst at the boundary.”
throttle /ˈθrɑː.t̬əl/ điều tiết, bóp tốc độ “We throttle free-tier keys to sixty requests a minute.”
fail open /feɪl ˈoʊ.pən/ lỗi thì cho qua “For read endpoints we fail open if Redis is down.”
fail closed /feɪl kloʊzd/ lỗi thì chặn “OTP sending fails closed because each SMS costs money.”
atomic /əˈtɑː.mɪk/ nguyên tử, không bị chen “The Lua script makes the check-and-decrement atomic.”
quota /ˈkwoʊ.t̬ə/ hạn mức “Each plan has its own quota stored in the database.”
backoff /ˈbæk.ɑːf/ lùi thời gian thử lại “Clients should retry with exponential backoff after a 429.”

Ghi chép dựa trên khoá System Design (Ronin Engineer), viết lại theo cách hiểu của mình.