bbeck / token-bucket

Token bucket algorithm for rate-limiting
Apache License 2.0
334 stars 93 forks source link

FixedIntervalRefillStrategy assumes period to be starting at 0. #15

Open PushkarPahare opened 7 years ago

PushkarPahare commented 7 years ago

There is problem with initializing lastRefillTime to negative periodDurationInNanos. Say periodDurationInNanos is 1 (period 1, time unit nanoseconds), in that case it will initialize lastRefillTime to -1.

Now lets look at the period calculation:

public synchronized long refill()
  {
    long now = ticker.read();  // [1]
    ...
    long numPeriods = Math.max(0, (now - lastRefillTime) / periodDurationInNanos); // [2]
    ...

[1] will return a big number (say 1188589593996144), and [2] will simple add 1 to the big number making it 1188589593996145. (See the problem yet). If you divide this by periodDurationInNanos (which was 1 btw). You get huge amount of tokens prebuilt.

Why does not test catch this? MockTicket always starts at 0. But System ticker won't.

mattcarrier commented 7 years ago

I believe this can be fixed by replacing:

this.lastRefillTime = -periodDurationInNanos;
this.nextRefillTime = -periodDurationInNanos;

with:

this.lastRefillTime = ticker.read();
this.nextRefillTime = lastRefillTime + periodDurationInNanos;