Atomic Sliding Window in Redis with Lua

Your learning outcome for this lesson:

By the end of this session, you will be able to implement the sliding window logic using a Lua script for atomic updates in Redis. This will ensure your rate limiter is correct and free of race conditions, even under high concurrency.

1. A Practical Pivot: From HASH to Sorted Set

In our previous discussion, we chose a Redis HASH to implement the sliding window counter. The plan was to have each field in the hash represent a sub-window counter. This approach is very memory-efficient.

However, when we try to implement this logic atomically within a single Lua script, we encounter some practical challenges:

1. Reading the Window: To get the total count, the script would need to get all fields (HGETALL), iterate through them in Lua, filter out the expired sub-windows, and sum the counts of those still within the main window. For a client with a long history, HGETALL can become a performance bottleneck.
2. Atomic Cleanup: While newer Redis commands like HEXPIRE allow for per-field TTLs, the core logic of summing multiple fields and then incrementing one of them is complex to express atomically and performantly without HGETALL.

This is a classic trade-off scenario. While the HASH approach is optimal for memory, the Sorted Set (ZSET) approach is far more idiomatic and simpler to implement correctly and atomically in Redis for this specific algorithm.

For our project, we will pivot to the Sorted Set implementation for the sliding window. It demonstrates a deeper understanding of Redis data structures and the trade-offs involved—a quality that is highly valued in system design interviews and portfolio reviews.

Here's the trade-off we're making:

• Memory: We'll use slightly more memory, as we store a unique entry for each request instead of an aggregated counter.
• Simplicity & Correctness: In exchange, we get a much simpler, more robust, and highly performant atomic implementation using Redis's built-in ZSET commands.

2. The Sliding Window Algorithm with Sorted Sets

Let's visualize how this works. We use a Sorted Set for each client, where:

• Members: Are unique identifiers for each request. A timestamp alone isn't unique enough, so we'll use a combination of the timestamp and a random value.
• Scores: Are the Unix timestamps of when each request occurred.

The process for each incoming request is an atomic, three-step dance performed by our Lua script:

1. Remove: Delete any members whose score (timestamp) is older than the current time minus the window duration. This is the "sliding" action.
2. Count: Get the size of the set. This is the number of requests in the current window.
3. Add: If the count is below the limit, add the new request to the set.

This process guarantees that we are always looking at the correct time window and that the check-and-update operation is free of race conditions.

3. Dissecting the Lua Script

Now, let's look at the Lua script that performs this logic. While the following resource is written for Go, the Lua script it contains is universal and perfectly illustrates the Sorted Set pattern for a sliding window.

Let's break down the key parts of the script you just studied:

Inputs (KEYS and ARGV):

• KEYS[1]: The key of our sorted set (e.g., ratelimit:sw:user:123).
• ARGV[1]: The window size in milliseconds.
• ARGV[2]: The limit (max requests).
• ARGV[3]: The now timestamp in milliseconds.
• ARGV[4]: A request_id to ensure each member in the set is unique.

Core Logic:

1. redis.call('ZREMRANGEBYSCORE', key, 0, now - window)

   • This is the most critical command. It atomically removes all members from the sorted set whose scores (timestamps) are outside our sliding window.

2. local count = redis.call('ZCARD', key)

   • This gets the number of members remaining in the set, which is our current request count.

3. if count < limit then ...

   • If the current count is below the configured limit, the request is allowed.

4. redis.call('ZADD', key, now, request_id)

   • If allowed, the new request is added to the sorted set with its timestamp as the score.

5. redis.call('EXPIRE', key, math.ceil(window / 1000))

   • This is a crucial memory management step. It ensures that if a client becomes inactive, the entire sorted set is automatically deleted from Redis, preventing memory leaks. We set the expiration to the window size in seconds.

The script then returns an array of values, including whether the request was allowed and what the remaining request count is. This is useful for the application and for setting HTTP headers like X-RateLimit-Remaining.

4. Integrating the Lua Script with Spring Boot

Now that you understand the script's logic, how do you execute it from your Java application? This is where Spring Data Redis comes in.

The following article provides a fantastic example of wrapping a Lua script for the sliding window algorithm within a Spring Boot service.

As you saw in the resource, the key components for integration are:

• DefaultRedisScript<T>: An object that holds your Lua script. You can load the script from a string or an external .lua file. You also specify the expected return type (e.g., Long.class or List.class).
• RedisTemplate<String, String>: The central Spring Data Redis class for executing commands.
• redisTemplate.execute(script, keys, args...): This method sends the script and its parameters to Redis for atomic execution.

You will use this pattern to build your RedisSlidingWindowRateLimiter class, which will implement the RateLimiter interface you designed earlier.

Conclusion

Congratulations! You have now mastered the most common and robust pattern for implementing a distributed sliding window rate limiter. You not only understand the mechanics but also the important design trade-offs that lead to this solution.

Key Takeaways:

• The Sorted Set (ZSET) approach is the idiomatic Redis pattern for a sliding window rate limiter due to its atomic and performant nature when used with Lua.
• The core logic revolves around the atomic sequence of ZREMRANGEBYSCORE, ZCARD, and ZADD.
• Using EXPIRE on the Redis key is essential for automatic memory cleanup of inactive clients.
• In Spring Boot, you can execute Lua scripts using RedisTemplate and DefaultRedisScript.

Next Steps

In our next lesson, we will implement the token bucket algorithm using a Lua script. This will provide a nice contrast, as the token bucket's state is perfectly suited to the HASH data type we originally discussed, reinforcing the principle of choosing the right data structure for the specific problem at hand.