Rate Limiting: The Algorithms and How Real APIs Implement Them

Rate limiting is the practice of constraining how much traffic a given identity, an IP address, a user account, an API key, may send within a time window, and rejecting or delaying whatever exceeds it. The concept sounds simple. The hard part is the counting: tracking how many requests an identity has made recently, accurately and cheaply, at a scale where storing every individual request timestamp forever isn't practical. Several well-known algorithms solve this counting problem differently, with real tradeoffs between accuracy, memory cost, and how they handle bursts.

Why this matters, and where it's relevant

Without rate limiting, any endpoint reachable without authentication, or reachable by any authenticated user without a cap, can be hit as fast as a script can fire requests. This is especially costly for endpoints that do genuinely expensive work per request: a login endpoint performing a deliberately slow password hash, a search endpoint running a complex query, an endpoint making an outbound call to a third-party service. Rate limiting is the standard defense against this class of problem, and it's relevant to essentially any publicly reachable endpoint, not just ones that feel obviously sensitive. The HTTP status code and header contract for communicating a rate limit back to a client is itself standardized, which matters for building anything that consumes a rate-limited API correctly, not just for building one.

The algorithms

Token bucket

A bucket holds tokens, refilled at a fixed rate up to a maximum capacity. Each request consumes one token. If the bucket is empty, the request is rejected or delayed. This design allows bursts up to the bucket's capacity while still enforcing an average rate over time, which is closer to how real traffic actually arrives than a strictly constant rate would be.

Leaky bucket

Requests enter a fixed-capacity queue and are processed at a strictly constant rate; anything beyond the queue's capacity is dropped. This produces smooth, predictable output with no bursting at all, trading burst tolerance for a guarantee that whatever's downstream never sees a spike.

Fixed window counter

Requests are counted in discrete time windows (for example, one bucket per minute), and the counter resets at each window boundary. This is the cheapest option, a single integer per identity, but it has a well-documented flaw: a client can send a full quota right at the end of one window and another full quota right at the start of the next, effectively doubling the allowed burst at the boundary.

Sliding window log

A timestamp is stored for every request. On each new request, entries older than the window are purged and what remains is counted. This is exactly accurate, with no boundary flaw, but its memory cost scales with request volume rather than with the number of identities being tracked, which becomes expensive at real scale.

Sliding window counter

A hybrid that blends the previous window's count with the current one, weighted by how much of the current window has elapsed. This approximates the accuracy of a sliding log while keeping memory cost close to a fixed window's, roughly two integers per identity instead of one timestamp per request.

How real systems actually implement this

Cloudflare's own engineering blog documents exactly this evaluation process, and it's worth citing directly since it's a company describing its own production system, not a secondary summary. They explicitly rejected fixed window (the boundary-burst problem), sliding log (too much memory per-request timestamp storage), and leaky bucket (requires atomic multi-step operations incompatible with their memcached-based storage), settling on an approximated sliding window using the formula rate = previous_period_count * ((period_length - elapsed_time) / period_length) + current_period_count. Their reported production numbers: 0.003% of requests wrongly allowed or limited across 400 million requests, roughly 6% average deviation from the true rate, using only two integers of state per counter.

Stripe's own engineering blog describes using token bucket as their primary mechanism, layered with three additional, more specific limiters: a concurrent-requests limiter that caps simultaneous in-flight requests per resource independent of the rate itself (protecting against retry amplification on expensive endpoints), a fleet usage load shedder that reserves capacity for critical operations over less critical ones during high load, and a worker utilization load shedder that sheds load gradually by priority tier during incidents specifically to avoid oscillation. This is a useful example of rate limiting as one layer of a larger defense, not a single algorithm applied uniformly everywhere.

GitHub's REST API documentation is a good example of multiple simultaneous rate-limiting dimensions applied to one API at once: a primary hourly quota, a separate secondary limit on concurrent requests, a points-per-minute budget, and even a CPU-time budget, each independently enforced and each capable of triggering a limit response on its own.

The response contract: 429 and Retry-After

The status code for a rate-limited request, 429 Too Many Requests, comes from RFC 6585, which states the response should include details explaining the condition and may include a Retry-After header, and specifies that 429 responses must not be cached. Retry-After itself is currently specified in RFC 9110, section 10.2.3 (the consolidated HTTP semantics spec that obsoletes the older RFC 7231), and takes either an integer number of seconds or an HTTP date:

HTTP/1.1 429 Too Many Requests
Retry-After: 30

RFC 6585 is explicit that identifying the client for rate-limiting purposes, by IP, by user account, by API key, is left entirely to the server's implementation, not something the spec prescribes. Per-IP is the crudest option and breaks down under shared IPs (corporate networks, carrier-grade NAT); per-user or per-API-key, as Stripe and GitHub both use, is more precise and is what production APIs generally document and enforce.

Applying it

• Match the algorithm to the actual requirement: token bucket if some bursting is acceptable and even desirable, leaky bucket if downstream systems need a strictly smooth rate, sliding window counter as a good default when neither extreme is required.
• Don't build a rate limiter's counting logic from scratch without first checking whether a maintained library already implements the algorithm correctly. The Python limits library, for example, implements fixed window, sliding window counter, and moving window strategies as selectable, tested backends over Redis, Memcached, and MongoDB.
• Always return 429 with a Retry-After header, not a generic error. A well-behaved client can use that header to back off correctly instead of retrying immediately and making the situation worse.
• Consider layering more than one limiter, as Stripe does, rather than relying on a single rate-per-time-window check to cover every failure mode a service actually needs to defend against.