- Rate Limiter kiểm soát số lượng yêu cầu mà một người dùng, địa chỉ IP hoặc khóa API được phép gửi trong một khoảng thời gian xác định; khi vượt ngưỡng, hệ thống trả về mã HTTP 429 Too Many Requests kèm các trường Header
X-RateLimit-*vàRetry-After. - Trong 5 thuật toán kinh điển, Token Bucket (Xô chứa thẻ) được các ông lớn như Amazon AWS và Stripe ưa chuộng nhất vì vừa dễ cài đặt với \(\mathcal{O}(1)\) bộ nhớ, vừa cho phép lưu lượng đột biến ngắn hạn (Burst Traffic) hợp lệ của người dùng thật.
- Thuật toán Fixed Window Counter tuy đơn giản nhưng mắc điểm yếu chí mạng ở ranh giới hai cửa sổ thời gian (cho phép lượng truy cập gấp \(2\text{ lần}\) hạn ngạch); Sliding Window Log hoặc Sliding Window Counter khắc phục triệt để vấn đề này.
- Trong môi trường phân tán nhiều máy chủ API Gateway, việc đọc - kiểm tra - trừ bộ đếm trên Redis phải được gói vào một Redis Lua Script hoặc giao dịch nguyên tử để loại bỏ hoàn toàn lỗi tranh chấp đồng thời (Race Condition).
Vai trò của Rate Limiter và Vị trí đặt trong Kiến trúc
Khi thảo luận cùng người phỏng vấn ở bước đầu của bài toán nhập môn System Design cho lập trình viên, bạn cần làm rõ 3 mục tiêu sống còn của một hệ thống Rate Limiter:
- Chống cạn kiệt tài nguyên (Resource Starvation & DoS): Ngăn chặn bot tự động cào dữ liệu (Scraping), tấn công vét cạn mật khẩu (Brute-force Login) hoặc một khách hàng bị lỗi vòng lặp
while(true)làm nghẽn toàn bộ cơ sở dữ liệu dùng chung (Noisy Neighbor problem). - Kiểm soát chi phí hạ tầng và API bên thứ ba: Đặc biệt quan trọng với các dịch vụ gọi cổng SMS OTP, cổng thanh toán hoặc mô hình AI tính phí theo từng yêu cầu.
- Phân tầng gói cước thương mại (Tiered Pricing): Giới hạn tài khoản miễn phí ở mức \(60\text{ req/phút}\), tài khoản doanh nghiệp ở mức \(5{,}000\text{ req/phút}\).
Đặt Rate Limiter ở đâu?
Vị trí chuẩn xác nhất là tại tầng API Gateway / Reverse Proxy (như Kong, Envoy, NGINX hoặc Cloudflare) đứng ngay trước cụm Microservices. Đặt tại cổng biên giúp chặn các yêu cầu vi phạm ngay từ vòng ngoài trước khi chúng tiêu tốn băng thông mạng nội bộ, CPU xử lý nghiệp vụ hay kết nối Database. Vì nằm trên đường đi của mọi yêu cầu, phép kiểm tra Rate Limit không được phép truy vấn ổ cứng mà phải diễn ra hoàn toàn trong bộ nhớ RAM (thường qua cụm Redis In-Memory).
So sánh 5 thuật toán giới hạn lưu lượng kinh điển
Không có một thuật toán duy nhất hoàn hảo cho mọi kịch bản. Dưới đây là bản phân tích cơ chế và đánh đổi của 5 thuật toán phổ biến nhất:
| Thuật toán | Nguyên lý hoạt động cốt lõi | Bộ nhớ mỗi User | Xử lý đỉnh tải (Burst) | Điểm yếu / Đánh đổi lớn nhất |
|---|---|---|---|---|
| 1. Token Bucket (Xô chứa thẻ) | Xô có sức chứa tối đa \(C\) thẻ, được nạp tự động với tốc độ \(r\text{ thẻ/giây}\). Mỗi request lấy đi 1 thẻ; nếu xô rỗng thì từ chối. | \(\mathcal{O}(1)\) (chỉ lưu 2 số: tokens, last_ts) |
Cho phép đỉnh tải tức thời lên tới \(C\) request cùng lúc | Cần chọn cặp tham số \((C, r)\) khéo léo theo sức chịu tải của dịch vụ đích |
| 2. Leaky Bucket (Xô rò nước) | Các request đi vào một hàng đợi FIFO sức chứa \(C\) và được lấy ra xử lý với tốc độ cố định không đổi \(r\text{ req/s}\). | \(\mathcal{O}(C)\) cho hàng đợi | Làm phẳng hoàn toàn thành dòng chảy đều đặn | Nếu có đợt tăng tải ngắn hạn, các request mới phải nằm chờ trong hàng đợi gây tăng độ trễ |
| 3. Fixed Window Counter | Chia trục thời gian thành các ô cố định (ví dụ mỗi phút 10:00 - 10:01). Mỗi ô có 1 biến đếm tăng dần đến ngưỡng \(K\). |
\(\mathcal{O}(1)\) (1 biến đếm/ô) | Có thể bị lách luật ở mép cửa sổ | Lỗi gấp đôi tải ở biên: Gửi \(K\) request lúc 00:59 và \(K\) request lúc 01:01 \(\rightarrow\) \(2K\) request trong 2 giây! |
| 4. Sliding Window Log | Lưu danh sách dấu thời gian (Timestamp) của mọi request hợp lệ trong hàng đợi hai đầu; xóa các dấu thời gian cũ hơn \(t - W\). | \(\mathcal{O}(K)\) dấu thời gian | Chính xác tuyệt đối \(100\%\) ở mọi cửa sổ trượt | Tốn nhiều RAM nếu hạn ngạch \(K\) lớn (ví dụ \(K = 10{,}000\text{ req/giờ}\) cho hàng triệu user) |
| 5. Sliding Window Counter | Kết hợp bộ đếm của cửa sổ trước đó và cửa sổ hiện tại theo tỷ lệ phần trăm thời gian chồng lấp. | \(\mathcal{O}(1)\) (2 biến đếm) | Xấp xỉ mượt mà, chặn được lỗi gấp đôi ở biên | Là phép tính xấp xỉ tuyến tính (nhưng độ chính xác đạt tới \(99.99\%\) trên thực tế theo thống kê của Cloudflare) |
Đi sâu vào cài đặt: Token Bucket nạp lười (Lazy Refill)
Một sai lầm phổ biến của ứng viên khi cài đặt Token Bucket trong vòng phỏng vấn Coding là tạo một luồng chạy ngầm (setInterval hoặc Thread.sleep(1000)) để cộng thêm thẻ vào xô của hàng triệu người dùng mỗi giây. Cách làm đó sẽ đốt sạch CPU và RAM cho cả những người dùng đang ngoại tuyến!
Kỹ thuật chuẩn trong công nghiệp là Nạp lười khi có yêu cầu (Lazy Refill): Mỗi người dùng chỉ cần lưu đúng 2 con số trong bảng băm (Hash Table) hoặc Redis:
tokens: Số thẻ còn lại trong xô ở lần truy cập gần nhất.last_ts: Thời điểm (tính bằng giây hoặc mili-giây) của lần truy cập gần nhất.
Khi có một yêu cầu mới đến tại thời điểm now:
- Tính lượng thẻ mới được sinh ra kể từ lần cuối: \(\Delta = (\text{now} - \mathrm{last\_ts}) \times r\).
- Cập nhật số thẻ hiện có (không vượt quá sức chứa \(C\) của xô): \[\text{tokens} = \min\big(C,\; \text{tokens} + (\text{now} - \mathrm{last\_ts}) \times r\big)\]
- Gán
last_ts = now. - Nếu \(\text{tokens} \ge 1.0\): trừ \(\text{tokens} \leftarrow \text{tokens} - 1.0\) và Cho phép (
true/ HTTP 200). Ngược lại, giữ nguyêntokensvà Chặn (false/ HTTP 429).
Chạy tay (Dry-run) trên chuỗi 6 request thực tế
Giả sử cấu hình xô có sức chứa tối đa \(C = 3\text{ thẻ}\), tốc độ nạp \(r = 1\text{ thẻ/giây}\). Ban đầu tại \(t = 0\), xô đầy (\(\text{tokens} = 3\)). Xét 6 yêu cầu đến tại các mốc thời gian \(t = [0, 0, 0, 1, 1, 3]\text{ giây}\):
| Thứ tự Req | Thời điểm \(t\) (giây) | Khoảng trôi qua \(\Delta t\) | Số thẻ sau khi nạp lười | Kiểm tra \(\ge 1\)? | Số thẻ còn lại sau xử lý | Phản hồi của Rate Limiter |
|---|---|---|---|---|---|---|
| Req 1 | \(0\text{s}\) | \(0\text{s}\) | \(\min(3, 3 + 0) = 3\) | Có (\(3 \ge 1\)) | \(3 - 1 = 2\) | Cho phép (1 — 200 OK) |
| Req 2 | \(0\text{s}\) | \(0\text{s}\) | \(\min(3, 2 + 0) = 2\) | Có (\(2 \ge 1\)) | \(2 - 1 = 1\) | Cho phép (1 — 200 OK) |
| Req 3 | \(0\text{s}\) | \(0\text{s}\) | \(\min(3, 1 + 0) = 1\) | Có (\(1 \ge 1\)) | \(1 - 1 = 0\) | Cho phép (1 — 200 OK) |
| Req 4 | \(1\text{s}\) | \(1 - 0 = 1\text{s}\) | \(\min(3, 0 + 1 \times 1) = 1\) | Có (\(1 \ge 1\)) | \(1 - 1 = 0\) | Cho phép (1 — 200 OK) |
| Req 5 | \(1\text{s}\) | \(1 - 1 = 0\text{s}\) | \(\min(3, 0 + 0) = 0\) | Không (\(0 \lt 1\)) | \(0\) (giữ nguyên) | Từ chối (0 — 429 Chặn) |
| Req 6 | \(3\text{s}\) | \(3 - 1 = 2\text{s}\) | \(\min(3, 0 + 2 \times 1) = 2\) | Có (\(2 \ge 1\)) | \(2 - 1 = 1\) | Cho phép (1 — 200 OK) |
Chuỗi kết quả đầu ra cho 6 yêu cầu trên là 1 1 1 1 0 1. Dưới đây là mã nguồn cài đặt đầy đủ bằng C++17, Python và Java 21; chạy không có đầu vào, chương trình dùng đúng 6 yêu cầu này và in ra chuỗi đó:
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
struct TokenBucket {
long long capacity;
long long refill_per_sec;
long long tokens;
long long last_sec;
TokenBucket(long long cap, long long rate)
: capacity(cap), refill_per_sec(rate), tokens(cap), last_sec(0) {}
int allow(long long now_sec, long long cost = 1) {
long long elapsed = max(0LL, now_sec - last_sec);
tokens = min(capacity, tokens + elapsed * refill_per_sec);
last_sec = now_sec;
if (tokens >= cost) {
tokens -= cost;
return 1;
}
return 0;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long cap, rate;
int q;
if (!(cin >> cap >> rate >> q)) {
TokenBucket limiter(3, 1);
vector<long long> reqs = {0, 0, 0, 1, 1, 3};
for (size_t i = 0; i < reqs.size(); ++i) {
if (i) cout << " ";
cout << limiter.allow(reqs[i]);
}
cout << "\n";
return 0;
}
TokenBucket limiter(cap, rate);
for (int i = 0; i < q; ++i) {
long long t;
cin >> t;
if (i) cout << " ";
cout << limiter.allow(t);
}
cout << "\n";
return 0;
}
import sys
class TokenBucket:
def __init__(self, capacity: int, refill_per_sec: int) -> None:
self.capacity = capacity
self.refill_per_sec = refill_per_sec
self.tokens = capacity
self.last_sec = 0
def allow(self, now_sec: int, cost: int = 1) -> int:
elapsed = max(0, now_sec - self.last_sec)
self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_per_sec)
self.last_sec = now_sec
if self.tokens >= cost:
self.tokens -= cost
return 1
return 0
def main() -> None:
data = sys.stdin.read().split()
if not data:
cap, rate = 3, 1
reqs = [0, 0, 0, 1, 1, 3]
else:
cap = int(data[0])
rate = int(data[1])
q = int(data[2])
reqs = [int(x) for x in data[3 : 3 + q]]
limiter = TokenBucket(cap, rate)
print(" ".join(str(limiter.allow(t)) for t in reqs))
if __name__ == "__main__":
main()
import java.util.*;
public class Main {
static class TokenBucket {
long capacity;
long refillPerSec;
long tokens;
long lastSec;
TokenBucket(long cap, long rate) {
this.capacity = cap;
this.refillPerSec = rate;
this.tokens = cap;
this.lastSec = 0;
}
int allow(long nowSec) {
long elapsed = Math.max(0L, nowSec - lastSec);
tokens = Math.min(capacity, tokens + elapsed * refillPerSec);
lastSec = nowSec;
if (tokens >= 1) {
tokens -= 1;
return 1;
}
return 0;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long cap, rate;
long[] reqs;
if (!sc.hasNextLong()) {
cap = 3;
rate = 1;
reqs = new long[]{0, 0, 0, 1, 1, 3};
} else {
cap = sc.nextLong();
rate = sc.nextLong();
int q = sc.nextInt();
reqs = new long[q];
for (int i = 0; i < q; i++) reqs[i] = sc.nextLong();
}
TokenBucket limiter = new TokenBucket(cap, rate);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < reqs.length; i++) {
if (i > 0) sb.append(" ");
sb.append(limiter.allow(reqs[i]));
}
System.out.println(sb.toString());
}
}
Độ phức tạp thuật toán:
- Thời gian (Time Complexity): Mỗi yêu cầu chỉ thực hiện các phép toán số học cơ bản trong \(\mathcal{O}(1)\); với \(N\) yêu cầu, tổng thời gian là \(\mathcal{O}(N)\).
- Không gian (Space Complexity): \(\mathcal{O}(1)\) cho mỗi định danh người dùng.
Giải quyết bài toán Phân tán: Race Condition và Chuẩn HTTP 429
Khi hệ thống mở rộng lên 10 máy chủ API Gateway cùng đọc/ghi vào một cụm Redis, nếu bạn viết theo lối thông thường gồm 2 lệnh tách rời:
- Lệnh 1:
GET user_123_tokens(cả 2 máy chủ Gateway A và B cùng đọc thấytokens = 1ở cùng một mili-giây). - Lệnh 2: Cả Gateway A và B đều cho phép request đi qua rồi cùng gửi lệnh
SET user_123_tokens 0.
Hệ quả là người dùng gửi lọt 2 yêu cầu trong khi chỉ còn đúng 1 thẻ! Để triệt tiêu hoàn toàn Race Condition, toàn bộ logic tính toán Lazy Refill (đọc tokens, đọc last_ts, cộng thẻ mới, kiểm tra \(\ge 1\), trừ 1 thẻ và ghi lại với thời gian hết hạn TTL) phải được đóng gói vào một Redis Lua Script duy nhất (gọi qua lệnh EVALSHA). Vì nhân xử lý lệnh của Redis là đơn luồng (Single-threaded Event Loop), đoạn kịch bản Lua sẽ được thực thi nguyên tử (Atomic) từ đầu đến cuối mà không có bất kỳ kết nối nào xen ngang được.
Các trường HTTP Header thường trả về cho Client
Một thiết kế API lịch sự luôn thông báo rõ hạn ngạch trong phần Header của phản hồi HTTP để phía ứng dụng khách chủ động điều tiết tốc độ (Client-side Backoff). Retry-After là trường chuẩn của HTTP; nhóm X-RateLimit-* là quy ước phổ biến, mỗi hãng đặt tên hơi khác nhau:
X-RateLimit-Limit: 100(Tổng hạn ngạch tối đa trong cửa sổ).X-RateLimit-Remaining: 0(Số lượt gọi còn lại hiện tại).Retry-After: 15(Số giây cần chờ trước khi gửi lại yêu cầu tiếp theo khi nhận mã lỗi429 Too Many Requests).
Luyện ngay trên Big-O Coding
Cơ chế trượt cửa sổ thời gian bằng hàng đợi hai đầu (Deque) trong Sliding Window Log có cấu trúc giống hệt bài toán tìm cực trị trên cửa sổ trượt; hãy rèn luyện kỹ thuật này qua 2 bài toán thực chiến trong lộ trình phỏng vấn dưới đây:
Nên giới hạn lưu lượng theo Địa chỉ IP, theo user_id hay theo API Key?
Mỗi tiêu chí có ưu nhược điểm riêng nên các hệ thống thực tế thường kết hợp nhiều tầng (Multi-tier Rate Limiting):
- Với các điểm cuối chưa đăng nhập (như
/login,/register), bắt buộc phải giới hạn theo Địa chỉ IP kết hợp dấu vân tay thiết bị. Tuy nhiên cần lưu ý nhiều người dùng trong cùng một trường đại học hoặc văn phòng công ty dùng chung 1 địa chỉ IP công cộng (NAT), nên ngưỡng giới hạn theo IP cần đặt rộng hơn ngưỡng cá nhân. - Với các điểm cuối đã xác thực, giới hạn theo
user_idhoặcAPI Keylà chính xác và công bằng nhất.
Điều gì xảy ra nếu cụm Redis lưu trạng thái Rate Limiter bị mất kết nối tạm thời?
Bạn cần thảo luận với người phỏng vấn về hai chế độ dự phòng: Fail-open (Mở chốt khi lỗi) hoặc Fail-close (Đóng chốt khi lỗi). Trong phần lớn hệ thống thương mại điện tử, người ta chọn Fail-open (hoặc chuyển tạm sang bộ đếm Token Bucket trong RAM cục bộ của từng máy chủ API Gateway): chấp nhận cho lưu lượng vượt ngưỡng nhẹ trong vài phút sự cố Redis còn hơn là chặn nhầm \(100\%\) giao dịch mua hàng của khách thật.
Làm sao xử lý trường hợp một người dùng quá nóng (Hot User / DDoS từ 1 tài khoản) làm quá tải chính phân mảnh Redis chứa khóa của họ?
Với các khóa đã bị phát hiện vi phạm liên tục với tần suất hàng chục nghìn request/giây, việc hỏi đi hỏi lại Redis trên mỗi request cũng gây tốn băng thông mạng nội bộ. Giải pháp tối ưu là máy chủ API Gateway lưu một Danh sách chặn cục bộ ngắn hạn (Local In-Memory Blocklist Cache) trong 10–30 giây ngay trên RAM của Gateway để từ chối tức thì các request từ khóa đó mà không cần gọi sang Redis nữa.
Luyện LeetCode thực chiến theo pattern, giải bài trong 45 phút và mock interview cùng AI. 16 buổi online, lớp 7–12 học viên, chọn C++, Java hoặc Python.


