6

I am working on a pricing platform on wich I have to implement a distributed rate limiting algorithm. I have k gateways that provide x services. Any gateway can provide any service (via a load balancer). A customer buy a number of call per second to a service, its call could be routed through any gateway. So, is somebody knowing a good algorithm to update call counters on all gateways in order to limit customer calls?

Two important indicators, regarding this algorithm, are the network overhead and the deviation between the number of accepted calls and the rate limit.

Thanks!

Edit I just want to know if there is a "well-known" algorithm.

7
  • 1
    what algorithms have you tried that the answer wasn't within your bounds?
    – Woot4Moo
    Nov 16, 2012 at 20:47
  • 1
    I am studying the problem, I did not implement any algorithm for the moment because I don't know existing algorithm. We can easily imagine a naive algorithm that sends its counter after each call to inform other gateways that it received a call and then decrease all other counters but if the rate limit is around 10 000 calls per second, the network overhead is terrible. Another case could be the reate limit < the number of gateway and then imply counter broadcast after any call. Nov 16, 2012 at 20:53
  • If you know distributed rate limiting algorithms, give me their names :p Nov 16, 2012 at 20:58
  • 1
    You have put no effort into your research. Do not expect others to care about something that you yourself are not passionate about.
    – Woot4Moo
    Nov 16, 2012 at 21:01
  • Okay, I don't know exactly why you are answering my question in this way but I can give you numerous research articles dealing with this topic (goo.gl/L5tqf, goo.gl/wnGjw, goo.gl/PUA4r, etc.). My problem is nobody cares about network overhead. I just asked this question because I wanted to know if somebody had ever consider my metrics or if somebody had an experience return regarding my problem. And thanks for your link but I know Google and I know how to use it ;-) Nov 16, 2012 at 21:11

1 Answer 1

4

I've implemented a solution based on this article (archive.org). I think the algorithm is called Leaky Bucket but it works fine. It's not perfect since it allows the entire quota to be used in a burst, but overall it's very fast with node.js and Redis. The difference between accepted requests and rate can be quite high and depend on the ratio between sample window and bucket size.

4
  • 1
    Thanks a lot, I will implement this algorithm and check if is in my bounds :-) Nov 17, 2012 at 12:38
  • The link given for the article no longer appears to be available.
    – lrAndroid
    May 26, 2015 at 17:51
  • @IrAndroid: Fixed the link to point to archive.org.
    – mhvelplund
    May 27, 2015 at 7:01
  • The article mentioned by @mhvelplund can be found here. Jun 1, 2016 at 22:36

Not the answer you're looking for? Browse other questions tagged or ask your own question.