getTokensRemaining() returns unexpected values

Question

getTokensRemaining() returns unexpected values

brenc opened this issue 6 years ago · 3 comments

I've been using this package for years to provide rate limiting for a chat application and it has worked really well for me. I use a limiter for message rate (flood protection) and when the limiter has <= 50% tokens remaining, the server should send a warning message to the user.

Some users have always been able to trigger flood protection w/o getting any warning from the server and I have finally figured out why. Please consider the following code:

const RateLimiter = require('limiter').RateLimiter

const limiter = new RateLimiter(10, 'minute')
const remove = () => {
  let date = new Date()
  let remaining

  if (limiter.tryRemoveTokens(1)) {
    remaining = limiter.getTokensRemaining()
    console.log(`${date} - token removed, remaining: ${remaining}`)
  } else {
    console.log(`${date} - NO tokens remaining`)
  }
}

remove()

setInterval(() => {
  remove()
}, 3500)

Note the interval of 3.5 seconds.

This is the output:

Sat May 04 2019 17:05:03 GMT-0400 (EDT) - token removed, remaining: 9
Sat May 04 2019 17:05:07 GMT-0400 (EDT) - token removed, remaining: 8.584
Sat May 04 2019 17:05:10 GMT-0400 (EDT) - token removed, remaining: 8.168
Sat May 04 2019 17:05:14 GMT-0400 (EDT) - token removed, remaining: 7.751999999999999
Sat May 04 2019 17:05:17 GMT-0400 (EDT) - token removed, remaining: 7.336166666666665
Sat May 04 2019 17:05:21 GMT-0400 (EDT) - token removed, remaining: 6.920166666666665
Sat May 04 2019 17:05:24 GMT-0400 (EDT) - token removed, remaining: 6.504166666666665
Sat May 04 2019 17:05:28 GMT-0400 (EDT) - token removed, remaining: 6.088166666666664
Sat May 04 2019 17:05:31 GMT-0400 (EDT) - token removed, remaining: 5.672166666666664
Sat May 04 2019 17:05:35 GMT-0400 (EDT) - token removed, remaining: 5.255999999999998
Sat May 04 2019 17:05:38 GMT-0400 (EDT) - NO tokens remaining
[SNIP]
Sat May 04 2019 17:06:06 GMT-0400 (EDT) - token removed, remaining: 9

You can see here that getTokensRemaining() never returns a value below 50% of the bucket size at this interval. My expectation is that remaining tokens would decrement 10, 9, 8, 7 etc. so I'm really confused why this is happening. Even though 10 tokens were removed, getTokensRemaining() reported 5.255999999999998 when it should have reported 0 (at least in my mind).

Plus I might be confused as to how this works, but I would expect tokens to be slowly added back to the bucket over time. What appears to be happening here is that about a minute after the first removal, the bucket is filled back up with 10 tokens.

I've been digging through tickets and the code but I can't quite figure out what's happening here and what I can do about it. This seems like it might be a bug so I thought I'd report it.

Answer 1 · 2019-05-04T22:09:49.000Z

Looks like using TokenBucket itself gets the results I expect:

const { TokenBucket } = require('limiter')

const bucket = new TokenBucket(10, 10, 'minute', null)
const remove = () => {
  let date = new Date()
  let remaining

  if (bucket.tryRemoveTokens(1)) {
    remaining = bucket.content
    console.log(`${date} - token removed, remaining: ${remaining}`)
  } else {
    console.log(`${date} - NO tokens remaining`)
  }
}

bucket.content = 10

remove()

setInterval(() => {
  remove()
}, 3500)

Output:

Sat May 04 2019 18:00:35 GMT-0400 (EDT) - token removed, remaining: 9
Sat May 04 2019 18:00:39 GMT-0400 (EDT) - token removed, remaining: 8.5845
Sat May 04 2019 18:00:42 GMT-0400 (EDT) - token removed, remaining: 8.168666666666667
Sat May 04 2019 18:00:46 GMT-0400 (EDT) - token removed, remaining: 7.7524999999999995
Sat May 04 2019 18:00:49 GMT-0400 (EDT) - token removed, remaining: 7.336499999999999
Sat May 04 2019 18:00:53 GMT-0400 (EDT) - token removed, remaining: 6.920499999999999
Sat May 04 2019 18:00:56 GMT-0400 (EDT) - token removed, remaining: 6.504499999999998
Sat May 04 2019 18:01:00 GMT-0400 (EDT) - token removed, remaining: 6.088499999999998
[SNIP]
Sat May 04 2019 18:01:49 GMT-0400 (EDT) - token removed, remaining: 0.26333333333332964
Sat May 04 2019 18:01:52 GMT-0400 (EDT) - NO tokens remaining               
Sat May 04 2019 18:01:56 GMT-0400 (EDT) - token removed, remaining: 0.43133333333332957

Tokens appear to be getting dripped back into the bucket over the course of the interval vs. being dumped into the bucket all at once at the beginning of the next interval (as when using RateLimiter).

Answer 2 · 2021-08-04T16:11:26.000Z

@brenc Were you ever able to resolve this issue? I am having the same issue and finding the package unusable because of it.

Answer 3 · 2021-08-04T23:46:16.000Z

I ended up creating my own TokenBucket class, something like this:

'use strict'

const assert = require('assert').strict
const debug = require('debug')('TokenBucket')

const allowedIntervals = [
  'second',
  'minute',
  'hour',
  'day'
]
const intervalError = `parameter "interval" must be the number of ` +
  `milliseconds or one of the following: ${allowedIntervals.join(', ')}`

class TokenBucket {
  constructor ({
    interval,
    size
  }) {
    assert(['string', 'number'].includes(typeof interval), intervalError)

    if (typeof interval === 'number') {
      assert(interval > 0, 'parameter "interval" must be > 0')
    }

    assert(typeof size === 'number', 'parameter "size" must be a number')

    assert(size > 0, 'parameter "size" must be > 0')

    this._lastDrip = +new Date()
    this._size = size
    // Set the initial number of tokens in the bucket to the size of the
    // bucket.
    this._tokens = size

    if (typeof interval === 'string') {
      switch (interval) {
        case 'second':
          this._interval = 1000
          break
        case 'minute':
          this._interval = 1000 * 60
          break
        case 'hour':
          this._interval = 1000 * 60 * 60
          break
        case 'day':
          this._interval = 1000 * 60 * 60 * 24
          break
        default:
          throw new Error(intervalError)
      }
    } else {
      this._interval = interval
    }

    debug(`size: ${this._size}, tokens: ${this._tokens}, interval: ` +
      `${this._interval}`)
  }

  _drip () {
    const now = +new Date()
    const delta = Math.max(now - this._lastDrip, 0)
    const dripNum = delta * (this._size / this._interval)

    this._lastDrip = now

    debug(`ms since last drip: ${delta}, number of tokens going back into ` +
      `the bucket: ${dripNum}, current number of tokens in the bucket: ` +
      `${this._tokens}`)

    // This prevents the bucket from "overflowing."
    this._tokens = Math.min(this._tokens + dripNum, this._size)

    debug(`number of tokens after the drip: ${this._tokens}`)
  }

  remaining () {
    this._drip()
    return this._tokens
  }

  remove (num) {
    assert(typeof num === 'number', 'parameter "num" must be a number')
    assert(num > 0, 'parameter "num" must be > 0')

    if (num > this._size) {
      debug(`removing ${num} tokens from the bucket`)
      return false
    }

    this._drip()

    // No more tokens left in the bucket.
    if (num > this._tokens) {
      debug(`bucket is empty`)
      return false
    }

    this._tokens -= num

    return true
  }

  size () {
    return this._size
  }
}

module.exports = TokenBucket

Here's how it's used:

// Limit to 60/minute
const bucket = new TokenBucket({
  interval: 'minute',
  size: 60
})

if (bucket.remove(1)) { // returns false if no more tokens left
  doSomethingRateLimited()
} else {
  sendRateLimitedMessage()
}

console.log(`there are ${bucket.remaining()} tokens remaining`)

This has worked well for several years. There are probably better solutions esp. if you need to scale beyond one process.