令牌桶算法，速率限制javascript？

Question

我试图编写一个算法来防止超过5条消息在8秒内被发送，我在python中找到了令牌桶算法的公式，所以我尝试用javascript实现它，但我遗漏了一件事。

last_check变量对我来说不清楚。如果我马上跟踪60秒，问题是当它在59秒后返回时，数学就被抛掉了。

第一次迭代

如果last_check = new Date().getSeconds()，假设是它跟踪的那一分钟中的33秒，那么我们现在比较的是33秒。

当rateLimit()函数执行时，它得到调用它的current时间，例如消息，current new Date().getSeconds()是40秒，例如.last_check后7秒

所以time_passed现在是7秒，last_checked变成40。

津贴结果

allowance是7 * (5.0/8.0) = 4.375。

问题所在

如果last_checked停留在40秒和22秒直到一个新消息，那么下面的第二个迭代的公式就变成了。

二次迭代

current变成2 (40+22) new Date().getSeconds()循环回到2.time_passed现在是(2-40) = -38秒，last_checked现在是2。

津贴结果

allowance是-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/

Answer 1

在current - last_check中，您需要两个日期之间的差异，而不是二手日期之间的差异。

将new Date().getSeconds()替换为new Date().getTime()/1000 (或new Date().getTime()，但您必须用var per = 8000.0替换var per = 8.0 )。

这将导致current - last_check始终是秒的正数(或毫秒)，而不是当秒滚动到分钟时为负数。

Answer 2

我同意@Evilzebra的评论，即解决方案可能有点复杂。根据您需要的行为，我以如下方式实现了它：

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

Answer 3

您还可以使用我编写的防洪库。它使用令牌桶算法

使用：

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

希望这能有所帮助。