Higher token removals never fulfill

Hi all.

I had a few problems with the TokenBucket and ended up with a fix in calculating the waiting time. Most annoying was, that the TokenBucket did not let pass calls of different token-size-request.

The problem: if different operations work on the same TokenBucket with different number of tokens used, the operations with the higher number will be re-scheduled infinite.

orig:

function comeBackLater() {
  // How long do we need to wait to make up the difference in tokens?
  var waitInterval = Math.ceil(
    (count - self.content) * (self.interval / self.tokensPerInterval));
  setTimeout(function() { self.removeTokens(count, callback); }, waitInterval);
  return false;
}

What we can see here, is that overlapping intervals are not scheduled one after the other and faster timeouts will always eat the lower tokenBuckets from the internal counter. With full load, the self.removeTokens(count, callback) will never reach the token size required for the higher token-requests.

I added a third result value in the callback function (scheduledTokens) to give the user a feedback about how much tokens are already scheduled so that we can react if the number increases.

I ended up with this calculation:

function comeBackLater() {
      // How long do we need to wait to make up the difference in tokens?
      var waitInterval = Math.ceil(
        (count - self.content) * (self.interval / self.tokensPerInterval));

      var now = Date.now();
        // if there are no scheduledTokens, we reset the timer and put in the minimum waiting time
      if(self.scheduledTokens === 0) {
          self.scheduledTime = now;
      }
      // the waitInterval needs to be added to the already scheduled tokens.
      self.scheduledTime += waitInterval;
      // the realWaitInterval ends at the end of the max scheduledTime
      var realWaitingInterval = self.scheduledTime - now;

      // keep our tokens in mind that are already reserved  - the value is returned to the user
      self.scheduledTokens += count;
      setTimeout(function() {
        self.scheduledTokens -= count; // remove the done tokens from the counter
        self.removeTokens(count, callback);
      }, realWaitingInterval);
      return false;
    }

It may break the timing of tests (on my machine they are passing).

jhurliman / node-rate-limiter

Higher token removals never fulfill #56