Rate Limiting Algorithms

Definition: Techniques used to control the rate of incoming or outgoing requests to protect API services from abuse, overload, and resource exhaustion.

How It Works

Token bucket: a bucket holds up to a fixed capacity of tokens, refilled at a constant rate. Each request consumes one token; if the bucket is empty, the request is rejected or queued. Because tokens can accumulate while idle, this allows controlled bursts up to the bucket’s capacity.
Leaky bucket: incoming requests enter a fixed-size FIFO queue, processed (leaked out) at a constant rate regardless of arrival rate. Unlike token bucket, it smooths bursts into a steady output rate rather than allowing them through.
Fixed window counter: a counter increments per request within a fixed time window (e.g., per calendar minute) and resets to zero at the window boundary. Simple and cheap, but allows up to 2x the intended rate right at a window boundary, since a burst at the end of one window and a burst at the start of the next are both individually within limit.
Sliding window log: stores a timestamp for every request within the lookback period and counts how many fall within the trailing window on each new request. Precise, no boundary burst problem, but memory cost grows with request volume since every timestamp must be retained.
Sliding window counter: approximates the sliding log by combining the current and previous fixed window counts, weighted by how far into the current window the request falls. Much cheaper than the log approach, with only a small approximation error, and it’s the algorithm most production rate limiters converge on.
Concurrency (in-flight) limiting: distinct from rate-over-time limiting, this caps the number of simultaneous in-progress requests rather than requests per unit time, protecting against a backend where slow requests (not request count) are what exhausts resources.
Distributed rate limiting requires a shared state store (typically Redis) so that every request-handling node sees the same counters or bucket state; each request does an atomic increment-and-check (often via a Lua script in Redis to avoid a race between the check and the increment).
Rate limit responses conventionally include 429 Too Many Requests along with headers like X-RateLimit-Limit, X-RateLimit-Remaining, and Retry-After, so well-behaved clients can back off and retry appropriately instead of hammering the endpoint.
Worked example, token bucket: a bucket with capacity 10 and a refill rate of 1 token/second starts full. A client sends 10 requests in the same second, all succeed, draining the bucket to 0. An 11th request that same second is rejected. After 5 seconds of no traffic, the bucket has refilled to 5 tokens (capped at the 10-token capacity), so the client can burst up to 5 requests immediately, then must wait for further refill.
Worked example, sliding window counter: with a 60-second window and a limit of 100, suppose the previous window (the minute that just ended) had 80 requests, and 15 seconds into the current window there have been 20 requests so far. The estimated count is previous_window_count × (1 - elapsed_fraction) + current_window_count, here 80 × (1 - 15/60) + 20 = 80 × 0.75 + 20 = 80, still under the limit of 100, so the request is allowed.

Trade-offs

Token bucket allows bursts (good for bursty-but-legitimate traffic like a client retrying a batch of requests) at the cost of admitting short-term spikes well above the average rate, which downstream systems must still be able to absorb.
Leaky bucket produces a perfectly smooth output rate, which protects downstream systems more predictably, but it penalizes legitimate bursts by queuing (adding latency) or dropping them exactly like abusive traffic.
Fixed window counters are cheap (one counter, one key) but structurally allow a 2x burst at window boundaries, an accuracy gap that’s unacceptable for strict limits but fine for coarse, generous ones.
Sliding window log is the most accurate but the most expensive, storing per-request timestamps doesn’t scale gracefully to very high request rates or very long lookback windows.
Sliding window counter is the practical middle ground: small, bounded memory like the fixed window, accuracy close to the sliding log, at the cost of being an approximation rather than an exact count.
Centralizing rate-limit state in Redis (or similar) makes limits consistent across a fleet of servers, at the cost of adding a network round trip (and a new dependency whose own availability now matters) to every rate-limited request.

Why It Matters

It’s the primary defense against denial-of-service traffic, brute-force login attempts, and scraping, without which a single client (malicious or just buggy) can degrade service for everyone else.
It prevents noisy-neighbor problems in multi-tenant systems, where one tenant’s traffic spike shouldn’t be able to starve out every other tenant sharing the same backend capacity.
It shapes API product design directly: published rate limits (requests per minute, per API key) are part of the contract clients build against, and the choice of algorithm determines how forgiving or strict that contract feels in practice.

Common Pitfalls

Enforcing rate limits in local, per-process memory instead of a shared store. Behind a load balancer with multiple server instances, each instance enforces its own limit independently, so the effective limit becomes (per-instance limit × instance count), not the intended global limit.
Using a fixed window counter for a strict limit without accounting for the boundary-burst problem, then being surprised when clients get roughly double the advertised rate through by timing requests around the window edge.
Not distinguishing between rate limiting (requests over time) and concurrency limiting (simultaneous in-flight requests), when the actual resource being protected (a slow downstream call, a connection pool) is exhausted by concurrency, not request rate.
Applying a single global limit instead of scoping limits appropriately, per API key, per IP, per endpoint, so one abusive client or one expensive endpoint can exhaust a shared budget meant for everyone.
Failing to return clear signals (429, Retry-After) when throttling, forcing clients to guess at backoff timing instead of being told explicitly, which often makes retry storms worse, not better.
Not accounting for the added latency and failure mode of the shared rate-limit store itself; if Redis is unreachable, the system needs an explicit fail-open or fail-closed decision, not an undefined one.
Setting the same limit for authenticated and unauthenticated traffic, which either makes the authenticated limit too generous for anonymous abuse or too strict for legitimate high-volume authenticated clients.
Forgetting that rate limiting and abuse detection are different problems: a client staying just under the rate limit while still behaving maliciously (credential stuffing at a slow, steady rate) won’t be caught by request-rate limiting alone and needs separate anomaly detection.

Comparison

	Token Bucket	Leaky Bucket	Fixed Window	Sliding Window Log	Sliding Window Counter
Allows bursts	Yes, up to bucket capacity	No, smooths to constant rate	Yes, up to 2x at boundary	No	Approximately no
Memory cost	Low, one counter + timestamp	Low, one queue/counter	Low, one counter	High, grows with request volume	Low, two counters
Accuracy	Exact	Exact	Boundary burst inaccuracy	Exact	Small approximation error
Implementation complexity	Low	Low-medium (needs a queue/worker)	Very low	Medium-high	Medium
Scales to high request volume	Yes	Yes	Yes	Poorly, memory grows with volume	Yes
Typical use	APIs wanting to permit legitimate bursts	Traffic shaping to a strict steady rate	Simple, coarse, cheap limits	Strict, low-volume limits	Most production API rate limiters

Debugging Walkthrough: Inconsistent Throttling Across a Fleet

A customer reports that their integration, capped at a documented 600 requests/minute per API key, gets 429 responses after only around 100 requests in a minute, far below the advertised limit. Another customer on the same plan reports the opposite: they’re sending well over 600/minute and never see a 429 at all.
First check: is the limiter’s shared state actually shared? Querying the Redis key that should hold this API key’s counter returns a value inconsistent with the request volume seen in the load balancer’s access logs, a strong hint the counter isn’t tracking the true global request count.
Second check: how many application server instances handle this traffic, and where does the rate-limit check actually run? The code review turns up the answer: the rate limiter was implemented with an in-process counter (a plain in-memory dictionary keyed by API key), not Redis, despite Redis being available and used elsewhere in the codebase.
That explains both symptoms at once. Behind a load balancer routing round-robin across, say, 6 instances, a client whose requests happen to concentrate on 1-2 instances (due to keep-alive connection reuse) gets throttled by that instance’s local limit divided across fewer servers, hitting 429 far sooner than 600/minute. A client whose requests spread evenly across all 6 instances effectively gets 6 × 600 = 3600/minute before any single instance’s local counter trips, explaining why they never see a limit at all.
Fix: move the counter into the shared Redis store with an atomic Lua script for the check-and-increment, so every instance reads and writes the same counter regardless of which one handles a given request.
Verify: after deployment, both customers’ observed throttling behavior converges to the documented 600/minute regardless of which backend instance serves the request, and a new dashboard panel graphing “requests allowed per instance” catches this specific drift (per-instance limiting silently reappearing) if it’s ever reintroduced by a future change.

Real-World Scenario

A public API enforces 100 requests per minute per API key using a sliding window counter backed by Redis. Each request runs a Lua script that atomically reads the previous and current minute’s counts, computes the weighted estimate, and either increments and allows or rejects with 429 plus a Retry-After header. A client that bursts 100 requests in the first second of a minute is throttled for the rest of that minute, unlike a fixed-window implementation that would let it send another 100 immediately after the minute rolls over, effectively doubling its real short-term rate.

FAQ

Which algorithm should I default to if I’m not sure? A sliding window counter backed by a shared store like Redis; it gives good accuracy at low memory cost and is what most rate-limiting middleware and API gateways implement by default.

Should rate limiting happen at the API gateway, the application, or both? Commonly both: the gateway handles coarse, cheap, edge-level limits (per IP, per API key) to shed obviously abusive traffic early, while the application can apply finer-grained, business-aware limits (per user action, per expensive operation).

How does rate limiting relate to consistent hashing? Distributed rate limiters often shard their counters across nodes using consistent hashing, so that all requests for a given key (API key, IP) consistently route to the same counter instance instead of needing a fully global lock.

Why do some APIs rate limit by cost/weight instead of raw request count? Because not all requests cost the same to serve, a search query and a single-row lookup shouldn’t count equally against the same budget; assigning weights (GitHub’s GraphQL API does this) protects backend capacity more accurately than a flat per-request count.

Should burst allowance be the same for every client tier? Not necessarily. Higher-paying or higher-trust tiers commonly get larger bucket capacity or higher refill rates, which is straightforward to express with token bucket (different capacity/rate per tier) but awkward with a strict sliding log.

Is client-side rate limiting useful? Yes, as a courtesy and to reduce wasted requests, but it can never be trusted as the actual enforcement mechanism, since a malicious or buggy client can simply ignore it; server-side enforcement is what actually protects the system.

History

Token bucket and leaky bucket originated in network traffic-shaping and QoS research from the 1980s, designed to police and smooth traffic on ATM and early packet-switched networks before either algorithm was ever applied to web APIs.
As public APIs became a primary product surface in the late 2000s (Twitter, GitHub, Stripe), rate limiting shifted from a network-layer concern to an application- and API-gateway-layer concern, with HTTP-specific conventions (429, Retry-After, X-RateLimit-* headers) emerging as a de facto standard.
The sliding window counter approximation became widely adopted as Redis-backed rate limiting matured, since it gave near-log accuracy without the log’s unbounded memory growth, making it practical at high request volumes.

Common Interview Questions

Why does a fixed window counter allow twice the intended rate at a boundary? Because a full burst can land in the last moments of one window and another full burst in the first moments of the next, and each window checks its own count independently.
How would you design a rate limiter that’s consistent across many servers? Back it with a shared, atomic store like Redis, using an atomic increment-and-check operation (e.g., a Lua script) to avoid race conditions between concurrent requests.
What’s the difference between rate limiting and throttling versus circuit breaking? Rate limiting controls how much traffic is let through based on a policy; a circuit breaker stops sending traffic to a downstream dependency that’s already failing, regardless of the caller’s own request rate.
When would leaky bucket be preferred over token bucket? When the priority is a perfectly smooth, predictable output rate to protect a downstream system, rather than allowing legitimate clients to burst.
How should a rate limiter behave if its shared state store (e.g., Redis) becomes unavailable? This is a deliberate fail-open (allow requests, risk overload) versus fail-closed (reject requests, risk unnecessary downtime) design decision, not an accident.

Example

GitHub’s REST API limits unauthenticated requests to 60 calls per hour and authenticated requests to 5,000 per hour, implemented with counters tracked per token. Stripe’s API uses a token-bucket-style limiter that allows short bursts while enforcing a steady average rate, returning 429 with rate-limit headers when exceeded.

Design Checklist

Is the limit scoped correctly (per API key, per IP, per endpoint), or is a single shared budget letting one client or one expensive endpoint starve everyone else?
Does the algorithm’s burst behavior match the traffic it needs to handle: bursty-but-legitimate (token bucket) versus needing a smooth, protected downstream rate (leaky bucket)?
Is rate-limit state shared correctly across every server instance, or does each instance silently enforce its own independent limit?
Are 429 responses paired with clear Retry-After guidance so well-behaved clients back off instead of retrying immediately?
Has the fail-open versus fail-closed behavior been decided explicitly for when the shared rate-limit store is unavailable?

Referenced by

Dig deeper

Spot an error in this note?