Rate Limiting: The Algorithms and When Each One Fits

Rate limiting protects a system from more load than it can serve — whether the source is abuse, a misbehaving client, or your own retry logic amplifying a problem.

For a separate people-operations perspective, this walkthrough covers detecting artificial activity signals.

The algorithm choice determines how bursts are handled, and the distributed case introduces a failure that the single-node version does not have.

The four algorithms

Fixed window

Count requests per fixed interval. Reset at the boundary.

Simple, cheap, one counter per key. And it has a specific flaw: a client can send the full allowance at the end of one window and the full allowance at the start of the next, producing twice the intended rate across the boundary.

With a limit of 100 per minute, 100 requests at 11:59:59 and 100 at 12:00:01 is 200 in two seconds, and every one is within the limit.

Acceptable where the limit is a rough guard. Not acceptable where the downstream genuinely cannot take the burst.

Sliding window log

Store a timestamp per request; count those within the trailing window. Exact, and memory grows with the request rate — a busy key stores every timestamp.

Correct, and expensive at scale.

Sliding window counter

The practical compromise. Keep counters for the current and previous window, and estimate the rate by weighting the previous window's count by how much of it still falls inside the trailing period.

Approximate, cheap, and it removes the boundary burst. This is the right default for most API rate limiting.

Token bucket

A bucket holds up to N tokens and refills at a fixed rate. Each request takes one; an empty bucket means rejection.

This is the one that models what you usually want. The refill rate is the sustained limit; the bucket size is the permitted burst. A client that has been idle accumulates tokens and can burst, which is usually correct behaviour — bursts are normal and the sustained rate is what protects you.

Leaky bucket is the variant that enforces a smooth output rate rather than permitting bursts. Right when the downstream cannot absorb any burst at all — a hardware device, a strictly rate-limited third-party API.

Choosing: token bucket where bursts are acceptable and sustained rate is the constraint. Leaky bucket where the downstream needs smoothness. Sliding window counter where you are enforcing a published API quota.

The distributed problem

The algorithms above assume one counter. With ten instances, each with its own counter, a limit of 100 becomes an effective limit of 1000.

Shared state — Redis or similar — is the usual answer, and it must be atomic. Read-then-write across a network round trip is a race, and under exactly the load you are limiting, the race is lost frequently.

-- one script, one round trip, atomic
local current = redis.call('INCR', KEYS[1])
if current == 1 then
  redis.call('EXPIRE', KEYS[1], ARGV[1])
end
return current

The cost is a network round trip on every request, which is significant on a hot path.

Local buckets with periodic reconciliation avoid the round trip: each instance limits locally at its share of the total and syncs periodically. Approximate, much faster, and it over-admits when traffic is unevenly distributed across instances.

And the decision that matters most: what happens when the shared store is unavailable?

Fail open and the limiter stops protecting you at the moment load is highest.

Fail closed and a Redis outage takes down your entire API.

Neither is right in general. The workable answer is usually to fall back to a conservative local limit — protection continues, approximately, without the dependency being able to cause a total outage.

What to limit by, and what to return

By API key or account for authenticated traffic. The only identifier that is meaningful.

By IP address for unauthenticated traffic, with the caveat that it is shared behind NAT and corporate proxies, so a limit low enough to stop an attacker may block an office.

Per endpoint, not globally. An expensive search endpoint and a cheap health check should not share a budget.

By cost, not by count, where request costs vary widely. Charging a query more tokens than a simple read is a small change with a large effect on how well the limit protects the thing you care about.

When rejecting, return 429, and include:

• Retry-After, so the client knows when to try again
• The limit, the remaining allowance, and the reset time, so a well-behaved client can pace itself rather than probing

A rate limiter without these headers teaches clients to retry blindly, which is the behaviour you were trying to prevent. See timeouts and retries.

Related but different mechanisms

Frequently conflated, and they solve different problems.

Rate limiting caps requests per client over time. Protects against abuse and runaway clients.

Concurrency limiting caps requests in flight. This is what actually protects a resource with a fixed capacity — a connection pool, a thread pool. A client can be within its rate limit and still exhaust your pool if each request is slow.

Load shedding rejects requests when the system is already overloaded, regardless of who sent them. Reactive rather than configured, and it is what keeps a service alive when the aggregate exceeds capacity even though every client is compliant.

Backpressure propagates the constraint upstream so producers slow down rather than being rejected.

Most systems need concurrency limiting and load shedding more than they need rate limiting, and reach for rate limiting first because it is the one with a familiar name.

Practical points

Set the limit from measured capacity, not from a round number. Load test to find where latency degrades, and set below it.

Make it configurable without a deploy. You will need to change it during an incident.

Log rejections with the key, so you can distinguish an attack from a legitimate client that outgrew its allowance.

Alert on rejection rate. A sudden rise is either an attack or a client bug, and both need attention.

Have a bypass for internal traffic, and be careful with it — an internal service exempted from limits is a way for one team to take down another.

Test what happens at the limit, not just below it. The rejection path is the least exercised code and it has bugs like any other.

The summary

Token bucket for sustained-rate-with-burst, leaky bucket where the downstream needs smoothness, sliding window counter for published quotas.

Fixed windows admit double the rate across the boundary.

Distributed limiting needs atomic shared state, and the important decision is what happens when that state is unreachable — usually a conservative local fallback rather than fail open or fail closed.

Return 429 with Retry-After and limit headers, or you have built something that produces retry storms.

And check whether you actually need concurrency limiting instead — for protecting a fixed resource, it is usually the right tool.