Jun 17, 2024redis python

Beach Volleyball Scores

Life's a garden. Dig it.

Challenge¶

You recently developed a REST API that lets people fetch scores and details about 🏐 beach volleyball games. Unfortunately, some people are abusing the API, making hundreds of requests per second 😤!

In order to protect your servers, implement a sliding window API rate limiter that works like this..

Each request to your API has an associated API key.
Each API key is allowed to make up to 5 requests in any 10-second window.

Exclude denied requests from each key's quota. In other words, if a key makes a request every second for 60 seconds, 30 of its requests should be allowed (5 allowed, then 5 denied, then 5 allowed, then 5 denied, ...).

Starter Code

def allow_request(api_key: str):
    """
    Check if this api key is allowed to make a request right now.
    :return: True or False
    """
 
    pass

Solution¶

Stream

import datetime
import redis
 
def allow_request(api_key: str):
    """
    Check if this api key is allowed to make a request right now.
    :return: True or False
    """
 
    # Get the current Unix epoch time. (number of seconds since 1970-01-01 00:00:00 UTC)
    now = datetime.datetime.now(tz=datetime.timezone.utc).timestamp()
 
    # Connect to redis
    r = redis.Redis(host="localhost", port=6379, db=0, decode_responses=True)
 
    # Define redis key
    key = f'api-calls-log:{api_key}'
 
    # Fetch the stream (if it exists)
    if (stream := r.xrange(key, min="-", max="+")) is not None:
 
        # If the stream has length 5 and the last element is within 10 seconds, return False
        if len(stream) >= 5 and now - float(stream[0][0].split('-')[0])/1000 <= 10:
            return False
 
    # Insert one row into the stream with irrelevant, dummy values.
    # (The only thing we care about is the auto-generated timestamp id..)
    r.xadd(name=key, fields={'': ''}, maxlen=5, approximate=False)
 
    return True

Tests

import time
 
# Make one api call every second
# The first 5 calls should be allowed, the next 5 should be blocked, ...
for i in range(20):
    print(allow_request(api_key="test"))
    time.sleep(1)
 
# True
# True
# True
# True
# True
# False
# False
# False
# False
# False
# True
# True
# True
# True
# True
# False
# False
# False
# False
# False

Explanation

This solution relies on a redis stream. Redis streams act like an append only log. Furthermore, we can restrict the size of a stream, and redis automatically tracks the time each stream entry gets added. 🙌 We can leverage these properties to implement our rate limiter with the following algorithm..

First, check if the stream exists. If it doesn't, allow the request and create the stream with its first entry. Initially it might look like this

('1662818315896-0', {'': ''})

Breakdown

1662818315896-0 is the auto-generated id of the entry.
- 1662818315896 is the number of milliseconds since 1970-01-01 00:00:00 UTC.
- -0 is a sequential id, in case we happened to insert multiple elements within the same millisecond.
{'': ''} is the key-value pair for this entry. (For our purposes, this data is not needed, so we use empty strings.)

As the user makes more requests, the stream continues to grow..

('1662818319931-0', {'': ''})  <- newest
('1662818318921-0', {'': ''})
('1662818317912-0', {'': ''})
('1662818316907-0', {'': ''})
('1662818315896-0', {'': ''})  <- oldest

If we restrict the stream to a max size of 5, then each new stream element will push the oldest element out of the stream!

{++('1662818320945-0', {'': ''})++}  <- added
('1662818319931-0', {'': ''})
('1662818318921-0', {'': ''})
('1662818317912-0', {'': ''})
('1662818316907-0', {'': ''})
{--('1662818315896-0', {'': ''})--} <- removed

So, how do we impose the rate limit?
When a new API request comes in, we block the request if

the stream has 5 elements and
the oldest stream element was created less than 10 seconds ago.

Otherwise, we allow the request and insert a new entry into the stream.

Sorted Set

import datetime
import redis
 
def allow_request(api_key: str):
    """
    Check if this api key is allowed to make a request right now.
    :return: True or False
    """
 
    # Get the current Unix epoch time. (number of seconds since 1970-01-01 00:00:00 UTC)
    now = datetime.datetime.now(tz=datetime.timezone.utc).timestamp()
 
    # Connect to redis
    r = redis.Redis(host="localhost", port=6379, db=0, decode_responses=True)
 
    # Define redis key
    key = f'api-calls-log:{api_key}'
 
    # Remove elements older than 10 seconds
    r.zremrangebyscore(name=key, min=-1, max=now - 10)
 
    # Check if the sorted set has >= 5 elements
    if (n := r.zcount(name=key, min=-1, max=now)) >= 5:
        return False
 
    # Insert element into sorted set representing this request
    r.zadd(name=key, mapping={str(now): now}, ex)
 
    return True

Tests

import time
 
# Make one api call every second
# The first 5 calls should be allowed, the next 5 should be blocked, ...
for i in range(20):
    print(allow_request(api_key="test"))
    time.sleep(1)
 
# True
# True
# True
# True
# True
# False
# False
# False
# False
# False
# True
# True
# True
# True
# True
# False
# False
# False
# False
# False

Explanation

This solution relies on a redis sorted set. Sorted sets let you store a collection of unique strings, each with an associated score which can be used to sort the collection's elements, fetch elements by range, remove elements by range, etc.

In our case, we create a sorted set for each API key. Each sorted set has one element per allowed API request. We set the name and score of each element as the Unix epoch time of the request (i.e. the number of seconds since 1970-01-01 00:00:00).

For example, the API key 123 might have a sorted set like this.

('1662833710.562739', 1662833710.562739)
('1662833711.57193', 1662833711.57193)
('1662833712.580853', 1662833712.580853)
('1662833713.589906', 1662833713.589906)
('1662833714.59408', 1662833714.59408)

When a new request comes in, we remove elements from the sorted set which are more than 10 seconds old. Then we check the length of the sorted set. If the length is >= 5, we deny the request. Otherwise, we allow the request and insert a new element into the sorted set (representing the time of this new request).