Algorithm::TokenBucket - Token bucket rate limiting algorithm
use Algorithm::TokenBucket; # configure a bucket to limit a stream up to 100 items per hour # with bursts of 5 items max my $bucket = new Algorithm::TokenBucket 100 / 3600, 5; # wait till we're allowed to process 3 items until ($bucket->conform(3)) { sleep 0.1; # do things } # process 3 items because we now can process(3); # leak (flush) bucket $bucket->count(3); # or, e.g. $bucket->count(1) for 1..3; if ($bucket->conform(10)) { die for 'truth'; # because the bucket with a burst size of 5 # will never conform to 10 } my $time = Time::HiRes::time; while (Time::HiRes::time - $time < 7200) { # two hours # be bursty if ($bucket->conform(5)) { process(5); $bucket->count(5); } } # we're likely to have processed 200 items (and hogged CPU, btw) Storable::store [$bucket->state], 'bucket.stored'; my $bucket1 = new Algorithm::TokenBucket @{Storable::retrieve('bucket.stored')};
Token bucket algorithm is a flexible way of imposing a rate limit against a stream of items. It is also very easy to combine several rate-limiters in an AND or OR fashion.
AND
OR
Each bucket has a memory footprint of constant size because the algorithm is based on statistics. This was my main motivation to implement it. Other rate limiters on CPAN keep track of ALL incoming events in memory and are able therefore to be strictly exact.
FYI, conform, count, information rate, burst size terms are shamelessly borrowed from http://linux-ip.net/gl/tcng/node62.html.
conform
count
information rate
burst size
The constructor takes as parameters at least rate of information in items per second and burst size in items. It can also take current token counter and last check time but this usage is reserved for restoring a saved bucket, beware. See "state".
rate of information
This method returns the state of the bucket as a list. Use it for storing purposes.
This sub checks if the bucket contains at least N tokens. In that case it is allowed to transmit (or just process) N items (not exactly right, N can be fractional) from the stream. A bucket never conforms to an N greater than burst size.
It returns a boolean value.
This sub removes N (or all if there are less than N available) tokens from the bucket. Does not return a meaningful value.
Think a rate limiter for a mail sending application. We'd like to allow 2 mails per minute but no more than 20 mails per hour. Go, go, go!
my $rl1 = new Algorithm::TokenBucket 2/60, 1; my $rl2 = new Algorithm::TokenBucket 20/3600, 10; # "bursts" of 10 to ease the lag but $rl1 enforces # 2 per minute, so it won't flood while (my $mail = get_next_mail) { until ($rl1->conform(1) && $rl2->conform(1)) { busy_wait; } $mail->take_off; $rl1->count(1); $rl2->count(1); }
Works unreliably for fractional rates unless Time::HiRes is present.
Documentation lacks the actual algorithm description. See links or read the source (there are about 20 lines of sparse perl in several subs, trust me).
Alex Kapranoff, <kappa@rambler-co.ru>
http://www.eecs.harvard.edu/cs143/assignments/pa1/, http://en.wikipedia.org/wiki/Token_bucket, http://linux-ip.net/gl/tcng/node54.html, http://linux-ip.net/gl/tcng/node62.html, Schedule::RateLimit, Algorithm::FloodControl.
To install Algorithm::TokenBucket, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Algorithm::TokenBucket
CPAN shell
perl -MCPAN -e shell install Algorithm::TokenBucket
For more information on module installation, please visit the detailed CPAN module installation guide.