JavaScript Token Bucket Algorithm

Token Bucket is a rate-limiting algorithm in which there is a bucket that gets refilled at a particular rate with tokens. To perform an action, one or more tokens can be taken out or redeemed from this bucket. When there are no more tokens left, the action cannot be performed until the bucket is refilled and further tokens are available. We call it burst when tokens are redeemed at a greater pace than the rate-limit till the bucket is emptied. The algorithm, its sample run, and possible uses are shared below:

The Algorithm

class TokenBucket {
  constructor(bucketSize = 5, refillInterval = 1000) {
    this.tokens = bucketSize;

    setInterval(() => {
      if (this.tokens < bucketSize) {
        this.tokens++;
      }
    }, refillInterval);
  }

  redeem() {
    if (this.tokens) {
      this.tokens--;
      return true;
    }
    return false;
  }
};

refillInterval is the refill rate, which expects milliseconds. Default is 1000 (1 sec).
Inside the constructor we setInterval for every refillInterval, and increment tokens if less than bucketSize.
redeem() returns true or false depending on tokens availability in the bucket.

Sample Run

Let’s initialize TokenBucket with bucket size 3 and default 1 second refill interval. Then redeem() 10 of them immediately in a for loop. Afterwards, redeem one at every 0.9 seconds.

const bucket = new TokenBucket(3);

for (let i = 0; i < 10; i++) {
  console.log(bucket.redeem());
}

setInterval(() => {
  console.log(bucket.redeem());
}, 900);

The result would look like:

1. true
2. true
3. true
4. false
5. false
6. false
7. false
8. false
9. false
10. false
11. false
12. true
13. true
14. true
15. true
16. true
17. true
18. true
19. true
20. true
21. false
22. true
23. true
24. true
25. true
26. true
27. true
28. true
29. true
30. true
31. false
32. true
33. true

Here, first three trues comprise a burst, because the bucket was exhausted at a higher rate than refill rate. After that, the redeem() returned false till the bucket got refilled. The rest of the redeems have an occasional false because our sample run rate of consumption is just 100 milliseconds quicker than the refill rate of 1000 milliseconds.

Possible Uses

Rate limit a Node/Express API with middleware.
Add rate limiting on frontend applications for all or certain API calls, to mirror the backend rate-limiting in place. This should save load on backend which would have to deny the request with status 429 anyway. (The client rate-limiting is not guaranteed and can easily be bypassed. It only works for honest users surpassing their API consumption limits unintentionally.)
To not show the same error message to the user if recurred rapidly.
In game implementations, this algorithm can be used in health replenish or similar features.

javascript algorithms

JavaScript Token Bucket Algorithm

And its Possible Uses

The Algorithm

Sample Run

Possible Uses

See also