Redis Key Structures for Rate Limiting

Your learning outcome for this lesson:

By the end of this lesson, you will be able to design a Redis key structure for the sliding window and token bucket algorithms. This involves choosing the right Redis data types and defining a naming convention that is scalable, debuggable, and supports the multi-tenant requirements of our project.

1. Principles of Redis Key Design

A well-designed key schema is not just a detail; it's a critical part of a robust distributed system. For our rate limiter, we need a key structure that is:

• Unambiguous and Debuggable: A key like ratelimit:user_id:123:search_api tells you exactly what it's for. A key like rl_xyz does not. Good naming saves you significant time when monitoring or troubleshooting.
• Collision-Free: Using a specific prefix for our application, such as ratelimit:, ensures our keys won't clash with other applications that might use the same Redis instance.
• Flexible for Multi-Tenancy: The structure must accommodate the different client identifiers we plan to support (IP address, user ID, API key, endpoint). This is where the RateLimitKeyResolver you designed earlier will feed into our key creation.
• Cluster-Aware: For production systems running on a Redis Cluster, keys need to be designed so that all keys accessed by a single Lua script reside on the same physical node. This is achieved using "hash tags," where part of the key is enclosed in curly braces, like ratelimit:{user_id:123}:search. Redis ensures that all keys with the same content inside {} are allocated to the same hash slot.

With these principles in mind, we will adopt a general key format:

ratelimit:{algorithm}:{resolved_key}

Where:

• algorithm will be sw for sliding window or tb for token bucket.
• resolved_key is the unique identifier for the client, which could be a simple IP address (ip::1) or a composite key (user:42:endpoint:/v1/data).

This structure provides a clean, organized namespace for all our rate limiting data.

2. Key Structure for the Token Bucket Algorithm

Let's start with the token bucket algorithm. It's conceptually simpler, which makes its data storage requirements more direct.

To operate the token bucket, what state must we persist for each client?

1. The number of currently available tokens.
2. The timestamp of when the bucket was last accessed (to calculate token refills).

A Redis HASH is the ideal data structure for this. It allows us to store multiple field-value pairs under a single key, perfectly mapping to the state we need to maintain.

Our proposed design is:

• Key: ratelimit:tb:{resolved_key}
  • Example: ratelimit:tb:apiKey:abc-123
• Data Type: HASH
• Fields within the Hash:
  • tokens: The current count of available tokens.
  • timestamp: The last access time (as a Unix timestamp).

Let's look at how this works in practice.

This design is simple and efficient. When our Lua script runs, it will use HMGET to fetch both values, calculate the refilled tokens, and use HMSET to update the state in a single atomic operation.

To learn more about how this HASH-based approach is used, please review the following resource.

Memory Management

What happens when a client stops making requests? We don't want their token bucket data to live in Redis forever. We can solve this by setting an expiration time on the key itself using the EXPIRE command. For example, we can set the key ratelimit:tb:apiKey:abc-123 to expire after 1 hour of inactivity. If the user makes another request, our script will update the hash and reset the TTL, keeping the key alive. This self-cleaning mechanism is crucial for managing memory efficiently.

3. Key Structure for the Sliding Window Counter Algorithm

The sliding window algorithm is more complex, as it requires tracking request counts across multiple time intervals (sub-windows). There are a few ways to model this in Redis, each with different trade-offs.

Option A: The HASH-based Counter Approach

In this model, we use a Redis HASH where each field represents a sub-window, and its value is the request counter for that interval.

• Key: ratelimit:sw:{resolved_key}
  • Example: ratelimit:sw:ip:127.0.0.1
• Data Type: HASH
• Fields within the Hash:
  • The field key is the Unix timestamp representing the start of a sub-window (e.g., 1672531260 for the minute starting at 12:01:00).
  • The field value is the number of requests counted in that sub-window.

To check the rate limit, our script would:

1. Identify the current and previous sub-windows that fall within the main window.
2. Fetch their counts from the hash using HGET or HMGET.
3. Sum the counts to get the total number of requests in the sliding window.
4. If the request is allowed, increment the counter for the current sub-window using HINCRBY.

To understand this approach better, watch the following video from Redis, which explains and visualizes this exact method.

Option B: The Sorted Set Approach

An alternative is to use a Redis Sorted Set (ZSET). Instead of counters, we store an entry for every single request.

• Key: ratelimit:sw:{resolved_key}
• Data Type: ZSET
• Members: A unique identifier for each request (e.g., timestamp:random_number).
• Scores: The Unix timestamp of the request.

To check the rate limit, our script would:

1. Remove all members from the sorted set with a score (timestamp) older than the current window using ZREMRANGEBYSCORE.
2. Count the remaining members in the set using ZCARD. This is the current request count.
3. If the count is below the limit, add the new request to the set using ZADD.

This method is shown in the Lua script within the check_sliding_window function in the OneUptime article (LINK, section 0) you reviewed earlier.

Comparison and Our Choice

For our project, we will proceed with the HASH-based counter approach (Option A). It is significantly more memory-efficient at scale, which is a key consideration in system design. The slight loss in accuracy is an acceptable trade-off for most real-world applications. This choice also presents a more interesting implementation challenge, which will be valuable for your portfolio.

Conclusion

You have now created the architectural blueprints for storing our rate limiter's state in a distributed environment. This design phase is essential for ensuring our final implementation is logical, efficient, and scalable.

Key Takeaways:

• A well-defined key naming convention like ratelimit:{algorithm}:{resolved_key} is vital for clarity, debugging, and multi-tenancy.
• For the Token Bucket algorithm, a Redis HASH is the perfect fit, storing tokens and timestamp fields under a single key per client.
• For the Sliding Window algorithm, we will use a Redis HASH to act as a collection of counters, where each field represents a sub-window timestamp and its value is the request count.
• In both cases, we will use EXPIRE on the top-level key to ensure automatic cleanup of inactive client data, preventing memory leaks.

Next Steps

With our data structures now clearly defined, we are ready to build the engine. In the next lesson, we will implement the sliding window logic using a Lua script. You will write the code that atomically reads the relevant sub-window counters from the hash, checks the limit, and increments the counter for the current request, bringing our design to life.