rate limiter
Four algorithms, one interface: token bucket, fixed window, sliding log, sliding counter. About 150 lines, no dependencies. None of them read the clock; the current time is an argument, which is what lets all four run on identical traffic below and lets the tests use a fake clock.
Running live in this tab. Source in lib/ratelimit.
Traffic
Every request below is handed to all four limiters with the same timestamp, so any difference is the algorithm. Offering 14 requests per second against a limit of 10 per 1s.
Algorithms
Dark ticks are accepted, pink ticks rejected, newest on the right. Peak is the most accepts in any window-length slice, which is where the four contracts diverge: sliding log holds a hard cap, sliding counter approximates it, token bucket deliberately allows a burst up to its bucket size, and fixed window exceeds it by accident.
The window boundary problem
Fixed window counts requests inside the current wall-clock window and resets on rollover. Nothing stops a client from spending the whole limit at the end of one window and the whole limit again at the start of the next.
Press burst across a window boundary above. It schedules 10 requests just before the next boundary and 10 just after. Fixed window accepts nearly all of them, so its peak jumps to roughly 20, twice the configured limit. Sliding log holds at 10 exactly, and sliding counter holds within a request or two of it, since it estimates the previous window rather than storing it.
Token bucket also reads above the limit in that slice, which is worth separating: it bounds the average rate and lets a saved-up bucket drain at once, so its burst is a deliberate size you configure. Fixed window's burst is an accident of where the boundary happens to fall, and a client can aim at it.
This is the whole reason the other three algorithms exist. It is also a test rather than a claim: ratelimit/test.mjs asserts that fixed window accepts 2x the limit across a boundary, and that sliding log never does.
Trade-offs
| algorithm | state per key | bursts | accuracy |
|---|---|---|---|
| token bucket | 2 numbers | allows a full bucket | exact on average rate |
| fixed window | 2 numbers | allows 2x at a boundary | wrong at boundaries |
| sliding log | 1 timestamp per request | never | exact |
| sliding counter | 3 numbers | smoothed | estimate, small error |
Token bucket is the usual answer because the state is tiny and a burst after an idle period is normally what you want. Sliding log is the one to pick when the limit is a contract you cannot exceed, and it is affordable only while the limit is small.
What breaks with more than one server
Everything above holds the counter in one process. Behind a load balancer with three servers, each one holds a third of the picture, so a client gets three times the limit.
The usual fix is to move the counter into Redis and make the check atomic, either with INCR plus EXPIRE for fixed window or a small Lua script for token bucket, so the read and the write cannot interleave between servers.
That buys correctness and costs a network round trip on every request. The common compromise is to keep a local limiter as a cheap first pass and only consult the shared counter for requests that pass it, which is approximate but bounded, and much cheaper.
Not built here. This page is the single-process version.
Usage
import { tokenBucket } from "./lib/ratelimit/limiters.mjs";
const limiter = tokenBucket({ limit: 10, windowMs: 1000 });
if (!limiter.allow(Date.now())) {
return res.status(429).end();
}
node ratelimit/test.mjs # 25 tests, fake clock, no sleepsOne limiter instance per key. In a real service that means a map from client id to limiter, plus eviction so the map does not grow forever.