Win a copy of Zero to AI - A non-technical, hype-free guide to prospering in the AI era this week in the Artificial Intelligence and Machine Learning forum!
  • 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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Paul Clapham
  • Bear Bibeault
  • Jeanne Boyarsky
Sheriffs:
  • Ron McLeod
  • Tim Cooke
  • Devaka Cooray
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Jj Roberts
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • salvin francis
  • Scott Selikoff
  • fred rosenberger

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

 
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • 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
  • 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: 9
  • Mark post as helpful
  • send pies
  • 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: 6630
161
Android Mac OS X Firefox Browser VI Editor Tomcat Server Safari
  • Likes 1
  • Mark post as helpful
  • send pies
  • 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
 
If you try to please everybody, your progress is limited by the noisiest fool. And this tiny ad:
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop
https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
reply
    Bookmark Topic Watch Topic
  • New Topic