Question 360808 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – Implementing token bucket algorithm

I’m currently working on implementing a token bucket algorithm in JavaScript to monitor the number of requests per second. The objective is to allow requests to proceed if there are sufficient tokens available in the bucket, otherwise, the system should enforce rate limiting.
However, upon testing my code, I observed that it consistently outputs ‘false’. Should I incorporate the use of setInterval to ensure its proper functionality?

 class TokenBucket {
        constructor(maxBucketSize, numberOfRequests, windowSizeForRateLimitInMilliseconds) {
            this.maxBucketSize = maxBucketSize;
            this.numberOfRequests = numberOfRequests;
            this.windowSizeForRateLimitInMilliseconds = windowSizeForRateLimitInMilliseconds;
            this.refill();
        }
    
        tryConsume() {
            this.refill();
            if (this.numberOfTokenAvailable > 0) {
                this.numberOfTokenAvailable--;
                return true;
            }
            return false;
        }
    
        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);
        }
    }
    
    // Example usage:
    const tokenBucket = new TokenBucket(10, 5, 10000); // Max bucket size: 10, 5 requests per 10 seconds
    console.log(tokenBucket.tryConsume()); // Outputs: true (tokens available)
    console.log(tokenBucket.tryConsume()); // Outputs: true (tokens available)
    console.log(tokenBucket.tryConsume()); // Outputs: true (tokens available)
    console.log(tokenBucket.tryConsume()); // Outputs: true (tokens available)
    console.log(tokenBucket.tryConsume()); // Outputs: true (tokens available)
    console.log(tokenBucket.tryConsume()); // Outputs: false (no tokens available)
Tags:

2

Answers


  1. 0

    The issue with your code lies in the refill() method. It doesn’t correctly refill the token bucket based on the time elapsed since the last 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);
}

    The refill() method checks if the current time is past the next refill time.
    If it’s time to refill, it updates the lastRefillTime, calculates the next refill time, and refills the bucket by adding numberOfRequests tokens.

    Corrected Implementation:

    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);
    }
}
    Login or Signup to reply.
  2. 0

    You forgot to init

    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.log(tokenBucket.tryConsume()); // Outputs: true (tokens available)
    console.log(tokenBucket.tryConsume()); // Outputs: true (tokens available)
    console.log(tokenBucket.tryConsume()); // Outputs: true (tokens available)
    console.log(tokenBucket.tryConsume()); // Outputs: true (tokens available)
    console.log(tokenBucket.tryConsume()); // Outputs: true (tokens available)
    console.log(tokenBucket.tryConsume()); // Outputs: false (no tokens available)
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search