Реализация алгоритма ведра токенов

Проблема с вашим кодом заключается в методе refill(). Он неправильно пополняет корзину токенов в зависимости от времени, прошедшего с момента последнего пополнения.

refill() {
    if (Date.now() < this.nextRefillTime) {
        return;
    }
    this.lastRefillTime = Date.now();
    this.nextRefillTime = this.lastRefillTime + this.windowSizeForRateLimitInMilliseconds;
    this.numberOfTokenAvailable = Math.min(this.maxBucketSize, this.numberOfTokenAvailable + this.numberOfRequests);
}

Метод refill() проверяет, прошло ли текущее время после следующего времени пополнения. Если пришло время пополнения, он обновляет значение LastRefillTime, вычисляет время следующего пополнения и заполняет корзину, добавляя токены NumberOfRequests.

Исправленная реализация:

refill() {
    const currentTime = Date.now();
    const timeElapsed = currentTime - this.lastRefillTime;
    const tokensToAdd = Math.floor(timeElapsed / this.windowSizeForRateLimitInMilliseconds) * this.numberOfRequests;
    
    if (tokensToAdd > 0) {
        this.lastRefillTime = currentTime;
        this.numberOfTokenAvailable = Math.min(this.maxBucketSize, this.numberOfTokenAvailable + tokensToAdd);
    }
}

Вы забыли инициализировать

this.nextRefillTime = -Infinity;
this.numberOfTokenAvailable = 0;

 class TokenBucket {
        constructor(maxBucketSize, numberOfRequests, windowSizeForRateLimitInMilliseconds) {
            this.maxBucketSize = maxBucketSize;
            this.numberOfRequests = numberOfRequests;
            this.windowSizeForRateLimitInMilliseconds = windowSizeForRateLimitInMilliseconds;
            this.nextRefillTime = -Infinity;
            this.numberOfTokenAvailable = 0;
            this.refill();
        }
    
        tryConsume() {
            this.refill();
            if (this.numberOfTokenAvailable > 0) {
                this.numberOfTokenAvailable--;
                return true;
            }
            return false;
        }
    
        refill() {
            if (Date.now() < this.nextRefillTime) {
                return;
            }
            debugger;
            this.lastRefillTime = Date.now();
            this.nextRefillTime = this.lastRefillTime + this.windowSizeForRateLimitInMilliseconds;
            this.numberOfTokenAvailable = Math.min(this.maxBucketSize, this.numberOfTokenAvailable + this.numberOfRequests);
        }
    }
    
    // Example usage:
    const tokenBucket = new TokenBucket(10, 5, 10000); // Max bucket size: 10, 5 requests per 10 seconds
    console.info(tokenBucket.tryConsume()); // Outputs: true (tokens available)
    console.info(tokenBucket.tryConsume()); // Outputs: true (tokens available)
    console.info(tokenBucket.tryConsume()); // Outputs: true (tokens available)
    console.info(tokenBucket.tryConsume()); // Outputs: true (tokens available)
    console.info(tokenBucket.tryConsume()); // Outputs: true (tokens available)
    console.info(tokenBucket.tryConsume()); // Outputs: false (no tokens available)

Token Bucket — отличный алгоритм ограничения скорости, но он не работает так, как вы пытаетесь его написать. О ведре токенов можно думать так:

• Каждый разрешенный запрос извлекает токен из корзины. Если запрос поступает при отсутствии токенов, запрос отклоняется.

• Токены добавляются в корзину по одному с постоянной скоростью, пока количество токенов в корзине меньше максимального предела.

Ограничение скорости и ограничение пакета являются параметрами алгоритма.

Этот алгоритм имеет массу преимуществ. Он близко соответствует возможностям защищаемых систем, что делает его очень полезным. Он также не имеет какого-либо странного поведения, связанного с произвольно выбранными «временными окнами», как это делают более наивные алгоритмы ограничения скорости.

Это также очень легко реализовать. Если вы все сделаете правильно, для этого потребуется только одно слово состояния, которое вы можете обновлять атомарно, и вам нужно обновлять это состояние только тогда, когда вы разрешаете запрос — никаких событий таймера не требуется.

Однако способ реализации корзины токенов отличается от того, как вы об этом думаете...

В любой момент времени в ведре находится некоторое количество токенов. Если оставить его в покое, ведро будет заполняться до тех пор, пока не достигнет предела всплеска. Назовем время, когда он достигнет этого предела, временем заполнения.

Представьте, что вместо отслеживания текущего количества токенов в корзине мы просто отслеживаем соответствующее время заполнения. Это позволяет нам в любой момент в будущем определить, сколько токенов находится в ведре:

• Если current_time > fill_time, то tokens = burst_limit. Легкий.
• Если current_time < fill_time, то tokens = burst_limit - rate_limit * (fill_time-current_time). Также легко. Если это меньше 1, то вам следует отклонить запрос.

Самое замечательное в использовании времени заполнения заключается в том, что оно меняется только тогда, когда вы разрешаете запрос. Вот почему вам не нужны какие-либо события таймера или что-то в этом роде. Это проведет вас на пути к хорошей реализации корзины токенов. Но есть еще несколько оптимизаций, которые мне хотелось бы сделать.

1. Пусть t1_time = fill_time - (burst_limit-1) / rate_limit. Это было время в прошлом, когда ведро с одним жетоном заполнялось до текущей емкости. Мне нравится отслеживать это, а не время заполнения, потому что вы можете напрямую сравнить его с текущим временем и разрешить запрос, когда t1_time <= current_time.

2. Вместо того, чтобы вести учет времени в секундах или миллисекундах, ведите учет времени в токенах. Это token_time = clock_time * rate_limit. Это изменение означает, что отслеживаемое вами состояние (t1_time) всегда может быть целым числом, что решает множество сложных проблем, связанных с округлением и т. д.

При всем при этом реализация корзины токенов, как и было обещано, очень проста:

class TokenBucket {

    constructor(ratePerSecond, burstLimit) {
        // Factor that converts time in milliseconds to time in tokens
        // This isn't necessarily an integer
        this.tokensPerMilli = ratePerSecond*1000;
        // The difference, in token time, between the one-token-in-bucket time
        // and now, if we just took a token from a *full* bucket
        this.fullBucketLag = burstLimit-2;
        // Now, in tokens instead of milliseconds
        const tokenNow = Date.now() * this.tokensPerMilli;
        // Initialize the one-token-in-bucket time so that the bucket is
        // initially full.  In another language, you could use an integer
        // data type for this.
        this.t1Time = tokenNow-burstLimit;
    }

    tryConsume() {
        // Now, in tokens instead of milliseconds
        const tokenNow = Date.now() * this.tokensPerMilli;
        if (tokenNow < this.t1Time) {
            // denied
            return false;
        } else {
            // allowed
            this.t1Time = Math.max(this.t1Time + 1, tokenNow - this.fullBucketLag);
            return true;
        }
    }
}