Sliding Window Counter Algorithm

Combine the Fixed window counter algorithm and Sliding window log algorithm

We introduce a new formula for the request that comes in the edge case:
number of request=request in the current window+request in previous windows×overlap percentage \text{number of request} = \text{request in the current window} + \text{request in previous windows} \times \text{overlap percentage}

For example we have:

Pasted image 20230321174225.png

And there are 5 requests in the previous minute. And in the current minute, we currently have 3 requests so far.

If new request come in, according to the formula, we have:

  • number of requests=3+5×70\text{number of requests} = 3 + 5\times 70% = 6.5
  • Now we can decide to round up or down based on our algorihtm. Let's say initially we decide all the requests to be rounded down, therefore we have 6 requests
  • Let's say our rate limitor allows maximum of 7 requests (soft rate limiting) per minute, we can take 1 more request

Pros and Cons

Pros

  • Memory efficiency
  • Solution for edge case for sliding windows

Cons

  • Sometimes it's inaccurate because it assume in the previous windows the requests are distributed evenly. But the error rates are very low based on an experiments done by CloudFlare