Token Bucket vs. Sliding Window: Rate Limiting Algorithms in Detail

1. Why the concrete algorithm actually makes a difference

At first glance, all rate limiting algorithms solve the same problem: preventing a client from sending more than a fixed number of requests in a given period. On closer inspection, though, the algorithms differ substantially in how they handle load spikes at window boundaries, how much memory they need per client, and how precisely they actually enforce the theoretical limit. A naively implemented algorithm can, in practice, let through twice as many requests as the configured limit suggests.

For a Symfony team implementing rate limiting through the built-in RateLimiter component or a custom Redis-based solution, it therefore pays to take a close look at the underlying strategy, instead of blindly relying on a library's default configuration. The following sections place the four most common algorithms into concrete context and show where the practical pitfalls lie in each case.

2. Fixed window: simple, but with a burst problem at window boundaries

Fixed window is the simplest algorithm: for a fixed time window, say every full minute, a counter is kept that rejects further requests once the limit is exceeded and resets to zero on window change. The implementation is trivial and memory-efficient, since only a single counter per client and window is needed, without storing individual request timestamps.

The structural problem shows up at the window boundary: a client can exhaust the full limit right before a window ends and again the full limit right after the window begins, effectively allowing double the configured limit within a very short period around the boundary. For systems meant to protect against real load spikes, that is a dangerous gap that is often overlooked in naive fixed-window implementations.

<?php
// Fixed-window rate limiting with Redis (simplified)
final class FixedWindowRateLimiter
{
    public function __construct(private readonly \Redis $redis) {}

    public function isAllowed(string $clientId, int $limit, int $windowSeconds): bool
    {
        $windowKey = sprintf('rl:%s:%d', $clientId, intdiv(time(), $windowSeconds));
        $count = $this->redis->incr($windowKey);

        if ($count === 1) {
            $this->redis->expire($windowKey, $windowSeconds);
        }

        return $count <= $limit;
    }
}

3. Sliding window: mitigating the window boundary problem

Sliding window counter combines two neighboring fixed-window counters, weighted by the elapsed time within the current window, to achieve a smoother approximation of a true sliding window without the full memory overhead of a sliding log. The formula weights the previous window's counter by the fraction that still falls within the current sliding window, plus the full counter of the current window.

This approximation significantly reduces the burst problem at window boundaries, without being perfect: in rare edge cases, the weighting can still produce slightly different results compared to an exact sliding window. For the vast majority of practical API rate limiting use cases, though, this approximation is accurate enough, at noticeably lower memory cost than a full sliding log.

4. Sliding log: exact precision at the cost of memory usage

Sliding log stores the timestamp of every single request from a client and, on each new request, counts how many timestamps fall within the sliding time window, continuously removing older timestamps outside the window. This approach delivers absolutely exact results with no approximation at all, since no rounding or weighting error occurs.

The price of this precision is memory usage that grows linearly with the number of requests allowed per window, instead of a single constant counter. At very high limits (thousands of requests per minute per client), this memory overhead becomes noticeable in Redis, which is why sliding log is usually only used at low to moderate limits or for use cases with especially high precision requirements.

<?php
// Sliding-log rate limiting with Redis sorted sets
final class SlidingLogRateLimiter
{
    public function __construct(private readonly \Redis $redis) {}

    public function isAllowed(string $clientId, int $limit, int $windowSeconds): bool
    {
        $key = "rl:log:{$clientId}";
        $now = microtime(true);
        $windowStart = $now - $windowSeconds;

        // Remove old entries outside the window
        $this->redis->zRemRangeByScore($key, '-inf', (string) $windowStart);

        $count = $this->redis->zCard($key);
        if ($count >= $limit) {
            return false;
        }

        $this->redis->zAdd($key, $now, (string) $now);
        $this->redis->expire($key, $windowSeconds);
        return true;
    }
}

5. Token bucket: controlled bursts instead of rigid windows

Token bucket works conceptually differently from window-based algorithms: a bucket with fixed capacity is continuously refilled with tokens at a fixed rate, every request consumes one token, and a request is only rejected when the bucket is empty. This allows controlled bursts up to the bucket capacity, followed by steady usage bounded by the refill rate, instead of a rigid ceiling per fixed time window.

This behavior fits real user behavior better, where short bursts of requests (for example when loading a page with several parallel API calls) are normal and legitimate, but a permanently high request rate should still be prevented. Token bucket is therefore the default algorithm in many production-grade API gateways and is also supported as a strategy by Symfony's built-in RateLimiter component.

6. Rate limiting across multiple server instances

In-memory rate limiting only works as long as all of a client's requests reach the same server instance, which is practically never guaranteed for a horizontally scaled Symfony application behind a load balancer. A central data store like Redis is therefore practically indispensable for distributed rate limiting, since all instances need to check against the same, shared counter state.

This centralization brings its own challenges: race conditions from concurrent access by multiple instances must be prevented through atomic Redis operations (INCR, Lua scripts), and the latency of the central store becomes the limiting factor for the speed of the rate limit check itself, which can become relevant at very high request volume.

7. How the algorithm choice concretely affects the user experience

An overly rigid algorithm like a naive fixed window frustrates legitimate users who briefly need more requests (for example when initially loading a dashboard with several API calls), but otherwise stay well below the average limit. Token bucket with sufficient bucket capacity allows exactly this kind of legitimate burst, without lowering the baseline protection level against sustained abuse.

Conversely, an overly generous token bucket configuration can no longer prevent real abuse from short, very high-frequency request bursts. Finding the right balance between bucket capacity and refill rate therefore requires observing real usage behavior instead of choosing values arbitrarily, ideally with monitoring that makes the actual distribution of request bursts visible.

8. Communicating rate limit status transparently through HTTP headers

Regardless of the chosen algorithm, an API client should learn how many requests remain and when the limit resets through standard headers like X-RateLimit-Limit, X-RateLimit-Remaining, and X-RateLimit-Reset, instead of only discovering the limit through sudden 429 errors. This transparency lets well-implemented clients proactively throttle their own request rate instead of repeatedly hitting the limit.

With token bucket, X-RateLimit-Remaining directly reflects the current bucket fill level; with window-based algorithms, it is the difference between the limit and the current counter state within the window. Computing these values consistently and correctly is part of a well-designed rate limiting implementation, not just an optional detail for especially careful APIs.

9. The four algorithms compared side by side

The table below summarizes the key properties of the four algorithms to make the choice easier for your own use case.

10. Summary

11. FAQ: Rate Limiting Algorithms: The Essentials at a Glance