Implementing token bucket algorithm

March 17, 2024

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)

>Solution :

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)