Sliding Windows Rate Rimiter

The ratelimiter used by the metrics string indexer to rate-limit DB writes.

As opposed to the API rate limiter, a limit in the “sliding window” rate limiter such as “10 requests / minute” does not reset to 0 every minute. Instead each window can be configured with a “granularity” setting such that the window gradually resets in steps of granularity seconds.

Additionally this rate-limiter is not coupled to per-project/organization scopes, and can apply multiple sliding windows at once. On the flipside it is not strongly consistent and depending on usage it is very easy to over-spend quota, as checking quota and spending quota are two separate steps.

Example

We want to enforce the number of requests per organization via two limits:

• 100 per 30-second

• 10 per 3-seconds

On every request, our API endpoint calls:

check_and_use_quotas(RequestedQuota(
    prefix=f"org-id:{org_id}"
    quotas=[
        Quota(
            window_seconds=30,
            limit=100,

            # can be arbitrary depending on how "sliding" the sliding
            # window should be. This one configures per-10-second granularity
            # to make the example simpler
            granularity=10,
        ),
        Quota(
            window_seconds=3,
            limit=10,
            granularity=1,
        )
    ]
))

For a request happening at time 900 for org_id=123, the redis backend checks the following keys:

sliding-window-rate-limit:123:3:900
sliding-window-rate-limit:123:3:899
sliding-window-rate-limit:123:3:898
sliding-window-rate-limit:123:30:90
sliding-window-rate-limit:123:30:89
sliding-window-rate-limit:123:30:88

…none of which exist, so the values are assumed 0 and the request goes through. It then sets the following keys:

sliding-window-rate-limit:123:30:90 += 1
sliding-window-rate-limit:123:3:900 += 1

Another request for the same org happens at time 902.

• The keys starting with :123:30: sum up to 1, so the 30-second limit of 100 is not exceeded.

• The keys starting with :123:3: sum up to 1, so the 3-second limit of 10 is not exceeded.

This request is granted the minimum allowed from the two requested, in this case that is 9 (3-second limit of 10 - 1 used)

Because no quota is exceeded, the request is granted. If one quota summed up to 100 or 10, respectively, the request would be rejected.

When using the quotas, the keys change as follows:

sliding-window-rate-limit:123:3:900 = 1
sliding-window-rate-limit:123:3:902 = 1
sliding-window-rate-limit:123:30:90 = 2

class sentry_redis_tools.sliding_windows_rate_limiter.GrantedQuota(prefix, granted, reached_quotas)

exception sentry_redis_tools.sliding_windows_rate_limiter.InvalidConfiguration

class sentry_redis_tools.sliding_windows_rate_limiter.Quota(window_seconds, granularity_seconds, limit, prefix_override=None)

iter_window(request_timestamp)

Iterate over the quota’s window, yielding values representing each (absolute) granule.

This function is used to calculate keys for storing the number of requests made in each granule.

The iteration is done in reverse-order (newest timestamp to oldest), starting with the key to which a currently-processed request should be added. That request’s timestamp is request_timestamp. :rtype: Iterator[int]

• request_timestamp / self.granularity_seconds - 1

• request_timestamp / self.granularity_seconds - 2

• request_timestamp / self.granularity_seconds - 3

• …

limit: int

How many units are allowed within the given window.

class sentry_redis_tools.sliding_windows_rate_limiter.RedisSlidingWindowRateLimiter(client)

The main class to instantiate for the rate limiter.

Example usage:

quotas = [
    Quota(
        window_seconds=10,
        granularity_seconds=1,
        limit=10,
    )
]

for timestamp in range(10):
    resp = limiter.check_and_use_quotas(
        [RequestedQuota(prefix="foo", requested=1, quotas=quotas)],
        timestamp=TIMESTAMP_OFFSET + timestamp,
    )
    assert resp == [GrantedQuota(prefix="foo", granted=1, reached_quotas=[])]

resp = limiter.check_and_use_quotas(
    [RequestedQuota(prefix="foo", requested=1, quotas=quotas)],
    timestamp=TIMESTAMP_OFFSET + 9,
)
assert resp == [GrantedQuota(prefix="foo", granted=0, reached_quotas=quotas)]

check_and_use_quotas(requests, timestamp=None)

Check the quota requests in Redis and consume the quota in one go. See check_within_quotas for parameters.

Return type:

Sequence[GrantedQuota]

check_within_quotas(requests, timestamp=None)

Check whether the given requests are within quota, but do not actually consume quota.

Consuming the quota is done via use_quotas(), and should be done after the protected resource has actually been consumed.

Return type:

Tuple[int, Sequence[GrantedQuota]]

use_quotas(requests, grants, timestamp)

Actually use up quotas after checking them using check_within_quotas() and consuming the underlying resource.

If you don’t care for this two-step dance, use check_and_use_quotas().

Return type:

None

class sentry_redis_tools.sliding_windows_rate_limiter.RequestedQuota(prefix, requested, quotas)