Rate Limiting Algorithms: Token Bucket vs Sliding Window Explained

Rate limiting is a crucial mechanism employed by public APIs to regulate the number of requests a client can make within a specific timeframe. Without it, a single misbehaving client, retry loop, or scraper can consume excessive capacity, hindering the service for all other users. The two primary algorithms used in rate limiting are token bucket and sliding window, each with distinct trade-offs.

Token bucket operates by maintaining a fixed number of tokens, replenished at a steady rate. Each incoming request consumes one token. If a token is available, the request proceeds, and the token count decreases by one. If the bucket is empty, the request is rejected or delayed until the next token arrives. The token bucket's key characteristic is its ability to accommodate unused tokens up to its capacity, allowing idle clients to send a burst of requests immediately and then adhere to the steady refill rate.

This behavior aligns with real-world traffic patterns, such as a dashboard loading multiple resources simultaneously upon page load and then becoming dormant. However, token bucket is a smoothing model rather than a precise historical count, focusing on the availability of capacity rather than the exact number of requests within a given period.

In contrast, the sliding window algorithm tackles the issue of fixed windows by employing a rolling period approach. Instead of measuring the number of requests since a specific minute, it focuses on the requests occurring within the trailing 60 seconds, commencing from the present moment. There are two common implementations of sliding window: a true sliding log, which maintains timestamps for each request and counts those falling within the trailing window, offering accuracy but potentially consuming significant memory under high request volumes.

The more common approach is a sliding window counter, which maintains two fixed window counters (the current one and the previous one) and computes a weighted count based on the request's position within the current window. This weighted method approximates the true sliding log with minimal storage overhead, making it a popular choice in production systems, including Redis-based rate limiters.

Sliding window excels in precision and fairness across boundaries, providing an answer that aligns with the common understanding of "100 requests per minute." However, it lacks the burst tolerance offered by token bucket, as it does not naturally credit clients that have been well under their limit for an extended period when a burst arrives.

In practice, token bucket is well-suited for scenarios where short bursts are normal and desirable, such as API gateways protecting infrastructure, client SDKs pacing outbound calls, or instances where traffic smoothing is the primary goal. Sliding window, on the other hand, is more appropriate when the limit is contractual or billing-relevant, such as per-plan API quotas that need to be enforceable and transparent to customers who inquire about 429 responses.

Ultimately, neither algorithm is inherently superior; rather, the choice depends on the specific problem being addressed. Depending on the scenario, an API gateway or edge service might employ token bucket to safeguard backend capacity, while an internal caching layer within the same company may opt for sliding window to enforce per-user or per-API-key limits.

The response provided by the rate limiting mechanism is equally important as the chosen algorithm, with a 429 status code accompanied by a Retry-After header or the increasingly standard RateLimit response being commonly employed.