Thoughts on Rate Limiting algorithm with request rate not per unit of time

[Ron Foster]

Hello,  

I am trying to find an implement a rate limiting algorithm where the rate limit is not per unit of time. For instance, let's say our service needs to allow 8 requests every 4 seconds. I am thinking this won't be the same as saying 2 requests per second. I tried searching online but couldn't find one which accepts a variable rate limit. I was thinking of using Token Bucket Algorithm but am confused as to how to accommodate the variable limit? Like currently, it just adds tokens based on the constant rate. I can't use any 3rd party library. Any thoughts/pointers/suggestions?

Thanks.

[Jim Venolia]

Google trailing average, or moving average.  One of those should do the trick.

The question is what happens when you exceed the limit.  Do you drop the token, or make a queue of tokens waiting?  If the queue fills up what then?

You might want to read up on networking also.  The hardware can send at a certain max rate, packets get queued up to handle bursts.  Make the queue too large and you get something called buffer bloat, which is bad.

[Ron Foster]

Jim Venolia wrote:Google trailing average, or moving average.  One of those should do the trick.

The question is what happens when you exceed the limit.  Do you drop the token, or make a queue of tokens waiting?  If the queue fills up what then?

You might want to read up on networking also.  The hardware can send at a certain max rate, packets get queued up to handle bursts.  Make the queue too large and you get something called buffer bloat, which is bad.

Thanks for the quick response. I will look into those. When the rate exceeds the limit then we stop responding for x seconds on that end point alone (different end points are supposed to have different allowable rates). I was thinking of dropping the request(s) as soon as the threshold is crossed and accept the first one in after x seconds.

[Tim Moores]

A cache that removes entries after 8 seconds would also work. See https://github.com/jhalterman/expiringmap for one possible approach to that, or something like https://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/map/PassiveExpiringMap.html