/ 
Algorithm-TokenBucket-0.38
River stage one • 4 direct dependents • 6 total dependents
⭐ Starred 2 GitHub stars
/ README.md

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 = Algorithm::TokenBucket->new(100 / 3600, 5);

# wait until we are 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);  # same as $bucket->count(1) for 1..3;

if ($bucket->conform(10)) {
    die;
    # because a bucket with the 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)

Storable::store $bucket, 'bucket.stored';
my $bucket1 =
    Algorithm::TokenBucket->new(@{Storable::retrieve('bucket.stored')});

DESCRIPTION

The 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 constant memory footprint because the algorithm is based on the information rate. Other rate limiters may keep track of ALL incoming items in memory. It allows them to be more accurate.

FYI, the conform, count, information rate, and burst size terms are taken from the metering primitives page of the Linux Traffic Control - Next Generation system documentation.

INTERFACE

METHODS

EXAMPLES

Imagine a rate limiter for a mail sending application. We would like to allow 2 mails per minute but no more than 20 mails per hour.

my $rl1 = Algorithm::TokenBucket->new(2/60, 1);
my $rl2 = Algorithm::TokenBucket->new(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 the "until($)" method.

my $bucket = Algorithm::TokenBucket->new(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

Documentation lacks the actual algorithm description. See links or read the source (there are about 20 lines of sparse Perl in several subs).

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.

Paul Cochrane contributed various documentation and infrastructure fixes.

COPYRIGHT AND LICENSE

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

This is free software; you can redistribute it and/or modify it under the terms GNU General Public License version 3.

AUTHOR

Alex Kapranoff, <alex@kapranoff.ru>

SEE ALSO