Rate Limit is violated in a sense if I remove 1 token every second when I define bucket interval as 1 minute

[amlandas]

I implement a queue to hold requests until the condition t remove a token holds true, and if it does I remove a token and proceed with my task. I define my bucket size to be 3, and the rate limit interval as 1 minute. Given below is the code I used initially to implement rate limiter.

Throttler.prototype.checkAndExecute = function ()
  if (this.queue.length > 0) 
    if (this.limiter.getTokensRemaining() > 0)
      if (this.limiter.tryRemoveTokens(1)) {
        var job = that.queue.shift();
        if (job) {
          // do my job....
        }
      }
    }
  }
};

I wrap the above function inside an interval to check the queue contents and trigger the job if a token is available. Code given below -

this.peekInterval = setInterval( function() {
    that.checkAndExecute();
  }, 1000 );

The issue is that when I send 10 jobs to the queue, the first 3 are picked immediately by removing tokens from the bucket and executed. So, ideally, my request to remove 1 more token should not be allowed until at least 60 seconds have passed since I removed the first token. But, the bcuket gets filled up with another token in 20 seconds (60 seconds / 3), and the 4th job gets to execute in the 21st second. Thus, in the 1 minute interval since the first token was removed, more than 3 jobs got executed (in fact 5 jobs execute in the first minute itself), which violates the rate limit I set - 3 jobs per minute.

I am able to work around with this by modifying the checkAndExecute function in the way below -

Throttler.prototype.checkAndExecute = function () {
  if (that.queue.length > 0) {
    if (this.limiter.getTokensRemaining() >= this.bucketSize) {
      if (this.limiter.tryRemoveTokens(1)) {
        var job = that.queue.shift();
        if (job) {
          // do my job....
        }
      }
    }
  }
};

I'm not sure if anyone else has faced this scenario like I did, but just wanted to flag this out.

I understand that how the node rate-limiter and token-bucket functions holds good when a user wants to implement the token bucket algorithm, but in true definition of a rate limiter, the bucket should not be filled with additional tokens until the time interval since the removal of the 1st token has expired.

[jhurliman]

Thanks for flagging this up. I think an ideal fix would be highlighting this default behavior in the README, and adding a constructor option for RateLimiter that would change it's behavior to be more like a true "N tokens per T time units".

[amlandas]

Agree that'll help a lot.
One of the approach to include this solution may be-
Instead of dripping the delta of the tokens due in the function drip(), when the rateLimiter.getRemainingTokens() is called, the count control can be handled inside the RateLimiter itself.
There can be a bucket(array) of size defined by the bucketSize by API user, and every call to removeToken will push the current date and time into the array. Any fresh call to the rate limiter getRemainingTokens function will get the contents of the array, and compare each date-time of the array against the (current date-time - interval) defined by user. All cases in the array that fall in the condition are actually tokens in use, and the value of (bucketSize - tokens in use) will give the remaining tokens.
The call to removeToken can internally call getRemainingTokens and assign tokens only if sufficient ones are available. That way it can remain fail safe given any moment in time.

It's just my take on the solution and also that it'll have a running time of the order of O(n), i.e. (bucketSize), there may be better/faster ways of doing it without invoking too many changes into the existing code.

[nss213]

Was this issue intended to be closed? It seems to me the problem is still reproducible:

import {RateLimiter} from 'limiter';

async function removeTokensAsync(limiter, count) {
	return new Promise((resolve, reject) => {
		limiter.removeTokens(count, (err, remaining) => {
			if (err) reject(err);
			else resolve(remaining);
		});
	});
}

describe('rateLimiter', () => {
	it('tries to break the limit', async () => {
		const limiter = new RateLimiter(20, 'second');

		await removeTokensAsync(limiter, 1);
		// wait 700ms
		await(new Promise((resolve) => {
			setTimeout(resolve, 700);
		}));
		const startTime = Date.now();
		await removeTokensAsync(limiter, 19);
		await removeTokensAsync(limiter, 10);
		const endTime = Date.now();

		expect(startTime-endTime).toBeGreaterThan(1000);
		console.log(endTime - startTime);

	});
})

I totally understand that you may prefer not to change the existing behavior, I just wanted to make sure I was not missing something.

[jhurliman]

Reopened as this still should either be documented as a limitation and/or make improvements to RateLimiter to match the expected behavior. I would be worried about the suggestion of using an unbounded array of timestamps, but I don't have an alternative proposal off hand so I'll leave this ticket open for discussion.

[blair]

Two ways of fixing this I see.

Having a heap where you put a timestamp and count of each successful request. When you do a new one, get the minimum values off the heap as long as the timestamp is older than the rate interval. Then you count the number of items remaining in the heap. Doing this is log(n).

The other is doing a calculation to internally calculate a known rate that takes into account the behavior. So with an input of 3 over one minute, you would see that you would get 5. So maybe you give internally use a rate of 3/(3/5) == 1.799 and then over time you would not go over 3/min. Of course, you give up the ability to do three requests immediately.

The advantage of the current method is that it does allow for some burstiness. If the requests support N requests per sec and burst up to M, then maybe the current code will work, assuming you can pick the parameters appropriately.