API Rate Limiting: Pick the Right Algorithm
This article explains how to choose the right rate limiting algorithm for your API, comparing fixed window, sliding window, token bucket, and leaky bucket approaches. You will learn the trade-offs of each method and get practical guidance for shipping reliable limits that protect your service without frustrating legitimate users.
Why Rate Limiting Matters
APIs are shared resources. Without rate limits, a single client can monopolize your server, drive up costs, or trigger a cascading failure. Rate limiting is the practice of controlling how many requests a client can make in a given time period. It is distinct from authentication and authorization: those decide who can access what, while rate limiting decides how often they can do it.
Good rate limiting does more than block excess traffic. It protects downstream databases from overload, prevents brute-force attacks on login endpoints, and ensures fair usage across all customers. A well-chosen algorithm balances strictness against usability: too strict and you frustrate users; too loose and you defeat the purpose.
The Core Algorithms
Four algorithms dominate modern API rate limiting. Each has a different model for tracking and enforcing limits.
- Fixed Window – Divides time into buckets (e.g., 1 minute). A client gets a maximum number of requests per bucket. The counter resets at the start of each window.
- Sliding Window Log – Stores a timestamp for every request. To check a new request, it counts timestamps within the last N seconds. This is precise but memory-intensive.
- Sliding Window Counter – A hybrid that uses the previous window’s count plus the current window’s count, weighted by how much of the previous window has elapsed. It approximates a true sliding log with far less memory.
- Token Bucket – A bucket holds tokens that refill at a fixed rate. Each request consumes one token. If the bucket is empty, the request is denied. This allows bursts up to the bucket size.
- Leaky Bucket – Requests enter a queue (the bucket) and are processed at a constant rate. If the queue is full, new requests are rejected. This smooths bursts but adds latency.
Each algorithm solves a slightly different problem. Fixed window is simple but allows double requests at window boundaries. Token bucket is ideal for allowing short bursts while enforcing a long-term average. Leaky bucket is best when you need a steady, predictable outflow.
How to Choose the Right Algorithm
There is no universal “best” algorithm; the right choice depends on your traffic patterns and business requirements. Consider these factors:
- Burst tolerance – Can a client send 10 requests instantly, then wait? Token bucket allows this; fixed window might reject the 11th even if the client was idle for 59 seconds.
- Memory constraints – Sliding window log stores every request timestamp, which can be expensive for high-traffic APIs. Sliding window counter uses just two counters per client.
- Latency sensitivity – Leaky bucket adds a queue delay. If your API must respond in milliseconds, token bucket or sliding window counter are better.
- Fairness – Fixed window can penalize a client that starts near the end of a window. Sliding window algorithms are fairer.
- Implementation complexity – Fixed window is trivial to implement with a simple counter and timestamp. Sliding window log requires a sorted set or similar structure.
As a rule of thumb: use token bucket for most public APIs where you want to allow occasional bursts. Use sliding window counter when you need precise limits without high memory use. Use fixed window only for internal tools or when simplicity outweighs accuracy. Avoid leaky bucket unless you specifically need to smooth out request flow.
Common Pitfalls and Misconceptions
One common mistake is assuming that a rate limit of “100 requests per minute” means you can send 100 requests at 12:00:59 and another 100 at 12:01:01. With a fixed window, that is exactly what happens – you get 200 requests in two seconds. This is the “boundary problem.” Token bucket and sliding window algorithms eliminate this by not resetting at arbitrary boundaries.
Another misconception is that rate limiting is only about rejecting requests. Good rate limiting also includes:
- Returning the
Retry-Afterheader so clients know when to try again. - Including
X-RateLimit-Limit,X-RateLimit-Remaining, andX-RateLimit-Resetheaders so clients can self-throttle. - Using a 429 HTTP status code with a clear error body.
Many developers also forget to apply rate limits per user, per IP, and per API key separately. A single IP behind a NAT can represent many users, and a single user can rotate IPs. The right granularity depends on your authentication model.
Implementation Considerations
In a distributed system, rate limit counters must be shared across all server instances. A common approach is to store counters in a centralized store like Redis, using atomic operations such as INCR and EXPIRE for fixed window, or a Lua script for sliding window counter.
Be aware of clock synchronization. If your servers use different clocks, a fixed window that resets at a local time can behave inconsistently. Use UTC or a single authoritative time source.
Also consider what happens when the rate limiter itself fails. If Redis is down, do you allow all requests (fail-open) or block all (fail-closed)? Fail-open protects availability but leaves you unprotected; fail-closed protects the system but can cause an outage. Many APIs choose fail-open with a circuit breaker that disables the limiter temporarily.
Costs and Performance
Rate limiting adds overhead to every request. The cost depends on the algorithm and storage:
- Fixed window – One counter read/write per request. Very cheap.
- Sliding window log – One write per request and a range query. Expensive at scale.
- Sliding window counter – Two counter reads/writes per request. Moderate.
- Token bucket – One counter read/write, plus a timestamp for refill. Cheap.
- Leaky bucket – Usually requires a queue, which adds memory and latency.
For high-throughput APIs, even a few milliseconds of extra latency per request can add up. In-memory counters are fastest, but they don’t work across multiple instances. Redis with pipelining or Lua scripts can keep overhead low.
Alternatives to Traditional Rate Limiting
If the algorithms above don’t fit, consider these alternatives:
- Concurrency limiting – Limit the number of simultaneous requests, not the rate. Useful for long-polling or streaming endpoints.
- Load shedding – When the system is overloaded, reject a percentage of requests (e.g., random 10%). This protects the system without per-client tracking.
- Priority queues – Allow higher-tier clients to bypass limits or get larger quotas.
- Adaptive throttling – Adjust limits dynamically based on system health, not just client behavior.
These are not replacements for rate limiting but can complement it. For example, you might use token bucket for per-client limits and load shedding as a safety net.
Frequently Asked Questions
What is the difference between rate limiting and throttling?
Rate limiting sets a hard cap on requests per time unit and rejects excess requests. Throttling is a broader term that may include delaying requests (like leaky bucket) or reducing quality of service. In practice, the terms are often used interchangeably, but throttling usually implies slowing down rather than outright blocking.
Should I use a fixed window or token bucket for a public API?
Token bucket is generally better for public APIs because it allows natural bursts (like a client sending 10 requests at once after loading a page) while still enforcing a long-term average. Fixed window can cause unfair rejections at the boundary and is harder to tune for bursty clients.
How do I choose the rate limit numbers?
Start by measuring your actual traffic and server capacity. Determine the maximum requests per second your backend can handle without degrading, then divide by the expected number of active clients. Add a safety margin. For example, if your server handles 1000 req/s and you expect 100 active clients, a limit of 5 req/s per client is a reasonable starting point.
What should I return when a client exceeds the limit?
Return HTTP 429 Too Many Requests with a JSON error body. Include a Retry-After header in seconds. Also include rate limit headers (e.g., X-RateLimit-Remaining) so clients can proactively slow down.
Can rate limiting prevent DDoS attacks?
Rate limiting can mitigate some DDoS attacks, especially application-layer attacks that send many requests, but it is not a complete solution. Distributed attacks from many IPs may bypass per-client limits. Use rate limiting in combination with other defenses like IP reputation, CDN filtering, and load balancing.
How do I test my rate limiter?
Write automated tests that send requests in a loop and assert that the 101st request (when limit is 100) returns 429. Test boundary conditions: send requests just before and after the window resets. Use a tool like Apache JMeter or a simple script to simulate bursty traffic.
Related
Method: the standard formula for this calculation, rounded as each result states. See how the calculators work or report an error.