ENGINEERING GUIDE
Mastering API Rate Limiting
Token bucket, leaky bucket, fixed window and sliding window: how each controls traffic, where it permits bursts, and what changes when your API runs on multiple servers.
- Topic
- API traffic control
- Algorithms
- Four approaches
- Examples
- JavaScript · single process
- Production concerns
- Atomicity, identity, failures
What is rate limiting?
Rate limiting bounds how much work a caller may request over time. It protects finite CPU, memory, connection pools and paid downstream services, while leaving capacity for other callers.
Consider a code-execution service. Repeatedly pressing Run creates expensive jobs. A policy such as three submissions per ten seconds per account limits that workload before it reaches the worker queue. This is an illustrative policy, not a claim about LeetCode's actual limits.
Token bucket
A bucket holds up to a fixed capacity. Tokens refill at a steady rate, and each accepted request consumes one. Idle time restores burst allowance, but never beyond the capacity.
Capacity and refill rate are separate controls. A bucket with five tokens and a refill rate of one token per second accepts five immediate requests, then roughly one per second. It does not promise evenly spaced arrivals. AWS API Gateway documents this rate-and-burst model.
JavaScript
class TokenBucket {
constructor(limit, seconds) {
if (!Number.isInteger(limit) || limit < 1 || !Number.isFinite(seconds) || seconds <= 0) {
throw new RangeError("Use a positive integer limit and positive seconds");
}
this.capacity = limit;
this.tokens = limit;
this.refillPerSecond = limit / seconds;
this.updatedAt = performance.now();
}
allowRequest() {
const now = performance.now();
const elapsed = (now - this.updatedAt) / 1000;
this.tokens = Math.min(this.capacity,
this.tokens + elapsed * this.refillPerSecond);
this.updatedAt = now;
if (this.tokens < 1) return false;
this.tokens -= 1;
return true;
}
}
const bucket = new TokenBucket(5, 5);
console.log(Array.from({ length: 6 }, () => bucket.allowRequest()));
// [true, true, true, true, true, false]State is constant-sized per caller. Choose this when occasional bursts are useful, such as a client syncing several items after being idle.
Leaky bucket
A leaky bucket drains accumulated load at a steady rate. There are two useful interpretations: a meter rejects requests when accumulated load is too high; a queue-based shaper buffers requests and releases them at a paced rate. They are not interchangeable.
The example below is a meter. It tracks a virtual water level without storing requests or starting background timers. It admits a burst up to capacity, then rejects until enough load has drained. To produce evenly spaced downstream work, use a bounded queue with a separate scheduler.
JavaScript
class LeakyBucket {
constructor(limit, seconds) {
if (!Number.isInteger(limit) || limit < 1 || !Number.isFinite(seconds) || seconds <= 0) {
throw new RangeError("Use a positive integer limit and positive seconds");
}
this.capacity = limit;
this.level = 0;
this.leakPerSecond = limit / seconds;
this.updatedAt = performance.now();
}
allowRequest() {
const now = performance.now();
this.level = Math.max(0, this.level -
((now - this.updatedAt) / 1000) * this.leakPerSecond);
this.updatedAt = now;
if (this.level + 1 > this.capacity) return false;
this.level += 1;
return true;
}
}
const meter = new LeakyBucket(5, 5);
console.log(Array.from({ length: 6 }, () => meter.allowRequest()));
// [true, true, true, true, true, false]A shaper trades burst smoothing for queueing latency. Bound both queue length and maximum waiting time. A scheduler controls dispatch timing, not guaranteed completion timing: downstream jobs can still take different amounts of time.
Fixed window
Count accepted requests inside aligned time windows and reset the counter when the window changes. This needs only a counter and a window identifier per caller.
The boundary is the main trade-off. With a limit of 100 per minute, a caller can send 100 just before a boundary and another 100 immediately after it. Each window obeys the policy, but the short-term burst approaches twice the limit.
JavaScript
class FixedWindow {
constructor(limit, seconds) {
if (!Number.isInteger(limit) || limit < 1 || !Number.isFinite(seconds) || seconds <= 0) {
throw new RangeError("Use a positive integer limit and positive seconds");
}
this.limit = limit;
this.windowMs = seconds * 1000;
this.windowId = -1;
this.count = 0;
}
allowRequest() {
const id = Math.floor(performance.now() / this.windowMs);
if (id !== this.windowId) {
this.windowId = id;
this.count = 0;
}
if (this.count >= this.limit) return false;
this.count += 1;
return true;
}
}
const fixed = new FixedWindow(5, 60);
console.log(Array.from({ length: 6 }, () => fixed.allowRequest()));
// [true, true, true, true, true, false]This teaching example aligns windows to the process's monotonic clock. Distributed implementations need a shared definition of the window boundary. Choose fixed windows when simplicity matters and boundary bursts are acceptable.
Sliding window log
Keep timestamps for accepted requests in the trailing interval. Before accepting another request, remove entries at or before the cutoff and count what remains. Unlike fixed windows, there is no global reset boundary.
This enforces an exact trailing-window count, but does not evenly pace traffic. A caller can still spend its entire allowance at once when the log is empty. A sliding-window counter is a different, approximate approach that combines counts from adjacent windows.
JavaScript
class SlidingWindow {
constructor(limit, seconds) {
if (!Number.isInteger(limit) || limit < 1 || !Number.isFinite(seconds) || seconds <= 0) {
throw new RangeError("Use a positive integer limit and positive seconds");
}
this.limit = limit;
this.windowMs = seconds * 1000;
this.requests = [];
}
allowRequest() {
const now = performance.now();
const cutoff = now - this.windowMs;
this.requests = this.requests.filter(time => time > cutoff);
if (this.requests.length >= this.limit) return false;
this.requests.push(now);
return true;
}
}
const sliding = new SlidingWindow(5, 60);
console.log(Array.from({ length: 6 }, () => sliding.allowRequest()));
// [true, true, true, true, true, false]This simple implementation scans up to the configured limit on each check and stores up to that many timestamps per caller. For larger limits, use a queue with a head index and periodic compaction, or a shared sorted-set implementation with atomic cleanup, count and insert.
Choosing an algorithm
Token bucket
Bound sustained traffic while allowing an explicit burst budget. Constant-sized state per caller.
Leaky bucket
Use a meter for accumulated-load admission or a bounded shaper queue for paced dispatch. Make the distinction explicit.
Fixed window
Small state and simple reset semantics. Accept the possibility of a double burst around a boundary.
Sliding window log
Exact trailing-window counts, with timestamp storage and more work per check. It removes reset-boundary spikes, not all bursts.
Start with the resource you need to protect. Expensive code execution may need a per-account submission limit plus a global worker-concurrency cap. Email delivery may need a paced queue. A cheap read endpoint may tolerate a simpler counter.
Across multiple servers
A separate in-memory bucket in every API replica multiplies the effective allowance. Shared state can enforce a common policy, but the decision and update must be atomic.
Redis INCR itself is atomic. The problem is a multi-command sequence: a process can fail between incrementing a new counter and attaching its expiry. Redis documents using a Lua script to keep those steps together. Sliding-log cleanup, counting and insertion similarly need one atomic decision.
Choose the key
Prefer authenticated account or API-key identity. IP limits can penalize shared networks; only trust forwarded addresses from configured proxies.
Bound memory
Expire inactive keys and cap key cardinality. Otherwise a limiter can become a memory-exhaustion target.
Define failure behavior
Decide whether a store outage should fail open or fail closed per endpoint. Record limiter latency, errors and rejected traffic.
Make retries useful
Return HTTP 429 for policy rejection with meaningful retry guidance. Clients should back off with jitter rather than immediately retrying.
Test boundaries
Test empty and full buckets, exact cutoff times, simultaneous requests, long idle periods, process restarts and shared-store outages.
Separate delivery guarantees
Rate limiting does not make payment retries safe or recover a lost job. Use idempotency and queue acknowledgements where the workflow requires them.