Fixed Window Counter: The Boundary Burst Problem

Your learning outcome for this lesson:

By the end of this lesson, you will be able to describe the fixed window counter algorithm and its major flaw, the boundary burst problem.

1. The Fixed Window Counter Algorithm

The Fixed Window Counter is the most straightforward rate-limiting algorithm. The core idea is to divide time into fixed intervals (or "windows") and maintain a counter for each client within that window.

The algorithm operates with two main parameters:

• Window Size: The duration of the time interval (e.g., 60 seconds).
• Limit: The maximum number of requests allowed within that window (e.g., 100 requests).

Here's how it works:

1. When a request arrives, the algorithm identifies the current time window. For a 60-second window, this could be the start of the current minute (e.g., 10:30:00, 10:31:00, etc.).
2. It retrieves the counter for the requesting client for this specific window.
3. If the counter is below the limit, the request is allowed, and the counter is incremented.
4. If the counter has reached the limit, the request is rejected.
5. At the beginning of a new time window, the counter for every client is reset to zero.

Let's watch a short video that explains this mechanism.

To reinforce this, let's look at a textual explanation with a diagram.

The primary advantages of this algorithm are its simplicity and low memory footprint. You only need to store one counter per user for the current window.

2. The Critical Flaw: The Boundary Burst Problem

While simple, the Fixed Window Counter algorithm has a significant weakness that can undermine its effectiveness. This flaw is known as the boundary burst problem.

Because the counter abruptly resets at the start of a new window, a client can send a high volume of traffic concentrated around the boundary between two windows.

Consider a rate limit of 100 requests per minute.

• A user could send 100 requests at 10:30:59. These are all allowed because they are within the 10:30:00 - 10:31:00 window.
• The window boundary passes, and at 10:31:01, the counter resets. The user immediately sends another 100 requests. These are also allowed because they fall into the new window.

The result? The user successfully sent 200 requests in just a few seconds, effectively doubling the intended rate limit. This can lead to the very same server overload issues we are trying to prevent.

Let's see this problem visualized.

This issue is also clearly explained in the ByteByteGo article you read earlier (in the same section, under Figure 9). Here is another diagram that illustrates the concept well.

This problem makes the Fixed Window Counter unsuitable for services that require strict, consistent rate enforcement. However, its simplicity makes it a good starting point and a useful baseline for comparison. For your project, you'll implement this algorithm as an in-memory version to demonstrate this baseline before moving on to more robust solutions.

3. Sketching the Implementation Data Structure

Given your background in computer science and data structures, let's briefly consider how you might implement this. We won't write the code today (that's for the next module), but we can design the data structure.

For an in-memory, thread-safe implementation, a java.util.concurrent.ConcurrentHashMap is an excellent choice.

• Key: A String representing the client identifier (e.g., an IP address).
• Value: An object that holds the count and the window timestamp. In Java, you could use AtomicInteger for the count to handle concurrent requests safely.

However, a simple AtomicInteger is not enough, as you also need to know which window that count belongs to. A simple approach would be:

Map<String, Pair<Long, AtomicInteger>>

Where the Pair contains:

• Long: The start timestamp of the current window (e.g., System.currentTimeMillis() / 60000 * 60000).
• AtomicInteger: The request count for that window.

When a request comes in for a given client:

1. Calculate the current window's start timestamp.
2. Retrieve the Pair for that client from the map.
3. If no entry exists or if the entry's timestamp is from a previous window, create a new entry with the current window's timestamp and a count of 1.
4. If the entry's timestamp matches the current window, atomically increment the counter.
5. Finally, check if the new count exceeds the limit.

This is just a high-level sketch. The actual implementation in the next module will refine this logic within our Spring Boot interceptor.

Key Takeaways

• Fixed Window Counter is a simple rate-limiting algorithm that divides time into fixed intervals and counts requests per client within each interval.
• Its main components are a window size and a request limit.
• The primary advantage is its simplicity and memory efficiency.
• Its critical weakness is the boundary burst problem, where traffic concentrated at the edges of two consecutive windows can lead to the system allowing up to double the configured rate limit.
• This flaw makes it unsuitable for systems needing strict enforcement but provides a valuable starting point for understanding more advanced algorithms.

Next Steps

The boundary burst problem clearly shows we need a more accurate algorithm. How can we avoid the hard reset at the window's edge?

In the next lesson, we will explore the Sliding Window Counter algorithm. This algorithm is a direct evolution of the Fixed Window approach and is specifically designed to solve the boundary burst problem by smoothing out the counting process across window boundaries.