policybook / rate-limiter

rate-limiter

Policies for deciding whether a request may proceed. They differ far less in *how much* they let through than most comparisons suggest, and far more in what they cost to run and how they behave at the edges.

Run these side by side → Same trace, same seed, stepped in lockstep.

Choosing one

If you need	Use	Because
A sensible default	token bucket	Bursts allowed and bounded, no seam, exact retry hint.
The same thing with the least state	GCRA	Identical decisions from one integer per key instead of three: 34 bytes against 42.
Smoothing, not budgeting	leaky bucket	Its default capacity of 1 forces even spacing. At equal parameters it is the token bucket.
An exact “N in any window” guarantee	sliding log	The only policy that makes that sentence literally true, at 834 bytes per key.
To limit across processes without coordination	sliding counter	Epoch-aligned windows shard with two counters and no messages.
The simplest thing a stored procedure can do	fixed window	One `INCR` with a TTL, and a boundary where twice the limit slips through.
RPM and TPM, the LLM-API shape	dual bucket	Two ceilings checked together, charged atomically.

Benchmarks

Accept rate on each trace, measured by this repository's benchmarks.

Policy	`steady`	`bursty`	`many-keys`	`overload`
Dual bucket	1.0000	1.0000	1.0000	0.6747
GCRA	1.0000	1.0000	1.0000	0.3429
Leaky bucket	1.0000	1.0000	1.0000	0.3429
Token bucket	1.0000	1.0000	1.0000	0.3429
Fixed window	0.9927	0.9692	1.0000	0.3374
Sliding log	0.9772	0.9692	1.0000	0.3374
Sliding counter	0.9847	0.9692	1.0000	0.3373

Every policy

Dual bucket

Requests per minute and tokens per minute, checked together and charged atomically. The shape every LLM API uses, and the only policy here that sees both ways a caller can overwhelm you.

GCRA

The token bucket kept as a single theoretical arrival time. Identical decisions, one integer per key instead of three, which is why network gear and Redis modules use it.

Leaky bucket

A level that rises with each request and drains at a steady rate. The same algorithm as the token bucket, stated as smoothing rather than as a budget.

Token bucket recommended

Spend from a balance that refills at a steady rate and stops at a burst. Continuous refill, no window seam, and an exact retry hint: the default rate limiter.

Fixed window

Count requests inside a clock-aligned window and reset at the edge. Two integers per key, and a client can push twice the limit through across a boundary.

Sliding log

Keep every admitted request's timestamp and count the ones still inside the window. Exact, with no boundary effect, at a cost of one timestamp per permit per key.

Sliding counter

Two adjacent window counts, weighted by how far into the new window you are. Removes the boundary burst for three integers per key instead of a hundred timestamps.