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.