Sliding Window Counter is a hybrid solution that combines Fixed Window Counter and Sliding Window Log.
Fixed Window Counter is not a robust rate-limiting solution because it can’t correctly handle burst requests. But It is a memory-efficient solution. Sliding Window Log is a powerful solution since it enforces a hard limit on every time window. However, It isn’t memory efficient solution.
Sliding Window Counter tries to achieve efficient memory usage and a robust rate-limiting solution. Let’s first rewind the fixed window counter solution.
The fixed window counter algorithm is memory efficient because it only needs to count requests. However, we want to use a sliding window to make the rate limiter more robust.
However, the problem is that since we only know the counter in each fixed time window, the sliding window doesn’t know how many requests are in it.
Here is the simple solution. Let’s calculate the weighted counter for the previous fixed time window. Then, we can estimate how many requests are in the current sliding window. In the above example, we can calculate like the below.
- previous_window_request_count = 8
- current_window_request_count = 5
- previous_window_count_weight = 0.47
- Hence, 8 * 0.47 + 5 = 8.76
We just estimated that there are 8.76 requests in the current sliding window. I floored this calculation result for my simple implementation below.
The above is the simple implementation for a sliding window counter. I calculated prev_window_weight and calculated estimation counts in the current sliding window.
Please note that to make this solution memory efficient, you’d better remove unused keys in the hashmap. To make my implementation simple, I didn’t include such optimization.
I tried 1000 TPS requests to the 10 LIMIT sliding window counter implementation. And it works amazingly. I can’t find any flickering on my logs.
Summary
Sliding Window Counter is a robust and memory-efficient rate-limiting algorithm. However, no algorithm is perfect. Since it estimates the current sliding window counter by portion, It is not strictly correct estimation.
Cloudflare uses this solution, and its article is fantastic. Please check -> How we built rate limiting capable of scaling to millions of domains. The blog shares test results in the real environment, and the rate-limiter only allows 0.003% of requests have been wrongly allowed.
Thanks for reading this post :)
