Fixed-Window Rate Limiting: Implementation & Pitfalls

Hello! Welcome back.

In our last lesson, we implemented the token bucket algorithm, a sophisticated method for rate limiting that gracefully handles traffic bursts while enforcing a sustained average rate. We saw how its flexibility makes it a popular choice for production systems.

Today, we shift our focus to a different, much simpler algorithm. While token bucket is powerful, its implementation can be more complex. Sometimes, a simpler approach is sufficient, but it comes with its own set of trade-offs.

The learning outcome for this lesson is to implement a fixed-window counter rate limiter, explaining its memory efficiency and boundary condition issues. We will explore its core mechanics, implement it using Python and Redis, and critically analyze its primary weakness.

---

1. The Fixed-Window Counter Algorithm

The fixed-window counter is one of the most straightforward rate limiting algorithms. The core idea is to divide time into fixed intervals, or "windows," and maintain a counter for each client within each window.

For a clear explanation of this concept and its place in a system design context, please watch the following segment from an interview breakdown by a former Meta staff engineer.

To see this in action, the next video provides a great animation that visualizes how requests are handled and what happens at the window boundaries.

As both videos highlight, the algorithm's main appeal is its simplicity. But its primary flaw, the boundary burst issue, is significant and is something we need to analyze carefully.

---

2. Implementation with Python and Redis

For a distributed system like the ones you build at AWS, state must be managed centrally. An in-memory counter on a single application instance won't work, as it doesn't provide a global view of a client's requests. Redis is an excellent tool for this, providing fast, centralized, and atomic operations.

Let's walk through how to implement a fixed-window counter using Redis. The core of the logic relies on two Redis commands:

• INCR: Atomically increments a counter. If the key doesn't exist, it's created and set to 1. This atomicity is crucial for handling concurrent requests without race conditions.
• EXPIRE: Sets a time-to-live on a key. This is perfect for ensuring our counters for old windows are automatically cleaned up, which is key to the algorithm's memory efficiency.

The following article provides a fantastic walkthrough of this logic. While the code is in TypeScript, the principles are identical.

Your Turn: Python Implementation

Now, let's translate that logic into Python. The article below provides a clean Python implementation that mirrors the logic from the Redis guide.

Based on this example, try to write your own is_allowed_fixed_window function.

Requirements:

1. The function should accept client_id, max_requests, and window_seconds.
2. It should connect to a local Redis instance.
3. Implement the logic to create a window-specific key. For example: f"rate_limit:{client_id}:{current_window}".
4. Use redis-py's incr and expire methods to manage the count.
5. Return True if the count is within the limit, and False otherwise.

This exercise will solidify your understanding of how to apply the algorithm in a distributed-friendly way.

---

3. Analyzing the Trade-offs

Your preference for analyzing trade-offs is crucial for a senior engineer. Let's break down the pros and cons of the fixed-window algorithm, which are central to its learning outcome.

Memory Efficiency (Pro)

The fixed-window counter is extremely memory-efficient. For each client making requests, you only need to store one key in Redis per active time window.

For example, with a limit of 1000 requests per hour per user:

• A user makes a request at 10:15 AM. A key like ratelimit:user123:10 is created with a value of 1 and an expiry of one hour.
• Subsequent requests before 11:00 AM just increment this single key.
• At 11:05 AM, a new key ratelimit:user123:11 is created.
• The old key ratelimit:user123:10 automatically expires around 11:15 AM.

This is highly efficient compared to algorithms that need to store a timestamp for every single request.

Boundary Condition Issues (Con)

The major drawback is the potential for a "burst attack" at the window boundary.

Let's use a concrete example:

• Rule: 100 requests per minute.
• Window 1: 12:00:00 to 12:00:59.
• Window 2: 12:01:00 to 12:01:59.

A client can make 100 requests at 12:00:59 (all allowed) and another 100 requests at 12:01:00 (all allowed). The result is 200 requests in about one second, which can easily overwhelm a downstream service. This happens because the counter abruptly resets to zero at the boundary, with no memory of the recent past.

This lack of precision makes the fixed-window algorithm unsuitable for services that require strict control over request rates.

---

4. Algorithm Comparison

So, how does the fixed-window counter stack up against the token bucket we learned previously, and other alternatives?

The comparison table from the Redis article provides a perfect summary.

This table is a valuable reference. The choice between these algorithms depends entirely on the specific requirements of your service:

• Need something simple and "good enough" for low-stakes use cases like login attempt throttling? A fixed-window counter is often fine.
• Need to protect a critical, high-throughput service and ensure a smooth traffic pattern? A token bucket is a much safer and more robust choice.

---

Conclusion

In this lesson, we explored the fixed-window counter algorithm, the simplest form of rate limiting. We learned its mechanics, implemented it with Python and Redis, and, most importantly, analyzed its strengths and weaknesses.

Key Takeaways:

• Fixed-Window Counter: Divides time into fixed intervals and uses a simple counter for each client within that interval.
• Memory Efficiency: It's highly memory-efficient, requiring only one key per client per active window in a system like Redis. The EXPIRE command makes cleanup automatic.
• Atomicity: Using INCR in Redis is essential for a correct, race-condition-free implementation in a distributed environment.
• Boundary Issue: Its primary weakness is allowing clients to send a burst of traffic (up to 2x the limit) by straddling the boundary between two windows. This makes it imprecise and potentially unsafe for sensitive systems.

Next Lesson Preview

The boundary issue of the fixed-window counter is a significant problem. In our next lesson, we will directly address it by exploring a more accurate, but more memory-intensive, alternative. You will implement a sliding-window log rate limiter, detailing how it improves accuracy over the fixed-window approach. This will continue our journey through the trade-offs of rate-limiting design.