I could use some pseudo-code, or better, Python. I am trying to implement a rate-limiting queue for a Python IRC bot, and it partially works, but if someone triggers less messages than the limit (e.g., rate limit is 5 messages per 8 seconds, and the person triggers only 4), and the next trigger is over the 8 seconds (e.g., 16 seconds later), the bot sends the message, but the queue becomes full and the bot waits 8 seconds, even though it's not needed since the 8 second period has lapsed.
Here the simplest algorithm, if you want just to drop messages when they arrive too quickly (instead of queuing them, which makes sense because the queue might get arbitrarily large):
rate = 5.0; // unit: messages per = 8.0; // unit: seconds allowance = rate; // unit: messages last_check = now(); // floating-point, e.g. usec accuracy. Unit: seconds when (message_received): current = now(); time_passed = current - last_check; last_check = current; allowance += time_passed * (rate / per); if (allowance > rate): allowance = rate; // throttle if (allowance < 1.0): discard_message(); else: forward_message(); allowance -= 1.0;
There are no datastructures, timers etc. in this solution and it works cleanly :) To see this, 'allowance' grows at speed 5/8 units per seconds at most, i.e. at most five units per eight seconds. Every message that is forwarded deducts one unit, so you can't send more than five messages per every eight seconds.
rate should be an integer, i.e. without non-zero decimal part, or the algorithm won't work correctly (actual rate will not be
rate=0.5; per=1.0; does not work because
allowance will never grow to 1.0. But
rate=1.0; per=2.0; works fine.
Use this decorator @RateLimited(ratepersec) before your function that enqueues.
Basically, this checks if 1/rate secs have passed since the last time and if not, waits the remainder of the time, otherwise it doesn't wait. This effectively limits you to rate/sec. The decorator can be applied to any function you want rate-limited.
In your case, if you want a maximum of 5 messages per 8 seconds, use @RateLimited(0.625) before your sendToQueue function.
import time def RateLimited(maxPerSecond): minInterval = 1.0 / float(maxPerSecond) def decorate(func): lastTimeCalled = [0.0] def rateLimitedFunction(*args,**kargs): elapsed = time.clock() - lastTimeCalled leftToWait = minInterval - elapsed if leftToWait>0: time.sleep(leftToWait) ret = func(*args,**kargs) lastTimeCalled = time.clock() return ret return rateLimitedFunction return decorate @RateLimited(2) # 2 per second at most def PrintNumber(num): print num if __name__ == "__main__": print "This should print 1,2,3... at about 2 per second." for i in range(1,100): PrintNumber(i)