Fixed window: simple but flawed
Count requests per minute. Reset at the minute boundary. The problem: a user can fire 100 requests at 11:59:59 and another 100 at 12:00:00 — 200 requests in 2 seconds while technically staying within the 100/min limit.
Sliding window log
Store the timestamp of every request. Count how many fall within the last 60 seconds. Accurate but memory-expensive — at scale, storing every timestamp per user is not practical.
Sliding window counter
The practical middle ground. Keep counts for the current and previous window, then weight them:
function isAllowed(userId: string, limit: number, windowMs: number): boolean {
const now = Date.now();
const currentWindow = Math.floor(now / windowMs);
const previousWindow = currentWindow - 1;
const elapsed = (now % windowMs) / windowMs;
const prevCount = getCount(userId, previousWindow);
const currCount = getCount(userId, currentWindow);
const estimated = prevCount * (1 - elapsed) + currCount;
return estimated < limit;
}
Two counters per user instead of thousands of timestamps. Close enough to accurate for most APIs.
Token bucket: burst-friendly
If your API should allow short bursts but limit sustained throughput, token bucket is the right choice. Tokens refill at a steady rate. Each request costs one token. If the bucket is empty, the request is rejected.
class TokenBucket {
private tokens: number;
private lastRefill: number;
constructor(private capacity: number, private refillRate: number) {
this.tokens = capacity;
this.lastRefill = Date.now();
}
tryConsume(): boolean {
this.refill();
if (this.tokens < 1) return false;
this.tokens -= 1;
return true;
}
private refill() {
const now = Date.now();
const elapsed = (now - this.lastRefill) / 1000;
this.tokens = Math.min(this.capacity, this.tokens + elapsed * this.refillRate);
this.lastRefill = now;
}
}
Which one should you use
- Sliding window: when you want predictable, evenly distributed throughput. Good for public APIs with per-user quotas.
- Token bucket: when you want to allow bursts. Good for webhook receivers, batch endpoints, and internal services where traffic is naturally bursty.
Implementation detail: use Redis
Both algorithms work in-memory for a single server. For distributed systems, use Redis. The sliding window counter needs two INCR operations with EXPIRE. The token bucket maps naturally to a Redis hash with a Lua script for atomic refill-and-consume.