令牌桶算法，速率限制javascript

Question

我试图写一个算法，以防止在8秒内发送超过5个消息，我在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

我同意@Evilzebra的评论，这个解决方案可能有点复杂。根据你需要的行为，我这样实现它:

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

Answer 2

在current - last_check中，您需要的是两个日期之间的差异，而不是秒针所在位置的差异。

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

这将导致current - last_check总是正的秒数(或毫秒)，而不是负的，当秒转到分钟。

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