Should the leaky bucket implementation should have timer-interrupt based implementation to leak the requests to be processed accurately? In current implementation it leaks at every new request, if the time gap b/w requests is huge that would lead to starvation of requests to be processed.
There is a common misunderstanding about Fixed Window algorithm.
It isn't necessary to connect window boundaries to calendar intervals. Fixed Window doesn't start at 01:30 and ends at 01:31. It starts when the first request arrives and lasts for 1 minute. So it is impossible to send all requests in the end of time frame and then all requests at the beginning of next time frame. The problem is not that bad as it seems.
On the countrary, in almost every article, authors write that there is boundary problem, like x2 traffic bursts. The same people say that Token Bucket is good because it allows traffic bursts. So why traffic bursts is bad for Fixed Window and good for Token Bucket? Do you find it contradictive? I do.
For token bucket alog especially java logic the bucket is getting filled according to milliseconds, but i have doubt for rate limiting, doesn't we have to set it at the end of the seconds?
If yes we are setting at the end of the second then this algorithm will fail when there are multiple requests and if the bucket didn't have enough tokens it should reject the request as there are no enough tokens and if time has elapsed it should refill the bucket. But in given code as we are filling the bucket each time services get requests even though it didn't have enough tokens.
we have to add below condition in refill function -
I think that your implementation of sliding window counter is not correct because of your calculation based on the following:
Window Transition Logic:
The logic moves to a new window if the elapsed time (timePassedInWindow) exceeds the windowSizeInSeconds.
If the elapsed time is much greater than the window size (size 15 seconds and elapsed time e.g.100 seconds), it effectively considers the last "previous window" as still valid. The previousWindowCount is updated with the currentWindowCount regardless of the gap.
Weighted Count:
The calculation combines a weighted count of the previous window and the current window. This includes the current window’s elapsed time and the proportion of the previous window that overlaps with the sliding window.
Handling Long Gaps:
When long gaps occur e.g. above 100 seconds between last and current request with 15 seconds window, the previous window’s count remains part of the calculation, even if its relevance has expired due to the large time gap.
Nice post!!
Should the leaky bucket implementation should have timer-interrupt based implementation to leak the requests to be processed accurately? In current implementation it leaks at every new request, if the time gap b/w requests is huge that would lead to starvation of requests to be processed.
Hey. Good visuals.
There is a common misunderstanding about Fixed Window algorithm.
It isn't necessary to connect window boundaries to calendar intervals. Fixed Window doesn't start at 01:30 and ends at 01:31. It starts when the first request arrives and lasts for 1 minute. So it is impossible to send all requests in the end of time frame and then all requests at the beginning of next time frame. The problem is not that bad as it seems.
On the countrary, in almost every article, authors write that there is boundary problem, like x2 traffic bursts. The same people say that Token Bucket is good because it allows traffic bursts. So why traffic bursts is bad for Fixed Window and good for Token Bucket? Do you find it contradictive? I do.
Read more on Fixed Window algorithm here
https://github.com/animir/node-rate-limiter-flexible/wiki/Fixed-Window-rate-limiting-algorithm-explained
For token bucket alog especially java logic the bucket is getting filled according to milliseconds, but i have doubt for rate limiting, doesn't we have to set it at the end of the seconds?
If yes we are setting at the end of the second then this algorithm will fail when there are multiple requests and if the bucket didn't have enough tokens it should reject the request as there are no enough tokens and if time has elapsed it should refill the bucket. But in given code as we are filling the bucket each time services get requests even though it didn't have enough tokens.
we have to add below condition in refill function -
if (elapsedSecondFromLastRefill <= 0) {
System.out.println("No refill needed, elapsed seconds: " + elapsedSecondFromLastRefill);
return;
}
correct me if I am wrong?
I think that your implementation of sliding window counter is not correct because of your calculation based on the following:
Window Transition Logic:
The logic moves to a new window if the elapsed time (timePassedInWindow) exceeds the windowSizeInSeconds.
If the elapsed time is much greater than the window size (size 15 seconds and elapsed time e.g.100 seconds), it effectively considers the last "previous window" as still valid. The previousWindowCount is updated with the currentWindowCount regardless of the gap.
Weighted Count:
The calculation combines a weighted count of the previous window and the current window. This includes the current window’s elapsed time and the proportion of the previous window that overlaps with the sliding window.
Handling Long Gaps:
When long gaps occur e.g. above 100 seconds between last and current request with 15 seconds window, the previous window’s count remains part of the calculation, even if its relevance has expired due to the large time gap.