Rate limiter phân tán
Hiểu đề
Yêu cầu chức năng
- Hệ thống giới hạn số request theo client (API key, user id hoặc IP) và theo endpoint
- Request vượt hạn mức nhận 429 kèm thông tin còn bao nhiêu và khi nào thử lại
- Admin đổi hạn mức theo gói (free, pro, enterprise) mà không cần deploy lại
- Một client gọi qua nhiều server hoặc nhiều region vẫn bị tính chung một hạn mức
Yêu cầu phi chức năng
- Độ trễ thêm vào mỗi request p99 < 2 ms
- Chịu được 1 triệu req/s đỉnh trên 3 region
- Sai số đếm giữa các region ≤ 5% so với hạn mức
- Rule mới có hiệu lực trong < 30 s
- Rate limiter hỏng không được làm sập API (độ sẵn sàng đường request 99,99%)
Ngoài phạm vi: Chống DDoS tầng mạng L3/L4 (giao cho nhà cung cấp edge); Phát hiện bot bằng hành vi hoặc CAPTCHA; Tính tiền theo lượng dùng (billing).
Thực thể và API
| Method | Endpoint | Ghi chú |
|---|---|---|
| POST | /internal/v1/ratelimit/check | Gateway hoặc sidecar gửi client key, endpoint, cost. Trả allowed, remaining, resetAt. Thường được nhúng thẳng vào gateway thay vì gọi HTTP. |
| GET | /v1/rules | Liệt kê rule theo gói và endpoint, kèm số version. |
| PUT | /v1/rules/{ruleId} | Admin sửa hạn mức. Tăng version để gateway kéo bản mới. |
| GET | /v1/clients/{clientId}/usage | Client xem mức dùng hiện tại so với hạn mức. |
Thiết kế tổng thể
Đi lần lượt từng yêu cầu chức năng. Mục tiêu ở đây là chạy đúng, việc tối ưu để dành cho phần đào sâu.
1) Hệ thống giới hạn số request theo client và endpoint
Mỗi request được nhận diện client, tìm rule trong cache cục bộ, rồi kiểm tra và trừ quota bằng một lệnh nguyên tử trên Redis. Kết quả quyết định cho đi tiếp hay trả 429 ngay tại gateway.
- 1Request tới gateway, đọc API key hoặc user id từ token, không có thì dùng IP
- 2Tìm rule khớp (gói + endpoint) trong bộ nhớ của gateway
- 3Gọi một Lua script trên Redis: nạp token theo thời gian đã trôi qua, trừ 1 nếu còn
- 4Còn token thì chuyển request tới service phía sau
- 5Hết token thì trả 429 và ghi ThrottleEvent theo mẫu
Nguồn: Grokking Modern System Design · ch.19 Rate Limiter ↗ · bài "Design of a Rate Limiter" · mục "Detailed design" (client identifier builder, throttle rules cache, decision-maker) ; Redis in Action ↗ · ch.11 · §11.1.1 Loading Lua scripts into Redis, §11.1.2 Creating a new status message (EVAL/EVALSHA chạy nguyên tử) ; Microservices Patterns ↗ (.zip) · ch.8 · §8.2.1 Overview of the API gateway pattern, mục "Implementing edge functions" (tr. 262)
2) Request vượt hạn mức nhận 429 kèm thông tin thử lại
Client lịch sự cần biết còn bao nhiêu và chờ bao lâu, nếu không chúng sẽ retry liên tục làm tải tệ hơn. Script trả luôn remaining và thời điểm reset nên không cần gọi thêm.
- 1Script trả về allowed, remaining, resetAt
- 2Gateway gắn header RateLimit-Limit, RateLimit-Remaining, RateLimit-Reset cho mọi response
- 3Response 429 có thêm Retry-After tính bằng giây
- 4SDK phía client đọc Retry-After và backoff có jitter
Nguồn: Grokking Modern System Design · ch.19 Rate Limiter ↗ · bài "Design of a Rate Limiter" · mục "Detailed design" (trả 429 Too Many Requests) ; Chưa có nguồn trong thư viện: tên header RateLimit-* / Retry-After và backoff có jitter phía client không có trong sách, giữ lại như quy ước HTTP cơ bản
3) Admin đổi hạn mức mà không cần deploy
Rule nằm trong một DB nhỏ, có version. Gateway giữ bản sao trong bộ nhớ và cập nhật khi version đổi, nên đường request không bao giờ phải đọc DB rule.
- 1Admin gọi PUT /v1/rules/{ruleId}, rule service ghi DB và tăng version
- 2Gateway kéo danh sách rule mỗi 10 s hoặc nhận push
- 3Gateway thay bảng rule trong bộ nhớ bằng bản mới
- 4Rule có hiệu lực trên toàn bộ gateway trong < 30 s
Nguồn: Grokking Modern System Design · ch.19 Rate Limiter ↗ · bài "Design of a Rate Limiter" · mục "Detailed design" (Rule database, Rules retriever chạy nền định kỳ, Throttle rules cache)
Hạ tầng theo quy mô
Cùng một sản phẩm, ba mức người dùng. Chọn từng mức để xem sơ đồ, phép tính và cấu hình server thay đổi thế nào.
Rate limit là middleware trong chính API Node.js, đếm chung trên một Redis managed nhỏ bằng fixed window. Rule nằm trong file config. Hai instance API nên không thể đếm trong bộ nhớ.
Ước lượng
- Request: 10.000 × 150 = 1.500.000 req/ngày / 86.400 ≈ 17,4 req/s, đỉnh ×3 ≈ 52 req/s
- API: ceil(52 / 600) = 1, lấy tối thiểu 2 instance
- Redis: mỗi lần kiểm tra ≈ 2 lệnh (INCR + EXPIRE) → 52 × 2 ≈ 104 ops/s, ≈ 0,1% sức một node
- RAM: 10.000 key × (40 + 8 + 100 B) × 1,3 ≈ 1,9 MB
- Hạn mức mẫu 100 req/phút/key = 100 / 60 ≈ 1,7 req/s mỗi client
Nguồn con số: Grokking Modern System Design · ch.5 Back-of-the-envelope Calculations ↗ · mục "Standard numbers to remember", "Requests estimation" ; Quy tắc ước lượng của khoá học · /hoc/chon-server
Bảng hạ tầng
| Thành phần | Chọn | Số lượng | Cấu hình | Vì sao |
|---|---|---|---|---|
| Load balancer | LB managed của Cloud Run / ALB | 1 (managed) | Mặc định | Chia tải cho 2 instance API. |
| API + middleware | Node.js (NestJS), middleware rate limit dùng Redis | 2 | 2 vCPU · 4 GB RAM | 52 req/s chỉ khoảng 5% sức một instance; limit chạy ngay trong process. |
| Bộ đếm | Redis managed, fixed window INCR + EXPIRE | 1 | 1 GB RAM | Vài MB dữ liệu và 104 ops/s; không có replica vì đã chọn fail open. |
| Database | PostgreSQL managed (API key, gói cước) | 1 | 2 vCPU · 8 GB | Lưu API key và gói, API cache trong bộ nhớ 60 s. |
| Rule | File JSON trong repo, đọc lúc khởi động | 1 file | Vài chục dòng | Rule ít đổi, sửa rule bằng một lần deploy là chấp nhận được. |
- Điểm xuất phát
- Dùng Redis chung ngay từ đầu vì có 2 instance
- Fixed window là đủ khi mục tiêu chỉ là chặn client lỗi
Khi có nhiều service, mỗi service tự gắn middleware khác nhau và request xấu vẫn tiêu tài nguyên service. Burst ở ranh giới cửa sổ bắt đầu gây đột biến tải.
Cấu hình và chi phí là ước lượng để học và trình bày trong phỏng vấn. Xem cách tính ở bài Chọn server.
So sánh nhanh ba mức
| Thành phần | Mức 1 | Mức 2 | Mức 3 |
|---|---|---|---|
| Người dùng | 10.000 DAU · ≈ 50 req/s cần bảo vệ | 1 triệu DAU · ≈ 20.000 req/s cần bảo vệ | 50 triệu+ DAU · 1 triệu req/s trên 3 region |
| Chi phí | ≈ 50–100 USD/tháng | ≈ 1.500–3.000 USD/tháng (chỉ tầng gateway và rate limit) | ≈ 35.000–60.000 USD/tháng (chỉ tầng gateway và rate limit, phần lớn là 126 pod gateway) |
| Load balancer | LB managed của Cloud Run / ALB 1 (managed) × Mặc định | L7 LB managed 1 (managed) × Mặc định | Chưa cần |
| API + middleware | Node.js (NestJS), middleware rate limit dùng Redis 2 × 2 vCPU · 4 GB RAM | Chưa cần | Chưa cần |
| Bộ đếm | Redis managed, fixed window INCR + EXPIRE 1 × 1 GB RAM | Redis Cluster, key có hash tag theo client 3 shard × 2 = 6 node × 2 vCPU · 4 GB RAM | Chưa cần |
| Database | PostgreSQL managed (API key, gói cước) 1 × 2 vCPU · 8 GB | Chưa cần | Chưa cần |
| Rule | File JSON trong repo, đọc lúc khởi động 1 file × Vài chục dòng | Chưa cần | Chưa cần |
| API gateway | Chưa cần | Kong (plugin rate limit dùng Redis, Lua token bucket) 9 × 2 vCPU · 4 GB RAM | Envoy trên Kubernetes, token bucket cục bộ + đồng bộ theo lô 126 pod (42/region) × 8 vCPU · 16 GB RAM |
| Limiter dự phòng | Chưa cần | Token bucket trong bộ nhớ gateway Trong mỗi gateway × Hạn mức / 9 | Chưa cần |
| Rule service | Chưa cần | Node.js + PostgreSQL managed 2 + 1 DB × 1 vCPU · 2 GB; DB 2 vCPU · 8 GB | Chưa cần |
| Giám sát | Chưa cần | Prometheus + Grafana 1 bộ (managed) × Mặc định | Prometheus + log ThrottleEvent lấy mẫu 1% 1 bộ/region × Managed |
| Edge / WAF | Chưa cần | Chưa cần | Cloudflare hoặc AWS WAF, rule theo IP Toàn cầu (managed) × Hạn mức thô theo IP |
| DNS + LB | Chưa cần | Chưa cần | Anycast / GeoDNS + L7 LB mỗi region 3 region × Active-active |
| Bộ đếm region | Chưa cần | Chưa cần | Redis Cluster, Lua cho thao tác gộp 3 shard × 2 = 6 node/region, tổng 18 × 4 vCPU · 8 GB RAM |
| Đồng bộ chéo region | Chưa cần | Chưa cần | Kafka + MirrorMaker 2 3 broker/region, tổng 9 × Topic delta 6 partition |
| Sync worker | Chưa cần | Chưa cần | Consumer Go hoặc Node.js, ghi INCRBY vào key remote 3 pod/region, tổng 9 × 2 vCPU · 4 GB |
| Rule control plane | Chưa cần | Chưa cần | Rule service + PostgreSQL, push qua xDS tới Envoy 3 pod + 1 DB HA × 2 vCPU · 4 GB; DB 4 vCPU · 16 GB |
Đào sâu
Mỗi câu hỏi đi từ cách đơn giản đến cách người phỏng vấn mong đợi ở cấp senior.
1) Chọn thuật toán đếm nào?
Đếm theo khung phút cố định bằng key dạng client:12h05 và INCR. Rất rẻ, một key một số nguyên. Nhưng client có thể gửi đủ hạn mức ở giây 59 và thêm đủ hạn mức ở giây 0 của phút sau, tức gấp đôi trong 2 giây.
Đánh đổi: Rẻ và dễ hiểu nhất nhưng cho phép burst gấp 2 lần ở ranh giới cửa sổ.
Nguồn: Grokking Modern System Design · ch.19 Rate Limiter ↗ · bài "Rate Limiter Algorithms" · mục "Fixed window counter algorithm" (Disadvantages: burst gấp đôi ở mép cửa sổ)
Lưu timestamp của từng request trong một sorted set, xóa phần cũ hơn cửa sổ rồi đếm. Chính xác tuyệt đối. Nhưng hạn mức 10.000 req/giờ nghĩa là tới 10.000 phần tử mỗi client, tốn RAM và CPU.
Đánh đổi: Chính xác nhất nhưng bộ nhớ tăng theo hạn mức, không hợp với hạn mức lớn.
Nguồn: Grokking Modern System Design · ch.19 Rate Limiter ↗ · bài "Rate Limiter Algorithms" · mục "Sliding window log algorithm" (Disadvantages: tốn bộ nhớ lưu timestamp) ; Redis in Action ↗ · ch.3 · §3.5 Sorted sets
Sliding window counter giữ 2 bộ đếm (cửa sổ hiện tại và trước) và ước lượng bằng trọng số thời gian, sai số nhỏ với chỉ 2 số nguyên. Token bucket giữ số token và thời điểm nạp, cho phép burst có kiểm soát rồi giữ tốc độ trung bình, hợp với API công khai. Chọn token bucket khi muốn cho phép burst ngắn, sliding window counter khi muốn hạn mức theo phút dễ giải thích.
Đánh đổi: Bộ nhớ cố định mỗi client và đủ chính xác, đổi lại là ước lượng chứ không chính xác tuyệt đối.
Nguồn: Grokking Modern System Design · ch.19 Rate Limiter ↗ · bài "Rate Limiter Algorithms" · mục "Token bucket algorithm", "Sliding window counter algorithm", "A comparison of rate-limiting algorithms"
2) Nhiều gateway cùng cập nhật một bộ đếm trên Redis, làm sao không bị race?
Đọc số token, tính toán trong Node.js, rồi ghi lại. Hai gateway đọc cùng lúc thấy còn 1 token, cả hai cho qua và cùng ghi 0. Dưới tải cao, client vượt hạn mức nhiều lần.
Đánh đổi: Dễ viết nhưng sai đúng lúc quan trọng nhất là khi tải cao.
Nguồn: Grokking Modern System Design · ch.19 Rate Limiter ↗ · bài "Design of a Rate Limiter" · mục "Race condition" ("get-then-set")
Với fixed window, INCR đã nguyên tử nên đủ đúng, thêm EXPIRE trong cùng MULTI. Với token bucket cần đọc rồi ghi, WATCH/MULTI phát hiện xung đột và thử lại. Khi một client nóng bị nhiều gateway gọi cùng lúc, số lần thử lại tăng vọt.
Đánh đổi: Đúng, nhưng optimistic lock thử lại nhiều dưới tranh chấp và tốn nhiều round-trip.
Nguồn: Redis in Action ↗ · ch.4 · §4.4 Redis transactions (WATCH/MULTI/EXEC) ; Redis in Action ↗ · ch.11 · §11.3 Doing away with WATCH/MULTI/EXEC (nhiều lần thử lại khi tranh chấp cao) ; Grokking Modern System Design · ch.19 Rate Limiter ↗ · bài "Design of a Rate Limiter" · mục "Race condition" ("set-then-get")
Đưa toàn bộ logic nạp token, kiểm tra và trừ vào một Lua script, gọi bằng EVALSHA. Redis chạy script đơn luồng nên không có race và chỉ tốn một round-trip. Ở Redis Cluster, đặt mọi key của một client chung hash tag như {client123} để chúng nằm cùng shard. Dùng thời gian của Redis (TIME) thay vì đồng hồ từng gateway.
Đánh đổi: Nguyên tử và nhanh nhất, đổi lại script phải ngắn vì nó chặn Redis trong lúc chạy và logic khó test hơn code ứng dụng.
Nguồn: Redis in Action ↗ · ch.11 · §11.1.1 Loading Lua scripts into Redis (SCRIPT LOAD + EVALSHA), §11.1.2 (Redis không cho lệnh khác chạy khi đang chạy script), §11.5 Summary (giới hạn script khi sharding) ; Chưa có nguồn trong thư viện: hash tag của Redis Cluster và lệnh TIME không có trong sách
3) Đặt rate limiter ở đâu: gateway, trong service hay sidecar?
Giới hạn ở client thì kẻ xấu bỏ qua được. Giới hạn trong bộ nhớ từng instance thì với 10 instance, client thực tế được gấp 10 lần hạn mức và con số thay đổi theo autoscale.
Đánh đổi: Không tốn hạ tầng nhưng không thực thi được hạn mức thật.
Nguồn: Grokking Modern System Design · ch.19 Rate Limiter ↗ · bài "Requirements of a Rate Limiter's Design" · mục "Where to place the rate limiter" (đặt ở client dễ bị can thiệp), mục "Two models for implementing a rate limiter"
Mỗi service tự gắn middleware gọi Redis. Hiểu được ngữ cảnh nghiệp vụ, ví dụ giới hạn số lần gửi OTP theo số điện thoại. Nhưng request xấu đã đi qua LB và tốn tài nguyên service, và mỗi team viết một kiểu.
Đánh đổi: Linh hoạt theo nghiệp vụ nhưng lặp code và chặn muộn.
Nguồn: Grokking Modern System Design · ch.19 Rate Limiter ↗ · bài "Requirements of a Rate Limiter's Design" · mục "Where to place the rate limiter" (server side, middleware) và Points to Ponder "Can a rate limiter be used as a load balancer?" (giới hạn theo thao tác nên đặt ở application server)
Edge/WAF chặn IP gửi quá dày trước khi vào hạ tầng. API gateway (hoặc sidecar Envoy trong service mesh) thực thi hạn mức theo API key và gói cước bằng một cấu hình chung. Chỉ những giới hạn cần dữ liệu nghiệp vụ mới nằm trong service. Mỗi lớp có trách nhiệm rõ và request xấu bị chặn càng sớm càng tốt.
Đánh đổi: Chặn sớm và thống nhất, đổi lại phải quản lý rule ở nhiều lớp và debug 429 khó hơn nếu không ghi rõ lớp nào chặn.
Nguồn: Microservices Patterns ↗ (.zip) · ch.8 · §8.2.1 Overview of the API gateway pattern, mục "Implementing edge functions" (rate limiting, tr. 262) ; Microservices Patterns ↗ (.zip) · ch.12 · §12.4.5 Using a service mesh to separate deployment from release (Istio/Envoy enforce quota và rate limit, tr. 409–410) ; Grokking Modern System Design · ch.19 Rate Limiter ↗ · bài "Design of a Rate Limiter" · Point to Ponder (nhiều rate limiter ở các tầng khác nhau) ; Chưa có nguồn trong thư viện: WAF/edge chặn theo IP
4) Redis chết hoặc chạy nhiều region thì xử lý thế nào?
Redis lỗi thì chặn hết request, nghĩa là rate limiter làm sập toàn bộ API. Một Redis đặt ở một region khiến request từ châu lục khác tốn thêm hàng chục ms mỗi lần kiểm tra (Grokking ghi một gói SF→NYC mất ≈ 71 ms).
Đánh đổi: Đếm chính xác toàn cầu nhưng biến rate limiter thành điểm chết duy nhất và rất chậm.
Nguồn: Grokking Modern System Design · ch.19 Rate Limiter ↗ · bài "Design of a Rate Limiter" · mục "Request processing", Point to Ponder (khi rate limiter lỗi, mặc định không throttle) ; Grokking Modern System Design · ch.19 Rate Limiter ↗ · bài "Requirements of a Rate Limiter's Design" · mục "Two models for implementing a rate limiter" (DB tập trung tăng độ trễ) ; Grokking Modern System Design · ch.5 Back-of-the-envelope Calculations ↗ · mục "Standard numbers to remember" (gửi gói SF→NYC ≈ 71 ms)
Gọi Redis với timeout khoảng 5 ms, lỗi hoặc quá hạn thì cho qua. Để không mở toang, mỗi gateway giữ token bucket trong bộ nhớ với hạn mức = hạn mức chung / số instance. Mỗi region có Redis riêng.
Đánh đổi: API sống khi Redis chết, đổi lại lúc sự cố hạn mức chỉ gần đúng và mỗi region đếm riêng.
Nguồn: Grokking Modern System Design · ch.19 Rate Limiter ↗ · bài "Design of a Rate Limiter" · Point to Ponder (mặc định không throttle khi rate limiter hỏng), mục "Conclusion" (nhiều rate limiter, không có điểm chết duy nhất)
Mỗi region đếm trên Redis của mình, gateway gom số dùng theo lô rồi đẩy delta sang region khác qua Kafka mỗi 1 s. Quyết định dựa trên số cục bộ cộng số từ region khác, sai số giới hạn bởi lượng request lọt trong 1 s. Endpoint đắt hoặc nhạy cảm (đăng nhập, OTP, thanh toán) fail closed, còn lại fail open có giới hạn cục bộ.
Đánh đổi: Nhanh và chịu được mất một region, đổi lại chấp nhận vượt hạn mức nhỏ trong khoảng đồng bộ và hệ thống phức tạp hơn nhiều.
Nguồn: Grokking Modern System Design · ch.19 Rate Limiter ↗ · bài "Requirements of a Rate Limiter's Design" · mục "Two models for implementing a rate limiter" (DB phân tán: client có thể vượt hạn mức trong lúc gom trạng thái) ; Grokking Modern System Design · ch.19 Rate Limiter ↗ · bài "Design of a Rate Limiter" · mục "A rate limiter should not be on the client's critical path" (cập nhật offline) ; Chưa có nguồn trong thư viện: đồng bộ delta qua Kafka giữa các region (thư viện không có sách Kafka)
Trong phỏng vấn
- “Tôi chọn token bucket vì cho phép burst ngắn mà vẫn giữ tốc độ trung bình, bộ nhớ cố định mỗi client.”
- “Kiểm tra và trừ token nằm trong một Lua script để Redis chạy nguyên tử, tránh race giữa các gateway.”
- “Rate limiter không được là lý do API sập: mặc định fail open có giới hạn cục bộ, chỉ endpoint nhạy cảm mới fail closed.”
- “Ở nhiều region tôi đếm tại chỗ và đồng bộ delta mỗi giây, chấp nhận sai số nhỏ để không phải trả 100 ms cho mỗi request.”
- Đếm trong bộ nhớ từng instance rồi quên rằng autoscale nhân hạn mức lên theo số instance
- GET rồi SET từ code ứng dụng, bị race khi tải cao
- Chỉ trả 429 mà không có Retry-After, client retry liên tục làm tải tệ hơn
- Đặt một Redis toàn cầu cho mọi region, mỗi request thêm vài chục tới hơn 100 ms
Đọc thêm
Sách trong thư viện của bạn. Số chương có thể lệch nhẹ so với bản PDF.