Cloudflare's approximation of the moving window algorithm (= Sliding Window Counter?)

[Merinorus]

Hi,

I was learning about rate limiters and found this article from the Cloudflare blog. It explains how they built a limiter that:

• is a good approximation of the moving window algorithm,
• is much more memory efficient than the moving window algorithm (2x more memory than the fixed window algorithm at most)
• is quite simple to understand, compared to the moving window or the GCRA algorithm.

I find this very interesting, as I currently use the moving window algorithm in production and I would like to optimize the RAM usage. I tried to make a POC that implements their article. It seems to be working with an in-memory limiter (10 requests per 10 seconds):

INFO:     Application startup complete.
Counter incremented.
previous window expires: 0
current  window expires: 19.999830722808838
previous window counter: 0
current  window counter: 1
Approximated    counter: 1
INFO:     127.0.0.1:34904 - "GET /home HTTP/1.1" 200 OK
Counter incremented.
previous window expires: 0
current  window expires: 19.965747594833374
previous window counter: 0
current  window counter: 2
Approximated    counter: 2
INFO:     127.0.0.1:34904 - "GET /home HTTP/1.1" 200 OK
Counter incremented.
previous window expires: 0
current  window expires: 19.735856771469116
previous window counter: 0
current  window counter: 3
Approximated    counter: 3
INFO:     127.0.0.1:34904 - "GET /home HTTP/1.1" 200 OK
Counter incremented.
previous window expires: 0
current  window expires: 19.639801025390625
previous window counter: 0
current  window counter: 4
Approximated    counter: 4
INFO:     127.0.0.1:34904 - "GET /home HTTP/1.1" 200 OK
Counter incremented.
previous window expires: 0
current  window expires: 19.456570386886597
previous window counter: 0
current  window counter: 5
Approximated    counter: 5
INFO:     127.0.0.1:34904 - "GET /home HTTP/1.1" 200 OK
Counter incremented.
previous window expires: 0
current  window expires: 19.257863759994507
previous window counter: 0
current  window counter: 6
Approximated    counter: 6
INFO:     127.0.0.1:34904 - "GET /home HTTP/1.1" 200 OK
Counter incremented.
previous window expires: 0
current  window expires: 19.093891620635986
previous window counter: 0
current  window counter: 7
Approximated    counter: 7
INFO:     127.0.0.1:34904 - "GET /home HTTP/1.1" 200 OK
Counter incremented.
previous window expires: 0
current  window expires: 18.8642418384552
previous window counter: 0
current  window counter: 8
Approximated    counter: 8
INFO:     127.0.0.1:34904 - "GET /home HTTP/1.1" 200 OK
Counter incremented.
previous window expires: 0
current  window expires: 17.358734130859375
previous window counter: 0
current  window counter: 9
Approximated    counter: 9
INFO:     127.0.0.1:34904 - "GET /home HTTP/1.1" 200 OK
Counter incremented.
previous window expires: 0
current  window expires: 17.09188961982727
previous window counter: 0
current  window counter: 10
Approximated    counter: 10
INFO:     127.0.0.1:34904 - "GET /home HTTP/1.1" 200 OK
Counter incremented.
previous window expires: 0
current  window expires: 16.68333125114441
previous window counter: 0
current  window counter: 11
Approximated    counter: 11
INFO:     127.0.0.1:34904 - "GET /home HTTP/1.1" 429 Too Many Requests
Counter incremented.
previous window expires: 0
current  window expires: 15.86026406288147
previous window counter: 0
current  window counter: 12
Approximated    counter: 12
INFO:     127.0.0.1:34904 - "GET /home HTTP/1.1" 429 Too Many Requests
Counter incremented.
previous window expires: 0
current  window expires: 12.376554012298584
previous window counter: 0
current  window counter: 13
Approximated    counter: 13
INFO:     127.0.0.1:34904 - "GET /home HTTP/1.1" 429 Too Many Requests
Current window time elapsed, move the counter to the previous window.
Counter incremented.
previous window expires: 8.99974513053894
current  window expires: 18.99987530708313
previous window counter: 13
current  window counter: 1
Approximated    counter: 13
INFO:     127.0.0.1:34904 - "GET /home HTTP/1.1" 429 Too Many Requests
Counter incremented.
previous window expires: 6.391803741455078
current  window expires: 16.391934633255005
previous window counter: 13
current  window counter: 2
Approximated    counter: 11
INFO:     127.0.0.1:34904 - "GET /home HTTP/1.1" 429 Too Many Requests
Counter incremented.
previous window expires: 3.016955614089966
current  window expires: 13.017089128494263
previous window counter: 13
current  window counter: 3
Approximated    counter: 7
INFO:     127.0.0.1:34904 - "GET /home HTTP/1.1" 200 OK
Counter incremented.
previous window expires: 1.4776816368103027
current  window expires: 11.47780728340149
previous window counter: 13
current  window counter: 4
Approximated    counter: 6
INFO:     127.0.0.1:34904 - "GET /home HTTP/1.1" 200 OK
Counter incremented.
previous window expires: 0.4189605712890625
current  window expires: 10.419093608856201
previous window counter: 13
current  window counter: 5
Approximated    counter: 6
INFO:     127.0.0.1:34904 - "GET /home HTTP/1.1" 200 OK
Current window time elapsed, move the counter to the previous window.
Counter incremented.
previous window expires: 8.999818563461304
current  window expires: 18.999898672103882
previous window counter: 5
current  window counter: 1
Approximated    counter: 6
INFO:     127.0.0.1:34904 - "GET /home HTTP/1.1" 200 OK

Of course, the implementation is "naive". I guess the actions should be atomic. I am a simple user of Redis and MongoDB but I could try to look at a proper implementation.

Is it worth going further?

Thank you for your attention!

Edit: seems like it's just the Sliding window counter algorithm, it wasn't invented by Cloudflare.

[alisaifee]

This is definitely worth looking into. I have come across this in the past and the memory efficiency with a minor trade off in accuracy with respect to the existing moving window implementation is quite significant, but I didn't have time to look into how to make it work atomically with the various backend storages at the time.

For testing I would recommend updating https://github.com/alisaifee/limits/blob/master/tests/test_strategy.py & https://github.com/alisaifee/limits/blob/master/tests/aio/test_strategy.py (copy paste a few of the fixed window tests) - and that would allow you to test across the different storages.

I did take your branch for a quick test and for basic use cases it actually worked out of the box for all the supported storages (since you're using existing storage methods this was somewhat expected).