Fixed Window Rate Limiting: Boundary Burst Math & Fixes

Fixed window rate limiting is a simple algorithm that counts requests in a fixed time period (like one per second) and rejects requests beyond the limit. Its core weakness is the “boundary burst” problem: because the counter resets at each window boundary, a client can send up to twice the allowed rate by splitting requests across two adjacent windows. This article explains the math behind that burst, why it matters, and the practical fixes—sliding windows, token buckets, and hybrid approaches—with concrete examples.

Formula

The fixed window algorithm itself is simple: for each window of length W seconds, allow at most R requests. The boundary burst maximum is 2R requests over any two consecutive windows (assuming the client times requests perfectly). The formulas used in the calculator above are:

• Max requests in two windows: M = 2 × R
• Burst ratio: B = actual / M (1.0 means the client used the full boundary burst; >1 means they exceeded even that)
• Excess over two-window capacity: E = actual − M (negative means no excess)

Variables: R = allowed requests per window (req), W = window length (seconds), actual = requests sent across two adjacent windows (req). The calculator shows the theoretical maximum burst and how a given request pattern compares.

Worked Example

Using the defaults: R = 10 requests per 60-second window, and the client sends 18 requests across two windows.

1. Max two-window capacity: M = 2 × 10 = 20 requests.
2. Burst ratio: B = 18 / 20 = 0.9 — the client used 90% of the theoretical maximum burst.
3. Excess: E = 18 − 20 = −2 — no excess; the client stayed within the 2-window limit.

The calculator returns 20 as the max burst, 0.9 as the ratio, and −2 as excess (shown as a negative, meaning no violation). If the client sent 25 requests, the ratio would be 1.25 and excess 5, showing they beat even the boundary burst.

Why the Boundary Burst Happens

The fixed window algorithm divides time into non-overlapping intervals, e.g., 00:00–00:59, 01:00–01:59. Each interval has its own counter. A client can send R requests in the last millisecond of window 1 and another R in the first millisecond of window 2. From the server’s perspective, each window is within its limit, but the client effectively sent 2R requests in a span of a few milliseconds. This is not a bug in the math—it’s a direct consequence of the reset boundary. The longer the window, the more damaging the burst can be relative to the average rate.

Real-World Impact and Examples

Consider an API that allows 100 requests per hour. A client can send 100 requests at 10:59:59.999 and another 100 at 11:00:00.001—200 requests in 2 milliseconds. For a database-backed endpoint, this can cause a spike that triggers alerts or even outages. Another example: a login endpoint with 5 attempts per minute. An attacker can try 5 attempts at the end of one minute and 5 at the start of the next, effectively doubling the brute-force rate. The burst is especially problematic for rate limits that protect expensive operations (search, payments, file uploads) because the cost is concentrated in a tiny time slice.

Better Fixes: Sliding Window, Token Bucket, and Hybrids

Several algorithms solve the boundary burst. The most common are:

• Sliding window log: Store timestamps of each request. On a new request, remove timestamps older than W seconds, then count remaining. This gives exact sliding-window semantics but uses memory proportional to request rate.
• Sliding window counter (hybrid): Keep the current and previous window counts. For a new request, compute a weighted estimate: count = previous_window_count × (elapsed_time / W) + current_window_count. If that estimate is below the limit, allow. This is memory-efficient and approximates the sliding log well.
• Token bucket: Maintain a bucket that fills at a steady rate (e.g., 10 tokens per second) up to a maximum capacity (burst size). Each request removes one token. This allows natural bursts up to the bucket size but enforces a long-term average. It’s the most flexible and is used by many API gateways.
• Leaky bucket: Requests enter a queue and are processed at a fixed rate. This smooths bursts but adds latency and can drop requests if the queue is full.

The sliding window counter is often the best trade-off: it eliminates the boundary burst with O(1) memory per key and is easy to implement in Redis or a database.

How to Choose the Right Algorithm

Choosing depends on your constraints:

• Memory vs. accuracy: Sliding window log is most accurate but memory-heavy. Sliding counter uses almost no memory but is approximate. Token bucket uses a single counter per key.
• Burst tolerance: If you want to allow short bursts (e.g., a user refreshing a dashboard), token bucket with a burst capacity of 2–3× the average is ideal. If you want strict smoothing, leaky bucket.
• Distributed systems: In a multi-server setup, you need a shared store (Redis, database). Sliding counter and token bucket are easy to implement atomically with Lua or transactions.
• Ease of explanation: Fixed window is easiest to document, but the burst is a known issue. Sliding counter is nearly as simple and much safer.

Common Misconceptions

One common belief is that increasing the window length (e.g., from 1 minute to 1 hour) reduces the burst. It doesn’t—the burst is always 2R regardless of W. A longer window only spreads the average, but the boundary still allows a doubled rate for an instant. Another misconception is that the token bucket is the same as a sliding window. They are similar in spirit but differ: token bucket allows bursts up to bucket size at any time, while sliding window limits the count in any rolling period. For example, a token bucket with capacity 10 and rate 1/sec allows 10 requests at t=0, then 1/sec. A sliding window of 10/sec allows 10 requests at t=0, but then the next request must wait until the first one ages out—so at t=0.1 you can’t send another (the window count is still 10). Token bucket would allow another at t=1.0 (when a token refills).

Costs and Trade-offs

Fixed window is the cheapest: O(1) memory and O(1) time per request. Sliding window log is the most expensive: O(n) memory per key (n = requests in window) and O(log n) time to remove old timestamps. Sliding counter is O(1) memory and time, but the estimate can be off by up to one request in edge cases (when the previous window is full and the current is nearly empty). Token bucket is O(1) but requires a timer or a lazy refill calculation. In practice, the sliding counter is so close to exact that most systems use it. The cost of not fixing the burst can be higher than the implementation cost: a single attacker can double the load on your backend, potentially causing downtime or increased cloud bills.

Frequently Asked Questions

Does the boundary burst happen with sliding window rate limiting?

No. Sliding window algorithms (log or counter) measure the request count over a rolling period, so there is no reset boundary. A client cannot double the rate by timing requests across a boundary because the window moves continuously.

Can I just use a longer fixed window to avoid the burst?

No. The burst is always 2× the per-window limit, regardless of window length. A longer window makes the burst less frequent but just as severe when it happens. The only fix is to change the algorithm.

Is the token bucket the same as a sliding window?

Not exactly. Token bucket allows bursts up to the bucket capacity at any time, even if the last burst was recent. Sliding window enforces a strict count over any rolling period. Token bucket is more forgiving for spiky traffic, while sliding window is stricter.

How do I implement sliding window counter in Redis?

Store two keys: the current window count and the previous window count, each with an expiry. On each request, compute the weighted estimate: prev × (elapsed / W) + current. If the estimate is below the limit, increment the current count. Use a Lua script to make it atomic. This is a common pattern in API gateways.

What happens if my rate limit is per user, not per IP?

The same algorithms apply—you just key the counter by user ID instead of IP. The boundary burst problem is identical, and the fixes work the same way. The only extra consideration is that user-based limits often need a distributed store because users may hit different servers.

Is the boundary burst a security vulnerability?

It can be. For login endpoints, it doubles the number of password guesses per minute. For payment APIs, it can double the rate of charges. It’s not a vulnerability in the code, but it weakens the rate limit’s protective intent. Most security standards recommend using a sliding window or token bucket for authentication endpoints.

Related

• Lenovo Yoga 6 India Launch: Price, Specs, Availability
• Modern Warfare 4 Operator Skins: Full Guide
• Hostinger Renewal Periods & Advance Payments

in rate | Requests allowed per window | req | 10 | 1 | 10000
in window | Window length (seconds) | s | 60 | 1 | 86400
in burst | Actual requests sent in one boundary pair | req | 18 | 0 | 20000
out max_burst | Max requests in two windows (2x rate) | req | rate * 2 | 0
out burst_ratio | Burst vs. allowed (x) | x | burst / (rate * 2) | 2
out excess | Requests over 2-window capacity | req | burst - rate * 2 | 0