3 Rate Limiting Patterns with Redis

I will write down several Redis Rate Limit patterns.
Here, as an example, we will assume that the Rate Limit is applied per IP address (hereinafter ip).

※All patterns are Redis Cluster compatible.

1. Single Counter Pattern

Redis Key Design

※ The part enclosed by % is a variable.

(String type) ratelimit:%ip%
ex)
ratelimit:127.0.0.1

Pseudo Application Code

• Separate keys per IP.
• If the key count exceeds 10, return ERROR.
• Keys expire every 1 second.
• INCR&EXPIRE is executed atomically with LuaScript.

script = """
             local current
             current = redis.call("incr",KEYS[1])
             if tonumber(current) == 1 then
                 redis.call("expire",KEYS[1],1)
             end
         """
ip = IP_ADDRESS()
keyname = "ratelimit:"+ip
current = redis.GET(keyname)
IF current != NULL AND current > 10 THEN
    ERROR "too many requests per second"
ELSE
    redis.EVAL(script,1,keyname)
END

A Single Counter Rate Limit implementation.
INCR&EXPIRE is implemented using EVAL, which executes LuaScript.
If not implemented with LuaScript, the key will remain in Redis if the application dies before EXPIRE is executed.
By changing the TTL from 1 second, Rate Limiting can be performed for any duration.

2. Pattern for storing arbitrary metadata in RateLimit

Redis Key Design

※ The part enclosed by % is a variable.

(List type) ratelimit:%ip%
ex)
ratelimit:127.0.0.1

Pseudo Application Code

• Separate keys per IP.
• Store arbitrary metadata in the List's value.
• If the List's length exceeds 10, return ERROR.
• Keys (=List) expire every 1 second.
• INCR&EXPIRE is executed atomically with LuaScript.

script = """
             redis.call("rpush",KEYS[1],VALUE[1])
             redis.call("expire",KEYS[1],1)
         """
userid = USER_ID()
ip = IP_ADDRESS()
keyname = "ratelimit:"+ip
current = redis.LLEN(keyname)
IF current != NULL AND current > 10 THEN
    ERROR "too many requests per second"
ELSE
    IF redis.EXISTS(keyname) == FALSE
        redis.EVAL(script,1,keyname,userid)
    ELSE
        redis.RPUSHX(keyname,userId)
    END
END

This method utilizes the fact that LLEN, the command to get the length of a List type, is O(1).
The values in the List are not used for Rate Limiting, so arbitrary metadata, such as user IDs, can be embedded.
Therefore, in this example, when the IP address Rate Limit is reached, by looking at the values in that List, it is possible to immediately identify which user's access caused it.

Note that in this code, due to a race condition, EXISTS might return false, leading to multiple clients unnecessarily executing the LuaScript.
However, this is not a problem in the context of Rate Limiting. (It merely sets EXPIRE again redundantly.)

The disadvantage is that it consumes memory proportional to the size of the metadata and the access frequency.

3. Pattern capable of Sliding Window aggregation

Redis Key Design

※ The part enclosed by % is a variable.

(String type) {ratelimit:%ip%:}%timestamp%
ex)
{ratelimit:127.0.0.1:}1605054195

Pseudo Application Code

• Separate keys per IP * timestamp.
• Increment the current timestamp.
• Retrieve past data in a single round trip with the mget command.
• Set a hash tag on the key to enable mget even in Redis Cluster.
• Old keys are removed by Redis's EXPIRE.

script = """
             redis.call("incr",KEYS[1])
             redis.call("expire",KEYS[1],16)
         """
timestamp = CURRENT_UNIX_TIME()
ip = IP_ADDRESS()
keyname = "{ratelimit:"+ip+":}"+timestamp
redis.EVAL(script,1,keyname)
keynames = []
FOR(i=0; i<15; i++)
    keynames[0] = "{ratelimit:"+ip+":}"+timestamp-i
END
counts = []
counts = redis.MGET(keynames)
sum = 0
FOR(i=0;i<15;i++)
    sum += counts[i]
    IF i == 0 && sum > 1000 THEN // Allow up to 1000 requests per second (burst allowed)
        ERROR "too many requests per second"
    END
    
    IF i == 9 && sum > 5000 THEN // Allow up to 5000 requests per 10 seconds
        ERROR "too many requests per 10 seconds"
    END
    
    IF i == 14 && sum > 7000 THEN // Allow up to 7000 requests per 15 seconds
        ERROR "too many requests per 15 seconds"
    END
END

This is a Sliding Window method used when you want to allow a burst of access for the most recent 1 second, but block it if it continues for 10 seconds, for example.
Only the parts requiring atomicity are put into LuaScript, so mget is not included in LuaScript.
By including mget as well, Redis queries can be contained within a single Round Trip, and the readability of the code (maintainability of LuaScript) does not significantly worsen.
Also, since the keys are separated, mget, which is a Multi Command, cannot be used directly in a Redis Cluster. Therefore, the hash tags feature { } is used.
Since the mget command is O(n) proportional to the number of elements n to be retrieved, care must be taken with the sliding window length.

Summary

Pattern Name	Features
Single Counter	Minimum memory usage as it only records the current number of accesses. Used to suppress instantaneous load.
Metadata Attachment	Consumes memory due to list length. Can record arbitrary metadata, allowing for more advanced domain-dependent processing.
Sliding Window	Requires memory and computational power proportional to the sliding window length. Used in advanced use cases where temporary bursts are allowed, but sustained access is not.