Skip to main content

Implementing Rolling Rate Limits

Redis sorted sets are different from other collection types, in that they are a collection of unique string values called "members", which each have an associated "score"; the score is similar to a key, and the member is similar to a value, but they work a bit differently. The score doesn't have to be unique, but the member does, unlike key/value collections where it's the other way around.

Sorted sets can be used to efficiently implement rolling rate limits for parts of your website, including per user or with other conditions. This is very useful for limiting access to certain operations, for example to prevent abuse, or prevent your website being overloaded with unnecessary or malicious requests.

Implementation

For the sake of example, suppose we want to limit a website's search function to 5 operations per minute for all users. We can implement this by using a sorted set where the score for each entry in the set is the current time in seconds, and the member is the same as the score (we don't need the member, but the member value must be unique in a sorted set). Let's call the sorted set key RATELIMIT:SEARCH.

Each time a user requests a search, we call the ZCOUNT function on the RATELIMIT:SEARCH key. This command counts the number of members in the sorted set that have a score between the minimum and maximum we specify. 

Suppose the current time in seconds since the epoch is 1724436736. We would execute the following command:

# Syntax is ZCOUNT [key] [min] [max].
# Here, the min is 60 seconds ago, and the max is the current time.
ZCOUNT RATELIMIT:SEARCH 1724436676 1724436736

This will return the count of members in the set whose score is between the min and max values, which in this case, means any members that were added in the last 60 seconds. If this count is 5 or more, then we know that the rate limit has been exceeded and we can refuse the search request by the user; if not, we allow the search, and we use the ZADD and EXPIRE commands to accomplish two things:

  • Firstly, add the new member to the sorted set, with the score being the current time in seconds.
  • Secondly, add or refresh the expiry time for the sorted set to 60 seconds; if no search is made for longer than this period of time, the set will be deleted. All data inside it would already be outdated at this point, so it's a good way to save memory.
# Syntax is ZADD [key] [score] [member].
# We're setting the score and member to be the same here.
ZADD RATELIMIT:SEARCH 1724436736 1724436736

# Syntax is EXPIRE [key] [seconds] [options].
# We are both setting the expiry time for the sorted set if it doesn't exist,
# and if it does, refreshing the expiry time to 1 minute.
EXPIRE RATELIMIT:SEARCH 60

This is simple enough, but we also need to get rid of outdated entries from this set to prevent it becoming huge; otherwise we will end up with a gigantic sorted set in Redis over time that would both be slow, and eat up memory. The EXPIRE command will delete the sorted set if it becomes over 60 seconds old, but it will not delete individual members within the sorted set that are old; so long as searches are made more than once a minute, the sorted set will grow and grow and grow.

To solve this problem, we can remove all entries more than 60 seconds old from the set each time we check the rate limit for a user, using the ZREMRANGEBYSCORE command:

# Syntax is ZREMRANGEBYSCORE [key] [min] [max].
# Here, the min is 60 seconds ago, and the max is the current time.
ZREMRANGEBYSCORE RATELIMIT:SEARCH 1724436676 1724436736


Back to top