Rate limiting algorithms

The algorithms behind rate limiters and how to run them across many servers: fixed window, sliding window log, sliding window counter, token bucket, leaky bucket and GCRA, with their accuracy, memory and burst behaviour, plus distributed counters, Lua atomicity and response headers.

Reading is half of it. See this used in a real interview: walk through Design a Rate Limiter →

"Design a rate limiter" is one of the most common system design questions, and the first decision is which algorithm to use. Each one counts requests differently, which changes how bursts behave, how much memory it takes, and how accurate it is at window edges. This guide compares them, then covers running them across a fleet of servers.

Fixed window counter

Count requests per key per window (for example per minute): key user:42:202610051230, INCR it, set an expiry, reject when above the limit.

• Very cheap: one counter per key per window.
• Edge burst problem: a client can send the full limit at 12:30:59 and again at 12:31:00, doubling the rate briefly.

Sliding window log

Store the timestamp of every request (for example in a sorted set). On each request, remove timestamps older than the window, count the rest, and allow if under the limit.

• Exact: no edge bursts.
• Memory grows with the limit: a limit of 10,000 per hour stores up to 10,000 timestamps per client.

Sliding window counter

Approximate the sliding window with two fixed windows: count in the current window plus the previous window's count weighted by how much of it still overlaps.

estimate = current + previous × (1 − elapsed_fraction_of_current)

• Two counters per key, smooth behaviour, small error that assumes requests were evenly spread in the previous window.
• A good default for API limits.

Token bucket

Each key has a bucket holding up to B tokens, refilled at r tokens per second. Each request takes a token; with none left, it is rejected (or delayed).

• Allows bursts up to B, while enforcing an average rate r.
• Only two values per key: token count and last refill time, with refill computed lazily on each request.
• Used widely (cloud APIs, network traffic shaping).

Leaky bucket

Requests enter a queue that drains at a fixed rate; when the queue is full, new requests are dropped.

• Smooths output to a constant rate, which protects downstream systems that cannot absorb bursts.
• Adds queueing delay; as a pure limiter (without the queue) it behaves like a token bucket with a small burst.

GCRA (generic cell rate algorithm) implements leaky-bucket semantics with a single timestamp per key (the theoretical arrival time) and is popular in Redis-based limiters.

Comparison

Running it across many servers

A limit of 100 requests per minute must hold across all API servers. Options:

• Central store: every server checks and updates counters in Redis. Make each check atomic with a Lua script (read, compute, update in one step) to avoid races between servers. Adds one fast round trip per request. See Redis data structures.
• Local limits: each of N servers enforces limit / N. No network call, but inaccurate when traffic is unevenly spread.
• Hybrid: local counters synced to the central store periodically, or local token buckets refilled from a central allocation. Fast with bounded error.

Shard the counter store by key; consider what happens if it is unavailable: usually fail open (allow traffic) for general limits, and fail closed only for abuse-critical ones.

Choosing keys and limits

• Keys: user id, API key, IP (careful with shared IPs and mobile carriers), endpoint, tenant. Several limits often apply at once (per user and per endpoint and global).
• Different limits for different costs: a search may cost 10 units, a profile read 1.
• Higher limits for paid tiers; separate limits for expensive operations like signups and password attempts. See trust and safety.

Telling clients

Return 429 Too Many Requests with Retry-After, and expose RateLimit-Limit, RateLimit-Remaining and RateLimit-Reset style headers so well-behaved clients can pace themselves. Log and monitor rejections per key to spot abuse and misconfigured clients. See API gateways.

In the interview

For Design a Rate Limiter: clarify per-what and how strict; pick a token bucket (bursts allowed) or sliding window counter (smooth) and say why; store state in Redis with an atomic Lua script, sharded by key; run the check in the gateway or a sidecar; fail open on store outages; return 429 with headers. Mention the local-plus-sync hybrid if latency matters.

Checklist

• Algorithm chosen for burst behaviour, accuracy and memory.
• Atomic check-and-update in a shared store, sharded by key.
• Local or hybrid limits where a network call per request is too costly.
• Fail-open versus fail-closed decided per limit.
• Multiple keys and cost-weighted limits.
• 429 responses with Retry-After and rate limit headers.