NAME

Algorithm::TokenBucket - Token bucket rate limiting algorithm

SYNOPSIS

    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, 'bucket.stored';
    my $bucket1 = new Algorithm::TokenBucket
            @{Storable::retrieve('bucket.stored')};

DESCRIPTION

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.

Each bucket has a memory footprint of constant size because the algorithm is based on information rate. This was my main motivation to implement it. Other rate limiters on CPAN keep track of ALL incoming items in memory. It allows them to be precisely accurate.

FYI, conform, count, information rate, burst size terms are shamelessly borrowed from http://linux-ip.net/gl/tcng/node62.html page.

INTERFACE

METHODS

new($$;$$)

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".

state()

This method returns the state of the bucket as a list. Use it for storing purposes. Buckets also natively support freezing and thawing with Storable by providing STORABLE_* callbacks.

conform($)

This sub checks if the bucket contains at least N tokens. In that case it is allowed to transmit (or process) N items (not exactly right because N can be fractional) from the stream. A bucket never conforms to an N greater than burst size.

It returns a boolean value.

count($)

This sub removes N (or all if there are less than N available) tokens from the bucket. Does not return a meaningful value.

until($)

This sub returns the number of seconds until N tokens can be removed from the bucket. It's especially useful in multitasking environments like POE where you cannot busy-wait. One can safely schedule the next conform($N) check in until($N) seconds instead of checking repeatedly.

Note that until() does not take into account burst size. That means a bucket will not conform to N even after sleeping for until($N) seconds if N is greater than burst size.

get_token_count()

Returns the current number of tokens in the bucket. This method may be useful for inspection or debugging purposes. You should not examine the state of the bucket for rate limiting purposes.

This number will frequently be fractional so it's not exactly a "count".

EXAMPLES

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);
    }

Now, let's fix the CPU-hogging example from "SYNOPSIS" using "until()" method.

    my $bucket = new Algorithm::TokenBucket 100 / 3600, 5;
    my $time = Time::HiRes::time;
    while (Time::HiRes::time - $time < 7200) {  # two hours
        # be bursty
        Time::HiRes::sleep $bucket->until(5);
        if ($bucket->conform(5)) {  # should always be true
            process(5);
            $bucket->count(5);
        }
    }
    # we're likely to have processed 200 items (without hogging the CPU)

BUGS

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).

until($N) does not return infinity if $N is greater than burst size. Sleeping for infinity seconds is both useless and hard to debug.

ACKNOWLEDGMENTS

Yuval Kogman contributed the "until" method, proper Storable support and other things.

Alexey Shrub contributed the "get_token_count" method.

COPYRIGHT AND LICENSE

This software is copyright (C) 2012 by Alex Kapranoff.

This is free software; you can redistribute it and/or modify it under the same terms as the Perl 5 programming language system itself.

AUTHOR

Alex Kapranoff, <kappa@cpan.org>

SEE ALSO

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.