Rate Limiting: Token Bucket vs Sliding Window
A client hammers your login endpoint. You added a limit: 100 requests per minute per IP. You feel safe. Then someone fires 100 requests at 12:00:59.900 and another 100 at 12:01:00.100. Your counter reset at the minute boundary, so both bursts pass. In a 200-millisecond window your “100 per minute” endpoint just served 200 requests, and your auth service is on fire.
That is the fixed-window boundary problem, and it is why the simplest rate limiter you can build is also the one that quietly fails under exactly the traffic you meant to stop. Here is the uncomfortable choice between the algorithms that actually hold a limit, and how to build one in Redis and Node without race conditions.
The fixed window and its double burst
A fixed-window counter is one key per time bucket. In Redis it is two commands: increment the counter, set an expiry.
INCR rl:1.2.3.4:20260722_1200
EXPIRE rl:1.2.3.4:20260722_1200 60The key embeds the window (1200 = the 12:00 minute), so the counter resets for free when the key expires. It is fast, it is O(1) memory, and it is wrong at the edges. Because each window starts fresh, a client can spend its full quota at the tail of one window and its full quota at the head of the next. Two windows, one continuous burst, up to 2x your intended rate in a sliver of real time.
sequenceDiagram
participant C as Client
participant R as Rate limiter
Note over R: limit = 100 / minute
C->>R: 100 reqs @ 12:00:59.9
R-->>C: counter=100, all allowed
Note over R: window rolls, counter resets to 0
C->>R: 100 reqs @ 12:01:00.1
R-->>C: counter=100, all allowed
Note over C,R: 200 requests in 200ms
The counter is accurate for its own window. Reality does not care about your window boundaries.
Token bucket: rate plus burst
The token bucket separates two things fixed windows conflate: the sustained rate and the allowed burst. A bucket holds up to capacity tokens. Tokens refill at a steady rate per second. Every request removes a token; if the bucket is empty, the request is rejected.
Worked example: capacity 10, refill 5 tokens per second. A client that has been idle starts with a full bucket, so it can fire 10 requests instantly (the burst). After that it is throttled to the refill rate: one token every 200ms, 5 per second sustained. If it sends nothing for 2 seconds, the bucket refills by 10 but caps at capacity, so it never banks more than 10. You get a smooth sustained rate with a bounded, predictable burst, which is exactly what most APIs want.
The elegant part: you do not run a background timer to add tokens. You compute the refill lazily on each request from the elapsed time since you last touched the bucket. Store two fields, tokens and last-update timestamp, and do the math on read.
Sliding window: log vs counter
The sliding window fixes the boundary problem by measuring the last N seconds continuously, not the current fixed bucket.
The sliding window log stores a timestamp for every request in a Redis sorted set. On each request you prune entries older than the window, count what remains, and reject if the count is at the limit.
ZREMRANGEBYSCORE rl:1.2.3.4 0 <now-window>
ZCARD rl:1.2.3.4
ZADD rl:1.2.3.4 <now> <now>-<nonce>This is exact to the millisecond. The cost is memory and CPU: you store one sorted-set member per request, so a client allowed 10,000 requests holds 10,000 entries. Under attack traffic that is a lot of memory and O(log N) work per call.
The sliding window counter is the approximation Cloudflare runs across its network. Keep just two numbers, the count in the previous fixed window and the count in the current one, and weight the previous window by how much of it still overlaps the trailing window.
estimated = current + previous * ((window - elapsed_in_current) / window)Cloudflare’s own example: a 50 requests per minute limit, 42 in the previous minute, 18 in the current minute, 15 seconds into the current window:
estimate = 18 + 42 * ((60 - 15) / 60)
= 18 + 42 * 0.75
= 49.5 -> allowed (next request tips it over 50)Two counters per client, O(1) memory, no per-request timestamps. Across 400 million requests from 270,000 sources, Cloudflare measured 0.003% of requests wrongly allowed or limited, with none of the throttled sources actually sitting below the threshold (zero false positives). For almost every API this is the right default: it holds the limit without the memory of a log.
Distributed enforcement needs atomicity
Local per-process counters break the moment you run more than one instance behind a load balancer, because a client just spreads its requests across instances. The fix is a shared store, and Redis is the standard one: sub-millisecond, single-threaded command execution, on the request path.
The trap is the read-decide-write race. Two concurrent requests both read tokens = 1, both decide “allowed”, both write back, and you have spent a token twice. INCR is atomic on its own, but a token bucket needs to read state, compute a refill, decide, and write, and those steps must be one atomic unit. A MULTI/EXEC transaction does not help here because you cannot branch on a value you have not read yet.
The answer is a Lua script. Redis runs EVAL scripts atomically: the server blocks all other activity for the script’s entire runtime, so the whole read-refill-decide-write cycle is safe.
-- KEYS[1] = bucket key
-- ARGV: capacity, refillPerSec, nowMs, cost
local capacity = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local cost = tonumber(ARGV[4])
local b = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(b[1])
local ts = tonumber(b[2])
if tokens == nil then tokens = capacity; ts = now end
-- lazy refill from elapsed time
local elapsed = math.max(0, now - ts) / 1000
tokens = math.min(capacity, tokens + elapsed * rate)
local allowed = tokens >= cost
if allowed then tokens = tokens - cost end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
-- reclaim idle keys once a full refill has elapsed
redis.call('EXPIRE', KEYS[1], math.ceil(capacity / rate) + 1)
local retry = 0
if not allowed then retry = math.ceil((cost - tokens) / rate) end
return { allowed and 1 or 0, tokens, retry }One note on correctness: when a Lua script returns a number, Redis converts it into an integer reply and drops the decimal part (the docs are explicit: to return a float you must return a string). So the tokens you get back in Node is already floored. That is fine for a “remaining” display, but be aware it is not the exact stored float, which keeps its fractional part inside Redis.
Wiring it into Node and returning 429
Load the script once and call it per request with node-redis. All EVAL arguments must be strings.
import { createClient } from 'redis';
const redis = createClient({ url: process.env.REDIS_URL });
await redis.connect();
const TOKEN_BUCKET = `...the Lua above...`;
async function takeToken(id, { capacity, refillPerSec, cost = 1 }) {
const [allowed, tokens, retryAfter] = await redis.eval(TOKEN_BUCKET, {
keys: [`rl:${id}`],
arguments: [String(capacity), String(refillPerSec),
String(Date.now()), String(cost)],
});
return { allowed: allowed === 1, remaining: tokens, retryAfter };
}
export function rateLimit({ capacity, refillPerSec }) {
return async (req, res, next) => {
const id = req.ip; // or API key / tenant id
const { allowed, remaining, retryAfter } =
await takeToken(id, { capacity, refillPerSec });
res.setHeader('RateLimit-Limit', capacity);
res.setHeader('RateLimit-Remaining', Math.max(0, remaining));
if (!allowed) {
res.setHeader('Retry-After', retryAfter); // RFC 9110, delta-seconds
res.setHeader('RateLimit-Reset', retryAfter);
return res.status(429).json({ error: 'Too Many Requests' });
}
next();
};
}When you reject, return 429 Too Many Requests (RFC 6585) and always send Retry-After so well-behaved clients back off instead of retrying blindly and making the pileup worse. Retry-After accepts either delta-seconds or an HTTP-date (RFC 9110, Section 10.2.3). The RateLimit-Limit, RateLimit-Remaining, and RateLimit-Reset fields are a widely deployed de-facto convention (GitHub and plenty of gateways emit an X-RateLimit-* or RateLimit-* variant), and they let clients self-throttle before they ever hit a 429. One caveat if you track the spec: the IETF draft (draft-ietf-httpapi-ratelimit-headers) did not bless those three names. It settled on a single structured RateLimit field plus a RateLimit-Policy field, for example RateLimit: "default";r=50;t=30 alongside RateLimit-Policy: "default";q=100;w=60. Emit whatever your clients already understand, just do not assume the three-header form is the ratified standard. A rate limiter is one half of controlling load; the other half is what your server does when the queue backs up, which is where handling backpressure in Node.js picks up. And rejecting with a 429 only helps if callers respect it, because retries are not a fix on their own.
Takeaway
Fixed windows are cheap and lie at the boundary. The token bucket gives you a clean split between sustained rate and burst and is the best general default for API quotas. The sliding window log is exact but pays for it in memory; the sliding window counter is the pragmatic distributed choice, holding the limit for two numbers per client. Whichever you pick, enforce it in Redis inside a Lua script so the decision is atomic, and answer with a 429 plus Retry-After so clients throttle instead of storm. Choose the shape of the burst you can tolerate, then make the enforcement race-free. If you also need to decide which HTTP verb carries the request being limited, see the query method in Node and NestJS.