Rate Limiting Algorithms Explained

What Is a Rate Limiter?

A rate limiter is a mechanism that controls how many requests a client can send to a service within a defined time interval. It tracks incoming requests against a configured limit and decides whether to allow or reject each request.

For example, an API may allow 100 requests per minute per client. Once the client reaches this limit, further requests may be rejected with an HTTP 429 Too Many Requests response until the configured policy allows more requests.

Rate limiting helps protect backend services from excessive traffic, prevents resource misuse, and ensures fair access to APIs.

Where Should a Rate Limiter Be Implemented?

A rate limiter can be implemented on the client side, on the server side, or as middleware between clients and API servers.

Client-Side Rate Limiting

The client controls how frequently it sends requests. However, clients can bypass these limits, so client-side rate limiting alone cannot protect an API.

Server-Side Rate Limiting

The server checks incoming requests against configured limits and decides whether to allow or reject them. Since the API provider controls the implementation, this approach provides reliable enforcement.

Middleware or API Gateway

A rate limiter can run as a separate component between clients and API servers. It checks incoming requests before forwarding allowed requests to the backend.

For example, if an API allows two requests per second per client, the first two requests are forwarded to the API servers, while the third is rejected with an HTTP 429 Too Many Requests response.

This approach is useful for applications with multiple API servers because requests can be checked at a common entry point.

Rate Limiting Algorithms

Rate-limiting algorithms use different approaches to track incoming requests and decide whether to allow or reject them. The following five algorithms differ in how they manage request counts, time windows, and traffic bursts.

1. Token Bucket Algorithm

The Token Bucket algorithm is a widely used rate-limiting algorithm. It controls incoming requests using a bucket that holds a limited number of tokens. Tokens are added at a configured rate, and each request consumes one token.

How Does It Work?

• Bucket capacity: The bucket has a predefined maximum capacity. For example, if its capacity is 4, it can hold at most 4 tokens.
• Token refill: Tokens are added at a fixed rate, such as 2 tokens per second. If the bucket is full, additional tokens are discarded.
• Request handling: When a request arrives, the rate limiter checks whether a token is available. If one is available, it is consumed and the request is allowed.
• Request rejection: If no tokens are available, the request is rejected.

Suppose the bucket capacity is 4 tokens and the refill rate is 4 tokens per minute.

• At 1:00:00, the bucket contains 4 tokens.
• At 1:00:05, three requests arrive and consume 3 tokens, leaving 1 token.
• At 1:00:20, another request consumes the remaining token. Any additional request is rejected until a token becomes available.
• At 1:01:00, the bucket can refill up to its capacity of 4 tokens.

Parameters

The Token Bucket algorithm uses two main parameters:

• Bucket size: The maximum number of tokens the bucket can hold.
• Refill rate: The number of tokens added to the bucket over a specified period.

The number of buckets depends on the rate-limiting rules. For example, separate buckets may be used for different API endpoints or individual IP addresses. A global bucket can be used when the system needs to limit the total number of requests across all clients.

Advantages

• Easy to implement and memory-efficient.
• Allows short bursts of traffic when tokens are available.

Limitations

• Choosing the right bucket size and refill rate requires careful tuning.

2. Leaky Bucket Algorithm

The Leaky Bucket algorithm is a rate-limiting algorithm that processes requests at a fixed rate. It is usually implemented using a First-In, First-Out (FIFO) queue, where incoming requests wait until they can be processed.

Unlike the Token Bucket algorithm, which allows bursts when tokens are available, the Leaky Bucket algorithm controls the rate at which requests leave the queue.

How Does It Work?

• Request arrival: When a request arrives, the system checks whether the queue has space.
• Queue capacity: If the queue is not full, the request is added to the queue.
• Request rejection: If the queue is full, the incoming request is rejected.
• Request processing: Requests are removed from the queue and processed at a fixed rate, one after another.

Suppose a rate limiter has a queue capacity of 4 requests and processes 2 requests per second.

• At 1:00:00: Four requests arrive and enter the queue.
• At 1:00:00.2: Another request arrives, but the queue is full, so the request is rejected.
• At 1:00:01: Two requests are processed, freeing space in the queue.
• After that: New requests can enter the queue as space becomes available, while queued requests continue to be processed at the configured rate.

Parameters

The Leaky Bucket algorithm has two main parameters:

• Bucket size: The maximum number of requests the queue can hold.
• Outflow rate: The rate at which requests are processed, such as 2 requests per second.

Advantages

• Memory-efficient because the queue has a fixed capacity.
• Provides a steady request-processing rate.
• Helps prevent sudden traffic bursts from overwhelming backend services.

Limitations

• A burst of requests can fill the queue, causing newer requests to be rejected even if they are valid.
• Requests may experience delays while waiting in the queue.
• Choosing the right queue size and processing rate requires careful tuning.

3. Fixed Window Counter Algorithm

The Fixed Window Counter algorithm divides time into fixed intervals and maintains a separate request counter for each interval. It allows requests up to a configured limit within each window. Once the limit is reached, additional requests are rejected until the next window begins.

How Does It Work?

• Time windows: Divide time into fixed intervals, such as 1 second or 1 minute.
• Request counting: Each incoming request increments the counter for the current window.
• Request allowance: If the counter is below the configured limit, the request is allowed.
• Request rejection: Once the limit is reached, additional requests are rejected until the counter resets at the start of the next window.

Suppose an API allows a maximum of 3 requests per second.

• At 1:00:00: The counter starts at zero. The first three requests are allowed.
• At 1:00:00.5: Two more requests arrive. Both are rejected because the limit has already been reached.
• At 1:00:01: A new time window begins, and the counter resets to zero. The next three requests can be allowed.

The Boundary Problem

One major limitation of this algorithm is that it can allow a sudden burst of requests around the boundary between two windows.

Suppose an API allows 5 requests per minute:

• From 2:00:00 to 2:00:59: Five requests are allowed.
• Just after 2:01:00: The counter resets, allowing another five requests.

A client could send five requests just before 2:01:00 and five more immediately after it. This means 10 requests could be allowed within a very short period, even though the configured limit is 5 requests per minute.

Advantages

• Easy to understand and implement.
• Memory-efficient because only a counter and window information need to be maintained.
• Works well when limits reset at fixed intervals, such as per-minute quotas.

Limitations

• Traffic bursts around window boundaries can allow more requests than intended over a short period.
• The counter resets suddenly at the beginning of each new window, rather than tracking requests across a rolling time period.

4. Sliding Window Log Algorithm

The Sliding Window Log algorithm addresses the boundary problem of the Fixed Window Counter algorithm by tracking the timestamps of individual requests. Instead of resetting a counter at fixed intervals, it considers requests within a rolling time window.

For example, if an API allows 2 requests per minute, the algorithm checks how many requests the client has made during the last 60 seconds before deciding whether to accept a new request.

How Does It Work?

• Store timestamps: Maintain a log of request timestamps, often using an in-memory data store such as Redis.
• Remove outdated timestamps: When a new request arrives, remove timestamps that fall outside the current time window.
• Record the request: Add the timestamp of the incoming request to the log.
• Check the limit: If the number of recorded requests is within the configured limit, accept the request. Otherwise, reject it.

Suppose an API allows a maximum of 2 requests per minute.

• At 1:00:01: The log is empty. The request timestamp is added, and the request is accepted. Log size: 1.
• At 1:00:30: The timestamp is added. There are now 2 requests within the window, so the request is accepted. Log size: 2.
• At 1:00:50: The timestamp is added, bringing the count to 3. Since this exceeds the limit, the request is rejected.
• At 1:01:40: The algorithm removes timestamps older than 1:00:40. The timestamps from 1:00:01 and 1:00:30 are removed, leaving the recent timestamp from 1:00:50. The new request is added and accepted because the count is now 2.

The key point is that the algorithm checks a rolling 60-second window, not a fixed clock-based minute.

Advantages

• Accurate rate limiting because every request is evaluated against a rolling time window.
• Avoids the boundary problem of the Fixed Window Counter algorithm.
• Provides precise control over how many requests are allowed during a given period.

Limitations

• Requires more memory because it stores individual request timestamps rather than just a counter.
• Processing each request involves removing expired timestamps and checking the log.
• Under high traffic, storing and managing large numbers of timestamps can become expensive.

When Is It Useful?

The Sliding Window Log algorithm is useful when precise rate limiting is important, such as protecting sensitive API endpoints or enforcing strict per-client request limits. However, its memory overhead can make it less suitable for systems handling very high request volumes.

5. Sliding Window Counter Algorithm

The Sliding Window Counter algorithm combines the simplicity of the Fixed Window Counter algorithm with the flexibility of a sliding time window. Instead of storing every request timestamp, it uses counters from the previous and current windows to estimate the number of requests in the rolling window.

This approach reduces memory usage while helping address the traffic spikes that can occur at fixed window boundaries.

How Does It Work?

• Count requests: Maintain separate counters for the previous and current fixed time windows.
• Calculate the overlap: Determine how much of the previous window falls within the current rolling window.
• Estimate the request count: Multiply the previous window's request count by its overlap percentage, then add the current window's count.
• Check the limit: Allow the incoming request if the estimated count remains within the configured limit. Otherwise, reject it.

Suppose an API allows a maximum of 7 requests per minute. At a particular moment:

• Previous minute: 5 requests.
• Current minute: 3 requests.
• Elapsed time in the current minute: 30 seconds.
• Remaining portion of the previous minute included in the rolling window: 50%.

The estimated request count is calculated as follows:

If the implementation rounds down, the estimated count is 5. Since this is below the limit of 7, the new request can be accepted.

Note: This is an estimate, not an exact count, because the algorithm does not know precisely when requests occurred within the previous window.

Advantages

• Memory-efficient: Stores window counters instead of individual request timestamps.
• Reduces boundary spikes: Considers traffic from the previous window rather than resetting the effective count abruptly.
• Practical for high traffic: Offers a useful balance between accuracy and resource usage.

Limitations

• Approximate results: Assumes requests in the previous window were distributed evenly over time, which may not reflect actual traffic.
• Potential inaccuracies: Some requests may be allowed or rejected incorrectly near the configured limit.
• Less suitable for strict limits: Systems requiring an exact count of requests in every rolling window may need a more precise algorithm.

When Is It Useful?

The Sliding Window Counter algorithm is useful for APIs that need efficient rate limiting without storing every request timestamp. It is a practical choice when lower memory usage and smoother traffic control are more important than maintaining an exact rolling-window count.

Conclusion

Each rate-limiting algorithm has its own trade-offs:

• Token Bucket: Allows short bursts while controlling the average request rate.
• Leaky Bucket: Processes requests at a steady rate to smooth traffic.
• Fixed Window Counter: Simple and memory-efficient, but can allow bursts around window boundaries.
• Sliding Window Log: Provides accurate rolling-window limits but requires more memory to store timestamps.
• Sliding Window Counter: Estimates rolling request counts with less memory, balancing efficiency and accuracy.

The right choice depends on your traffic patterns, accuracy requirements, memory constraints, and system architecture. Understanding these algorithms is the first step toward building reliable rate limiting.

In the next blog, we'll move from algorithms to a high-level system design, exploring how to build a scalable rate-limiting service, where to enforce limits, how to manage distributed counters, and how components such as Redis and API gateways fit into the architecture.