patternjavascriptMajor
Token bucket and leaky bucket: the two canonical rate limiter algorithms
Viewed 0 times
rate limitertoken bucketleaky bucketapi rate limitthrottlesliding window
Problem
Implementing a rate limiter from scratch is error-prone. The two main algorithms (token bucket and leaky bucket) are often confused, and developers reach for Redis without understanding the underlying mechanics.
Solution
Token bucket: tokens accumulate up to a max capacity at a fixed refill rate. Each request consumes a token. Allows bursts up to capacity. Leaky bucket: requests enter a fixed-size queue and are processed at a constant rate — excess requests are dropped. Smooths output, no bursts.
Why
Token bucket allows short bursts (good for bursty APIs). Leaky bucket guarantees a steady output rate (good for downstream protection). Sliding window log and sliding window counter are alternatives with more precise semantics but higher memory cost.
Gotchas
- Store last refill timestamp, not token count per tick — compute tokens added lazily on each request to avoid background timers
- Distributed rate limiting needs Redis (with Lua scripts for atomicity) or a dedicated service — in-memory buckets are per-process
- Sliding window counter (hybrid of fixed and sliding) is accurate within ~0.1% and memory-efficient
Code Snippets
Token bucket rate limiter with lazy refill
class TokenBucket {
constructor(capacity, refillPerSecond) {
this.cap = capacity;
this.tokens = capacity;
this.rate = refillPerSecond;
this.last = Date.now();
}
consume(count = 1) {
const now = Date.now();
const elapsed = (now - this.last) / 1000;
this.tokens = Math.min(this.cap, this.tokens + elapsed * this.rate);
this.last = now;
if (this.tokens >= count) { this.tokens -= count; return true; }
return false; // rate limited
}
}
const limiter = new TokenBucket(10, 2); // 10 burst, 2/sec refill
limiter.consume(); // true (token deducted)Context
API gateway rate limiting, client-side request throttling, or background job scheduling
Revisions (0)
No revisions yet.