CODEWITHSUNDEEP
javascriptalgorithm
Michael Joseph Aubry
Michael Joseph Aubry

Reputation: 13452

token bucket algorithm, rate limiting javascript?

I am trying to write an algorithm to prevent more than 5 messages being sent in 8 seconds, I found the formula for the token bucket algorithm in python, so I am trying to implement it with javascript but I am missing one thing.

The last_check variable isn't clear to me. If I track 60 seconds in a minute the problem is when it loops back over after the 59th second the math is thrown off.

First iteration

If last_check = new Date().getSeconds() let's say that it's the 33 second in the minute it tracks, we are now comparing to the 33 second.

When the rateLimit() function executes it gets the current time of when it has been called, a message for example, and the current new Date().getSeconds() is 40 seconds for example.... 7 seconds after last_check

So time_passed is now 7 seconds, last_checked becomes 40.

allowance result

The allowance is 7 * (5.0/8.0) = 4.375.

Where the problem lies

If last_checked stays at 40, and 22 seconds pass until a new message, then the formula for the second iteration below becomes.

Second iteration

current becomes 2 (40+22) the new Date().getSeconds() loops back to 2... time_passed is now (2-40) = -38 seconds, last_checked is now 2.

allowance result

The allowance is -38 * (5.0/8.0) = -23.75.

var rate = 5.0; // unit: messages
var per = 8.0; // unit: seconds
var allowance = rate; // unit: messages
var last_check = new Date().getSeconds();

function rateLimit() {
    current = new Date().getSeconds(); // floating-point, e.g. usec accuracy. Unit: seconds
    time_passed = current - last_check;
    last_check = current;
    allowance += time_passed * (rate / per);

    console.log('Current time: ' + current);
    console.log('Time passed: ' + time_passed);
    console.log('Last check: ' + last_check);
    console.log('Allowance: ' + allowance);

    if (allowance > rate) {
        allowance = rate; // throttle
        console.log('throttle');
    }
    if (allowance < 1.0) {
        console.log('discard message');
        return false;
    } else {
        allowance -= 1.0;
        console.log('forward message');
        return true;
    }
}

http://jsfiddle.net/wxjfcm5d/47/

Upvotes: 2

Views: 1331

Answers (3)

mehmatrix
mehmatrix

Reputation: 2168

You can also use flood-protection library that i've wrote. It uses Token Bucket Algorithm

Usage: 

import FloodProtection from 'flood-protection';

const floodProtection = new FloodProtection({
    rate: 5, 
    // default: 5, unit: messages
    // IMPORTANT: rate must be >= 1 (greater than or equal to 1)

    per: 8, 
    // default: 8, unit: seconds
});

Hope this helps.

Upvotes: 0

Dan D.
Dan D.

Reputation: 74655

In current - last_check, you need the difference between two dates, not the difference between where the second hand was.

Replace new Date().getSeconds() with new Date().getTime()/1000 (or new Date().getTime() but you'd have to replace var per = 8.0 with var per = 8000.0).

This will result in current - last_check always being a positive number of seconds (or milliseconds) rather than negative when the seconds roll over into minutes.

Upvotes: 1

Kassym Dorsel
Kassym Dorsel

Reputation: 4843

I agree with @Evilzebra's comment that the solution may be a little convoluted. Based on your needed behaviour I implemented it this way:

var ii = 0;
var perMils = per * 1000;
function rateLimit() {
    if (ii <= rate) {
        ++ii;
        setTimeout(function() {--ii;}, perMils);
        return true;
    }
    return false;
}

Upvotes: 2

Related Questions