How to use Redis's sorted set to implement Rate Limiter?

[ltd (Lê Trần Đạt)]

Hôm nay mình research một ít về cách dùng Redis Sorted Set để implement Rate Limiter sử dụng sliding window log algorithm. Đây là cái note của mình hi vọng có thể giúp được ai đó đang ôn luyện system design

Q: How does the Rate Limiter system look like at High level?
A:

Q: What is sorted set?
A: A sorted set is a collection of unique elements that are sorted in a specific order.

Q: What is sorted set in Redis?
A: It’s the same with sorted set above but we can give each unique element a score, Redis use this score to sort the set.

Q: How to use Redis Sorted Set to implement Rate Limiter?
A: Look at this example code (generated by chatGPT)

import time
import redis

# Initialize Redis connection
r = redis.Redis(host='localhost', port=6379, db=0)

def is_rate_limited(client_id, window_seconds, max_requests):
    current_time = int(time.time()) # Get the current Unix timestamp
    key = f'rate_limiter:{client_id}' # Create a unique Redis key for the client

    # Remove timestamps that are outside the time window
    r.zremrangebyscore(key, '-inf', current_time - window_seconds)

    # Get the current request count for the client within the time window
    request_count = r.zcard(key)

    # Check if the request limit has been reached
    if request_count < max_requests:
        # Add the new request timestamp to the Sorted Set and set the expiration time
        r.zadd(key, {current_time: current_time})
        r.expire(key, window_seconds)
        return False # Not rate-limited
    else:
        return True # Rate-limited

# Example usage
client_id = '123.456.789.0'
window_seconds = 60
max_requests = 10

if is_rate_limited(client_id, window_seconds, max_requests):
    print('You have reached the maximum number of requests. Please try again later.')
else:
    print('Request allowed.')

Q: How does this command r.zadd(key, {current_time: current_time}) look like in redis-cli?
A:
ZADD command signature look like this

ZADD <key> <score> <member>

So the example should look like this

ZADD rate_limiter:123.456.789.0 1679251200 1679251200

Q: Why use current_time twice in r.zadd(key, {current_time: current_time})?
A:

• current_time (2) is used as score so that we can use zremrangebyscore to quickly remove out of range window
• current_time (1) is used as unique key, so we can count how many requests with zcard

Q: Do we really need to set expiry r.expire(key, window_seconds)?
A: We don’t but If clients never query again, zremrangebyscore won’t get call so expiry will remove stale data

Q: How does the sequence diagram of this function is_rate_limited look like?
A: