System designCore3 min

Rate limiting algorithms

Cap how fast each client can call you, so one noisy caller, buggy script or attack can't take the service down for everyone else.

1 · Why

Protect capacity, and share it fairly

A rate limiter counts requests per key (an API token, a user, an IP address) and rejects those over the limit with 429 Too Many Requests and a Retry-After header. It usually runs at the edge, in the API gateway, before any real work is done.

Over the limit, the gateway answers 429 itself; the service never sees the request.

2 · The algorithms

Five ways to count

Algorithm	How it counts	Memory per key	Catch
Fixed window	A counter per minute, reset on the minute	One number	Allows 2× the limit across a window boundary
Sliding log	A timestamp per request; count those in the last minute	One entry per request	Exact, but memory grows with the limit
Sliding window counter	This minute's count plus a weighted share of the last one's	Two numbers	A close approximation, not exact
Token bucket	Tokens drip in at the rate; each request takes one	Two numbers	Allows bursts up to the bucket size, by design
Leaky bucket	Requests queue and drain at a fixed rate	A queue	Smooth output, but bursts wait instead of going through

The fixed window's flaw: with a limit of 100 a minute, a client can send 100 at 0:59 and 100 more at 1:00, so 200 in two seconds. The sliding window counter fixes it cheaply: at 1:15, count this window's requests plus 75% of the previous window's.

3 · The usual choice

Token bucket: a steady rate with room for bursts

The bucket holds up to *b* tokens,
for example 20, and starts full.
Tokens refill at rate *r*,
for example 10 a second, and never beyond b.
Each request takes a token.
No token left: reject with 429.
So a quiet client can burst,
sending 20 at once, but can't average more than 10 a second.

No timer needed: refill lazily on each request

typescript

function allow(b: { tokens: number; at: number }, rate: number, size: number, now: number) {
  b.tokens = Math.min(size, b.tokens + ((now - b.at) / 1000) * rate);
  b.at = now;
  if (b.tokens < 1) return false;
  b.tokens -= 1;
  return true;
}

4 · Across many servers

Share the count, or split the limit

With ten gateway servers, each one counting on its own lets a client get ten times the limit. The two usual answers:

Approach	How	Trade-off
Shared counters	Every gateway updates the key's counter in Redis in one atomic step (a script, or INCR with an expiry)	Exact, but adds a network hop per request and a dependency; decide whether to allow or deny when Redis is down
Local limits	Each of N gateways allows limit ÷ N	No extra hop; unfair if traffic isn't evenly spread

Either way, tell clients where they stand: Retry-After on a 429, and headers with the remaining quota, so well-behaved clients slow down before they're cut off.

Check yourself

3 questions

1. Limit 100 a minute with a fixed window. What's the most a client can get through in two seconds?

2. A token bucket has size 20 and refills 10 tokens a second. A client has been idle. What can it do?

3. Ten gateways each enforce the full limit with their own local counter. What goes wrong?

Takeaways

Remember this

Limit per key at the edge, and answer 429 with Retry-After.
Fixed windows allow double bursts at the boundary; sliding window counters fix that for two numbers of memory.
Token bucket is the usual choice: a steady rate, with bursts up to the bucket size.
Across servers, share counters atomically or split the limit.