• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

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

 
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Ranch Hand
Posts: 574
VI Editor Chrome Linux
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Saloon Keeper
Posts: 7611
177
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic