Rate Limiting — Thuật Toán Và Implementation Cho API
Các thuật toán rate limiting: Token Bucket, Leaky Bucket, Sliding Window — implementation trong Node.js và Cloudflare Workers.
Rate limiting bảo vệ API khỏi abuse, brute force, và traffic spike. Bài này trình bày các thuật toán phổ biến và cách implement.
Tại Sao Cần Rate Limiting?#
- Chống DDoS, brute force
- Đảm bảo fair usage cho tất cả user
- Bảo vệ backend khỏi quá tải
- Giảm chi phí (đặc biệt với AI API)
Thuật Toán#
1. Fixed Window Counter#
Đơn giản nhất — đếm request trong cửa sổ thời gian cố định:
class FixedWindowRateLimiter {
private windows = new Map<string, { count: number; resetAt: number }>();
constructor(
private windowMs: number,
private maxRequests: number,
) {}
check(key: string): boolean {
const now = Date.now();
let window = this.windows.get(key);
if (!window || now > window.resetAt) {
window = { count: 0, resetAt: now + this.windowMs };
this.windows.set(key, window);
}
window.count++;
return window.count <= this.maxRequests;
}
}
const limiter = new FixedWindowRateLimiter(60_000, 10);
// 10 requests / phútVấn đề: Traffic burst ở biên giới window — 10 request ở 0:59 và 10 request ở 1:00 = 20 request trong 2 giây.
2. Sliding Window Log#
Lưu timestamp từng request — kiểm tra số request trong N giây qua:
class SlidingWindowLog {
private logs = new Map<string, number[]>();
constructor(
private windowMs: number,
private maxRequests: number,
) {}
check(key: string): boolean {
const now = Date.now();
let log = this.logs.get(key) || [];
const windowStart = now - this.windowMs;
// Loại bỏ entries cũ
log = log.filter(t => t > windowStart);
this.logs.set(key, log);
if (log.length >= this.maxRequests) {
return false;
}
log.push(now);
return true;
}
}Chính xác hơn nhưng tốn bộ nhớ — lưu timestamp mỗi request.
3. Sliding Window Counter (Redis)#
Kết hợp fixed window + sliding — dùng Redis sorted set:
import { createClient } from 'redis';
const redis = createClient();
async function checkRateLimit(
key: string,
limit: number,
windowSec: number,
): Promise<{ allowed: boolean; remaining: number; resetAt: number }> {
const now = Date.now();
const windowStart = now - windowSec * 1000;
// Transaction
const multi = redis.multi();
multi.zRemRangeByScore(key, 0, windowStart); // Xoá entries cũ
multi.zAdd(key, { score: now, value: `${now}` });
multi.zCard(key); // Đếm entries trong window
multi.expire(key, windowSec);
const [, , count] = await multi.exec();
const requestCount = count as number;
return {
allowed: requestCount <= limit,
remaining: Math.max(0, limit - requestCount),
resetAt: Math.ceil((windowStart + windowSec * 1000) / 1000),
};
}4. Token Bucket#
Bucket chứa N token. Mỗi request lấy 1 token. Token được thêm vào với rate R.
class TokenBucket {
private buckets = new Map<string, { tokens: number; lastRefill: number }>();
constructor(
private capacity: number, // Max tokens
private refillRate: number, // Tokens/second
) {}
private refill(key: string) {
const bucket = this.buckets.get(key);
if (!bucket) return;
const now = Date.now();
const elapsed = (now - bucket.lastRefill) / 1000;
const newTokens = elapsed * this.refillRate;
bucket.tokens = Math.min(this.capacity, bucket.tokens + newTokens);
bucket.lastRefill = now;
}
tryConsume(key: string): boolean {
if (!this.buckets.has(key)) {
this.buckets.set(key, { tokens: this.capacity, lastRefill: Date.now() });
}
this.refill(key);
const bucket = this.buckets.get(key)!;
if (bucket.tokens >= 1) {
bucket.tokens -= 1;
return true;
}
return false;
}
}Ưu điểm: Cho phép burst ngắn (nếu bucket đầy) nhưng rate trung bình ổn định.
5. Leaky Bucket#
Request vào bucket, xử lý với rate cố định. Nếu bucket đầy → request bị từ chối.
Dùng hàng đợi — phù hợp cho xử lý bất đồng bộ.
Implementation — Express Middleware#
import rateLimit from 'express-rate-limit';
import RedisStore from 'rate-limit-redis';
import { createClient } from 'redis';
const redis = createClient();
// Global limiter
const globalLimiter = rateLimit({
windowMs: 60_000,
max: 100,
standardHeaders: true,
legacyHeaders: false,
message: { error: 'Too many requests' },
});
// Auth limiter — strict hơn
const authLimiter = rateLimit({
windowMs: 15 * 60_000,
max: 5,
skipSuccessfulRequests: false,
keyGenerator: (req) => req.ip,
handler: (req, res) => {
res.status(429).json({
error: 'Too many login attempts. Try again later.',
retryAfter: Math.ceil(req.rateLimit.resetTime / 1000),
});
},
});
// API key limiter — dùng Redis store cho distributed
const apiLimiter = rateLimit({
store: new RedisStore({
sendCommand: (...args: string[]) => redis.sendCommand(args),
}),
windowMs: 60_000,
max: (req) => {
// Different limits for different tiers
const tier = req.headers['x-api-tier'] || 'free';
const limits = { free: 10, pro: 100, enterprise: 1000 };
return limits[tier as keyof typeof limits] || 10;
},
keyGenerator: (req) => req.headers['x-api-key'] as string,
});
app.use('/api/', globalLimiter);
app.use('/api/auth/login', authLimiter);
app.use('/api/v2', apiLimiter);Response Headers#
Luôn trả về rate limit info trong response headers:
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 45
X-RateLimit-Reset: 1718845200
Retry-After: 45Cloudflare Rate Limiting#
Cloudflare có rate limiting built-in:
# Wrangler AI — hoặc dashboard
wrangler ratelimit create my-limit --limit 100 --period 60Workers:
export default {
async fetch(request: Request, env: Env): Promise<Response> {
const key = request.headers.get('CF-Connecting-IP') || 'unknown';
const { success } = await env.myRateLimiter.limit({ key });
if (!success) {
return new Response('Too Many Requests', { status: 429 });
}
return new Response('OK');
},
};Distributed Rate Limiting#
Khi nhiều server — dùng Redis centralized:
Server 1 ─┐
Server 2 ─┼→ Redis (atomic counters)
Server 3 ─┘Redis Lua script — atomic:
-- rate_limit.lua
local key = KEYS[1]
local limit = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
redis.call('ZREMRANGEBYSCORE', key, 0, now - window)
local count = redis.call('ZCARD', key)
if count >= limit then
return 0
end
redis.call('ZADD', key, now, now)
redis.call('EXPIRE', key, window)
return limit - count - 1Best Practices#
- Always return headers — client biết khi nào retry
- Different limits per endpoint — auth strict, public loose
- Use token key — IP + API key + userId
- Distributed store — Redis nếu nhiều server
- Graceful degradation — khi Redis down → allow temporarily
- Log violations — để phát hiện abuse pattern
Kết Luận#
Rate limiting không chỉ là bảo vệ — nó là quản lý tài nguyên. Fixed window đơn giản, sliding window chính xác, token bucket linh hoạt. Redis cho distributed systems. Cloudflare cho edge rate limiting. Chọn theo nhu cầu: đơn giản hay chính xác.