Smooth out requests to rate limitted API

Question

        wasted requests     not enough time for those requests
                 |                       |
                 |                       |
(1) |-x--x-----------------x----x--x--x| x  x   (executing requests)
      ..                   .    .....           (sending requests)
(2) |-x--x-----------------x----xxxx-x-|        (executing requests)

(3) |xx-x--x--x---x---x----x----x-----x|        (executing requests, ideal)

I'm trying to figure out when to send requests to an API that would be spaced as much consistently as possible.

The most straght-forward solution would be to keep the requests spaced enough so that the API wouldn't throttle (1). However this technique wastes a lot of requests.

I came up with the idea to let the requests run a lot more quickly when there's a lot of space left and slow down when at the end (3). However when the API after the interval received its 120th request in the last minute, the requests were too slow. It'd be optimal to send the every 0.5 seconds (60/120), but my script was sending them every 0.85 seconds.

How would I accomplish something similar to the example show in (2)?

Edit: Here's the code I tried. It's a lot finnicky.

class Limitter:
    def __init__(self, num, interval, minimal=.2):
        self.num = num
        self.interval = interval
        self.minimal = minimal

        self._next = None

        self._requests = []
        self._lock = Lock()

    def _get_duration(self):
        now = time.time()
        self._requests = filter(lambda x: now - x < self.interval, self._requests)

        if len(self._requests) < 2:     # if not enough requests stored, return interval / num
            return float(self.interval) / self.num
        else:
            oldest = self._requests[0]
            newest = self._requests[-1]
            req_left = self.num - len(self._requests)

            if self.num == len(self._requests):             # if num reached, do this. It doesn't work at all
                return max(.5, oldest - (now - 60) + .4)    # tried to hotfix with some constants

            time_left = float(oldest + self.interval - newest)
            unit_time = time_left / req_left
            slant = -1.4 / self.num * req_left + 1.7        # slant that enables the different timing (first short, then long)(just a linear function)
            return unit_time * slant

    def acquire(self):
        with self._lock:
            now = time.time()

            if self._next:
                duration = self._next - time.time()
                if duration > 0:
                    time.sleep(duration)

            delta = self._get_duration()
            self._requests.append(time.time())
            self._next = time.time() + delta

if __name__ == '__main__':
    l = Limitter(120, 60)

    for i in range(240):
        l.acquire()

I'm developing an "API" for Hypixel API. They have a limit of 120 requests per minute. The requests are just communicating with the official API. I'm just trying to get information as fast as possible. I don't think the limit is there to protect the API from me.

Answer 1

I didn't analyze your solution completely, but it looks a bit too complicated in my opinion. I'd simply keep the last 120 request timestamps (as you do) and delay each request that would be less than 60 seconds after the 120th request before. Then you will be able to handle bursts but still ensure that there are never more than 120 requests within any 60-second interval. If the user manages to create 120 requests within 30 seconds, he/she will have to wait half a minute before the next one can be processed. If you set a minimum delay between requests you will reduce maximum burst frequency, but users with intermittent bursts and pauses will be at a slight disadvantage. In practice, this might not make a real difference, though.