💻 computer science

A Comparative Survey of API Rate-Limiting Algorithms: Token Bucket, Leaky Bucket, and Sliding Window

This paper surveys and experimentally compares five widely used API rate-limiting algorithms—token bucket, leaky bucket, fixed window, sliding window log, and sliding window counter—to evaluate their trade-offs in burst tolerance and precision, ultimately providing guidance for selecting the most appropriate algorithm based on specific traffic characteristics and system constraints.

Original authors: Umair Saleem

Published 2026-09-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Umair Saleem

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Modern digital services rely on a delicate balance between availability and protection. When millions of people try to access a website or an application at once, the servers behind the scenes can become overwhelmed, much like a single-lane bridge clogged by a sudden surge of traffic. To prevent this collapse, engineers use a mechanism called rate limiting, which acts as a gatekeeper. This gatekeeper counts how many requests a specific user or device sends within a certain period and blocks any that exceed a safe threshold. The goal is not to punish users, but to ensure that the system remains stable for everyone, preventing a few heavy users from consuming all the available resources. However, not all traffic arrives in a steady stream; sometimes it comes in sudden, sharp bursts, such as when a popular news story breaks or a system retries a failed connection. The challenge for engineers is deciding how to handle these bursts: should the system allow a temporary spike to pass through, or should it strictly enforce a flat limit regardless of the situation?

A recent study by Umair Saleem investigates the different mathematical rules used to build these digital gatekeepers. The research focuses on five specific methods that are commonly used in the industry: the token bucket, the leaky bucket, the fixed window counter, the sliding window log, and the sliding window counter. Each of these methods has a different way of tracking time and counting requests, leading to different behaviors when a surge of traffic hits. To understand which method works best, the author did not rely on theory alone but built a computer simulation to test them all under identical conditions. The simulation created a realistic stream of over one thousand requests over a period of one hundred seconds. This stream included a steady background flow of eight requests per second, interrupted by two distinct bursts of activity: a five-second period where traffic jumped to forty requests per second, followed by a sharper, two-second spike reaching sixty requests per second. By running this exact same traffic pattern through each of the five algorithms, the study could measure exactly how many requests each method accepted, how many it rejected, and how the system behaved during the spikes.

The results revealed a clear split in how these algorithms handle the pressure of a traffic surge. The token bucket and the leaky bucket performed in a nearly identical manner when used simply to decide whether to accept or reject a request. Both methods allowed the system to absorb the bursts more effectively than the others, accepting a total of 844 requests out of the 1,057 sent, which translates to an acceptance rate of roughly 80 percent. During the first major burst, these two methods allowed 69 requests through, and during the second, sharper burst, they allowed 38 requests through. This happened because these algorithms are designed with a built-in capacity to store "spare" permission for future use, allowing them to smooth out the spikes without immediately turning users away. In contrast, the sliding window log was the most rigid of all the methods. It never allowed more than ten requests to pass in any single second, strictly adhering to the configured limit. While this provided the most precise protection against overload, it came at a high cost: it rejected the most traffic overall, accepting only 67.9 percent of the requests. It was the only method that guaranteed the system would never see a spike above the limit, but it did so by turning away legitimate users more frequently than the other methods.

The remaining three methods fell somewhere in the middle, showing predictable flaws based on how they measured time. The fixed window counter, which resets its count at the start of every new second, suffered from a timing error at the boundaries. Because it could reset its counter just as a burst of traffic arrived, it allowed a temporary spike of up to fifteen requests in a single second, which was higher than the intended limit. The sliding window counter tried to fix this by looking at the previous second as well, but it only partially corrected the issue, peaking at thirteen requests. The study found that the choice of algorithm depends entirely on what the system needs to protect. If the goal is to keep users happy and allow for natural bursts of activity, such as a page reloading with multiple data calls, the token bucket is the superior choice because it balances high acceptance with steady performance. If the goal is to protect a fragile downstream system that cannot tolerate any spike whatsoever, the sliding window log is the better option, despite its lower acceptance rate. The research concludes that there is no single perfect tool for every job; instead, engineers must choose the method that aligns with their specific tolerance for traffic spikes and their available memory resources.

Technical Summary: A Comparative Survey of API Rate-Limiting Algorithms

Problem Definition

Modern backend systems expose APIs to unpredictable client populations, where uncontrolled traffic from a single client or a small group can consume disproportionate resources, leading to service degradation or cascading failures. Rate limiting serves as a foundational mechanism to mitigate this by restricting the number of requests a client can issue within a specific time interval.

The core challenge lies in selecting an algorithm that balances conflicting constraints:

Decision Latency: The algorithm must compute acceptance/rejection in constant or near-constant time.
Memory Footprint: State tracking per client must be bounded.
Distributed Consistency: The mechanism must function correctly when replicated across multiple servers, often requiring shared data stores or eventually consistent approximations.
Burst Tolerance vs. Precision: Different use cases (e.g., protecting fragile downstream dependencies vs. enforcing pricing tiers) require varying levels of tolerance for traffic spikes and memory overhead.

No single algorithm is optimal for all scenarios, necessitating a comparative analysis of the trade-offs between burst handling, memory cost, timing precision, and implementation complexity.

Methodology

The paper conducts a comparative survey of five widely used rate-limiting techniques:

Token Bucket: Models a container refilled at a constant rate, permitting bursts up to capacity.
Leaky Bucket: Increments a counter on request and decrements at a constant rate, smoothing output or discarding excess.
Fixed Window Counter: Divides time into discrete intervals with a simple counter, resetting at boundaries.
Sliding Window Log: Stores timestamps for every request within the trailing window for exact counting.
Sliding Window Counter: A compromise using weighted estimates from current and previous windows to approximate log accuracy with constant memory.

Experimental Evaluation:
To move beyond qualitative theory, the author implemented all five algorithms in Python and evaluated them against an identical synthetic traffic trace.

Configuration: All algorithms were set to a sustained rate limit of 10 requests/second. Token and Leaky buckets included a burst capacity of 20. Window-based algorithms used a 1-second window.
Traffic Trace: A 100-second trace generated by a Poisson process (8 req/s baseline) featuring two artificial burst events:
- Burst 1: 5 seconds at 40 req/s (194 requests).
- Burst 2: 2 seconds at 60 req/s (125 requests).
Metrics: The study measured acceptance rates, peak instantaneous throughput, and specific burst handling behavior.

Key Contributions and Results

1. Equivalence of Token and Leaky Buckets as Admission Meters

The experimental results demonstrated that the Token Bucket and Leaky Bucket produced identical accept/reject decisions for every request in the trace.

Finding: When used purely as admission meters with matching capacity and rate, the two algorithms are mathematically equivalent. The leaky bucket's "level" and the token bucket's "unused capacity" are complementary quantities.
Distinction: They diverge only when the leaky bucket is used in its queuing form to smooth output timing, a behavior not captured in the accept/reject model used here.
Performance: Both algorithms accepted the highest volume of traffic during bursts (79.8% acceptance rate) and reached a peak instantaneous throughput of 29 req/s, directly leveraging the configured burst allowance.

2. The Precision of the Sliding Window Log

The Sliding Window Log was identified as the only algorithm with zero tolerance for exceeding the configured limit.

Finding: It never accepted more than 10 requests in any 1-second window, strictly adhering to the design guarantee.
Trade-off: This strictness came at the cost of the lowest overall acceptance rate (67.9%) and the highest memory overhead ( $O(n)$ per client), as it must store a timestamp for every request.

3. Performance of Window-Based Counters

The Fixed Window and Sliding Window Counter algorithms fell predictably between the extremes of the bucket algorithms and the sliding window log.

Fixed Window: Showed the largest boundary-burst artifact, allowing up to twice the intended rate at window edges (peak 15 req/s). It offered the lowest implementation complexity and memory cost but the lowest accuracy (73.3% acceptance).
Sliding Window Counter: Provided a middle ground, approximating log accuracy with constant memory ( $O(1)$ ). It achieved a 71.1% acceptance rate with a peak of 13 req/s, partially correcting the boundary effects seen in the fixed window.

Significance and Guidance

The paper concludes that the "best" algorithm is not universal but depends entirely on the specific system constraints and traffic patterns:

For Burst Absorption: The Token Bucket is recommended for general-purpose API rate limiting. It offers the best balance of burst tolerance and simplicity, sustaining the highest acceptance rate while enforcing long-run averages. It is the de facto standard in production libraries (e.g., Bucket4j).
For Strict Downstream Protection: If the goal is a hard, unconditional ceiling on instantaneous load to protect fragile dependencies, the Sliding Window Log is superior, as it guarantees no spikes above the limit, despite higher memory costs.
For Constant Output Rates: Systems requiring a strictly non-bursty request rate for downstream consumers should utilize the Leaky Bucket in its queuing form.
For Resource-Constrained Environments: The Sliding Window Counter serves as a reasonable compromise when exact enforcement is desired but the memory cost of a full log is prohibitive.

The author emphasizes that selection should be driven by measured traffic characteristics (e.g., frequency of bursts), latency budgets, and consistency requirements, rather than relying on a single default algorithm. The study validates that while theoretical trade-offs exist, empirical testing confirms distinct behavioral differences in how these algorithms handle real-world burst scenarios.