Distributed rate limiting algorithm
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.
Answer
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.