Rate limiting algorithms: how token buckets forgive bursts
Your API has a capacity whether or not you wrote it down. The database answers only so many queries per second. The worker pool has only so many threads. Somewhere in the stack there is a number, and the only open question is who discovers it: you, on purpose, with a limit you chose and documented, or your users, at 2 a.m., when one customer's misconfigured cron job discovers it for everyone at once. The first client to hurt a public API is rarely an attacker. It's a for loop with no sleep in it.
Every system is rate limited. The only choice is whether the limit is a number you picked and enforce politely, or a number production discovers on your behalf.
A rate limiter moves the refusal to the front door, where saying no costs a few microseconds and a small response. Without one, the refusal happens at the database, and there it looks like an outage. The algorithms differ in exactly one thing: how faithfully their bookkeeping matches the capacity arithmetic you are trying to enforce.
The fixed window, and the burst it waves through
The obvious implementation is a counter per client that resets on a clock boundary: 100 requests per minute, counter zeroed at the top of each minute. It is one integer per client, and it's wrong in a way clients will find without trying:
limit: 100 requests/minute, counter resets on the minute boundary
11:59:59.9 burst of 100 counted in the 11:59 window all admitted
12:00:00.1 burst of 100 counted in the 12:00 window all admitted
result: 200 requests admitted in 0.2 seconds, against a limit of 100/minuteNeither burst broke the rule as the counter understands it, and yet the backend just absorbed double the advertised limit in a fifth of a second. Any client whose traffic straddles the boundary, deliberately or by accident of scheduling, gets the same free double. If your capacity math assumed 100 per minute meant 100 per any minute, the fixed window quietly voids the assumption exactly when load is highest.
Token bucket: a refill rate plus a burst allowance
The bucket
refill 2/s, cap 8
6 of 8 available
One second of traffic
The token bucket fixes this with two numbers instead of one. A bucket holds at most capacity
tokens and gains rate tokens per second. Each admitted request spends one token; an empty
bucket means rejection. The long-run throughput can never exceed the refill rate, while the
capacity decides how much of a burst you are willing to absorb at once.
That pair matches how clients actually behave. Real traffic is not smooth: a page load fires a dozen API calls in 100 milliseconds and then goes quiet, and a batch job wakes on the hour and does a day of work in a minute. A limiter that only understands smooth traffic punishes normal clients for their shape. The token bucket forgives the shape and enforces the average, which is the thing your capacity arithmetic actually cares about.
The implementation is smaller than its reputation. No timer, no background thread: refill lazily, computed from elapsed time whenever a request shows up.
public sealed class TokenBucket(double capacity, double refillPerSecond)
{
private double _tokens = capacity;
private long _lastRefill = Stopwatch.GetTimestamp();
private readonly object _lock = new();
public bool TryConsume()
{
lock (_lock)
{
long now = Stopwatch.GetTimestamp();
double elapsed = (now - _lastRefill) / (double)Stopwatch.Frequency;
_tokens = Math.Min(capacity, _tokens + elapsed * refillPerSecond);
_lastRefill = now;
if (_tokens < 1)
{
return false;
}
_tokens -= 1;
return true;
}
}
}Most stacks ship a production version of this, ASP.NET Core's rate limiting middleware included. The sketch is worth internalizing anyway, because the two constructor arguments are the two promises you are making: the average you can afford, and the burst you will tolerate.
Sliding windows: buying accuracy with memory
If you want "no more than N in any trailing window" enforced exactly, the honest algorithm is the sliding window log: store a timestamp per admitted request, drop the ones older than the window, and count what remains. It has no boundary to exploit and no approximation error. It also costs memory proportional to the limit for every active client, which at ten thousand clients with a limit of 1,000 per minute is ten million timestamps doing bookkeeping for you.
The sliding window counter is the standard compromise. Keep counts for the current and previous fixed windows, and estimate the trailing window as the current count plus the previous count weighted by how much of the previous window still overlaps. The estimate assumes the previous window's traffic was evenly spread, so it can be slightly wrong at the edges, but it closes the boundary hole for two integers per client. Between these and the token bucket the choice is mostly about what you want to express: the bucket states a burst policy explicitly, the sliding counter approximates a smooth ceiling. Either one beats the fixed window.
Say no loudly: 429 with Retry-After
Rejection is an interface, and RFC 6585 gave it a status code. Return 429, and tell the client when trying again will work:
HTTP/1.1 429 Too Many Requests
Retry-After: 12
Content-Type: application/problem+json
{
"title": "Rate limit exceeded",
"detail": "This API key is limited to 100 requests per minute.",
"status": 429
}The tempting alternative, silently queueing the excess, is worse than it sounds. A queue hides
the overload signal from the one party who could reduce load, while every queued request holds a
connection and memory on your side. Latency climbs for all clients instead of failing fast for
the noisy one, and the client's own timeout eventually fires anyway, producing a retry you now
service on top of the queued original. A prompt 429 with Retry-After hands a well-behaved
client the one number it needs to become a good citizen. On that client side, honor the header
with exponential backoff and jitter rather than a fixed sleep, because a thousand rejected
clients that all sleep exactly twelve seconds will return in the same instant, and a rate limit
that synchronizes its own thundering herd has manufactured the burst it exists to prevent. What
else the client should do with a 429, and what happens when the request it retries is a payment,
is the other half of this story: see
idempotency in API design.
Where the limiter lives
Enforce in two places, because they answer different questions. The edge or gateway is the cheap, blunt layer: per-IP and per-key ceilings that stop floods before your application spends anything on them. The application layer is where fairness lives, because only it knows that this tenant is on the starter plan, that endpoint costs ten times more than the others, and this burst is a paid customer's nightly sync rather than abuse. Choose the limiting key just as deliberately. A per-IP limit punishes everyone behind one corporate NAT for a neighbor's enthusiasm, while a per-API-key limit maps the budget onto the entity you actually made promises to, which is usually the right answer for anything authenticated.
Once you run more than one instance, the counters have to live in a shared store, typically Redis with atomic increments and expiry, or a small script implementing the bucket server-side. Accept the slight over-admission that comes with it: two instances racing between read and update can each admit a request the other did not see. Serializing every request through a global lock to prevent that costs more than the extra request does. A rate limiter protects capacity; it's not a billing system. If 103 requests slip through against a limit of 100, your headroom should shrug.
The part you only learn by watching
Rate limiting reads as arithmetic and becomes judgment only through contact with a real system:
the burst that turned out to be legitimate, the Retry-After nobody honored, the shared counter
that cost more than it protected. That contact is hard to get at work, because nobody schedules
an overload for your education. Katabench's Labs shrink that gap with guided practice
inside real running systems, built up and verified step by step rather than sketched on a
whiteboard. The same conviction runs through the practice tracks,
where the grader judges what production judges, so the habit you build is asking what your code
costs rather than whether it merely works. A rate limiter is that question, asked at the front
door, before the answer gets expensive.