Beach Volleyball Scores 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

mystream

('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..

mystream

('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!

mystream

('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

1. the stream has 5 elements and
2. 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.

API key 123 sorted set

('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).

---

Back