Improve the performance of SimpleRateThrottle

[mohsen-mahmoodi]

The time complexity of SimpleRateThrottle.allow_request algorithm for history cleanup is O(n) which it's suitable for applications with cache_keys that have high cardinality.

In my case, I was going to create a custom throttling class, and the cache_key is a specific part of the request.path for example:

def get_cache_key(self, request, view):
    """
     Returns specific part of the URL as the cache_key. The referral code pattern is /r/<referral_code>/
    """
    referral_code = [part for part in a.split('/') if part][1]

    return self.cache_format % {
        'scope': self.scope,
        'ident': referral_code
    }

Another example can be users coming from a single ISP when we're using AnonRateThrottle.

Let's imagine we use a throttling rate like 1000000/min

if we receive 99% of the requests in somewhere between 0 to 30 seconds, and the rest 10% at 59 to 60, the history of requests will be updated in the cache for another minute. Now after we receive another request in the next 30 seconds the history cleanup algorithm will do 1000000 comparisons, or O(num_requests).

If we use bisect_right to drop the right of the list we can reduce this complexity to O(log(n)) simply.

We need a descending bisect right implementation:

def bisect_right_descending(sorted_list, value):
    """
    Find the insertion point for `value` in the descending order list to maintain sorted order.
    """
    lo, high = 0, len(sorted_list)

    while lo < high:
        mid = (lo + high) // 2
        if sorted_list[mid] > value:  # Adjust comparison for descending order
            lo = mid + 1
        else:
            high = mid

    return lo

and to rewrite the SimpleRateThrottle.allow_request as:

def allow_request(self, request, view):
    ....
    # Drop any requests from the history which have now passed the
    # throttle duration
    bisect_right = bisect_right_descending(self.history, now - self.duration)
    self.history = history[:bisect_right]
    ...