Rate Limiting: A Dynamic Distributed Rate Limiting with Redis

In our previous article, “Rate Limiting: The Sliding Window Algorithm” we explored the theoretical underpinnings of rate limiting and how the Sliding Window Algorithm serves as an effective solution. Now, it’s time to roll up our sleeves and dive into the practical side of things. In this new article, we will take that theoretical knowledge and put it into action.

Slide Limiter

Slide Limiter is an open-source TypeScript implementation of a sliding window rate-limiting algorithm that provides distributed rate-limiting functionality using Redis. It allows you to limit the number of requests or actions that can be performed within a specific time window in a dynamic efficient way.

Architecture and Implementation

Slide Limiter leverages a dynamic rate-limiting approach, allowing you to fine-tune rate limits based on their specific needs. By creating a SlideLimiter instance with customizable options, such as the duration of the time window and the maximum limit of requests, users gain the flexibility to enforce rate limits tailored to their application's requirements.

The architecture involves two essential components:

1. Slide Limiter (SlideLimiter): This is the central orchestrator responsible for managing rate limits. By interfacing with different store options, it offers a seamless way to enforce rate limiting across applications. The heart of the Slide Limiter is the hit method, which checks and enforces rate limits. If a request exceeds the defined rate limit, it can trigger the necessary actions, ensuring the orderly flow of requests.
2. Storage Options (RedisStore and MemoryStore): Slide Limiter allows you to choose between RedisStore and MemoryStore as storage backends. RedisStore is particularly well-suited for distributed systems where consistency and shared rate limiting across multiple servers are paramount. It employs a Lua script executed atomically in Redis, ensuring that rate-limiting operations are thread-safe. On the other hand, MemoryStore is ideal for single-node or testing environments, offering simplicity and ease of use.

The following code snippet is almost what you need to create a simple rate limiter and validate the hits count.

import Redis, { RedisOptions } from 'ioredis';  
import { RedisStore, SlideLimiter } from "slide-limiter";  

// Create a RedisStore instance  
const store = new RedisStore({  
    host: env.REDIS_HOST || 'localhost',  
    port: env.REDIS_PORT || 6379,  
    password: env.REDIS_PASSWORD,  
    db: env.REDIS_DATABASE || 0,  
});  
// SlideLimiter options  
const options = {  
  windowMs: 60000,  // 1 minute  
  maxLimit: 11,     // n + 1  
};  
const limiter = new SlideLimiter(store, options);  
const bucket = 'users';  
const key = "user123";  
// Remaining requests  
const remaining = await limiter.hit(bucket, key);  
if (remaining > 0) {  
  // Allow the action  
  console.log(`Action performed. Remaining requests: ${remaining}`);  
} else {  
  // Rate limit exceeded  
  console.log("Rate limit exceeded. Please try again later.");  
}

Use the limit you need + 1, as we have one method hit that does the increment and returns the count after consuming 1 hit

By creating a SlideLimiter instance with specific options, such as a one-minute time window and a maximum limit of 10 requests, we enable fine-grained control over the rate-limiting process.

With a defined bucket and key, we can effortlessly track and manage the rate limits for different users or entities. If the remaining requests exceed zero, the action is allowed to proceed, and the remaining request count is displayed. However, if the rate limit has been reached, the system gracefully handles the situation and informs the user that they should try again later.

Adaptive Rate Limiting with Dynamic Configuration

Dynamic rate limiting offers significant advantages when dealing with varying rate-limiting requirements across different operations or clients.

This flexibility enables us to tailor rate limits to specific use cases, such as granting higher limits to premium users or imposing stricter limits on resource-intensive operations.

The sliding window algorithm provides an elegant solution to this dynamic rate-limiting need by allowing real-time adjustments to the windowMs and maxLimit parameters.

For instance, when working with a specific bucket (e.g., main) and a key (e.g., 1234) with initial settings of windowMs = 60000 and maxLimit = 5, we can seamlessly modify these parameters for larger or smaller values with each new call to the hit function. This adaptability empowers applications to fine-tune rate limits on the fly, ensuring optimal performance and resource allocation.

Fine-Grained Rate Limiting Control

Slide Limiter uses the concept of buckets with keys to effectively control and manage the flow of requests within an application or system. These parameters serve specific roles in the rate-limiting process:

Bucket

The bucket parameter is a higher-level categorization that allows us to group rate limits for different resources or endpoints. It can be used to separate the count for specific endpoints or functionalities within your application.

In the context of a web API, for example, we might want to rate limit different endpoints differently. By using a bucket, we can create distinct rate limits for different parts of your application.

For instance, we could have separate buckets for /users/auth, /api/orders, and /api/profile, each with its own rate limit configuration.

Key

The key parameter represents the identifier for the resource or entity we want to rate limit per bucket. It is typically associated with a specific user, IP address, or any other unique identifier for the client making the request. For example, if we want to rate limit requests from different users or clients separately, we can use the user’s ID or IP address as the key. The key is an essential part of the rate-limiting process because it allows us to track and limit requests on a per-client basis.

Together, buckets and keys enable fine-grained control over rate limiting. Buckets categorize rate limits, while keys distinguish requests from different clients or entities, ensuring that rate limiting is not only efficient but also customizable to the specific needs of your application.

Redis Store

Redis is used here to store and update hits count atomically, which is suitable for distributed systems where rate-limiting needs to be consistent and shared across multiple servers.

How Redis Store Works

When we use Redis as a store for Slide Limiter, calls forhit function will call RedisStore -> hit function, which actually calls the following LUA script that will be executed by Redis server.

local current_time = redis.call('TIME')  
local bucket = KEYS[1]  
local id = KEYS[2]  
local key = bucket .. ":" .. id  
local window = tonumber(ARGV[1]) / 1000  
local limit = tonumber(ARGV[2])  
local trim_time = tonumber(current_time[1]) - window  
redis.call('ZREMRANGEBYSCORE', key, 0, trim_time)  
local request_count = redis.call('ZCARD', key)  
if request_count < limit then  
  redis.call('ZADD', key, current_time[1], current_time[1] .. current_time[2])  
  redis.call('EXPIRE', key, window)  
  return limit - request_count - 1;  
end  
return 0

This Lua script is designed to be executed atomically in Redis, ensuring that rate-limiting operations are consistent and thread-safe when multiple requests are made concurrently. It checks if the request count is within the defined limit and records each request’s timestamp, allowing for accurate rate-limiting enforcement.

It performs the following steps:

1. Get the Current Time: Use redis.call('TIME') to retrieve the current time in Redis, which is an array with two elements: the seconds and microseconds.
2. Construct the Key: Combine the bucket and id to create a unique key in Redis. This key represents the rate-limiting window for a specific resource (Both are provided when invoking the script).
3. Calculate the Time Window: Convert the provided windowMs (in milliseconds) to seconds by dividing it by 1000.
4. Check the Requests Count: Check the number of requests in the specified time window by using redis.call('ZCARD', key). This count represents the requests made within the defined time window.
5. Rate Limit Check: If the request count is less than the limit, it means there's still capacity for more requests.
6. Add Request Timestamp: Add the current time to the Redis sorted set with the timestamp as the score. This effectively records the time of the request.
7. Set Expiry Time: Set an expiry time on the Redis key using redis.call('EXPIRE', key, window). This ensures that rate-limiting data is automatically cleared from Redis after the defined time window.
8. Calculate Remaining Requests: Calculate the remaining requests by subtracting the request count from the limit and then subtracting 1. This accounts for the current request.
9. Return Remaining Requests: Return the number of remaining requests. If it’s greater than 0, the request is allowed; otherwise, it’s rate-limited.

Using Redis for rate limiting offers several benefits

1. Distributed and Scalable: Redis is a distributed, in-memory data store that is well-suited for scaling applications. By using a RedisStore, we can implement rate limiting in a distributed system, making it easier to handle high traffic and load balancing across multiple instances.
2. High-Performance: Redis is known for its exceptional read and write performance, making it an excellent choice for rate limiting. It can quickly store and retrieve rate-limiting data, reducing the latency of rate-limiting checks.
3. Expiration and Automatic Cleanup: Redis allows you to set expiration times for keys, making it easy to implement automatic data cleanup. This feature is crucial for rate limiting because it ensures that old rate limit data is removed, maintaining the accuracy of the rate limiter.
4. Atomic Operations: Redis supports atomic operations, which means rate limit checks and updates can be performed atomically in a single step. This ensures that rate-limiting operations are consistent, even in a multi-threaded or distributed environment.

Slide Limiter on GitHub

If you’re interested in more details, please visit the project page on GitHub

https://github.com/m-elbably/slide-limiter

Conclusion

Slide Limiter is a powerful tool for implementing rate limiting in your distributed applications. By combining the efficiency of the sliding window rate-limiting algorithm with the scalability and consistency of Redis, Slide Limiter offers a robust solution for managing the flow of requests and actions within your system. Whether you need to protect endpoints, manage client-specific rate limits, or dynamically adjust rate-limiting parameters, I think Slide Limiter provides the flexibility and control you will need.