Sliding-Window Counter Rate Limiter

Hello! Let's continue our deep dive into rate-limiting algorithms.

In our last lesson, we implemented the sliding-window log. We saw that it provides perfect accuracy by tracking every single request timestamp, but this precision comes at a high memory cost, making it potentially unsuitable for high-throughput services like the ones you build and maintain.

This lesson introduces a crucial compromise. We'll explore a hybrid approach that aims to strike a balance between the memory efficiency of a fixed window and the accuracy of a sliding log. Our learning outcome is to implement a sliding-window counter rate limiter as a memory-optimized alternative to the sliding-window log.

We will break down how this algorithm approximates a true sliding window using minimal state, implement it in Python with Redis, and connect the logic back to your expertise in Rust.

---

1. The Core Idea: An Educated Guess

The sliding-window counter algorithm is clever because it avoids storing every request timestamp. Instead, it approximates the count in a rolling window by only keeping track of two numbers: the count in the previous time window and the count in the current time window.

It then calculates an estimated count based on how far we've progressed into the current window.

The formula is:

$$\text{estimated\_count}=(\text{previous\_count}\times (1-\text{progress}))+\text{current\_count}$$

Where progress is a float from 0.0 to 1.0 representing the percentage of the current window that has elapsed.

As the current window progresses (progress goes from 0 to 1), the weight of the previous_count diminishes, and the current_count contributes more. This provides a smoother transition than the hard reset of a fixed-window counter.

For a verbal walkthrough with a concrete numerical example, the following video explains this exact concept.

The key takeaway is the memory efficiency. Instead of storing N timestamps per user (O(N) memory), this algorithm only requires storing two integer counters per user (O(1) memory), making it vastly more scalable.

---

2. Implementation with Python and Redis

Now, let's translate this concept into a practical implementation. We'll use Redis to store the two counters for each client.

The following article provides a clean Python class that implements this logic. We will analyze its structure and Redis usage.

Let's break down the Redis commands used here:

• pipe.get(key): Fetches the counts for the current and previous windows.
• pipe.incr(key): If the request is allowed, it increments the counter for the current window.
• pipe.expire(key, ...): It sets an expiration on the key. The expiration is set to 2 * window_seconds to ensure the key for the current window is still available for the next window's "previous count" calculation.

A Note on Atomicity and Race Conditions

In the previous lesson, we emphasized using Redis pipelines to ensure atomicity. The provided Python code correctly uses a pipeline for the INCR and EXPIRE commands, making the write operation atomic.

However, there's a subtle race condition in the broader "read-modify-write" cycle of the is_allowed function:

1. Request A reads counts (e.g., previous=0, current=99). estimated_count is 99.
2. Request B reads the same counts. estimated_count is also 99.
3. Request A sees 99 < 100, so it proceeds to increment the counter and returns True.
4. Request B also sees 99 < 100, proceeds to increment the counter, and returns True.

The result: two requests are allowed when only one should have been, and the counter becomes 101. For a production system like Rudi, this could lead to exceeding capacity agreements.

In a distributed environment, the robust solution is to perform the entire check-and-increment logic atomically on the Redis server itself using a Lua script. The script would take the client ID and current timestamp as arguments, perform the weighted calculation, check the limit, and increment the counter all in one indivisible operation. While we won't write the Lua script here, it's the standard production-grade pattern to solve this race condition.

---

3. Connection to Your Rust Experience

The core logic is, of course, language-agnostic. Your background in Rust gives you a strong foundation for understanding the state management involved. Let's look at how this would be structured in Rust for an in-memory implementation.

The Rust implementation uses a HashMap to store the WindowCounter structs. To make this thread-safe for a web server, you would wrap the HashMap in concurrency primitives like Arc<RwLock<...>>, which you're likely very familiar with. This serializes access to the map, preventing the race condition we just discussed in the context of a single service instance. The Lua script serves the same purpose but in a distributed context.

---

4. The All-Important Trade-offs

You wanted a focus on trade-offs, and this algorithm is defined by them. Let's explicitly compare the sliding-window counter to the log-based approach we learned previously.

Here's the summary:

Aspect	Sliding Window Log (Previous Lesson)	Sliding Window Counter (This Lesson)
Memory Usage	High (O(N) per client, stores N timestamps)	Low (O(1) per client, stores 2 counters)
Accuracy	Exact. No approximation.	Approximate. Assumes even request distribution.
Best For	Lower traffic APIs where precision is paramount.	High-traffic APIs where memory is a concern.
Implementation	Uses Redis Sorted Sets (ZSET).	Uses simple Redis keys/counters (GET/INCR).

The core trade-off is clear: the counter algorithm sacrifices perfect accuracy for a massive gain in memory efficiency. It's not perfectly fair—a burst of requests at the very end of the previous window will have a disproportionately high weight for a short time—but for many high-throughput systems, this "good enough" accuracy is an excellent compromise to avoid the memory explosion of the log method.

5. Alternative: A More Granular Counter

The two-bucket counter isn't the only way. Another popular variant of the "sliding-window counter" uses more buckets for higher precision, striking a different balance on the accuracy-memory spectrum.

Instead of just a "previous" and "current" window, you could break a 1-minute window into 60 one-second sub-windows (or buckets).

This N-bucket approach gives you a tunable knob. More buckets lead to higher accuracy but also higher memory usage and more computation (summing more buckets). This creates a spectrum of options:

1. Fixed Window: 1 counter. Lowest memory, lowest accuracy.
2. Sliding Counter (2 buckets): 2 counters. Very low memory, good accuracy.
3. Sliding Counter (N buckets): N counters. Low-to-moderate memory, very good accuracy.
4. Sliding Log: N timestamps. Highest memory, perfect accuracy.

Understanding this spectrum is key to making informed design decisions in a system design interview.

---

Conclusion

In this lesson, we explored the sliding-window counter algorithm, a practical and widely-used approach to rate limiting.

Key Takeaways:

• Memory-Optimized: The sliding-window counter is a memory-efficient alternative to the log-based approach, typically using O(1) space per client instead of O(N).
• Approximation through Weighting: It works by calculating a weighted average of the request counts from the previous and current time windows.
• The Trade-off: It sacrifices perfect accuracy for scalability, assuming that request traffic is reasonably distributed within a window.
• Atomicity is Critical: The read-modify-write cycle is prone to race conditions, requiring atomic operations (like a Lua script in Redis) for a production-safe implementation.
• A Spectrum of Options: The "counter" method can be implemented with 2 buckets for maximum memory efficiency or with N buckets for higher accuracy, allowing you to choose the right point on the cost-vs-precision spectrum.

Next Lesson Preview

We have now implemented three distinct rate-limiting algorithms: fixed-window counter, sliding-window log, and sliding-window counter. You understand their mechanics and individual trade-offs.

In the next lesson, we will synthesize this knowledge. The learning outcome is to compare the trade-offs (accuracy, memory, complexity) between token bucket, fixed-window, and sliding-window algorithms. We will introduce the final major algorithm—the token bucket—and create a comprehensive framework for you to choose the right tool for any given scenario.