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:
$$ \text{number of request} = \text{request in the current window} + \text{request in previous windows} \times \text{overlap percentage} $$

For example we have:

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:

• $\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