Sliding-Window Rate Limiting: Accuracy Over Fixed Windows

Hello! Welcome back to your training.

In our last lesson, we implemented the fixed-window counter, a simple and memory-efficient rate-limiting algorithm. However, we identified its critical flaw: the boundary problem, where a client can effectively double their request rate by sending bursts of traffic at the edge of two consecutive windows.

This lesson directly addresses that flaw. We'll explore a more precise, but more resource-intensive, algorithm designed to provide a true rolling window.

The learning outcome for this lesson is to implement a sliding-window log rate limiter, detailing how it improves accuracy over the fixed-window approach. We will dissect its mechanics, implement it using a data structure perfectly suited for the task, and analyze its significant trade-offs.

1. Solving the Boundary Problem

The core issue with the fixed-window counter is that it has no memory of the recent past once a new window begins. The counter simply resets. The sliding-window log algorithm solves this by maintaining a continuous record—a "log"—of individual request timestamps.

Instead of asking "How many requests have happened in this fixed block of time?", it asks "How many requests have happened in the last N seconds from this exact moment?"

To implement this, for each client, we store a list or log of timestamps for all their recent requests. When a new request arrives:

1. We remove any timestamps from the log that are older than our window period (e.g., older than 60 seconds ago).
2. We count the number of timestamps remaining in the log.
3. If this count is less than our limit, we add the new request's timestamp to the log and allow the request. Otherwise, we reject it.

The following image provides a step-by-step visualization of this process.

For a more dynamic explanation, the following video walks through the logic.

This approach completely eliminates the boundary problem. Since the window is always calculated relative to the current time, a client can never exceed the rate limit by "straddling" two windows.

2. Implementation with Redis Sorted Sets

To implement this in a distributed environment, we need a centralized data structure that can efficiently store sorted timestamps and perform range-based operations. While the video mentions a linked list, a more optimized choice in a system using Redis is a Sorted Set (ZSET).

A sorted set is ideal for this because:

• It stores members with an associated score, which we can use for the timestamp.
• It automatically keeps members sorted by score.
• It provides commands to efficiently remove members within a score range (i.e., time range) and to get the total number of members.

The following article provides an excellent implementation using Python and Redis sorted sets.

Connecting to Your Rust Experience

The logic here is conceptually similar to what you might implement in a single-node Rust application. For instance, the article Implementing API Rate Limiting in Rust shows an in-memory approach using Arc<Mutex<HashMap<IpAddr, Vec<DateTime<Utc>>>>>. In that case, you would:

1. Lock the Mutex.
2. Get the Vec<DateTime> for the specific IP.
3. Use .retain() on the vector to remove old timestamps.
4. Check .len() to see if the limit is exceeded.
5. .push() the new timestamp.

This mirrors the zremrangebyscore -> zcard -> zadd flow in Redis. The key difference is that Redis provides these operations atomically in a way that's accessible across a distributed fleet of services, whereas the Arc<Mutex> approach is confined to a single process's memory. The Redis sorted set is also more efficient for this specific task than a simple Vec, as removing elements from the start of a vector can be a linear-time operation, while zremrangebyscore is optimized for this very use case.

3. Analyzing the Trade-offs

Your focus on trade-offs is critical. The sliding-window log makes a very clear trade: it exchanges memory for accuracy.

Advantage: Perfect Accuracy

• This is the primary benefit. The rate limit is enforced precisely over any given time window, completely solving the boundary issue of the fixed-window counter. For services requiring strict guarantees, this accuracy is non-negotiable.

Disadvantage: High Memory Usage

• This is the algorithm's Achilles' heel. It needs to store a unique entry for every single request within the window.
• Consider a service with a limit of 1,000 requests per minute. For a single active user, Redis would store 1,000 entries (timestamps) in a sorted set.
• For a high-throughput system like your Rudi inference scheduler, which handles thousands of TPS, storing every request timestamp for every client would lead to enormous memory consumption. This makes the pure log-based approach impractical for very high-traffic APIs.

4. Concurrency and Atomicity

In our last lesson, we stressed the importance of INCR for atomic increments. Here, the situation is more complex as we have a multi-step "read-modify-write" pattern (remove old, count, add new).

If two requests arrive concurrently, you could have a race condition:

1. Request A removes old timestamps.
2. Request B removes the same old timestamps.
3. Request A reads the count (e.g., 999).
4. Request B reads the count (also 999).
5. Request A decides it's under the limit (1000) and adds its timestamp.
6. Request B also decides it's under the limit and adds its timestamp.
7. The final count becomes 1001, exceeding the limit.

This is why the pipeline used in the OneUptime Python code is so important. By wrapping the Redis commands in a pipeline (or a Lua script, which is another common pattern for this), we ensure that the entire sequence of operations for a single request is executed atomically by Redis. No other commands can interfere in the middle. This is the distributed equivalent of the Mutex lock you're familiar with in Rust.

Conclusion

In this lesson, we dissected the sliding-window log algorithm, a powerful technique that offers perfect rate-limiting accuracy by maintaining a timestamp for every request.

Key Takeaways:

• Solves the Boundary Problem: By maintaining a log of timestamps in a true rolling window, this algorithm provides exact rate limiting and eliminates the burst vulnerability of the fixed-window counter.
• Ideal Data Structure: Redis sorted sets (ZSET) are a perfect fit for implementing this in a distributed system, offering efficient, sorted storage and range-based removal.
• The Core Trade-off: The sliding-window log buys perfect accuracy at the cost of high memory usage (O(N) per client, where N is the request limit).
• Atomicity is Key: Multi-step operations must be performed atomically using mechanisms like Redis pipelines or Lua scripts to prevent race conditions under concurrent loads.

Next Lesson Preview

We've seen that the fixed-window counter is memory-efficient but inaccurate, while the sliding-window log is accurate but memory-intensive. Is there a middle ground?

In the next lesson, we will explore a hybrid approach that tries to get the best of both worlds. You will implement a sliding-window counter rate limiter as a memory-optimized alternative to the sliding-window log. This will complete our tour of the most common rate-limiting algorithms and the critical trade-offs between them.