Short answers to what readers ask most about this topic.
Which rate limiting algorithm should you use? Fixed window, sliding window log and counter, token bucket and leaky bucket compared with worked arithmetic and TypeScript.
Matthews Wong
Software Engineer
Key Takeaway
Use a token bucket when clients may burst but must stay under a long-run average rate, and a sliding window counter when you need a hard cap per time period with tiny memory. Fixed windows can allow double the limit at a boundary, and a leaky bucket smooths traffic instead of rejecting it.
A limit of 100 requests per minute sounds like one rule, but there are at least five different algorithms that can enforce it, and they disagree on the cases that matter: what happens at the edge of a minute, whether a quiet client may spend saved-up capacity, and how many bytes of state each caller costs you.
This post compares fixed window, sliding window log, sliding window counter, token bucket and leaky bucket with the arithmetic worked out by hand, then gives a TypeScript token bucket you can run. It is the algorithm companion to my NestJS and Redis implementation post; here nothing depends on a framework. Figures quoted from other people are attributed in the sources.
A rate limiter answers one question per request: allow or reject. The algorithm decides how that answer is computed from past traffic. Three properties separate the options: how much burst they tolerate, how accurately they enforce the stated limit, and how much state each key (user, API key or IP) needs. Everything below is a trade between those three.
The standard rejection is HTTP 429 Too Many Requests, defined in RFC 6585, which also allows a Retry-After header telling the client when to come back. The algorithm choice decides what number you can put in that header honestly. For the examples I use one limit throughout: 100 requests per 60 seconds per API key.
A fixed window keeps one counter per key per clock-aligned window. The first request in a window creates the counter, each request increments it, and the counter expires when the window ends. It needs one integer of state and, in Redis, an INCR plus an EXPIRE. That cheapness is why it is the first thing most people build.
# Limit: 100 requests per 60 s, fixed windows aligned to the minute
12:00:00 - 12:00:58 client sends nothing
12:00:59 client sends 100 requests window 12:00 count = 100 -> all allowed
12:01:00 window 12:01 starts, count = 0
12:01:00 - 12:01:01 client sends 100 requests window 12:01 count = 100 -> all allowed
# 200 accepted in about 2 seconds. Allowed rate: 100 per minute.
# A sliding window would have rejected every request in the second batch.The flaw is the boundary. The counter resets at the window edge regardless of what happened just before it, so a client can spend a full quota at the end of one window and another full quota at the start of the next. The worked timeline below shows 200 accepted requests in about two seconds against a limit of 100 per minute, twice the intended rate.
Worst case for a fixed window is two times the limit across a window edge. If the limit protects a downstream system that really falls over at 100 per minute, a fixed window will let you down at exactly the moment of a retry storm.
The sliding window log stores the timestamp of every accepted request, drops the ones older than 60 seconds, and counts what remains. It is exact: at any instant, no more than 100 requests fall inside the last 60 seconds. The cost is memory proportional to the limit. At 100 requests per minute, each busy key holds up to 100 timestamps, so 10,000 busy keys means up to 1,000,000 stored entries. In Redis this is typically a sorted set per key.
The sliding window counter keeps just two numbers, the previous window count and the current one, and weights the previous one by how much of it still overlaps the sliding window. Take 84 requests in the previous minute and 36 so far in this one, 15 seconds in. The overlap of the previous window is 45 of 60 seconds, which is 75 percent. The estimate is 84 x 0.75 + 36 = 63 + 36 = 99. That is under 100, so one more request is allowed.
// Sliding window counter: two integers per key
// now = 15 s into the current minute, limit = 100
const overlap = 1 - 15 / 60; // 0.75 of the previous window still counts
const estimate = prevCount * overlap + currCount;
// = 84 * 0.75 + 36 = 99
if (estimate < 100) {
currCount += 1; // allowed; estimate is now 100
} else {
reject(429); // the next request would exceed the limit
}The weighting assumes the previous window's requests were spread evenly, so it is an approximation. Cloudflare published an analysis of 400 million requests from 270,000 distinct sources and reported that 0.003 percent of requests were wrongly allowed or rate limited under this approach. That is a number about their traffic, not a guarantee about yours, but it shows the approximation error is small in practice. Two counters per key is the price.
A token bucket holds up to capacity tokens and gains tokens at a steady refill rate. Each request removes one token; if the bucket is empty the request is rejected. Wikipedia describes the same structure as a bucket checked for conformance to a rate and burstiness limit, and Stripe describes its own request limiter as a bucket per user that tokens are removed from on each request and slowly dripped back into.
The arithmetic is the whole appeal. Take capacity 10 and a refill of 2 tokens per second, which is 120 per minute sustained. A client arriving at an idle bucket may send 10 requests at once, then is held to 2 per second. Idle for 20 seconds, the bucket would hold 0 + 40 tokens but is capped at 10, so saved-up capacity is bounded by the capacity. In any 60 seconds the most it can send is 10 + 120 = 130. Capacity sets the burst, refill sets the average, and you tune them separately.
No timer is needed. The limiter stores only the token count and the time of the last update, and works out the refill lazily from the elapsed time on each request. That is two numbers per key, the same footprint as the sliding window counter.
Do not give the bucket a capacity equal to the refill per second unless you mean to forbid bursts. A capacity of 1 with a refill of 2 per second is a smooth 500 ms spacing, which most real clients will trip over.
A leaky bucket works as a queue that drains at a constant rate. Requests join the queue and leave it at the fixed rate; if the queue is full, new requests are dropped. Take a queue of 10 draining 2 per second and a sudden burst of 15 requests: 10 are queued, 5 are rejected, and the last queued request leaves after about 10 / 2 = 5 seconds. The output is perfectly smooth, which is the point, and the cost is latency.
The two are easy to confuse because Wikipedia notes the leaky bucket as a meter is equivalent to the token bucket. The practical difference is what happens to a burst. A token bucket lets it through immediately and then throttles; a leaky bucket queue absorbs it and delays it. Use the queueing form when the thing behind the limiter, such as a printer, a payment gateway or a legacy ERP endpoint, needs an even flow rather than a quick reply.
Choose by the behaviour you need at the edges, then check the state cost. This table summarises the five algorithms for the 100 per minute example, with state counted per key.
| Algorithm | State per key | Burst behaviour | Accuracy | Best for |
|---|---|---|---|---|
| Fixed window | 1 counter | Up to 200 across a window edge | Loose at boundaries | Cheap abuse protection where double bursts are harmless |
| Sliding window log | Up to 100 timestamps | Never above 100 in any 60 s | Exact | Strict caps on low-volume, high-value keys |
| Sliding window counter | 2 counters | Close to 100 in any 60 s | Approximate, small error | Hard per-period quotas at large scale |
| Token bucket | Tokens plus last-update time | Burst up to capacity, then the refill rate | Exact for its own definition | Public APIs that allow bursts but cap the average |
| Leaky bucket | Queue length plus last-drain time | No burst out; excess queued or dropped | Exact output rate | Protecting a backend that needs an even flow |
My default for an HTTP API on a single server is a token bucket per API key, because real clients are bursty and a page load firing 8 calls at once should not be punished. I reach for the sliding window counter when the contract is literally a quota, such as 1,000 calls per hour on a pricing plan, and I use the leaky bucket form only in front of something that cannot take bursts.
The algorithm is half the decision. Key by authenticated identity first, such as API key or tenant, and fall back to IP only for anonymous traffic, because many offices and mobile networks share one address. Then walk this checklist for each limit. The Redis-backed NestJS version of these ideas is in my earlier post on API rate limiting.
Read the NestJS and Redis implementation of API rate limiting
The TypeScript below is the single-process token bucket behind the numbers in section four. The trace in its comments uses capacity 10 and 2 tokens per second. It is not safe across processes, because two instances would each hold their own bucket, and it needs a sweep to evict idle keys or the map grows without bound.
interface Bucket {
tokens: number;
updatedAt: number; // ms
}
export class TokenBucketLimiter {
private buckets = new Map<string, Bucket>();
constructor(
private readonly capacity: number, // burst size
private readonly refillPerSec: number, // sustained rate
private readonly now: () => number = () => Date.now(), // injectable for tests
) {}
take(key: string, cost = 1): { allowed: boolean; retryAfterSec: number } {
const t = this.now();
// A new key starts full: a quiet client may burst immediately.
const b = this.buckets.get(key) ?? { tokens: this.capacity, updatedAt: t };
// Lazy refill: no timer, just arithmetic on elapsed time, capped at capacity.
const elapsedSec = (t - b.updatedAt) / 1000;
b.tokens = Math.min(this.capacity, b.tokens + elapsedSec * this.refillPerSec);
b.updatedAt = t;
this.buckets.set(key, b);
if (b.tokens >= cost) {
b.tokens -= cost;
return { allowed: true, retryAfterSec: 0 };
}
// Honest Retry-After: time until enough tokens exist, rounded up.
const missing = cost - b.tokens;
return { allowed: false, retryAfterSec: Math.ceil(missing / this.refillPerSec) };
}
}
// Trace with capacity 10, refill 2/s:
// t = 0 s 10 calls -> all allowed, tokens = 0
// t = 0 s 11th call -> rejected, missing = 1, retryAfterSec = ceil(1 / 2) = 1
// t = 3 s tokens = min(10, 0 + 3 * 2) = 6 -> 6 more calls allowed
const limiter = new TokenBucketLimiter(10, 2);
const verdict = limiter.take("api-key-123");Pick the algorithm by what a burst should do, not by what is easiest to write. A fixed window is fine until a boundary matters, a sliding window counter is the honest quota, a token bucket is the friendly default for APIs, and a leaky bucket is for protecting something fragile. Whichever you choose, state the sustained rate and the burst separately and return a Retry-After you can justify.
Sources and further reading